[deliverable/tracecompass.git] / org.eclipse.tracecompass.tmf.ui / src / org / eclipse / tracecompass / tmf / ui / views / histogram / HistogramDataModel.java

/*******************************************************************************
 * Copyright (c) 2011, 2015 Ericsson
 *
 * All rights reserved. This program and the accompanying materials are
 * made available under the terms of the Eclipse Public License v1.0 which
 * accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *   Francois Chouinard - Initial API and implementation
 *   Bernd Hufmann - Implementation of new interfaces/listeners and support for
 *                   time stamp in any order
 *   Francois Chouinard - Moved from LTTng to TMF
 *   Francois Chouinard - Added support for empty initial buckets
 *   Patrick Tasse - Support selection range
 *   Jean-Christian Kouamé, Simon Delisle - Added support to manage lost events
 *   Xavier Raynaud - Support multi-trace coloring
 *******************************************************************************/

package org.eclipse.tracecompass.tmf.ui.views.histogram;

import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;

import org.eclipse.core.runtime.ListenerList;
import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimeRange;
import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
import org.eclipse.tracecompass.tmf.core.trace.TmfTraceManager;

import com.google.common.base.Function;
import com.google.common.collect.FluentIterable;

/**
 * Histogram-independent data model.
 *
 * It has the following characteristics:
 * <ul>
 * <li>The <i>basetime</i> is the timestamp of the first event
 * <li>There is a fixed number (<i>n</i>) of buckets of uniform duration (
 * <i>d</i>)
 * <li>The <i>timespan</i> of the model is thus: <i>n</i> * <i>d</i> time units
 * <li>Bucket <i>i</i> holds the number of events that occurred in time range: [
 * <i>basetime</i> + <i>i</i> * <i>d</i>, <i>basetime</i> + (<i>i</i> + 1) *
 * <i>d</i>)
 * </ul>
 * Initially, the bucket durations is set to 1ns. As the events are read, they
 * are tallied (using <i>countEvent()</i>) in the appropriate bucket (relative
 * to the <i>basetime</i>).
 * <p>
 * Eventually, an event will have a timestamp that exceeds the <i>timespan</i>
 * high end (determined by <i>n</i>, the number of buckets, and <i>d</i>, the
 * bucket duration). At this point, the histogram needs to be compacted. This is
 * done by simply merging adjacent buckets by pair, in effect doubling the
 * <i>timespan</i> (<i>timespan'</i> = <i>n</i> * <i>d'</i>, where <i>d'</i> = 2
 * <i>d</i>). This compaction happens as needed as the trace is read.
 * <p>
 * The model allows for timestamps in not increasing order. The timestamps can
 * be fed to the model in any order. If an event has a timestamp less than the
 * <i>basetime</i>, the buckets will be moved to the right to account for the
 * new smaller timestamp. The new <i>basetime</i> is a multiple of the bucket
 * duration smaller then the previous <i>basetime</i>. Note that the
 * <i>basetime</i> might no longer be the timestamp of an event. If necessary,
 * the buckets will be compacted before moving to the right. This might be
 * necessary to not lose any event counts at the end of the buckets array.
 * <p>
 * The mapping from the model to the UI is performed by the <i>scaleTo()</i>
 * method. By keeping the number of buckets <i>n</i> relatively large with
 * respect to to the number of pixels in the actual histogram, we should achieve
 * a nice result when visualizing the histogram.
 * <p>
 *
 * @version 2.0
 * @author Francois Chouinard
 */
public class HistogramDataModel implements IHistogramDataModel {

    // ------------------------------------------------------------------------
    // Constants
    // ------------------------------------------------------------------------

    /**
     * The default number of buckets
     */
    public static final int DEFAULT_NUMBER_OF_BUCKETS = 16 * 1000;

    /**
     * Number of events after which listeners will be notified.
     */
    public static final int REFRESH_FREQUENCY = DEFAULT_NUMBER_OF_BUCKETS;

    // ------------------------------------------------------------------------
    // Attributes
    // ------------------------------------------------------------------------

