Changed median smoothing to preserve order.

The median smoothing now identifies and marks all
outliers in a result history the first time a smooth
value is requested. The outliers are the values that
were not selected at least once as the median value
when sliding the window. The smooth values are simply
the non-outliers.

This algorithm has the property of preserving the order
of the smooth values (simply since they are not moved
from their original positions at all!).

The old algorithm would effectively substitute each
value (except the first few ones which were
"uncomputable" because the window was right-aligned)
by its smoothest neighbor (possibly including itself).
In general, the ordering of the final smooth sequence
would then not match that of the original sequence.

5 files changed, 63 insertions, 140 deletions

diff --git a/src/bm/bmrequest.cpp b/src/bm/bmrequest.cpp
index 5f008b4..95bb7cb 100644
--- a/src/bm/bmrequest.cpp
+++ b/src/bm/bmrequest.cpp
@@ -5070,7 +5070,8 @@ QByteArray BMRequest_IndexGetValues::toReplyBuffer()
         deleteQuery(query);
 
         ResultHistoryInfo *rhInfo =
-            new ResultHistoryInfo(bmcontextIds.at(i), timestamps, values, metrics.at(i));
+            new ResultHistoryInfo(
+                bmcontextIds.at(i), timestamps, values, medianWinSize, metrics.at(i));
         rhInfos.append(rhInfo);
     }
 
@@ -5089,8 +5090,7 @@ QByteArray BMRequest_IndexGetValues::toReplyBuffer()
         // Candidate result histories exist, so compute index values ...
 
         QList<int> evalTimestamps;
-        IndexAlgorithm1 index(
-            rhInfos, baseTimestamp, medianWinSize, &evalTimestamps, &nonPositiveRH);
+        IndexAlgorithm1 index(rhInfos, baseTimestamp, &evalTimestamps, &nonPositiveRH);
         if (!index.isValid()) {
             return xmlConvert(
                 errorReply(
@@ -6436,7 +6436,8 @@ void BMRequest_GetHistories::handleReply_Image(const QStringList &args) const
 
             rhInfos.append(
                 new ResultHistoryInfo(
-                    -1, timestamps, values, metric, platform, host, gitRepo, gitBranch));
+                    -1, timestamps, values, -1, metric, platform, host, gitRepo,
+                    gitBranch));
         }
 
         // Create image ...
@@ -6879,9 +6880,7 @@ void BMRequest_GetIXHistories::handleReply_HTML(const QStringList &args) const
 
     reply += "The data points used for <i>baseVal</i>, <i>val</i><sub>1</sub>, and ";
     reply += "<i>val</i><sub>2</sub> are indicated in the graph as a blue circle, a red ";
-    reply += "square, and a red circle respectively. <b>Note:</b> due to the nature of ";
-    reply += "median smoothing, there is no guarantee that these three data points are ordered ";
-    reply += "in a particular way with respect to time.";
+    reply += "square, and a red circle respectively.";
 
     reply += "<br /><br />";
     reply += "The selected evaluation time is indicated by a blue vertical line ";
@@ -6968,7 +6967,7 @@ void BMRequest_GetIXHistories::handleReply_Image(const QStringList &args) const
 
         rhInfos.append(
             new ResultHistoryInfo(
-                -1, timestamps, values, metric, platform, host, gitRepo, gitBranch, testCase,
+                -1, timestamps, values, -1, metric, platform, host, gitRepo, gitBranch, testCase,
                 testFunction, dataTag));
 
         // Get the base- and diff positions and description ...
diff --git a/src/bm/index.cpp b/src/bm/index.cpp
index be29787..f71e0d8 100644
--- a/src/bm/index.cpp
+++ b/src/bm/index.cpp
@@ -32,9 +32,8 @@
 // Note: The dynamic memory in \a candidateRHInfos is deleted by this class.
 Index::Index(
     const QList<ResultHistoryInfo *> &candidateRHInfos, const int baseTimestamp,
-    int medianWinSize, QList<int> *evalTimestamps, int *rejectedNonPositive)
-    : baseTimestamp(baseTimestamp), medianWinSize(medianWinSize), valid(false)
-    , invalidReason_("uninitialized")
+    QList<int> *evalTimestamps, int *rejectedNonPositive)
+    : baseTimestamp(baseTimestamp), valid(false), invalidReason_("uninitialized")
 {
     init(candidateRHInfos, evalTimestamps, rejectedNonPositive);
 }
