timestampobjectlist.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (C) 2015 swift Project Community / Contributors
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-swift-pilot-client-1
 
 
#ifndef SWIFT_MISC_TIMESTAMPOBJECTLIST_H
#define SWIFT_MISC_TIMESTAMPOBJECTLIST_H
 
#include <algorithm>
 
#include <QtGlobal>
 
#include "config/buildconfig.h"
#include "misc/predicates.h"
#include "misc/swiftmiscexport.h"
#include "misc/timestampbased.h"
#include "misc/verify.h"
 
class QDateTime;
 
namespace swift::misc
{
    struct MillisecondsMinMaxMean
    {
        qint64 min; 
        qint64 max; 
        double mean; 
 
        bool isValid() const { return min >= 0 && max >= 0; }
 
        void reset()
        {
            min = -1;
            max = -1;
            mean = -1;
        }
 
        QString asString() const
        {
            return QStringLiteral("Min: %1ms Max: %2ms Mean: %3ms").arg(min).arg(max).arg(mean, 0, 'f', 2);
        }
    };
 
    template <class OBJ, class CONTAINER>
    class ITimestampObjectList
    {
        static_assert(std::is_base_of_v<ITimestampBased, OBJ>, "OBJ needs to implement ITimestampBased");
 
    public:
        enum HintTimestampSort
        {
            NoTimestampSortHint,
            TimestampLatestFirst,
            TimestampLatestLast
        };
 
        CONTAINER findBefore(const QDateTime &dateTime) const { return this->findBefore(dateTime.toMSecsSinceEpoch()); }
 
        CONTAINER findBefore(qint64 msSinceEpoch) const
        {
            return this->container().findBy([&](const OBJ &obj) { return obj.isOlderThan(msSinceEpoch); });
        }
 
        OBJ findObjectBeforeOrDefault(qint64 msSinceEpoch) const
        {
            const CONTAINER before = this->findBefore(msSinceEpoch);
            if (before.isEmpty()) { return OBJ(); }
            return before.latestObject();
        }
 
        CONTAINER findBeforeAndRemove(qint64 msSinceEpoch)
        {
            CONTAINER result(findBefore(msSinceEpoch));
            this->removeBefore(msSinceEpoch);
            return result;
        }
 
        CONTAINER findBeforeNowMinusOffset(qint64 msOffset) const
        {
            return this->findBefore(QDateTime::currentMSecsSinceEpoch() - msOffset);
        }
 
        CONTAINER findAfter(const QDateTime &dateTime) const { return this->findAfter(dateTime.toMSecsSinceEpoch()); }
 
        CONTAINER findAfter(qint64 msSinceEpoch) const
        {
            return this->container().findBy([&](const OBJ &obj) { return obj.isNewerThan(msSinceEpoch); });
        }
 
        CONTAINER findAfterNowMinusOffset(qint64 msOffset) const
        {
            return this->findAfter(QDateTime::currentMSecsSinceEpoch() - msOffset);
        }
 
        OBJ findObjectAfterOrDefault(qint64 msSinceEpoch) const
        {
            const CONTAINER after = this->findAfter(msSinceEpoch);
            if (after.isEmpty()) { return OBJ(); }
            return after.oldestObject();
        }
 
        CONTAINER findInvalidTimestamps() const
        {
            return this->container().findBy([&](const OBJ &obj) { return !obj.hasValidTimestamp(); });
        }
 
        OBJ findClosestTimeDistance(qint64 msSinceEpoch) const
        {
            if (this->container().isEmpty()) { return OBJ(); }
            const auto closest = std::min_element(this->container().cbegin(), this->container().cend(),
                                                  [=](const ITimestampBased &a, const ITimestampBased &b) {
                                                      return qAbs(a.getTimeDifferenceMs(msSinceEpoch)) <
                                                             qAbs(b.getTimeDifferenceMs(msSinceEpoch));
                                                  });
            return *closest;
        }
 
        bool hasInvalidTimestamps() const { return this->container().contains(&OBJ::hasValidTimestamp, false); }
 
