1 /*******************************************************************************
2 * Copyright (c) 2011, 2013 Ericsson
4 * All rights reserved. This program and the accompanying materials are
5 * made available under the terms of the Eclipse Public License v1.0 which
6 * accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * Francois Chouinard - Initial API and implementation
11 * Bernd Hufmann - Implementation of new interfaces/listeners and support for
12 * time stamp in any order
13 * Francois Chouinard - Moved from LTTng to TMF
14 * Francois Chouinard - Added support for empty initial buckets
15 * Patrick Tasse - Support selection range
16 *******************************************************************************/
18 package org
.eclipse
.linuxtools
.tmf
.ui
.views
.histogram
;
20 import java
.util
.Arrays
;
22 import org
.eclipse
.core
.runtime
.ListenerList
;
25 * Histogram-independent data model.
27 * It has the following characteristics:
29 * <li>The <i>basetime</i> is the timestamp of the first event
30 * <li>There is a fixed number (<i>n</i>) of buckets of uniform duration
32 * <li>The <i>timespan</i> of the model is thus: <i>n</i> * <i>d</i> time units
33 * <li>Bucket <i>i</i> holds the number of events that occurred in time range:
34 * [<i>basetime</i> + <i>i</i> * <i>d</i>, <i>basetime</i> + (<i>i</i> + 1) *
37 * Initially, the bucket durations is set to 1ns. As the events are read, they
38 * are tallied (using <i>countEvent()</i>) in the appropriate bucket (relative
39 * to the <i>basetime</i>).
41 * Eventually, an event will have a timestamp that exceeds the <i>timespan</i>
42 * high end (determined by <i>n</i>, the number of buckets, and <i>d</i>, the
43 * bucket duration). At this point, the histogram needs to be compacted. This is
44 * done by simply merging adjacent buckets by pair, in effect doubling the
45 * <i>timespan</i> (<i>timespan'</i> = <i>n</i> * <i>d'</i>, where <i>d'</i> =
46 * 2<i>d</i>). This compaction happens as needed as the trace is read.
48 * The model allows for timestamps in not increasing order. The timestamps can
49 * be fed to the model in any order. If an event has a timestamp less than the
50 * <i>basetime</i>, the buckets will be moved to the right to account for the
51 * new smaller timestamp. The new <i>basetime</i> is a multiple of the bucket
52 * duration smaller then the previous <i>basetime</i>. Note that the <i>basetime</i>
53 * might not be anymore a timestamp of an event. If necessary, the buckets will
54 * be compacted before moving to the right. This might be necessary to not
55 * loose any event counts at the end of the buckets array.
57 * The mapping from the model to the UI is performed by the <i>scaleTo()</i>
58 * method. By keeping the number of buckets <i>n</i> relatively large with
59 * respect to to the number of pixels in the actual histogram, we should achieve
60 * a nice result when visualizing the histogram.
64 * @author Francois Chouinard
66 public class HistogramDataModel
implements IHistogramDataModel
{
68 // ------------------------------------------------------------------------
70 // ------------------------------------------------------------------------
73 * The default number of buckets
75 public static final int DEFAULT_NUMBER_OF_BUCKETS
= 16 * 1000;
78 * Number of events after which listeners will be notified.
80 public static final int REFRESH_FREQUENCY
= DEFAULT_NUMBER_OF_BUCKETS
;
82 // ------------------------------------------------------------------------
84 // ------------------------------------------------------------------------
87 private final int fNbBuckets
;
88 private final long[] fBuckets
;
89 private long fBucketDuration
;
90 private long fNbEvents
;
91 private int fLastBucket
;
94 private long fFirstBucketTime
; // could be negative when analyzing events with descending order!!!
95 private long fFirstEventTime
;
96 private long fLastEventTime
;
97 private long fSelectionBegin
;
98 private long fSelectionEnd
;
99 private long fTimeLimit
;
101 // Private listener lists
102 private final ListenerList fModelListeners
;
104 // ------------------------------------------------------------------------
106 // ------------------------------------------------------------------------
109 * Default constructor with default number of buckets.
111 public HistogramDataModel() {
112 this(0, DEFAULT_NUMBER_OF_BUCKETS
);
116 * Default constructor with default number of buckets.
117 * @param startTime The histogram start time
120 public HistogramDataModel(long startTime
) {
121 this(startTime
, DEFAULT_NUMBER_OF_BUCKETS
);
125 * Constructor with non-default number of buckets.
126 * @param nbBuckets A number of buckets.
128 public HistogramDataModel(int nbBuckets
) {
133 * Constructor with non-default number of buckets.
134 * @param startTime the histogram start time
135 * @param nbBuckets A number of buckets.
138 public HistogramDataModel(long startTime
, int nbBuckets
) {
139 fFirstBucketTime
= fFirstEventTime
= fLastEventTime
= startTime
;
140 fNbBuckets
= nbBuckets
;
141 fBuckets
= new long[nbBuckets
];
142 fModelListeners
= new ListenerList();
148 * @param other A model to copy.
150 public HistogramDataModel(HistogramDataModel other
) {
151 fNbBuckets
= other
.fNbBuckets
;
152 fBuckets
= Arrays
.copyOf(other
.fBuckets
, fNbBuckets
);
153 fBucketDuration
= Math
.max(other
.fBucketDuration
, 1);
154 fNbEvents
= other
.fNbEvents
;
155 fLastBucket
= other
.fLastBucket
;
156 fFirstBucketTime
= other
.fFirstBucketTime
;
157 fFirstEventTime
= other
.fFirstEventTime
;
158 fLastEventTime
= other
.fLastEventTime
;
159 fSelectionBegin
= other
.fSelectionBegin
;
160 fSelectionEnd
= other
.fSelectionEnd
;
161 fTimeLimit
= other
.fTimeLimit
;
162 fModelListeners
= new ListenerList();
163 Object
[] listeners
= other
.fModelListeners
.getListeners();
164 for (Object listener
: listeners
) {
165 fModelListeners
.add(listener
);
169 // ------------------------------------------------------------------------
171 // ------------------------------------------------------------------------
174 * Returns the number of events in the data model.
175 * @return number of events.
177 public long getNbEvents() {
182 * Returns the number of buckets in the model.
183 * @return number of buckets.
185 public int getNbBuckets() {
190 * Returns the current bucket duration.
191 * @return bucket duration
193 public long getBucketDuration() {
194 return fBucketDuration
;
198 * Returns the time value of the first bucket in the model.
199 * @return time of first bucket.
201 public long getFirstBucketTime() {
202 return fFirstBucketTime
;
206 * Returns the time of the first event in the model.
207 * @return time of first event.
209 public long getStartTime() {
210 return fFirstEventTime
;
214 * Sets the model start time
215 * @param startTime the histogram range start time
216 * @param endTime the histogram range end time
219 public void setTimeRange(long startTime
, long endTime
) {
220 fFirstBucketTime
= fFirstEventTime
= fLastEventTime
= startTime
;
223 while (endTime
>= fTimeLimit
) {
229 * Returns the time of the last event in the model.
230 * @return the time of last event.
232 public long getEndTime() {
233 return fLastEventTime
;
237 * Returns the time of the current event in the model.
238 * @return the time of the current event.
239 * @deprecated As of 2.1, use {@link #getSelectionBegin()} and {@link #getSelectionEnd()}
242 public long getCurrentEventTime() {
243 return fSelectionBegin
;
247 * Returns the begin time of the current selection in the model.
248 * @return the begin time of the current selection.
251 public long getSelectionBegin() {
252 return fSelectionBegin
;
256 * Returns the end time of the current selection in the model.
257 * @return the end time of the current selection.
260 public long getSelectionEnd() {
261 return fSelectionEnd
;
265 * Returns the time limit with is: start time + nbBuckets * bucketDuration
266 * @return the time limit.
268 public long getTimeLimit() {
272 // ------------------------------------------------------------------------
274 // ------------------------------------------------------------------------
277 * Add a listener to the model to be informed about model changes.
278 * @param listener A listener to add.
280 public void addHistogramListener(IHistogramModelListener listener
) {
281 fModelListeners
.add(listener
);
285 * Remove a given model listener.
286 * @param listener A listener to remove.
288 public void removeHistogramListener(IHistogramModelListener listener
) {
289 fModelListeners
.remove(listener
);
292 // Notify listeners (always)
293 private void fireModelUpdateNotification() {
294 fireModelUpdateNotification(0);
297 // Notify listener on boundary
298 private void fireModelUpdateNotification(long count
) {
299 if ((count
% REFRESH_FREQUENCY
) == 0) {
300 Object
[] listeners
= fModelListeners
.getListeners();
301 for (Object listener2
: listeners
) {
302 IHistogramModelListener listener
= (IHistogramModelListener
) listener2
;
303 listener
.modelUpdated();
308 // ------------------------------------------------------------------------
310 // ------------------------------------------------------------------------
313 public void complete() {
314 fireModelUpdateNotification();
318 * Clear the histogram model.
319 * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
322 public void clear() {
323 Arrays
.fill(fBuckets
, 0);
325 fFirstBucketTime
= 0;
332 fireModelUpdateNotification();
336 * Sets the current event time (no notification of listeners)
338 * @param timestamp A time stamp to set.
339 * @deprecated As of 2.1, use {@link #setSelection(long, long)}
342 public void setCurrentEvent(long timestamp
) {
343 fSelectionBegin
= timestamp
;
344 fSelectionEnd
= timestamp
;
348 * Sets the current event time with notification of listeners
350 * @param timestamp A time stamp to set.
351 * @deprecated As of 2.1, use {@link #setSelectionNotifyListeners(long, long)}
354 public void setCurrentEventNotifyListeners(long timestamp
) {
355 fSelectionBegin
= timestamp
;
356 fSelectionEnd
= timestamp
;
357 fireModelUpdateNotification();
361 * Sets the current selection time range (no notification of listeners)
363 * @param beginTime The selection begin time.
364 * @param endTime The selection end time.
367 public void setSelection(long beginTime
, long endTime
) {
368 fSelectionBegin
= beginTime
;
369 fSelectionEnd
= endTime
;
373 * Sets the current selection time range with notification of listeners
375 * @param beginTime The selection begin time.
376 * @param endTime The selection end time.
379 public void setSelectionNotifyListeners(long beginTime
, long endTime
) {
380 fSelectionBegin
= beginTime
;
381 fSelectionEnd
= endTime
;
382 fireModelUpdateNotification();
386 * Add event to the correct bucket, compacting the if needed.
388 * @param eventCount The current event Count (for notification purposes)
389 * @param timestamp The timestamp of the event to count
393 public void countEvent(long eventCount
, long timestamp
) {
400 // Set the start/end time if not already done
401 if ((fFirstBucketTime
== 0) && (fLastBucket
== 0) && (fBuckets
[0] == 0) && (timestamp
> 0)) {
402 fFirstBucketTime
= timestamp
;
403 fFirstEventTime
= timestamp
;
407 if (timestamp
< fFirstEventTime
) {
408 fFirstEventTime
= timestamp
;
411 if (fLastEventTime
< timestamp
) {
412 fLastEventTime
= timestamp
;
415 if (timestamp
>= fFirstBucketTime
) {
418 while (timestamp
>= fTimeLimit
) {
424 // get offset for adjustment
425 int offset
= getOffset(timestamp
);
428 while((fLastBucket
+ offset
) >= fNbBuckets
) {
430 offset
= getOffset(timestamp
);
435 fLastBucket
= fLastBucket
+ offset
;
437 fFirstBucketTime
= fFirstBucketTime
- (offset
*fBucketDuration
);
441 // Increment the right bucket
442 int index
= (int) ((timestamp
- fFirstBucketTime
) / fBucketDuration
);
445 if (fLastBucket
< index
) {
449 fireModelUpdateNotification(eventCount
);
453 * Scale the model data to the width, height and bar width requested.
455 * @param width A width of the histogram canvas
456 * @param height A height of the histogram canvas
457 * @param barWidth A width (in pixel) of a histogram bar
458 * @return the result array of size [width] and where the highest value doesn't exceed [height]
460 * @see org.eclipse.linuxtools.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int, int, int)
463 public HistogramScaledData
scaleTo(int width
, int height
, int barWidth
) {
465 if ((width
<= 0) || (height
<= 0) || (barWidth
<= 0))
467 throw new AssertionError("Invalid histogram dimensions (" + width
+ "x" + height
+ ", barWidth=" + barWidth
+ ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
470 // The result structure
471 HistogramScaledData result
= new HistogramScaledData(width
, height
, barWidth
);
473 // Scale horizontally
474 result
.fMaxValue
= 0;
476 int nbBars
= width
/ barWidth
;
477 int bucketsPerBar
= (fLastBucket
/ nbBars
) + 1;
478 result
.fBucketDuration
= Math
.max(bucketsPerBar
* fBucketDuration
,1);
479 for (int i
= 0; i
< nbBars
; i
++) {
481 for (int j
= i
* bucketsPerBar
; j
< ((i
+ 1) * bucketsPerBar
); j
++) {
482 if (fNbBuckets
<= j
) {
485 count
+= fBuckets
[j
];
487 result
.fData
[i
] = count
;
488 result
.fLastBucket
= i
;
489 if (result
.fMaxValue
< count
) {
490 result
.fMaxValue
= count
;
495 if (result
.fMaxValue
> 0) {
496 result
.fScalingFactor
= (double) height
/ result
.fMaxValue
;
499 fBucketDuration
= Math
.max(fBucketDuration
, 1);
500 // Set selection begin and end index in the scaled histogram
501 if (fSelectionBegin
< fFirstBucketTime
) {
502 result
.fSelectionBeginBucket
= -1;
503 } else if (fSelectionBegin
> fLastEventTime
) {
504 result
.fSelectionBeginBucket
= fLastBucket
;
506 result
.fSelectionBeginBucket
= (int) ((fSelectionBegin
- fFirstBucketTime
) / fBucketDuration
) / bucketsPerBar
;
508 if (fSelectionEnd
< fFirstBucketTime
) {
509 result
.fSelectionEndBucket
= -1;
510 } else if (fSelectionEnd
> fLastEventTime
) {
511 result
.fSelectionEndBucket
= fLastBucket
;
513 result
.fSelectionEndBucket
= (int) ((fSelectionEnd
- fFirstBucketTime
) / fBucketDuration
) / bucketsPerBar
;
516 result
.fFirstBucketTime
= fFirstBucketTime
;
517 result
.fFirstEventTime
= fFirstEventTime
;
521 // ------------------------------------------------------------------------
523 // ------------------------------------------------------------------------
525 private void updateEndTime() {
526 fTimeLimit
= fFirstBucketTime
+ (fNbBuckets
* fBucketDuration
);
529 private void mergeBuckets() {
530 for (int i
= 0; i
< (fNbBuckets
/ 2); i
++) {
531 fBuckets
[i
] = fBuckets
[2 * i
] + fBuckets
[(2 * i
) + 1];
533 Arrays
.fill(fBuckets
, fNbBuckets
/ 2, fNbBuckets
, 0);
534 fBucketDuration
*= 2;
536 fLastBucket
= (fNbBuckets
/ 2) - 1;
539 private void moveBuckets(int offset
) {
540 for(int i
= fNbBuckets
- 1; i
>= offset
; i
--) {
541 fBuckets
[i
] = fBuckets
[i
-offset
];
544 for (int i
= 0; i
< offset
; i
++) {
549 private int getOffset(long timestamp
) {
550 int offset
= (int) ((fFirstBucketTime
- timestamp
) / fBucketDuration
);
551 if (((fFirstBucketTime
- timestamp
) % fBucketDuration
) != 0) {