@@ -168,7 +167,7 @@ bool IndexAlgorithm1::computeValues(
 
             // Attempt to sample the result history at this timestamp ...
             int targetPos = -1;
-            if (rhInfo->getSmoothPos(evalTimestamps_.at(i), medianWinSize, &targetPos)) {
+            if (rhInfo->findSmoothPos(evalTimestamps_.at(i), &targetPos)) {
 
                 const qreal targetVal = rhInfo->value(targetPos);
 
diff --git a/src/bm/index.h b/src/bm/index.h
index a181a7f..f07e4f0 100644
--- a/src/bm/index.h
+++ b/src/bm/index.h
@@ -33,7 +33,7 @@ class Index {
 public:
     Index(
         const QList<ResultHistoryInfo *> &candidateRHInfos, const int baseTimestamp,
-        int medianWinSize, QList<int> *evalTimestamps, int *rejectedNonPositive = 0);
+        QList<int> *evalTimestamps, int *rejectedNonPositive = 0);
     virtual ~Index();
 
     bool isValid() const { return valid; }
@@ -67,7 +67,6 @@ protected:
     QList<ResultHistoryInfo *> rhInfos;
     int baseTimestamp;
     QList<int> evalTimestamps_;
-    int medianWinSize;
 
 private:
     bool valid;
@@ -83,8 +82,8 @@ class IndexAlgorithm1 : public Index {
 public:
     IndexAlgorithm1(
         const QList<ResultHistoryInfo *> &candidateRHInfos, const int baseTimestamp,
-        int medianWinSize, QList<int> *evalTimestamps, int *rejectedNonPositive = 0)
-        : Index(candidateRHInfos, baseTimestamp, medianWinSize, evalTimestamps, rejectedNonPositive)
+        QList<int> *evalTimestamps, int *rejectedNonPositive = 0)
+        : Index(candidateRHInfos, baseTimestamp, evalTimestamps, rejectedNonPositive)
     {}
 
     bool computeValues(
diff --git a/src/bm/resulthistoryinfo.cpp b/src/bm/resulthistoryinfo.cpp
index 7bd23ce..be5b571 100644
--- a/src/bm/resulthistoryinfo.cpp
+++ b/src/bm/resulthistoryinfo.cpp
@@ -24,120 +24,27 @@
 #include "resulthistoryinfo.h"
 #include "bmmisc.h"
 
-// ### 2 B DOCUMENTED!
-bool ResultHistoryInfo::findTargetPos(
-    int timestamp, int medianWinSize, int *pos, qreal *distSum) const
-{
-    int pos_ = -1;
-
-    // Find target position ...
-    QList<int>::const_iterator it = qLowerBound(timestamps_.begin(), timestamps_.end(), timestamp);
-    if (it == timestamps_.begin()) {
-        Q_ASSERT(timestamp <= timestamps_.first());
-        if (timestamp == timestamps_.first())
-            pos_ = 0;
-    } else if (it == timestamps_.end()) {
-        Q_ASSERT(timestamp > timestamps_.last());
-        pos_ = timestamps_.size() - 1;
-    } else {
-        Q_ASSERT(timestamp > *(it - 1));
-        pos_ = (it - 1) - timestamps_.begin();
-    }
-    Q_ASSERT(pos_ >= -1);
-    Q_ASSERT(pos_ < timestamps_.size());
-
-    // Return true iff the target position is high enough to accommodate a right-aligned window
-    // (i.e. a window in which the target value is the rightmost value) ...
-    if ((pos_ + 1) >= medianWinSize) {
-        if (pos)
-            *pos = pos_;
-
-        if (distSum) {
-            // Compute sum of distances to the contributing values ...
-            *distSum = 0.0;
-            for (int i = (pos_ - medianWinSize) + 1; i <= pos_; ++i) {
-                Q_ASSERT(timestamps_.at(i) <= timestamp);
-                (*distSum) += static_cast<qreal>((timestamp - timestamps_.at(i)));
-            }
-        }
-
-        return true;
-    }
-
-    return false;
-}
-
-// Returns true iff at least \a medianWinSize values exist at or before
-// \a timestamp. Passes the zero-based position of the smoothed value (if found) in \a smoothPos.
-// If \a cache is true, the previously cached position will be replaced (or initially recorded).
-// (Note that the cache capacity is 1, which explains why the \a cache argument needs to be
-// passed; only the client knows which timestamp is likely to be requested multiple times!)
-// If \a distSum is non-null, it will be set to the sum of the distances between \a timestamp
-// and the timestamp of each contributing value.
-bool ResultHistoryInfo::getSmoothPos(
-    int timestamp, int medianWinSize, int *smoothPos, bool cache, qreal *distSum) const
+// Searches for the (zero-based) position of the last non-outlier value at or
+// before \a timestamp. If found, the position is passed in \a pos and the function returns
+// true. Otherwise, the function returns false.
+bool ResultHistoryInfo::findSmoothPos(int timestamp, int *pos) const
 {
-    Q_ASSERT(timestamp >= 0);
-    Q_ASSERT(medianWinSize > 0);
+    if (!outliersMarked)
+        markOutliers();
 
-    if (medianWinSize > timestamps_.size())
-        return false;
+    // Locate initial candidate position ...
+    QList<int>::const_iterator begin =
+        qLowerBound(timestamps_.begin(), timestamps_.end(), timestamp);
+    QList<int>::const_iterator end = qUpperBound(begin, timestamps_.end(), timestamp);
+    int i = (end - 1) - timestamps_.begin();
 
-    // Return cached position if possible ...
-    if (timestamp == cachedTimestamp) {
-        *smoothPos = cachedSmoothPos;
-        return true;
-    }
+    // Skip outliers ...
+    while ((i >= 0) && (outliers.testBit(i))) --i;
 
-    // Find a valid target position if possible ...
-    int pos = -1;
-    if (!findTargetPos(timestamp, medianWinSize, &pos, distSum)) {
-        if (cache)
-            cachedTimestamp = -1; // Invalidate cache
+    if (i == -1)
         return false;
-    }
-
-    // Compute value ...
-    const int lo = (pos - medianWinSize) + 1;
-    *smoothPos = lo + BMMisc::medianPos(values.mid(lo, medianWinSize));
-
-    if (cache) {
-        // Load cache ...
-        cachedSmoothPos = *smoothPos;
-        cachedTimestamp = timestamp;
-    }
-
-    return true;
-}
-
-// ### 2 B DOCUMENTED!
-bool ResultHistoryInfo::getSmoothValues(int medianWinSize, QList<qreal> *smoothValues) const
-{
-    Q_ASSERT(medianWinSize > 0);
-    Q_ASSERT(timestamps_.size() == values.size());
-    Q_ASSERT(smoothValues);
-
-    if (timestamps_.isEmpty())
-        return false;
-
-    smoothValues->clear();
-
-    for (int pos = 0; pos < timestamps_.size(); ++pos) {
-        int lo = pos;
-        int hi = pos;
-        while (true) {
-            Q_ASSERT((hi - lo) + 1 <= medianWinSize);
-            if ((hi - lo) + 1 == medianWinSize) break;
-            lo = qMax(lo - 1, 0);
-            if ((hi - lo) + 1 == medianWinSize) break;
-            hi = qMin(hi + 1, values.size() - 1);
-            if ((hi - lo) + 1 == medianWinSize) break;
-        }
-
-        const qreal smoothValue = BMMisc::median(values.mid(lo, (hi - lo) + 1));
-        smoothValues->append(smoothValue);
-    }
 
+    *pos = i;
     return true;
 }
 
@@ -166,3 +73,22 @@ qreal ResultHistoryInfo::maxValue() const
 
     return cachedMaxVal;
 }
+
+// ### 2 B DOCUMENTED!
+void ResultHistoryInfo::markOutliers() const
+{
+    // Initially mark all values as outliers ...
+    const bool ok = outliers.fill(true, values.size());
+    Q_ASSERT(ok); // hm ... can this really fail in this case?
+
+    // Slide the median window across the list of values and mark
+    // the median positions as non-outliers ...
+    Q_ASSERT(medianWinSize > 0);
+    const int lastPos = values.size() - medianWinSize;
+    for (int pos = 0; pos <= lastPos; ++pos) {
+        const int medianPos = pos + BMMisc::medianPos(values.mid(pos, medianWinSize));
+        outliers.clearBit(medianPos);
+    }
+
+    outliersMarked = true;
+}
diff --git a/src/bm/resulthistoryinfo.h b/src/bm/resulthistoryinfo.h
index ae57cd7..3da942a 100644
--- a/src/bm/resulthistoryinfo.h
+++ b/src/bm/resulthistoryinfo.h
@@ -26,20 +26,20 @@
 
 #include <QString>
 #include <QList>
+#include <QBitArray>
 
 class ResultHistoryInfo {
 public:
     ResultHistoryInfo(
         const int bmcontextId, const QList<int> &timestamps_, const QList<qreal> &values,
-        const QString &metric, const QString &platform = QString(), const QString &host = QString(),
-        const QString &gitRepo = QString(), const QString &gitBranch = QString(),
-        const QString &testCase = QString(), const QString &testFunction = QString(),
-        const QString &dataTag = QString())
+        const int medianWinSize, const QString &metric, const QString &platform = QString(),
+        const QString &host = QString(), const QString &gitRepo = QString(),
+        const QString &gitBranch = QString(), const QString &testCase = QString(),
+        const QString &testFunction = QString(), const QString &dataTag = QString())
         : bmcontextId_(bmcontextId), timestamps_(timestamps_), values(values)
-        , metric_(metric), platform_(platform), host_(host), gitRepo_(gitRepo)
-        , gitBranch_(gitBranch), testCase_(testCase), testFunction_(testFunction)
-        , dataTag_(dataTag), cachedTimestamp(-1), cachedSmoothPos(-1), hasCachedMinVal(false)
-        , hasCachedMaxVal(false)
+        , medianWinSize(medianWinSize), metric_(metric), platform_(platform), host_(host)
+        , gitRepo_(gitRepo), gitBranch_(gitBranch), testCase_(testCase), testFunction_(testFunction)
+        , dataTag_(dataTag), hasCachedMinVal(false), hasCachedMaxVal(false), outliersMarked(false)
     {
         Q_ASSERT(!timestamps_.isEmpty());
         Q_ASSERT(timestamps_.size() == values.size());
@@ -48,11 +48,8 @@ public:
         }
     }
 
-    bool getSmoothPos(
-        int timestamp, int medianWinSize, int *smoothPos, bool cache = false,
-        qreal *distSum = 0) const;
+    bool findSmoothPos(int timestamp, int *pos) const;
 
-    bool getSmoothValues(int medianWinSize, QList<qreal> *smoothValues) const;
     QList<int> timestamps() const { return timestamps_; };
     int size() const { return timestamps_.size(); }
     qreal timestamp(int i) const { return static_cast<qreal>(timestamps_.at(i)); }
@@ -70,12 +67,12 @@ public:
     QString testFunction() const { return testFunction_; }
     QString dataTag() const { return dataTag_; }
 
-    bool findTargetPos(int timestamp, int medianWinSize, int *pos = 0, qreal *distSum = 0) const;
-
 private:
     int bmcontextId_;
     QList<int> timestamps_;
     QList<qreal> values;
+    int medianWinSize;
+
     QString metric_;
     QString platform_;
     QString host_;
@@ -84,12 +81,15 @@ private:
     QString testCase_;
     QString testFunction_;
     QString dataTag_;
-    mutable bool cachedTimestamp;
-    mutable qreal cachedSmoothPos;
+
     mutable bool hasCachedMinVal;
     mutable bool hasCachedMaxVal;
     mutable qreal cachedMinVal;
     mutable qreal cachedMaxVal;
+
+    mutable bool outliersMarked;
+    mutable QBitArray outliers;
+    void markOutliers() const;
 };
 
 #endif // RESULTHISTORYINFO_H