    // Trace management
    private ITmfTrace fTrace = null;
    private final Map<ITmfTrace, Integer> fTraceMap = new LinkedHashMap<>();

    // Bucket management
    private final int fNbBuckets;
    private final HistogramBucket[] fBuckets;
    private final long[] fLostEventsBuckets;
    private long fBucketDuration;
    private long fNbEvents;
    private int fLastBucket;

    // Timestamps
    private long fFirstBucketTime; // could be negative when analyzing events
                                   // with descending order!!!
    private long fFirstEventTime;
    private long fEndTime;
    private long fSelectionBegin;
    private long fSelectionEnd;
    private long fTimeLimit;

    // Private listener lists
    private final ListenerList fModelListeners;

    // ------------------------------------------------------------------------
    // Constructors
    // ------------------------------------------------------------------------

    /**
     * Default constructor with default number of buckets.
     */
    public HistogramDataModel() {
        this(0, DEFAULT_NUMBER_OF_BUCKETS);
    }

    /**
     * Default constructor with default number of buckets.
     *
     * @param startTime
     *            The histogram start time
     */
    public HistogramDataModel(long startTime) {
        this(startTime, DEFAULT_NUMBER_OF_BUCKETS);
    }

    /**
     * Constructor with non-default number of buckets.
     *
     * @param nbBuckets
     *            A number of buckets.
     */
    public HistogramDataModel(int nbBuckets) {
        this(0, nbBuckets);
    }

    /**
     * Constructor with non-default number of buckets.
     *
     * @param startTime
     *            the histogram start time
     * @param nbBuckets
     *            A number of buckets.
     */
    public HistogramDataModel(long startTime, int nbBuckets) {
        fFirstBucketTime = fFirstEventTime = fEndTime = startTime;
        fNbBuckets = nbBuckets;
        fBuckets = new HistogramBucket[nbBuckets];
        fLostEventsBuckets = new long[nbBuckets];
        fModelListeners = new ListenerList();
        clear();
    }

    /**
     * Copy constructor.
     *
     * @param other
     *            A model to copy.
     */
    public HistogramDataModel(HistogramDataModel other) {
        fNbBuckets = other.fNbBuckets;
        fBuckets = new HistogramBucket[fNbBuckets];
        for (int i = 0; i < fNbBuckets; i++) {
            fBuckets[i] = new HistogramBucket(other.fBuckets[i]);
        }
        fLostEventsBuckets = Arrays.copyOf(other.fLostEventsBuckets, fNbBuckets);
        fBucketDuration = Math.max(other.fBucketDuration, 1);
        fNbEvents = other.fNbEvents;
        fLastBucket = other.fLastBucket;
        fFirstBucketTime = other.fFirstBucketTime;
        fFirstEventTime = other.fFirstEventTime;
        fEndTime = other.fEndTime;
        fSelectionBegin = other.fSelectionBegin;
        fSelectionEnd = other.fSelectionEnd;
        fTimeLimit = other.fTimeLimit;
        fModelListeners = new ListenerList();
        Object[] listeners = other.fModelListeners.getListeners();
        for (Object listener : listeners) {
            fModelListeners.add(listener);
        }
    }

    /**
     * Disposes the data model
     */
    public void dispose() {
        fTraceMap.clear();
        fTrace = null;
    }

    // ------------------------------------------------------------------------
    // Accessors
    // ------------------------------------------------------------------------

    /**
     * Returns the number of events in the data model.
     *
     * @return number of events.
     */
    public long getNbEvents() {
        return fNbEvents;
    }

    /**
     * Returns the number of buckets in the model.
     *
     * @return number of buckets.
     */
    public int getNbBuckets() {
        return fNbBuckets;
    }

    /**
     * Returns the current bucket duration.
     *
     * @return bucket duration
     */
    public long getBucketDuration() {
        return fBucketDuration;
    }

    /**
     * Returns the time value of the first bucket in the model.
     *
     * @return time of first bucket.
     */
    public long getFirstBucketTime() {
        return fFirstBucketTime;
    }