        void setCurrentUtcTime()
        {
            for (ITimestampBased &tsObj : this->container()) { tsObj.setCurrentUtcTime(); }
        }
 
        void setUtcTime(qint64 msSinceEpoch)
        {
            for (ITimestampBased &tsObj : this->container()) { tsObj.setMSecsSinceEpoch(msSinceEpoch); }
        }
 
        void setInvalidTimestampsToCurrentUtcTime()
        {
            for (ITimestampBased &tsObj : this->container())
            {
                if (tsObj.hasValidTimestamp()) { continue; }
                tsObj.setCurrentUtcTime();
            }
        }
 
        QDateTime latestTimestamp() const
        {
            if (this->container().isEmpty()) { return {}; }
            return this->latestObject().getUtcTimestamp();
        }
 
        qint64 latestTimestampMsecsSinceEpoch() const
        {
            const QDateTime dt(latestTimestamp());
            return dt.isValid() ? dt.toMSecsSinceEpoch() : -1;
        }
 
        QDateTime oldestTimestamp() const
        {
            if (this->container().isEmpty()) { return {}; }
            return this->oldestObject().getUtcTimestamp();
        }
 
        qint64 oldestTimestampMsecsSinceEpoch() const
        {
            const QDateTime dt(oldestTimestamp());
            return dt.isValid() ? dt.toMSecsSinceEpoch() : -1;
        }
 
        OBJ latestObject() const
        {
            if (this->container().isEmpty()) { return OBJ(); }
            const auto latest =
                std::max_element(this->container().begin(), this->container().end(), [](const OBJ &a, const OBJ &b) {
                    return a.getMSecsSinceEpoch() < b.getMSecsSinceEpoch();
                });
            return *latest;
        }
 
        OBJ oldestObject() const
        {
            if (this->container().isEmpty()) { return OBJ(); }
            const auto oldest =
                std::min_element(this->container().begin(), this->container().end(), [](const OBJ &a, const OBJ &b) {
                    return a.getMSecsSinceEpoch() < b.getMSecsSinceEpoch();
                });
            return *oldest;
        }
 
        int removeBefore(const QDateTime &dateTime) { return this->removeBefore(dateTime.toMSecsSinceEpoch()); }
 
        int removeBefore(qint64 msSinceEpoch)
        {
            return this->container().removeIf([&](const OBJ &obj) { return obj.isOlderThan(msSinceEpoch); });
        }
 
        int removeOlderThanNowMinusOffset(qint64 offsetMs)
        {
            const qint64 epoch = QDateTime::currentMSecsSinceEpoch() - offsetMs;
            return this->container().removeIf([&](const OBJ &obj) { return obj.isOlderThan(epoch); });
        }
 
        void sortLatestFirst()
        {
            this->container().sortOldestFirst();
            this->container().reverse();
        }
 
        void sortOldestFirst() { this->container().sort(predicates::MemberLess(&OBJ::getMSecsSinceEpoch)); }
 
        void push_frontKeepLatestFirst(const OBJ &value, bool replaceSameTimestamp = true, int maxElements = -1)
        {
            Q_ASSERT_X(maxElements < 0 || maxElements > 1, Q_FUNC_INFO, "Max.value wrong range");
            CONTAINER &c = this->container();
            if (replaceSameTimestamp && !c.isEmpty() && c[0].getMSecsSinceEpoch() == value.getMSecsSinceEpoch())
            {
                c[0] = value;
                if (maxElements > 0) { c.truncate(maxElements); }
            }
            else
            {
                if (maxElements > 0) { c.truncate(maxElements - 1); }
                const bool needSort = !c.isEmpty() && value.isOlderThan(c.front());
                c.push_front(value);
                if (needSort) { ITimestampObjectList::sortLatestFirst(); }
            }
 
            // crosscheck
            if (swift::config::CBuildConfig::isLocalDeveloperDebugBuild())
            {
                Q_ASSERT_X(this->isSortedLatestFirst(), Q_FUNC_INFO, "Wrong sort order");
            }
        }
 
