org.eclipse.linuxtools.tmf.ui/src/org/eclipse/linuxtools/tmf/ui/views/histogram/HistogramDataModel.java

   1 /*******************************************************************************
   2  * Copyright (c) 2011, 2013 Ericsson
   3  *
   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
   8  *
   9  * Contributors:
  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  *******************************************************************************/
  17
  18 package org.eclipse.linuxtools.tmf.ui.views.histogram;
  19
  20 import java.util.Arrays;
  21
  22 import org.eclipse.core.runtime.ListenerList;
  23
  24 /**
  25  * Histogram-independent data model.
  26  *
  27  * It has the following characteristics:
  28  * <ul>
  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
  31  * (<i>d</i>)
  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) *
  35  * <i>d</i>)
  36  * </ul>
  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>).
  40  * <p>
  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.
  47  * <p>
  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.
  56  * <p>
  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.
  61  * <p>
  62  *
  63  * @version 2.0
  64  * @author Francois Chouinard
  65  */
  66 public class HistogramDataModel implements IHistogramDataModel {
  67
  68     // ------------------------------------------------------------------------
  69     // Constants
  70     // ------------------------------------------------------------------------
  71
  72     /**
  73      *  The default number of buckets
  74      */
  75     public static final int DEFAULT_NUMBER_OF_BUCKETS = 16 * 1000;
  76
  77     /**
  78      * Number of events after which listeners will be notified.
  79      */
  80     public static final int REFRESH_FREQUENCY = DEFAULT_NUMBER_OF_BUCKETS;
  81
  82     // ------------------------------------------------------------------------
  83     // Attributes
  84     // ------------------------------------------------------------------------
  85
  86     // Bucket management
  87     private final int fNbBuckets;
  88     private final long[] fBuckets;
  89     private long fBucketDuration;
  90     private long fNbEvents;
  91     private int fLastBucket;
  92
  93     // Timestamps
  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;
 100
 101     // Private listener lists
 102     private final ListenerList fModelListeners;
 103
 104     // ------------------------------------------------------------------------
 105     // Constructors
 106     // ------------------------------------------------------------------------
 107
 108     /**
 109      * Default constructor with default number of buckets.
 110      */
 111     public HistogramDataModel() {
 112         this(0, DEFAULT_NUMBER_OF_BUCKETS);
 113     }
 114
 115     /**
 116      * Default constructor with default number of buckets.
 117      * @param startTime The histogram start time
 118      * @since 2.0
 119      */
 120     public HistogramDataModel(long startTime) {
 121         this(startTime, DEFAULT_NUMBER_OF_BUCKETS);
 122     }
 123
 124     /**
 125      * Constructor with non-default number of buckets.
 126      * @param nbBuckets A number of buckets.
 127      */
 128     public HistogramDataModel(int nbBuckets) {
 129         this(0, nbBuckets);
 130     }
 131
 132     /**
 133      * Constructor with non-default number of buckets.
 134      * @param startTime the histogram start time
 135      * @param nbBuckets A number of buckets.
 136      * @since 2.0
 137      */
 138     public HistogramDataModel(long startTime, int nbBuckets) {
 139         fFirstBucketTime = fFirstEventTime = fLastEventTime = startTime;
 140         fNbBuckets = nbBuckets;
 141         fBuckets = new long[nbBuckets];
 142         fModelListeners = new ListenerList();
 143         clear();
 144     }
 145
 146     /**
 147      * Copy constructor.
 148      * @param other A model to copy.
 149      */
 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);
 166         }
 167     }
 168
 169     // ------------------------------------------------------------------------
 170     // Accessors
 171     // ------------------------------------------------------------------------
 172
 173     /**
 174      * Returns the number of events in the data model.
 175      * @return number of events.
 176      */
 177     public long getNbEvents() {
 178         return fNbEvents;
 179     }
 180
 181     /**
 182      * Returns the number of buckets in the model.
 183      * @return number of buckets.
 184      */
 185     public int getNbBuckets() {
 186         return fNbBuckets;
 187     }
 188
 189    /**
 190     * Returns the current bucket duration.
 191     * @return bucket duration
 192     */
 193     public long getBucketDuration() {
 194         return fBucketDuration;
 195     }
 196
 197     /**
 198      * Returns the time value of the first bucket in the model.
 199      * @return time of first bucket.
 200      */
 201     public long getFirstBucketTime() {
 202         return fFirstBucketTime;
 203     }
 204
 205     /**
 206      * Returns the time of the first event in the model.
 207      * @return time of first event.
 208      */
 209     public long getStartTime() {
 210         return fFirstEventTime;
 211     }
 212
 213     /**
 214      * Sets the model start time
 215      * @param startTime the histogram range start time
 216      * @param endTime the histogram range end time
 217      * @since 2.0
 218      */
 219     public void setTimeRange(long startTime, long endTime) {
 220         fFirstBucketTime = fFirstEventTime = fLastEventTime = startTime;
 221         fBucketDuration = 1;
 222         updateEndTime();
 223         while (endTime >= fTimeLimit) {
 224             mergeBuckets();
 225         }
 226     }
 227
 228     /**
 229      * Returns the time of the last event in the model.
 230      * @return the time of last event.
 231      */
 232     public long getEndTime() {
 233         return fLastEventTime;
 234     }
 235
 236     /**
 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()}
 240      */
 241     @Deprecated
 242     public long getCurrentEventTime() {
 243         return fSelectionBegin;
 244     }
 245
 246     /**
 247      * Returns the begin time of the current selection in the model.
 248      * @return the begin time of the current selection.
 249      * @since 3.0
 250      */
 251     public long getSelectionBegin() {
 252         return fSelectionBegin;
 253     }
 254
 255     /**
 256      * Returns the end time of the current selection in the model.
 257      * @return the end time of the current selection.
 258      * @since 3.0
 259      */
 260     public long getSelectionEnd() {
 261         return fSelectionEnd;
 262     }
 263
 264     /**
 265      * Returns the time limit with is: start time + nbBuckets * bucketDuration
 266      * @return the time limit.
 267      */
 268     public long getTimeLimit() {
 269         return fTimeLimit;
 270     }
 271
 272     // ------------------------------------------------------------------------
 273     // Listener handling
 274     // ------------------------------------------------------------------------
 275
 276     /**
 277      * Add a listener to the model to be informed about model changes.
 278      * @param listener A listener to add.
 279      */
 280     public void addHistogramListener(IHistogramModelListener listener) {
 281         fModelListeners.add(listener);
 282     }
 283
 284     /**
 285      * Remove a given model listener.
 286      * @param listener A listener to remove.
 287      */
 288     public void removeHistogramListener(IHistogramModelListener listener) {
 289         fModelListeners.remove(listener);
 290     }
 291
 292     // Notify listeners (always)
 293     private void fireModelUpdateNotification() {
 294         fireModelUpdateNotification(0);
 295     }
 296
 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();
 304             }
 305         }
 306     }
 307
 308     // ------------------------------------------------------------------------
 309     // Operations
 310     // ------------------------------------------------------------------------
 311
 312     @Override
 313     public void complete() {
 314         fireModelUpdateNotification();
 315     }
 316
 317     /**
 318      * Clear the histogram model.
 319      * @see org.eclipse.linuxtools.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
 320      */
 321     @Override
 322     public void clear() {
 323         Arrays.fill(fBuckets, 0);
 324         fNbEvents = 0;
 325         fFirstBucketTime = 0;
 326         fLastEventTime = 0;
 327         fSelectionBegin = 0;
 328         fSelectionEnd = 0;
 329         fLastBucket = 0;
 330         fBucketDuration = 1;
 331         updateEndTime();
 332         fireModelUpdateNotification();
 333     }
 334
 335     /**
 336      * Sets the current event time (no notification of listeners)
 337      *
 338      * @param timestamp A time stamp to set.
 339      * @deprecated As of 2.1, use {@link #setSelection(long, long)}
 340      */
 341     @Deprecated
 342     public void setCurrentEvent(long timestamp) {
 343         fSelectionBegin = timestamp;
 344         fSelectionEnd = timestamp;
 345     }
 346
 347     /**
 348      * Sets the current event time with notification of listeners
 349      *
 350      * @param timestamp A time stamp to set.
 351      * @deprecated As of 2.1, use {@link #setSelectionNotifyListeners(long, long)}
 352      */
 353     @Deprecated
 354     public void setCurrentEventNotifyListeners(long timestamp) {
 355         fSelectionBegin = timestamp;
 356         fSelectionEnd = timestamp;
 357         fireModelUpdateNotification();
 358     }
 359
 360     /**
 361      * Sets the current selection time range (no notification of listeners)
 362      *
 363      * @param beginTime The selection begin time.
 364      * @param endTime The selection end time.
 365      * @since 3.0
 366      */
 367     public void setSelection(long beginTime, long endTime) {
 368         fSelectionBegin = beginTime;
 369         fSelectionEnd = endTime;
 370     }
 371
 372     /**
 373      * Sets the current selection time range with notification of listeners
 374      *
 375      * @param beginTime The selection begin time.
 376      * @param endTime The selection end time.
 377      * @since 3.0
 378      */
 379     public void setSelectionNotifyListeners(long beginTime, long endTime) {
 380         fSelectionBegin = beginTime;
 381         fSelectionEnd = endTime;
 382         fireModelUpdateNotification();
 383     }
 384
 385     /**
 386      * Add event to the correct bucket, compacting the if needed.
 387      *
 388      * @param eventCount The current event Count (for notification purposes)
 389      * @param timestamp The timestamp of the event to count
 390      *
 391      */
 392     @Override
 393     public void countEvent(long eventCount, long timestamp) {
 394
 395         // Validate
 396         if (timestamp < 0) {
 397             return;
 398         }
 399
 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;
 404             updateEndTime();
 405         }
 406
 407         if (timestamp < fFirstEventTime) {
 408             fFirstEventTime = timestamp;
 409         }
 410
 411         if (fLastEventTime < timestamp) {
 412             fLastEventTime = timestamp;
 413         }
 414
 415         if (timestamp >= fFirstBucketTime) {
 416
 417             // Compact as needed
 418             while (timestamp >= fTimeLimit) {
 419                 mergeBuckets();
 420             }
 421
 422         } else {
 423
 424             // get offset for adjustment
 425             int offset = getOffset(timestamp);
 426
 427             // Compact as needed
 428             while((fLastBucket + offset) >= fNbBuckets) {
 429                 mergeBuckets();
 430                 offset = getOffset(timestamp);
 431             }
 432
 433             moveBuckets(offset);
 434
 435             fLastBucket = fLastBucket + offset;
 436
 437             fFirstBucketTime = fFirstBucketTime - (offset*fBucketDuration);
 438             updateEndTime();
 439         }
 440
 441         // Increment the right bucket
 442         int index = (int) ((timestamp - fFirstBucketTime) / fBucketDuration);
 443         fBuckets[index]++;
 444         fNbEvents++;
 445         if (fLastBucket < index) {
 446             fLastBucket = index;
 447         }
 448
 449         fireModelUpdateNotification(eventCount);
 450     }
 451
 452     /**
 453      * Scale the model data to the width, height and bar width requested.
 454      *
 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]
 459      *
 460      * @see org.eclipse.linuxtools.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int, int, int)
 461      */
 462     @Override
 463     public HistogramScaledData scaleTo(int width, int height, int barWidth) {
 464         // Basic validation
 465         if ((width <= 0) ||  (height <= 0) || (barWidth <= 0))
 466          {
 467             throw new AssertionError("Invalid histogram dimensions (" + width + "x" + height + ", barWidth=" + barWidth + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
 468         }
 469
 470         // The result structure
 471         HistogramScaledData result = new HistogramScaledData(width, height, barWidth);
 472
 473         // Scale horizontally
 474         result.fMaxValue = 0;
 475
 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++) {
 480             int count = 0;
 481             for (int j = i * bucketsPerBar; j < ((i + 1) * bucketsPerBar); j++) {
 482                 if (fNbBuckets <= j) {
 483                     break;
 484                 }
 485                 count += fBuckets[j];
 486             }
 487             result.fData[i] = count;
 488             result.fLastBucket = i;
 489             if (result.fMaxValue < count) {
 490                 result.fMaxValue = count;
 491             }
 492         }
 493
 494         // Scale vertically
 495         if (result.fMaxValue > 0) {
 496             result.fScalingFactor = (double) height / result.fMaxValue;
 497         }
 498
 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;
 505         } else {
 506             result.fSelectionBeginBucket = (int) ((fSelectionBegin - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 507         }
 508         if (fSelectionEnd < fFirstBucketTime) {
 509             result.fSelectionEndBucket = -1;
 510         } else if (fSelectionEnd > fLastEventTime) {
 511             result.fSelectionEndBucket = fLastBucket;
 512         } else {
 513             result.fSelectionEndBucket = (int) ((fSelectionEnd - fFirstBucketTime) / fBucketDuration) / bucketsPerBar;
 514         }
 515
 516         result.fFirstBucketTime = fFirstBucketTime;
 517         result.fFirstEventTime = fFirstEventTime;
 518         return result;
 519     }
 520
 521     // ------------------------------------------------------------------------
 522     // Helper functions
 523     // ------------------------------------------------------------------------
 524
 525     private void updateEndTime() {
 526         fTimeLimit = fFirstBucketTime + (fNbBuckets * fBucketDuration);
 527     }
 528
 529     private void mergeBuckets() {
 530         for (int i = 0; i < (fNbBuckets / 2); i++) {
 531             fBuckets[i] = fBuckets[2 * i] + fBuckets[(2 * i) + 1];
 532         }
 533         Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, 0);
 534         fBucketDuration *= 2;
 535         updateEndTime();
 536         fLastBucket = (fNbBuckets / 2) - 1;
 537     }
 538
 539     private void moveBuckets(int offset) {
 540         for(int i = fNbBuckets - 1; i >= offset; i--) {
 541             fBuckets[i] = fBuckets[i-offset];
 542         }
 543
 544         for (int i = 0; i < offset; i++) {
 545             fBuckets[i] = 0;
 546         }
 547     }
 548
 549     private int getOffset(long timestamp) {
 550         int offset = (int) ((fFirstBucketTime - timestamp) / fBucketDuration);
 551         if (((fFirstBucketTime - timestamp) % fBucketDuration) != 0) {
 552             offset++;
 553         }
 554         return offset;
 555     }
 556
 557 }