1 /*******************************************************************************
2 * Copyright (c) 2011, 2012 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 *******************************************************************************/
17 package org
.eclipse
.linuxtools
.tmf
.ui
.views
.histogram
;
19 import java
.util
.Arrays
;
21 import org
.eclipse
.core
.runtime
.ListenerList
;
24 * Histogram-independent data model.
26 * It has the following characteristics:
28 * <li>The <i>basetime</i> is the timestamp of the first event
29 * <li>There is a fixed number (<i>n</i>) of buckets of uniform duration
31 * <li>The <i>timespan</i> of the model is thus: <i>n</i> * <i>d</i> time units
32 * <li>Bucket <i>i</i> holds the number of events that occurred in time range:
33 * [<i>basetime</i> + <i>i</i> * <i>d</i>, <i>basetime</i> + (<i>i</i> + 1) *
36 * Initially, the bucket durations is set to 1ns. As the events are read, they
37 * are tallied (using <i>countEvent()</i>) in the appropriate bucket (relative
38 * to the <i>basetime</i>).
40 * Eventually, an event will have a timestamp that exceeds the <i>timespan</i>
41 * high end (determined by <i>n</i>, the number of buckets, and <i>d</i>, the
42 * bucket duration). At this point, the histogram needs to be compacted. This is
43 * done by simply merging adjacent buckets by pair, in effect doubling the
44 * <i>timespan</i> (<i>timespan'</i> = <i>n</i> * <i>d'</i>, where <i>d'</i> =
45 * 2<i>d</i>). This compaction happens as needed as the trace is read.
47 * The model allows for timestamps in not increasing order. The timestamps can
48 * be fed to the model in any order. If an event has a timestamp less than the
49 * <i>basetime</i>, the buckets will be moved to the right to account for the
50 * new smaller timestamp. The new <i>basetime</i> is a multiple of the bucket
51 * duration smaller then the previous <i>basetime</i>. Note that the <i>basetime</i>
52 * might not be anymore a timestamp of an event. If necessary, the buckets will
53 * be compacted before moving to the right. This might be necessary to not
54 * loose any event counts at the end of the buckets array.
56 * The mapping from the model to the UI is performed by the <i>scaleTo()</i>
57 * method. By keeping the number of buckets <i>n</i> relatively large with
58 * respect to to the number of pixels in the actual histogram, we should achieve
59 * a nice result when visualizing the histogram.
63 * @author Francois Chouinard
65 public class HistogramDataModel
implements IHistogramDataModel
{
67 // ------------------------------------------------------------------------
69 // ------------------------------------------------------------------------
72 * The default number of buckets
74 public static final int DEFAULT_NUMBER_OF_BUCKETS
= 16 * 1000;
77 * Number of events after which listeners will be notified.
79 public static final int REFRESH_FREQUENCY
= DEFAULT_NUMBER_OF_BUCKETS
;
81 // ------------------------------------------------------------------------
83 // ------------------------------------------------------------------------
86 private final int fNbBuckets
;
87 private final long[] fBuckets
;
88 private long fBucketDuration
;
89 private long fNbEvents
;
90 private int fLastBucket
;
93 private long fFirstBucketTime
; // could be negative when analyzing events with descending order!!!
94 private long fFirstEventTime
;
95 private long fLastEventTime
;
96 private long fCurrentEventTime
;
97 private long fTimeLimit
;
99 // Private listener lists
100 private final ListenerList fModelListeners
;
102 // ------------------------------------------------------------------------
104 // ------------------------------------------------------------------------
107 * Default constructor with default number of buckets.
109 public HistogramDataModel() {
110 this(0, DEFAULT_NUMBER_OF_BUCKETS
);
114 * Default constructor with default number of buckets.
115 * @param startTime The histogram start time
118 public HistogramDataModel(long startTime
) {
119 this(startTime
, DEFAULT_NUMBER_OF_BUCKETS
);
123 * Constructor with non-default number of buckets.
124 * @param nbBuckets A number of buckets.
126 public HistogramDataModel(int nbBuckets
) {
131 * Constructor with non-default number of buckets.
132 * @param startTime the histogram start time
133 * @param nbBuckets A number of buckets.
136 public HistogramDataModel(long startTime
, int nbBuckets
) {
137 fFirstBucketTime
= fFirstEventTime
= fLastEventTime
= startTime
;
138 fNbBuckets
= nbBuckets
;
139 fBuckets
= new long[nbBuckets
];
140 fModelListeners
= new ListenerList();
146 * @param other A model to copy.
148 public HistogramDataModel(HistogramDataModel other
) {
149 fNbBuckets
= other
.fNbBuckets
;
150 fBuckets
= Arrays
.copyOf(other
.fBuckets
, fNbBuckets
);
151 fBucketDuration
= Math
.max(other
.fBucketDuration
, 1);
152 fNbEvents
= other
.fNbEvents
;
153 fLastBucket
= other
.fLastBucket
;
154 fFirstBucketTime
= other
.fFirstBucketTime
;
155 fFirstEventTime
= other
.fFirstEventTime
;
156 fLastEventTime
= other
.fLastEventTime
;
157 fCurrentEventTime
= other
.fCurrentEventTime
;
158 fTimeLimit
= other
.fTimeLimit
;
159 fModelListeners
= new ListenerList();
160 Object
[] listeners
= other
.fModelListeners
.getListeners();
161 for (Object listener
: listeners
) {
162 fModelListeners
.add(listener
);
166 // ------------------------------------------------------------------------
168 // ------------------------------------------------------------------------
171 * Returns the number of events in the data model.
172 * @return number of events.
174 public long getNbEvents() {
179 * Returns the number of buckets in the model.
180 * @return number of buckets.
182 public int getNbBuckets() {
187 * Returns the current bucket duration.
188 * @return bucket duration
190 public long getBucketDuration() {
191 return fBucketDuration
;
195 * Returns the time value of the first bucket in the model.
196 * @return time of first bucket.
198 public long getFirstBucketTime() {
199 return fFirstBucketTime
;
203 * Returns the time of the first event in the model.
204 * @return time of first event.
206 public long getStartTime() {
207 return fFirstEventTime
;
211 * Sets the model start time
212 * @param startTime the histogram range start time
213 * @param endTime the histogram range end time
216 public void setTimeRange(long startTime
, long endTime
) {
217 fFirstBucketTime
= fFirstEventTime
= fLastEventTime
= startTime
;
220 while (endTime
>= fTimeLimit
) {
226 * Returns the time of the last event in the model.
227 * @return the time of last event.
229 public long getEndTime() {
230 return fLastEventTime
;
234 * Returns the time of the current event in the model.
235 * @return the time of the current event.
237 public long getCurrentEventTime() {
238 return fCurrentEventTime
;
242 * Returns the time limit with is: start time + nbBuckets * bucketDuration
243 * @return the time limit.
245 public long getTimeLimit() {
249 // ------------------------------------------------------------------------
251 // ------------------------------------------------------------------------
254 * Add a listener to the model to be informed about model changes.
255 * @param listener A listener to add.
257 public void addHistogramListener(IHistogramModelListener listener
) {
258 fModelListeners
.add(listener
);
262 * Remove a given model listener.
263 * @param listener A listener to remove.
265 public void removeHistogramListener(IHistogramModelListener listener
) {
266 fModelListeners
.remove(listener
);
269 // Notify listeners (always)
270 private void fireModelUpdateNotification() {
271 fireModelUpdateNotification(0);
274 // Notify listener on boundary
275 private void fireModelUpdateNotification(long count
) {
276 if ((count
% REFRESH_FREQUENCY
) == 0) {
277 Object
[] listeners
= fModelListeners
.getListeners();
278 for (Object listener2
: listeners
) {
279 IHistogramModelListener listener
= (IHistogramModelListener
) listener2
;
280 listener
.modelUpdated();
285 // ------------------------------------------------------------------------
287 // ------------------------------------------------------------------------
291 * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#complete()
294 public void complete() {
295 fireModelUpdateNotification();
299 * Clear the histogram model.
300 * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
303 public void clear() {
304 Arrays
.fill(fBuckets
, 0);
306 fFirstBucketTime
= 0;
308 fCurrentEventTime
= 0;
312 fireModelUpdateNotification();
316 * Sets the current event time (no notification of listeners)
318 * @param timestamp A time stamp to set.
320 public void setCurrentEvent(long timestamp
) {
321 fCurrentEventTime
= timestamp
;
325 * Sets the current event time with notification of listeners
327 * @param timestamp A time stamp to set.
329 public void setCurrentEventNotifyListeners(long timestamp
) {
330 fCurrentEventTime
= timestamp
;
331 fireModelUpdateNotification();
335 * Add event to the correct bucket, compacting the if needed.
337 * @param eventCount The current event Count (for notification purposes)
338 * @param timestamp The timestamp of the event to count
342 public void countEvent(long eventCount
, long timestamp
) {
349 // Set the start/end time if not already done
350 if ((fFirstBucketTime
== 0) && (fLastBucket
== 0) && (fBuckets
[0] == 0) && (timestamp
> 0)) {
351 fFirstBucketTime
= timestamp
;
352 fFirstEventTime
= timestamp
;
356 if (timestamp
< fFirstEventTime
) {
357 fFirstEventTime
= timestamp
;
360 if (fLastEventTime
< timestamp
) {
361 fLastEventTime
= timestamp
;
364 if (timestamp
>= fFirstBucketTime
) {
367 while (timestamp
>= fTimeLimit
) {
373 // get offset for adjustment
374 int offset
= getOffset(timestamp
);
377 while((fLastBucket
+ offset
) >= fNbBuckets
) {
379 offset
= getOffset(timestamp
);
384 fLastBucket
= fLastBucket
+ offset
;
386 fFirstBucketTime
= fFirstBucketTime
- (offset
*fBucketDuration
);
390 // Increment the right bucket
391 int index
= (int) ((timestamp
- fFirstBucketTime
) / fBucketDuration
);
394 if (fLastBucket
< index
) {
398 fireModelUpdateNotification(eventCount
);
402 * Scale the model data to the width, height and bar width requested.
404 * @param width A width of the histogram canvas
405 * @param height A height of the histogram canvas
406 * @param barWidth A width (in pixel) of a histogram bar
407 * @return the result array of size [width] and where the highest value doesn't exceed [height]
409 * @see org.eclipse.linuxtools.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int, int, int)
412 public HistogramScaledData
scaleTo(int width
, int height
, int barWidth
) {
414 if ((width
<= 0) || (height
<= 0) || (barWidth
<= 0))
416 throw new AssertionError("Invalid histogram dimensions (" + width
+ "x" + height
+ ", barWidth=" + barWidth
+ ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
419 // The result structure
420 HistogramScaledData result
= new HistogramScaledData(width
, height
, barWidth
);
422 // Scale horizontally
423 result
.fMaxValue
= 0;
425 int nbBars
= width
/ barWidth
;
426 int bucketsPerBar
= (fLastBucket
/ nbBars
) + 1;
427 result
.fBucketDuration
= Math
.max(bucketsPerBar
* fBucketDuration
,1);
428 for (int i
= 0; i
< nbBars
; i
++) {
430 for (int j
= i
* bucketsPerBar
; j
< ((i
+ 1) * bucketsPerBar
); j
++) {
431 if (fNbBuckets
<= j
) {
434 count
+= fBuckets
[j
];
436 result
.fData
[i
] = count
;
437 result
.fLastBucket
= i
;
438 if (result
.fMaxValue
< count
) {
439 result
.fMaxValue
= count
;
444 if (result
.fMaxValue
> 0) {
445 result
.fScalingFactor
= (double) height
/ result
.fMaxValue
;
448 fBucketDuration
= Math
.max(fBucketDuration
, 1);
449 // Set the current event index in the scaled histogram
450 if ((fCurrentEventTime
>= fFirstBucketTime
) && (fCurrentEventTime
<= fLastEventTime
)) {
451 result
.fCurrentBucket
= (int) ((fCurrentEventTime
- fFirstBucketTime
) / fBucketDuration
) / bucketsPerBar
;
453 result
.fCurrentBucket
= HistogramScaledData
.OUT_OF_RANGE_BUCKET
;
456 result
.fFirstBucketTime
= fFirstBucketTime
;
457 result
.fFirstEventTime
= fFirstEventTime
;
461 // ------------------------------------------------------------------------
463 // ------------------------------------------------------------------------
465 private void updateEndTime() {
466 fTimeLimit
= fFirstBucketTime
+ (fNbBuckets
* fBucketDuration
);
469 private void mergeBuckets() {
470 for (int i
= 0; i
< (fNbBuckets
/ 2); i
++) {
471 fBuckets
[i
] = fBuckets
[2 * i
] + fBuckets
[(2 * i
) + 1];
473 Arrays
.fill(fBuckets
, fNbBuckets
/ 2, fNbBuckets
, 0);
474 fBucketDuration
*= 2;
476 fLastBucket
= (fNbBuckets
/ 2) - 1;
479 private void moveBuckets(int offset
) {
480 for(int i
= fNbBuckets
- 1; i
>= offset
; i
--) {
481 fBuckets
[i
] = fBuckets
[i
-offset
];
484 for (int i
= 0; i
< offset
; i
++) {
489 private int getOffset(long timestamp
) {
490 int offset
= (int) ((fFirstBucketTime
- timestamp
) / fBucketDuration
);
491 if (((fFirstBucketTime
- timestamp
) % fBucketDuration
) != 0) {