        void push_backIncreaseTimestamp(const OBJ &newObject)
        {
            if (this->container().isEmpty())
            {
                this->container().push_back(newObject);
                return;
            }
            const qint64 newMs = newObject.getMSecsSinceEpoch();
            const qint64 oldMs = this->container().back().getMSecsSinceEpoch();
            if (newMs > oldMs)
            {
                this->container().push_back(newObject);
                return;
            }
            this->push_backOverrideTimestamp(newObject, oldMs + 1);
        }
 
        void push_backOverrideTimestamp(const OBJ &newObject, qint64 newTsMsSinceEpoch)
        {
            OBJ newObjectCopy(newObject);
            newObjectCopy.setMSecsSinceEpoch(newTsMsSinceEpoch);
            this->container().push_back(newObjectCopy);
        }
 
        void setNewTimestampStartingLast(qint64 startTimeStampMs, qint64 deltaTimeMs)
        {
            if (this->container().isEmpty()) { return; }
            qint64 currentMs = startTimeStampMs;
            for (auto it = this->container().rbegin(); it != this->container().rend(); ++it)
            {
                it->setMSecsSinceEpoch(currentMs);
                currentMs += deltaTimeMs;
            }
        }
 
        int replaceIfSameTimestamp(const OBJ &newObject)
        {
            int c = 0;
            for (OBJ &obj : this->container())
            {
                if (obj.getMSecsSinceEpoch() == newObject.getMSecsSinceEpoch())
                {
                    obj = newObject;
                    c++;
                }
            }
            return c;
        }
 
        bool isSortedLatestLast() const
        {
            if (this->container().size() < 2) { return true; }
            qint64 max = -1;
            for (const ITimestampBased &obj : this->container())
            {
                if (!obj.hasValidTimestamp()) { return false; }
                if (obj.getMSecsSinceEpoch() < max) { return false; }
                max = obj.getMSecsSinceEpoch();
            }
            return true;
        }
 
        bool isSortedLatestFirst() const
        {
            if (this->container().size() < 2) { return true; }
            qint64 min = std::numeric_limits<qint64>::max();
            for (const ITimestampBased &obj : this->container())
            {
                if (!obj.hasValidTimestamp()) { return false; }
                if (obj.getMSecsSinceEpoch() > min) { return false; }
                min = obj.getMSecsSinceEpoch();
            }
            return true;
        }
 
        void addMsecs(qint64 msToAdd)
        {
            if (msToAdd == 0) { return; }
            for (ITimestampBased &obj : this->container()) { obj.addMsecs(msToAdd); }
        }
 
        void setSortHint(HintTimestampSort hint) { m_tsSortHint = hint; }
 
        MillisecondsMinMaxMean getTimestampDifferenceMinMaxMean() const
        {
            MillisecondsMinMaxMean mmm;
            mmm.reset();
            const CONTAINER &container = this->container();
            if (container.size() < 2) { return mmm; }
 
            // Do not confuse with adjusted sort hint!
            if (container.m_tsSortHint == NoTimestampSortHint)
            {
                CONTAINER copy(container);
                copy.sortLatestFirst();
                copy.m_tsSortHint = TimestampLatestFirst;
                return copy.getTimestampDifferenceMinMaxMean();
            }
 
            mmm.max = std::numeric_limits<qint64>::min();
            mmm.min = std::numeric_limits<qint64>::max();
            qint64 mean = 0;
            int c = 0;
            OBJ last;
 
            for (const OBJ &object : container)
            {
                if (c > 0)
                {
                    const ITimestampBased &l = last;
                    const ITimestampBased &o = object;
                    const qint64 diff = l.getAbsTimeDifferenceMs(o);
                    mmm.max = std::max(diff, mmm.max);
                    mmm.min = std::min(diff, mmm.min);
                    mean += diff;
                }
                c++;
                last = object;
            }
 
            mmm.mean = mean / c;
            return mmm;
        }
 
    protected:
        ITimestampObjectList() = default;
 
        const CONTAINER &container() const { return static_cast<const CONTAINER &>(*this); }
 
        CONTAINER &container() { return static_cast<CONTAINER &>(*this); }
 
