QmlProfiler: Add model template for range data

In order to unify the uses of range data and the calculation of first
and last ranges in visible areas we need a template class to provide the
respective algorithms.

Change-Id: I1c2e9c9fa9ae048262026236c4ff39017ab7913f
Reviewed-by: Kai Koehne <kai.koehne@digia.com>

4 files changed, 302 insertions, 2 deletions

diff --git a/src/plugins/qmlprofiler/qmlprofiler.pro b/src/plugins/qmlprofiler/qmlprofiler.pro
index c43d3043a3..aa23d616c8 100644
--- a/src/plugins/qmlprofiler/qmlprofiler.pro
+++ b/src/plugins/qmlprofiler/qmlprofiler.pro
@@ -30,7 +30,8 @@ SOURCES += \
     qmlprofilertracefile.cpp \
     abstracttimelinemodel.cpp \
     timelinemodelaggregator.cpp \
-    qmlprofilerpainteventsmodelproxy.cpp
+    qmlprofilerpainteventsmodelproxy.cpp \
+    sortedtimelinemodel.cpp
 
 HEADERS += \
     qmlprofilerconstants.h \
@@ -61,7 +62,8 @@ HEADERS += \
     qmlprofilertracefile.h \
     abstracttimelinemodel.h \
     timelinemodelaggregator.h \
-    qmlprofilerpainteventsmodelproxy.h
+    qmlprofilerpainteventsmodelproxy.h \
+    sortedtimelinemodel.h
 
 RESOURCES += \
     qml/qmlprofiler.qrc
diff --git a/src/plugins/qmlprofiler/qmlprofiler.qbs b/src/plugins/qmlprofiler/qmlprofiler.qbs
index bba8e13c79..018019c49a 100644
--- a/src/plugins/qmlprofiler/qmlprofiler.qbs
+++ b/src/plugins/qmlprofiler/qmlprofiler.qbs
@@ -50,6 +50,7 @@ QtcPlugin {
             "qmlprofilerviewmanager.cpp", "qmlprofilerviewmanager.h",
             "qv8profilerdatamodel.cpp", "qv8profilerdatamodel.h",
             "qv8profilereventview.h", "qv8profilereventview.cpp",
+            "sortedtimelinemodel.h", "sortedtimelinemodel.cpp",
             "timelinemodelaggregator.cpp", "timelinemodelaggregator.h",
             "timelinerenderer.cpp", "timelinerenderer.h",
         ]