    /**
     * Returns the time of the first event in the model.
     *
     * @return time of first event.
     */
    public long getStartTime() {
        return fFirstEventTime;
    }

    /**
     * Sets the trace of this model.
     *
     * @param trace
     *            - a {@link ITmfTrace}
     */
    public void setTrace(ITmfTrace trace) {
        this.fTrace = trace;
        fTraceMap.clear();
        int i = 0;
        for (ITmfTrace tr : TmfTraceManager.getTraceSet(fTrace)) {
            fTraceMap.put(tr, i);
            i++;
        }
    }

    /**
     * Gets the trace of this model.
     *
     * @return a {@link ITmfTrace}
     */
    public ITmfTrace getTrace() {
        return this.fTrace;
    }

    /**
     * Gets the traces names of this model.
     *
     * @return an array of trace names
     */
    public String[] getTraceNames() {
        FluentIterable<ITmfTrace> traces = FluentIterable.from(TmfTraceManager.getTraceSet(fTrace));
        FluentIterable<String> traceNames = traces.transform(new Function<ITmfTrace, String>() {
            @Override
            public String apply(ITmfTrace input) {
                return input.getName();
            }
        });
        return traceNames.toArray(String.class);
    }

    /**
     * Gets the number of traces of this model.
     *
     * @return the number of traces of this model.
     */
    public int getNbTraces() {
        Collection<ITmfTrace> traces = TmfTraceManager.getTraceSet(fTrace);
        if (traces.isEmpty()) {
            return 1; //
        }
        return traces.size();
    }

    /**
     * Sets the model start time
     *
     * @param startTime
     *            the histogram range start time
     * @param endTime
     *            the histogram range end time
     */
    public void setTimeRange(long startTime, long endTime) {
        fFirstBucketTime = fFirstEventTime = fEndTime = startTime;
        fBucketDuration = 1;
        updateEndTime();
        while (endTime >= fTimeLimit) {
            mergeBuckets();
        }
    }

    /**
     * Set the end time. Setting this ensures that the corresponding bucket is
     * displayed regardless of the event counts.
     *
     * @param endTime
     *            the time of the last used bucket
     */
    public void setEndTime(long endTime) {
        fEndTime = endTime;
        fLastBucket = (int) ((endTime - fFirstBucketTime) / fBucketDuration);
    }

    /**
     * Returns the end time.
     *
     * @return the time of the last used bucket
     */
    public long getEndTime() {
        return fEndTime;
    }

    /**
     * Returns the begin time of the current selection in the model.
     *
     * @return the begin time of the current selection.
     */
    public long getSelectionBegin() {
        return fSelectionBegin;
    }

    /**
     * Returns the end time of the current selection in the model.
     *
     * @return the end time of the current selection.
     */
    public long getSelectionEnd() {
        return fSelectionEnd;
    }

    /**
     * Returns the time limit with is: start time + nbBuckets * bucketDuration
     *
     * @return the time limit.
     */
    public long getTimeLimit() {
        return fTimeLimit;
    }

    // ------------------------------------------------------------------------
    // Listener handling
    // ------------------------------------------------------------------------

    /**
     * Add a listener to the model to be informed about model changes.
     *
     * @param listener
     *            A listener to add.
     */
    public void addHistogramListener(IHistogramModelListener listener) {
        fModelListeners.add(listener);
    }

    /**
     * Remove a given model listener.
     *
     * @param listener
     *            A listener to remove.
     */
    public void removeHistogramListener(IHistogramModelListener listener) {
        fModelListeners.remove(listener);
    }

    // Notify listeners (always)
    private void fireModelUpdateNotification() {
        fireModelUpdateNotification(0);
    }

    // Notify listener on boundary
    private void fireModelUpdateNotification(long count) {
        if ((count % REFRESH_FREQUENCY) == 0) {
            Object[] listeners = fModelListeners.getListeners();
            for (Object listener2 : listeners) {
                IHistogramModelListener listener = (IHistogramModelListener) listener2;
                listener.modelUpdated();
            }
        }
    }