        HintTimestampSort m_tsSortHint = NoTimestampSortHint; 
    };
 
    template <class OBJ, class CONTAINER>
    class ITimestampWithOffsetObjectList : public ITimestampObjectList<OBJ, CONTAINER>
    {
        static_assert(std::is_base_of_v<ITimestampWithOffsetBased, OBJ>, "OBJ needs to implement ITimestampBased");
 
    public:
        enum HintAdjustedTimestampSort
        {
            NoAdjustedTimestampSortHint,
            AdjustedTimestampLatestFirst
        };
 
        void sortAdjustedLatestFirst()
        {
            this->container().sortAdjustedOldestFirst();
            this->container().reverse();
        }
 
        CONTAINER getSortedAdjustedLatestFirst() const
        {
            CONTAINER copy(this->container());
            copy.sortAdjustedLatestFirst();
            return copy;
        }
 
        CONTAINER getLatestAdjustedTwoObjects(bool alreadySortedLatestFirst = false) const
        {
            if (this->container().size() < 2) { return CONTAINER(); }
            CONTAINER copy(alreadySortedLatestFirst ? this->container() :
                                                      this->container().getSortedAdjustedLatestFirst());
            copy.truncate(2);
            return copy;
        }
 
        void sortAdjustedOldestFirst()
        {
            this->container().sort(predicates::MemberLess(&OBJ::getAdjustedMSecsSinceEpoch));
        }
 
        bool containsZeroOrNegativeOffsetTime() const
        {
            return std::any_of(this->container().begin(), this->container().end(),
                               [](const ITimestampWithOffsetBased &obj) { return obj.getTimeOffsetMs() <= 0; });
        }
 
        bool containsNegativeOffsetTime() const
        {
            return std::any_of(this->container().begin(), this->container().end(),
                               [](const ITimestampWithOffsetBased &obj) { return obj.getTimeOffsetMs() < 0; });
        }
 
        void addMsecsToOffset(qint64 msToAdd)
        {
            for (ITimestampWithOffsetBased &obj : this->container()) { obj.addMsecsToOffsetTime(msToAdd); }
        }
 
        void push_frontKeepLatestAdjustedFirst(const OBJ &value, bool replaceSameTimestamp = true, int maxElements = -1)
        {
            Q_ASSERT_X(maxElements < 0 || maxElements > 1, Q_FUNC_INFO, "Max.value wrong range");
            CONTAINER &c = this->container();
            if (replaceSameTimestamp && !c.isEmpty() && c[0].getMSecsSinceEpoch() == value.getMSecsSinceEpoch())
            {
                c[0] = value;
                if (maxElements > 0) { c.truncate(maxElements); }
                return;
            }
 
            if (maxElements > 0) { c.truncate(maxElements - 1); }
            const bool needSort = !c.isEmpty() && value.isOlderThanAdjusted(c.front());
            c.push_front(value);
            if (needSort) { ITimestampWithOffsetObjectList::sortAdjustedLatestFirst(); }
        }
 
        void push_frontKeepLatestFirstAdjustOffset(const OBJ &value, bool replaceSameTimestamp = true,
                                                   int maxElements = -1)
        {
            ITimestampWithOffsetObjectList<OBJ, CONTAINER>::push_frontKeepLatestFirst(value, replaceSameTimestamp,
                                                                                      maxElements);
 
            // now sorted by timestamp
            // this reflects normally the incoming order
            // ts
            //  8: os 2 adj 12 => min os 4
            //  6: os 2 adj 11 => min os 5
            //  5: os 5 adj 10
            //  0: os 5 adj  5
            CONTAINER &c = this->container();
            if (c.size() < 2) { return; }
            ITimestampWithOffsetBased &front = c.front();
            const ITimestampWithOffsetBased &second = c[1];
            if (!front.isNewerThanAdjusted(second))
            {
                // const qint64 minOs = qMin(front.getTimeOffsetMs(), second.getTimeOffsetMs());
                const qint64 minReqOs =
                    second.getAdjustedMSecsSinceEpoch() - front.getMSecsSinceEpoch(); // minimal required
                const qint64 avgOs = (front.getTimeOffsetMs() + second.getTimeOffsetMs()) / 2;
                const qint64 os = qMax(minReqOs + 1, avgOs); // at least +1, as value must be > (greater)
                front.setTimeOffsetMs(os);
            }
 
            if (swift::config::CBuildConfig::isLocalDeveloperDebugBuild())
            {
                SWIFT_VERIFY_X(front.isNewerThanAdjusted(second), Q_FUNC_INFO, "Front/second timestamp");
                SWIFT_VERIFY_X(this->isSortedAdjustedLatestFirst(), Q_FUNC_INFO, "Wrong sort order");
            }
        }
 
