diff options
Diffstat (limited to 'src/bm/index.cpp')
| -rw-r--r-- | src/bm/index.cpp | 288 |
1 files changed, 288 insertions, 0 deletions
diff --git a/src/bm/index.cpp b/src/bm/index.cpp new file mode 100644 index 0000000..4e1cbd1 --- /dev/null +++ b/src/bm/index.cpp @@ -0,0 +1,288 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the BM project on Qt Labs. +** +** This file may be used under the terms of the GNU General Public +** License version 2.0 or 3.0 as published by the Free Software Foundation +** and appearing in the file LICENSE.GPL included in the packaging of +** this file. Please review the following information to ensure GNU +** General Public Licensing requirements will be met: +** http://www.fsf.org/licensing/licenses/info/GPLv2.html and +** http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** +** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +** +****************************************************************************/ + +#include "index.h" +#include "resulthistoryinfo.h" +#include "bmmisc.h" +#include <QBitArray> +#include <QDebug> + + +// ### 2 B DOCUMENTED! +// Note: The dynamic memory in \a candidateRHInfos is deleted by this class. +Index::Index( + const QList<ResultHistoryInfo *> &candidateRHInfos, const int baseTimestamp, + const QList<int> &evalTimestamps, int medianWinSize, int *rejectedNonPositive) + : baseTimestamp(baseTimestamp), evalTimestamps(evalTimestamps) + , medianWinSize(medianWinSize), valid(false), invalidReason_("uninitialized") +{ + init(candidateRHInfos, rejectedNonPositive); +} + +Index::~Index() +{ + // Free dynamic memory ... + for (int i = 0; i < rhInfos.size(); ++i) + delete rhInfos.at(i); +} + +// ### 2 B DOCUMENTED! +void Index::init(const QList<ResultHistoryInfo *> &candidateRHInfos, int *rejectedNonPositive) +{ + if (baseTimestamp < 0) { + valid = false; + invalidReason_ = "negative base timestamp"; + return; + } + + for (int i = 1; i < evalTimestamps.size(); ++i) { + if (evalTimestamps.at(i - 1) > evalTimestamps.at(i)) { + valid = false; + invalidReason_ = "non-increasing eval timestamp order"; + return; + } + } + + if (evalTimestamps.first() < 0) { + valid = false; + invalidReason_ = "negative eval timestamp"; + return; + } + + populateRHInfos(candidateRHInfos, rejectedNonPositive); + if (rhInfos.isEmpty()) { + valid = false; + invalidReason_ = "no valid result histories"; + return; + } + + valid = true; + invalidReason_ = ""; +} + +// Populates rhInfos from \a candidateRHInfos by rejecting certain result histories. +void Index::populateRHInfos( + const QList<ResultHistoryInfo *> &candidateRHInfos, int *rejectedNonPositive) +{ + int rejectedNonPositive_ = 0; + + for (int i = 0; i < candidateRHInfos.size(); ++i) { + + ResultHistoryInfo *rhInfo = candidateRHInfos.at(i); + Q_ASSERT(rhInfo->size() > 0); + + // Reject candidate if the time series contains at least one non-positive value ... + int j = 0; + for (; j < rhInfo->size(); ++j) { + if (rhInfo->value(j) <= 0.0) + break; + } + if (j < rhInfo->size()) { + delete rhInfo; + ++rejectedNonPositive_; + continue; + } + + // Accept candidate ... + rhInfos.append(rhInfo); + } + + if (rejectedNonPositive) + *rejectedNonPositive = rejectedNonPositive_; +} + + +//+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+= + +bool IndexAlgorithm1::computeValues( + QList<qreal> *values, int *baseValuePos, QList<int> *contrCounts, QString *error, + QList<QList<RankedInfo> > *topContr, int topContrLimit) const +{ + if (!isValid()) { + *error = invalidReason(); + return false; + } + + Q_ASSERT(rhInfos.size() > 0); + Q_ASSERT(values); + values->clear(); + Q_ASSERT(contrCounts); + contrCounts->clear(); + + QBitArray contr(rhInfos.size()); // Set of contributors (i.e. whether each result + // history is contributing at the current timestamp). + QBitArray hasBase(rhInfos.size()); // Whether a base value has been established for + // each result history. + QVector<int> basePos(rhInfos.size()); // Base value pos of each result history. + QVector<qreal> diffPrev(rhInfos.size()); // Previous base diff value of each result hist. + QVector<qreal> targetValPrev(rhInfos.size()); // Previous target value of each result history. + QVector<int> targetPosPrev(rhInfos.size()); // Previous target pos of each result history. + qreal hc = 0.0; // History constant to adjust for changes to the set of contributors. + + bool contr_prev_empty = true; + + *baseValuePos = -1; + + // Loop over evaluation timestamps ... + for (int i = 0; i < evalTimestamps.size(); ++i) { + + if (*baseValuePos == -1) { + // Determine if this evaluation timestamp represents the base timestamp ... + if (baseTimestamp < evalTimestamps.first()) { + *baseValuePos = 0; + } else if (((i < (evalTimestamps.size() - 1)) + && (baseTimestamp >= evalTimestamps.at(i)) + && (baseTimestamp < evalTimestamps.at(i + 1))) + || (i == (evalTimestamps.size() - 1))) + *baseValuePos = i; + } + + const QBitArray contr_prev = contr; + contr_prev_empty = (contr_prev.count(true) == 0); + + contr.fill(false); + + qreal dsum_all = 0.0; // Base diff sum of all contributors. + qreal dsum_existing = 0.0; // Base diff sum of all contributors that contributed at + // the previous evaluation timestamp as well. + + // Lists of most significant contributors ranked on BDC, where BDC is + // the base diff change between the current and the previous eval timestamp: + QList<QPair<RankedInfo, qreal> > rankedBest; // ... highest BDC + QList<QPair<RankedInfo, qreal> > rankedWorst; // ... lowest BDC + + // Loop over potential contributors ... + for (int j = 0; j < rhInfos.size(); ++j) { + + const ResultHistoryInfo *rhInfo = rhInfos.at(j); + + // Attempt to sample the result history at this timestamp ... + int targetPos = -1; + if (rhInfo->getSmoothPos(evalTimestamps.at(i), medianWinSize, &targetPos)) { + + const qreal targetVal = rhInfo->value(targetPos); + + if (hasBase.testBit(j)) { + + // Compute base diff and accumulate contribution ... + + const qreal baseVal = rhInfo->value(basePos.at(j)); + const qreal diff = BMMisc::log2diff(targetVal, baseVal, rhInfo->metric()); + + dsum_all += diff; + if (contr_prev.testBit(j)) + dsum_existing += diff; + + contr.setBit(j); + + const qreal diffChange = diff - diffPrev.at(j); + + const QString descr = + QString("base val: %1; val1: %2; val2: %3; abs log2 diff change: %4") + .arg(baseVal) + .arg(targetValPrev.at(j)) + .arg(targetVal) + .arg(qAbs(diffChange)); + RankedInfo rankedInfo( + rhInfo->bmcontextId(), basePos.at(j), targetPosPrev.at(j), targetPos, + descr); + + BMMisc::insertRankedId<RankedInfo>( + &rankedBest, topContrLimit, rankedInfo, diffChange); + BMMisc::insertRankedId<RankedInfo>( + &rankedWorst, topContrLimit, rankedInfo, -diffChange); + diffPrev.replace(j, diff); + + } else { + // Record base value position ... + basePos.replace(j, targetPos); + hasBase.setBit(j); + } + + targetValPrev.replace(j, targetVal); + targetPosPrev.replace(j, targetPos); + } + } + + contrCounts->append(contr.count(true)); // record contribution count + + qreal indexValue = -1.0; + + if (contr.count(true) > 0) { + // A base diff was computable for at least one contributor at this eval timestamp, + // so a valid index value may be derived ... + + const qreal dmean_all = dsum_all / contr.count(true); + + if (contr_prev.count(true) > 0) { + + // A base diff was computable for at least one contributor at the previous + // eval timestamp as well, so the set of contributors may potentially have + // been changed. + + // Compute the arithmetic mean of the existing contributors only (i.e. those + // who contributed both at this eval timestamp and the previous one) ... + const qreal dmean_existing = dsum_existing / contr_prev.count(true); + + // The index value should only be influenced by the existing contributors only ... + indexValue = dmean_existing - hc; + + if (contr != contr_prev) { + // The set of contributors changed, so adjust the history constant to ensure + // that the index value for the next eval timestamp is not influenced by the + // new contributors until their base diffs start to change ... + hc += (dmean_all - dmean_existing); + } + + } else { + + indexValue = dmean_all; // special initialization case + } + } + + values->append(indexValue); // record the raw index value (valid or not) + + if (topContr) { + + // Establish (if possible) a list of the most significant contributors ... + + QList<RankedInfo> tc; + + if ((i > 0) && (contrCounts->at(i) > 0) && (contrCounts->at(i - 1) > 0)) { + // The index value was computable for both this eval timestamp and the one + // preceding it, so rank wrt. high or low base diff change depending on whether + // the index value went up or down ... + QList<QPair<RankedInfo, qreal> > * ranked = + (values->at(i) > values->at(i - 1)) + ? &rankedBest // up + : &rankedWorst; // down + for (int j = 0; j < ranked->size(); ++j) + tc.append(ranked->at(j).first); + } + + topContr->append(tc); + } + } + + return true; +} |