    // ------------------------------------------------------------------------
    // Operations
    // ------------------------------------------------------------------------

    @Override
    public void complete() {
        fireModelUpdateNotification();
    }

    /**
     * Clear the histogram model.
     *
     * @see org.eclipse.tracecompass.tmf.ui.views.distribution.model.IBaseDistributionModel#clear()
     */
    @Override
    public synchronized void clear() {
        Arrays.fill(fBuckets, null);
        Arrays.fill(fLostEventsBuckets, 0);
        fNbEvents = 0;
        fFirstBucketTime = 0;
        fEndTime = 0;
        fSelectionBegin = 0;
        fSelectionEnd = 0;
        fLastBucket = -1;
        fBucketDuration = 1;
        updateEndTime();
        fireModelUpdateNotification();
    }

    /**
     * Sets the current selection time range (no notification of listeners)
     *
     * @param beginTime
     *            The selection begin time.
     * @param endTime
     *            The selection end time.
     */
    public void setSelection(long beginTime, long endTime) {
        fSelectionBegin = beginTime;
        fSelectionEnd = endTime;
    }

    /**
     * Sets the current selection time range with notification of listeners
     *
     * @param beginTime
     *            The selection begin time.
     * @param endTime
     *            The selection end time.
     */
    public void setSelectionNotifyListeners(long beginTime, long endTime) {
        fSelectionBegin = beginTime;
        fSelectionEnd = endTime;
        fireModelUpdateNotification();
    }

    /**
     * Add event to the correct bucket, compacting the if needed.
     *
     * @param eventCount
     *            The current event Count (for notification purposes)
     * @param timestamp
     *            The timestamp of the event to count
     * @param trace
     *            The event trace
     */
    @Override
    public synchronized void countEvent(long eventCount, long timestamp, ITmfTrace trace) {

        // Validate
        if (timestamp < 0) {
            return;
        }

        // Set the start/end time if not already done
        if ((fFirstBucketTime == 0) && (fLastBucket == -1) && (fBuckets[0] == null) && (timestamp > 0)) {
            fFirstBucketTime = timestamp;
            fFirstEventTime = timestamp;
            updateEndTime();
        }

        if (timestamp < fFirstEventTime) {
            fFirstEventTime = timestamp;
        }

        if (fEndTime < timestamp) {
            fEndTime = timestamp;
        }

        if (timestamp >= fFirstBucketTime) {

            // Compact as needed
            while (timestamp >= fTimeLimit) {
                mergeBuckets();
            }

        } else {

            // get offset for adjustment
            long preMergeOffset = getOffset(timestamp);

            // Compact as needed
            while ((fLastBucket + preMergeOffset) >= fNbBuckets) {
                mergeBuckets();
                preMergeOffset = getOffset(timestamp);
            }

            // after merging the offset should be less than number of buckets
            int offset = (int) preMergeOffset;
            moveBuckets(offset);

            fLastBucket = fLastBucket + offset;

            fFirstBucketTime = fFirstBucketTime - (offset * fBucketDuration);
            updateEndTime();
        }

        // Increment the right bucket
        int index = (int) ((timestamp - fFirstBucketTime) / fBucketDuration);
        if (fBuckets[index] == null) {
            fBuckets[index] = new HistogramBucket(getNbTraces());
        }
        Integer traceIndex = fTraceMap.get(trace);
        if (traceIndex == null) {
            traceIndex = 0;
        }
        fBuckets[index].addEvent(traceIndex);
        fNbEvents++;
        if (fLastBucket < index) {
            fLastBucket = index;
        }

        fireModelUpdateNotification(eventCount);
    }