        void push_frontKeepLatestFirstIgnoreOverlapping(const OBJ &value, bool replaceSameTimestamp = true,
                                                        int maxElements = -1)
        {
            CONTAINER &c = this->container();
            if (c.size() > 1)
            {
                const ITimestampWithOffsetBased front = c.front();
                if (value.getAdjustedMSecsSinceEpoch() <= front.getAdjustedMSecsSinceEpoch()) { return; }
            }
            ITimestampWithOffsetObjectList<OBJ, CONTAINER>::push_frontKeepLatestFirst(value, replaceSameTimestamp,
                                                                                      maxElements);
        }
 
        void prefillLatestAdjustedFirst(const OBJ &value, int elements, qint64 deltaTimeMs = -1)
        {
            this->container().clear();
            const qint64 osTime = value.getTimeOffsetMs();
            const qint64 os = -1 * qAbs(deltaTimeMs < 0 ? osTime : deltaTimeMs);
            if (swift::config::CBuildConfig::isLocalDeveloperDebugBuild())
            {
                SWIFT_VERIFY_X(os < 0, Q_FUNC_INFO, "Need negative offset time to prefill time");
            }
            this->container().push_front(value);
            for (int i = 1; i < elements; i++)
            {
                OBJ copy(value);
                copy.addMsecs(os * i);
                this->container().push_back(copy);
            }
            this->setAdjustedSortHint(ITimestampWithOffsetObjectList::AdjustedTimestampLatestFirst);
        }
 
        bool isSortedAdjustedLatestLast() const
        {
            if (this->container().isEmpty()) { return false; }
            if (this->container().size() < 2) { return true; }
            qint64 max = -1;
            for (const ITimestampWithOffsetBased &obj : this->container())
            {
                if (!obj.hasValidTimestamp()) { return false; }
                if (obj.getAdjustedMSecsSinceEpoch() < max) { return false; }
                max = obj.getAdjustedMSecsSinceEpoch();
            }
            return true;
        }
 
        bool isSortedAdjustedLatestFirst() const
        {
            if (this->container().size() < 2) { return true; }
            qint64 min = std::numeric_limits<qint64>::max();
            for (const ITimestampWithOffsetBased &obj : this->container())
            {
                if (!obj.hasValidTimestamp()) { return false; }
                if (obj.getAdjustedMSecsSinceEpoch() > min) { return false; }
                min = obj.getAdjustedMSecsSinceEpoch();
            }
            return true;
        }
 
        CONTAINER findAfterAdjusted(qint64 msSinceEpoch) const
        {
            return this->container().findBy(
                [&](const ITimestampWithOffsetBased &obj) { return obj.isNewerThanAdjusted(msSinceEpoch); });
        }
 
        OBJ findObjectAfterAdjustedOrDefault(qint64 msSinceEpoch) const
        {
            const CONTAINER after = this->findAfterAdjusted(msSinceEpoch);
            if (after.isEmpty()) { return OBJ(); }
            return after.oldestAdjustedObject();
        }
 
        CONTAINER findBeforeAdjusted(qint64 msSinceEpoch) const
        {
            return this->container().findBy(
                [&](const ITimestampWithOffsetBased &obj) { return obj.isOlderThanAdjusted(msSinceEpoch); });
        }
 