diff --git a/src/plugins/qmlprofiler/sortedtimelinemodel.cpp b/src/plugins/qmlprofiler/sortedtimelinemodel.cpp
new file mode 100644
index 0000000000..567c44981f
--- /dev/null
+++ b/src/plugins/qmlprofiler/sortedtimelinemodel.cpp
@@ -0,0 +1,110 @@
+/****************************************************************************
+**
+** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of Qt Creator.
+**
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+****************************************************************************/
+
+/*!
+    \class QmlProfiler::SortedTimelineModel
+    \brief Sorted model for timeline data
+
+    The SortedTimelineModel lets you keep any kind of range data sorted by
+    both start and end times, so that visible ranges can easily be computed.
+*/
+
+/*!
+    \fn SortedTimelineModel::clear()
+    Clears the ranges and their end times.
+*/
+
+/*!
+    \fn int SortedTimelineModel::count() const
+    Returns the number of ranges in the model.
+*/
+
+/*!
+    \fn qint64 SortedTimelineModel::firstStartTime() const
+    Returns the begin of the first range in the model.
+*/
+
+/*!
+    \fn qint64 SortedTimelineModel::lastEndTime() const
+    Returns the end of the last range in the model.
+*/
+
+/*!
+    \fn const SortedTimelineModel<Data>::Range &SortedTimelineModel::range(int index) const
+    Returns the range data at the specified index.
+*/
+
+/*!
+    \fn Data &SortedTimelineModel::data(int index)
+    Returns modifiable user data for the range at the specified index.
+*/
+
+/*!
+    \fn int SortedTimelineModel::insert(qint64 startTime, qint64 duration, const Data &item)
+    Inserts the given data at the given time position and returns its index.
+*/
+
+/*!
+    \fn int SortedTimelineModel::insertStart(qint64 startTime, const Data &item)
+    Inserts the given data as range start at the given time position and
+    returns its index. The range end isn't set.
+*/
+
+/*!
+    \fn int SortedTimelineModel::insertEnd(int index, qint64 duration)
+    Adds a range end for the given start index.
+*/
+
+/*!
+    \fn int SortedTimelineModel::findFirstIndexNoParents(qint64 startTime) const
+    Looks up the first range with an end time greater than the given time and
+    returns its index. If no such range is found it returns -1.
+*/
+
+/*!
+    \fn int SortedTimelineModel::findFirstIndex(qint64 startTime) const
+    Looks up the first range with an end time greater than the given time and
+    returns its parent's index. If no such range is found it returns -1. If there
+    is no parent it returns the found range's index. The parent of a range is the
+    range with the lowest start time that completely covers the child range.
+    "Completely covers" means:
+    parent.startTime <= child.startTime && parent.endTime >= child.endTime
+*/
+
+/*!
+    \fn int SortedTimelineModel::findLastIndex(qint64 endTime) const
+    Looks up the last range with a start time smaller than the given time and
+    returns its index. If no such range is found it returns -1.
+*/
+
+/*!
+    \fn void computeNesting()
+    Compute all ranges' parents.
+    \sa findFirstIndex
+*/
diff --git a/src/plugins/qmlprofiler/sortedtimelinemodel.h b/src/plugins/qmlprofiler/sortedtimelinemodel.h
new file mode 100644
index 0000000000..80f78f2fe2
--- /dev/null
+++ b/src/plugins/qmlprofiler/sortedtimelinemodel.h
@@ -0,0 +1,187 @@
+/****************************************************************************
+**
+** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of Qt Creator.
+**
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+****************************************************************************/
+
+#ifndef SORTEDTIMELINEMODEL_H
+#define SORTEDTIMELINEMODEL_H
+
+#include <QVector>
+#include <QLinkedList>
+
+namespace QmlProfiler {
+
+template<class Data>
+class SortedTimelineModel {
+public:
+    struct Range : public Data {
+        Range() : Data(), start(-1), duration(-1), parent(-1) {}
+        Range(qint64 start, qint64 duration, const Data &item) :
+            Data(item), start(start), duration(duration), parent(-1) {}
+        qint64 start;
+        qint64 duration;
+        int parent;
+        inline qint64 timestamp() const {return start;}
+    };
+
+    struct RangeEnd {
+        RangeEnd() : startIndex(-1), end(-1) {}
+        RangeEnd(int startIndex, qint64 end) :
+            startIndex(startIndex), end(end) {}
+        int startIndex;
+        qint64 end;
+        inline qint64 timestamp() const {return end;}
+    };
+
+    void clear()
+    {
+        ranges.clear();
+        endTimes.clear();
+    }
+
+    inline int count() const { return ranges.count(); }
+
+    inline qint64 lastEndTime() const { return endTimes.last().end; }
+    inline qint64 firstStartTime() const { return ranges.first().start; }
+
+    inline const Range &range(int index) { return ranges[index]; }
+    inline Data &data(int index) { return ranges[index]; }
+
+    inline int insert(qint64 startTime, qint64 duration, const Data &item)
+    {
+        /* Doing insert-sort here is preferable as most of the time the times will actually be
+         * presorted in the right way. So usually this will just result in appending. */
+        int index = insertSorted(ranges, Range(startTime, duration, item));
+        insertSorted(endTimes, RangeEnd(index, startTime + duration));
+        return index;
+    }
+
+    inline int insertStart(qint64 startTime, const Data &item)
+    {
+        return insertSorted(ranges, Range(startTime, 0, item));
+    }
+
+    inline void insertEnd(int index, qint64 duration)
+    {
+        ranges[index].duration = duration;
+        insertSorted(endTimes, RangeEnd(index, ranges[index].start + duration));
+    }
+
+    inline int findFirstIndex(qint64 startTime) const
+    {
+        int index = findFirstIndexNoParents(startTime);
+        if (index == -1)
+            return -1;
+        int parent = ranges[index].parent;
+        return parent == -1 ? index : parent;
+    }
+
+    inline int findFirstIndexNoParents(qint64 startTime) const
+    {
+        // in the "endtime" list, find the first event that ends after startTime
+        if (endTimes.isEmpty())
+            return -1;
+        if (endTimes.count() == 1 || endTimes.first().end >= startTime)
+            return endTimes.first().startIndex;
+        if (endTimes.last().end <= startTime)
+            return -1;
+
+        return endTimes[lowerBound(endTimes, startTime) + 1].startIndex;
+    }
+
+    inline int findLastIndex(qint64 endTime) const
+    {
+        // in the "starttime" list, find the last event that starts before endtime
+        if (ranges.isEmpty() || ranges.first().start >= endTime)
+            return -1;
+        if (ranges.count() == 1)
+            return 0;
+        if (ranges.last().start <= endTime)
+            return ranges.count() - 1;
+
+        return lowerBound(ranges, endTime);
+    }
+
+    inline void computeNesting()
+    {
+        QLinkedList<int> parents;
+        for (int range = 0; range != count(); ++range) {
+            Range &current = ranges[range];
+            for (QLinkedList<int>::iterator parent = parents.begin(); parent != parents.end();) {
+                qint64 parentEnd = ranges[*parent].start + ranges[*parent].duration;
+                if (parentEnd < current.start) {
+                    parent = parents.erase(parent);
+                } else if (parentEnd >= current.start + current.duration) {
+                    current.parent = *parent;
+                    break;
+                } else {
+                    ++parent;
+                }
+            }
+            parents.append(range);
+        }
+    }
+
+protected:
+    template<typename RangeDelimiter>
+    static inline int insertSorted(QVector<RangeDelimiter> &container, const RangeDelimiter &item)
+    {
+        for (int i = container.count();;) {
+            if (i == 0) {
+                container.prepend(item);
+                return 0;
+            }
+            if (container[--i].timestamp() <= item.timestamp()) {
+                container.insert(++i, item);
+                return i;
+            }
+        }
+    }
+
+    template<typename RangeDelimiter>
+    static inline int lowerBound(const QVector<RangeDelimiter> container, qint64 time)
+    {
+        int fromIndex = 0;
+        int toIndex = container.count() - 1;
+        while (toIndex - fromIndex > 1) {
+            int midIndex = (fromIndex + toIndex)/2;
+            if (container[midIndex].timestamp() < time)
+                fromIndex = midIndex;
+            else
+                toIndex = midIndex;
+        }
+
+        return fromIndex;
+    }
+
+    QVector<Range> ranges;
+    QVector<RangeEnd> endTimes;
+};
+
+}
+
+#endif