path: root/src/bm/index.cpp

/****************************************************************************
**
** 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;
}