    /**
     * Add lost event to the correct bucket, compacting the if needed.
     *
     * @param timeRange
     *            time range of a lost event
     * @param nbLostEvents
     *            the number of lost events
     * @param fullRange
     *            Full range or time range for histogram request
     */
    public void countLostEvent(TmfTimeRange timeRange, long nbLostEvents, boolean fullRange) {

        long startTime = timeRange.getStartTime().getValue();
        long endTime = timeRange.getEndTime().getValue();

        // Validate
        if (startTime < 0 || endTime < 0) {
            return;
        }

        // Set the start/end time if not already done
        if ((fFirstBucketTime == 0) && (fLastBucket == -1) && (fBuckets[0] == null)) {
            fFirstBucketTime = startTime;
            fFirstEventTime = startTime;
            updateEndTime();
        }

        // Compact as needed
        if (fullRange) {
            while (endTime >= fTimeLimit) {
                mergeBuckets();
            }
        }

        int indexStart = (int) ((startTime - fFirstBucketTime) / fBucketDuration);
        int indexEnd = (int) ((endTime - fFirstBucketTime) / fBucketDuration);
        int nbBucketRange = (indexEnd - indexStart) + 1;

        int lostEventPerBucket = (int) Math.ceil((double) nbLostEvents / nbBucketRange);
        long lastLostCol = Math.max(1, nbLostEvents - lostEventPerBucket * (nbBucketRange - 1));

        // Increment the right bucket, bear in mind that ranges make it almost
        // certain that some lost events are out of range
        for (int index = indexStart; index <= indexEnd && index < fLostEventsBuckets.length; index++) {
            if (index == (indexStart + nbBucketRange - 1)) {
                fLostEventsBuckets[index] += lastLostCol;
            } else {
                fLostEventsBuckets[index] += lostEventPerBucket;
            }
        }

        fNbEvents++;

        fireModelUpdateNotification(nbLostEvents);
    }