        OBJ findObjectBeforeAdjustedOrDefault(qint64 msSinceEpoch) const
        {
            const CONTAINER before = this->findBeforeAdjusted(msSinceEpoch);
            if (before.isEmpty()) { return OBJ(); }
            return before.latestAdjustedObject();
        }
 
        OBJ findClosestTimeDistanceAdjusted(qint64 msSinceEpoch) const
        {
            if (this->container().isEmpty()) { return OBJ(); }
            const auto closest =
                std::min_element(this->container().cbegin(), this->container().cend(),
                                 [=](const ITimestampWithOffsetBased &a, const ITimestampWithOffsetBased &b) {
                                     return qAbs(a.getAdjustedTimeDifferenceMs(msSinceEpoch)) <
                                            qAbs(b.getAdjustedTimeDifferenceMs(msSinceEpoch));
                                 });
            return *closest;
        }
 
        OBJ latestAdjustedObject() const
        {
            if (this->container().isEmpty()) { return OBJ(); }
            if (this->container().m_tsAdjustedSortHint == AdjustedTimestampLatestFirst)
            {
                return this->container().front();
            }
            const auto latest =
                std::max_element(this->container().begin(), this->container().end(), [](const OBJ &a, const OBJ &b) {
                    return a.getAdjustedMSecsSinceEpoch() < b.getAdjustedMSecsSinceEpoch();
                });
            return *latest;
        }
 
        OBJ oldestAdjustedObject() const
        {
            if (this->container().isEmpty()) { return OBJ(); }
            if (this->container().m_tsAdjustedSortHint == AdjustedTimestampLatestFirst)
            {
                return this->container().back();
            }
            const auto oldest =
                std::min_element(this->container().begin(), this->container().end(), [](const OBJ &a, const OBJ &b) {
                    return a.getAdjustedMSecsSinceEpoch() < b.getAdjustedMSecsSinceEpoch();
                });
            return *oldest;
        }
 
        QDateTime latestAdjustedTimestamp() const
        {
            if (this->container().isEmpty()) { return {}; }
            return this->latestAdjustedObject().getUtcTimestamp();
        }
 
        QDateTime oldestAdjustedTimestamp() const
        {
            if (this->container().isEmpty()) { return {}; }
            return this->oldestAdjustedObject().getUtcTimestamp();
        }
 
        qint64 latestAdjustedTimestampMsecsSinceEpoch() const
        {
            if (this->container().isEmpty()) { return -1; }
            const QDateTime dt(this->latestAdjustedTimestamp());
            return dt.isValid() ? dt.toMSecsSinceEpoch() : -1;
        }
 
        qint64 oldestAdjustedTimestampMsecsSinceEpoch() const
        {
            if (this->container().isEmpty()) { return -1; }
            const QDateTime dt(oldestAdjustedTimestamp());
            return dt.isValid() ? dt.toMSecsSinceEpoch() : -1;
        }
 
        void setAdjustedSortHint(HintAdjustedTimestampSort hint) { this->container().m_tsAdjustedSortHint = hint; }
 
        MillisecondsMinMaxMean getOffsetMinMaxMean() const
        {
            MillisecondsMinMaxMean mmm;
            mmm.reset();
            const CONTAINER &container = this->container();
            if (container.size() < 1) { return mmm; }
 
            mmm.max = std::numeric_limits<qint64>::min();
            mmm.min = std::numeric_limits<qint64>::max();
            qint64 mean = 0;
            int c = 0;
 
            for (const ITimestampWithOffsetBased &object : container)
            {
                if (!object.hasNonZeroOffsetTime()) { continue; }
                const qint64 os = object.getTimeOffsetMs();
                mmm.max = std::max(os, mmm.max);
                mmm.min = std::min(os, mmm.min);
                mean += os;
                c++;
            }
 
            if (c > 0) { mmm.mean = mean / c; }
            return mmm;
        }
 
    protected:
        ITimestampWithOffsetObjectList() = default;
 
        HintAdjustedTimestampSort m_tsAdjustedSortHint = NoAdjustedTimestampSortHint; 
    };
} // namespace swift::misc
 
#endif // SWIFT_MISC_TIMESTAMPOBJECTLIST_H