    /**
     * Scale the model data to the width, height and bar width requested.
     *
     * @param width
     *            A width of the histogram canvas
     * @param height
     *            A height of the histogram canvas
     * @param barWidth
     *            A width (in pixel) of a histogram bar
     * @return the result array of size [width] and where the highest value
     *         doesn't exceed [height]
     *
     * @see org.eclipse.tracecompass.tmf.ui.views.histogram.IHistogramDataModel#scaleTo(int,
     *      int, int)
     */
    @Override
    public HistogramScaledData scaleTo(int width, int height, int barWidth) {
        // Basic validation
        if ((width <= 0) || (height <= 0) || (barWidth <= 0)) {
            throw new AssertionError("Invalid histogram dimensions (" + width + "x" + height + ", barWidth=" + barWidth + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
        }
        if (fBucketDuration == 0) {
            throw new IllegalStateException("Bucket width is 0, that should be impossible"); //$NON-NLS-1$
        }

        // The result structure
        HistogramScaledData result = new HistogramScaledData(width, height, barWidth);

        // Scale horizontally
        result.fMaxValue = 0;

        int nbBars = width / barWidth;
        double bucketsPerBar = ((double) fLastBucket / nbBars);
        final long modelBucketStartTime = fFirstBucketTime;
        final long modelBucketEndTime = fEndTime;
        /*
         * If there is only one model bucket, use a duration of 1 to spread the
         * value over the scaled width, but store a scaled bucket duration of 0
         * to prevent the half-bucket offset in the bucket time calculations.
         */
        double bucketDuration = Math.max(modelBucketEndTime - modelBucketStartTime, 1) / (double) nbBars;
        result.fBucketDuration = fLastBucket == 0 ? 0 : bucketDuration;
        int scaledCount = 0;
        int scaledCountLostEvent = 0;
        int offset = (int) (0.5 / bucketDuration);
        for (int i = 0; i < result.fData.length; i++) {
            result.fData[i] = new HistogramBucket(getNbTraces());
        }
        for (int modelIndex = 0; modelIndex <= fLastBucket; modelIndex++) {
            double done = (double) modelIndex / (double) (fLastBucket);
            double doneNext = (double) (modelIndex + 1) / (double) (fLastBucket);
            final int scaledStart = Math.max((int) (done * nbBars) - offset, 0);
            final int scaledEnd = Math.min((int) (doneNext * nbBars) - offset, nbBars - 1);
            int scaledIndex = scaledStart;
            final HistogramBucket currentModelBucket = fBuckets[modelIndex];
            if (currentModelBucket != null) {
                do {
                    // Make sure last model bucket counted in last scaled index
                    scaledIndex = Math.min(scaledIndex, nbBars - 1);
                    if (result.fData[scaledIndex].getNbEvents() == 0) {
                        scaledCount = 0;
                        scaledCountLostEvent = 0;
                    }
                    result.fData[scaledIndex].add(currentModelBucket);
                    result.fLostEventsData[scaledIndex] += fLostEventsBuckets[modelIndex];
                    scaledCountLostEvent += fLostEventsBuckets[modelIndex];
                    scaledCount += currentModelBucket.getNbEvents();
                    if (!currentModelBucket.isEmpty()) {
                        result.fLastBucket = scaledIndex;
                    }
                    if (result.fMaxValue < scaledCount) {
                        result.fMaxValue = scaledCount;
                    }
                    if (result.fMaxCombinedValue < scaledCount + scaledCountLostEvent) {
                        result.fMaxCombinedValue = scaledCount + scaledCountLostEvent;
                    }
                    scaledIndex++;
                } while (scaledIndex < scaledEnd);
            }
        }

        // Scale vertically
        if (result.fMaxValue > 0) {
            result.fScalingFactor = (double) height / result.fMaxValue;
        }
        if (result.fMaxCombinedValue > 0) {
            result.fScalingFactorCombined = (double) height / result.fMaxCombinedValue;
        }

        fBucketDuration = Math.max(fBucketDuration, 1);

        // Set selection begin and end index in the scaled histogram
        if (fSelectionBegin == fEndTime) {
            // make sure selection is visible at the end
            result.fSelectionBeginBucket = result.fWidth - 1;
        } else {
            result.fSelectionBeginBucket = (int) Math.round(((fSelectionBegin - fFirstBucketTime) / (double) fBucketDuration) / bucketsPerBar);
        }

        if (fSelectionEnd == fEndTime) {
            // make sure selection is visible at the end
            result.fSelectionEndBucket = result.fWidth - 1;
        } else {
            result.fSelectionEndBucket = (int) Math.round(((fSelectionEnd - fFirstBucketTime) / (double) fBucketDuration) / bucketsPerBar);
        }

        result.fFirstBucketTime = fFirstBucketTime;
        result.fFirstEventTime = fFirstEventTime;
        return result;
    }

    // ------------------------------------------------------------------------
    // Helper functions
    // ------------------------------------------------------------------------

    private void updateEndTime() {
        fTimeLimit = fFirstBucketTime + (fNbBuckets * fBucketDuration);
    }

    private void mergeBuckets() {
        for (int i = 0; i < (fNbBuckets / 2); i++) {
            fBuckets[i] = new HistogramBucket(fBuckets[2 * i], fBuckets[(2 * i) + 1]);
            fLostEventsBuckets[i] = fLostEventsBuckets[2 * i] + fLostEventsBuckets[(2 * i) + 1];
        }
        Arrays.fill(fBuckets, fNbBuckets / 2, fNbBuckets, null);
        Arrays.fill(fLostEventsBuckets, fNbBuckets / 2, fNbBuckets, 0);
        fBucketDuration *= 2;
        updateEndTime();
        fLastBucket = (fNbBuckets / 2) - 1;
    }

    private void moveBuckets(int offset) {
        for (int i = fNbBuckets - 1; i >= offset; i--) {
            fBuckets[i] = new HistogramBucket(fBuckets[i - offset]);
            fLostEventsBuckets[i] = fLostEventsBuckets[i - offset];
        }

        for (int i = 0; i < offset; i++) {
            fBuckets[i] = null;
            fLostEventsBuckets[i] = 0;
        }
    }

    private long getOffset(long timestamp) {
        long offset = (fFirstBucketTime - timestamp) / fBucketDuration;
        if (((fFirstBucketTime - timestamp) % fBucketDuration) != 0) {
            offset++;
        }
        return offset;
    }
}