1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/media/TimeVarying.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,237 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-*/
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this file,
1.7 + * You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#ifndef MOZILLA_TIMEVARYING_H_
1.10 +#define MOZILLA_TIMEVARYING_H_
1.11 +
1.12 +#include "nsTArray.h"
1.13 +
1.14 +namespace mozilla {
1.15 +
1.16 +/**
1.17 + * This is just for CTOR/DTOR tracking. We can't put this in
1.18 + * TimeVarying directly because the different template instances have
1.19 + * different sizes and that confuses things.
1.20 + */
1.21 +class TimeVaryingBase {
1.22 +protected:
1.23 + TimeVaryingBase()
1.24 + {
1.25 + MOZ_COUNT_CTOR(TimeVaryingBase);
1.26 + }
1.27 + ~TimeVaryingBase()
1.28 + {
1.29 + MOZ_COUNT_DTOR(TimeVaryingBase);
1.30 + }
1.31 +};
1.32 +
1.33 +/**
1.34 + * Objects of this class represent values that can change over time ---
1.35 + * a mathematical function of time.
1.36 + * Time is the type of time values, T is the value that changes over time.
1.37 + * There are a finite set of "change times"; at each change time, the function
1.38 + * instantly changes to a new value. ReservedChanges should be set to the
1.39 + * expected number of change events that the object is likely to contain.
1.40 + * This value should be 0 for all consumers unless you know that a higher value
1.41 + * would be a benefit.
1.42 + * There is also a "current time" which must always advance (not go backward).
1.43 + * The function is constant for all times less than the current time.
1.44 + * When the current time is advanced, the value of the function at the new
1.45 + * current time replaces the values for all previous times.
1.46 + *
1.47 + * The implementation records a mCurrent (the value at the current time)
1.48 + * and an array of "change times" (greater than the current time) and the
1.49 + * new value for each change time. This is a simple but dumb implementation.
1.50 + * We maintain the invariant that each change entry in the array must have
1.51 + * a different value to the value in the previous change entry (or, for
1.52 + * the first change entry, mCurrent).
1.53 + */
1.54 +template <typename Time, typename T, uint32_t ReservedChanges>
1.55 +class TimeVarying : public TimeVaryingBase {
1.56 +public:
1.57 + TimeVarying(const T& aInitial) : mCurrent(aInitial) {}
1.58 + /**
1.59 + * This constructor can only be called if mCurrent has a no-argument
1.60 + * constructor.
1.61 + */
1.62 + TimeVarying() : mCurrent() {}
1.63 +
1.64 + /**
1.65 + * Sets the value for all times >= aTime to aValue.
1.66 + */
1.67 + void SetAtAndAfter(Time aTime, const T& aValue)
1.68 + {
1.69 + for (int32_t i = mChanges.Length() - 1; i >= 0; --i) {
1.70 + NS_ASSERTION(i == int32_t(mChanges.Length() - 1),
1.71 + "Always considering last element of array");
1.72 + if (aTime > mChanges[i].mTime) {
1.73 + if (mChanges[i].mValue != aValue) {
1.74 + mChanges.AppendElement(Entry(aTime, aValue));
1.75 + }
1.76 + return;
1.77 + }
1.78 + if (aTime == mChanges[i].mTime) {
1.79 + if ((i > 0 ? mChanges[i - 1].mValue : mCurrent) == aValue) {
1.80 + mChanges.RemoveElementAt(i);
1.81 + return;
1.82 + }
1.83 + mChanges[i].mValue = aValue;
1.84 + return;
1.85 + }
1.86 + mChanges.RemoveElementAt(i);
1.87 + }
1.88 + if (mCurrent == aValue) {
1.89 + return;
1.90 + }
1.91 + mChanges.InsertElementAt(0, Entry(aTime, aValue));
1.92 + }
1.93 + /**
1.94 + * Returns the final value of the function. If aTime is non-null,
1.95 + * sets aTime to the time at which the function changes to that final value.
1.96 + * If there are no changes after the current time, returns INT64_MIN in aTime.
1.97 + */
1.98 + const T& GetLast(Time* aTime = nullptr) const
1.99 + {
1.100 + if (mChanges.IsEmpty()) {
1.101 + if (aTime) {
1.102 + *aTime = INT64_MIN;
1.103 + }
1.104 + return mCurrent;
1.105 + }
1.106 + if (aTime) {
1.107 + *aTime = mChanges[mChanges.Length() - 1].mTime;
1.108 + }
1.109 + return mChanges[mChanges.Length() - 1].mValue;
1.110 + }
1.111 + /**
1.112 + * Returns the value of the function just before time aTime.
1.113 + */
1.114 + const T& GetBefore(Time aTime) const
1.115 + {
1.116 + if (mChanges.IsEmpty() || aTime <= mChanges[0].mTime) {
1.117 + return mCurrent;
1.118 + }
1.119 + int32_t changesLength = mChanges.Length();
1.120 + if (mChanges[changesLength - 1].mTime < aTime) {
1.121 + return mChanges[changesLength - 1].mValue;
1.122 + }
1.123 + for (uint32_t i = 1; ; ++i) {
1.124 + if (aTime <= mChanges[i].mTime) {
1.125 + NS_ASSERTION(mChanges[i].mValue != mChanges[i - 1].mValue,
1.126 + "Only changed values appear in array");
1.127 + return mChanges[i - 1].mValue;
1.128 + }
1.129 + }
1.130 + }
1.131 + /**
1.132 + * Returns the value of the function at time aTime.
1.133 + * If aEnd is non-null, sets *aEnd to the time at which the function will
1.134 + * change from the returned value to a new value, or INT64_MAX if that
1.135 + * never happens.
1.136 + * If aStart is non-null, sets *aStart to the time at which the function
1.137 + * changed to the returned value, or INT64_MIN if that happened at or
1.138 + * before the current time.
1.139 + *
1.140 + * Currently uses a linear search, but could use a binary search.
1.141 + */
1.142 + const T& GetAt(Time aTime, Time* aEnd = nullptr, Time* aStart = nullptr) const
1.143 + {
1.144 + if (mChanges.IsEmpty() || aTime < mChanges[0].mTime) {
1.145 + if (aStart) {
1.146 + *aStart = INT64_MIN;
1.147 + }
1.148 + if (aEnd) {
1.149 + *aEnd = mChanges.IsEmpty() ? INT64_MAX : mChanges[0].mTime;
1.150 + }
1.151 + return mCurrent;
1.152 + }
1.153 + int32_t changesLength = mChanges.Length();
1.154 + if (mChanges[changesLength - 1].mTime <= aTime) {
1.155 + if (aEnd) {
1.156 + *aEnd = INT64_MAX;
1.157 + }
1.158 + if (aStart) {
1.159 + *aStart = mChanges[changesLength - 1].mTime;
1.160 + }
1.161 + return mChanges[changesLength - 1].mValue;
1.162 + }
1.163 +
1.164 + for (uint32_t i = 1; ; ++i) {
1.165 + if (aTime < mChanges[i].mTime) {
1.166 + if (aEnd) {
1.167 + *aEnd = mChanges[i].mTime;
1.168 + }
1.169 + if (aStart) {
1.170 + *aStart = mChanges[i - 1].mTime;
1.171 + }
1.172 + NS_ASSERTION(mChanges[i].mValue != mChanges[i - 1].mValue,
1.173 + "Only changed values appear in array");
1.174 + return mChanges[i - 1].mValue;
1.175 + }
1.176 + }
1.177 + }
1.178 + /**
1.179 + * Advance the current time to aTime.
1.180 + */
1.181 + void AdvanceCurrentTime(Time aTime)
1.182 + {
1.183 + for (uint32_t i = 0; i < mChanges.Length(); ++i) {
1.184 + if (aTime < mChanges[i].mTime) {
1.185 + mChanges.RemoveElementsAt(0, i);
1.186 + return;
1.187 + }
1.188 + mCurrent = mChanges[i].mValue;
1.189 + }
1.190 + mChanges.Clear();
1.191 + }
1.192 + /**
1.193 + * Make all currently pending changes happen aDelta later than their
1.194 + * current change times.
1.195 + */
1.196 + void InsertTimeAtStart(Time aDelta)
1.197 + {
1.198 + for (uint32_t i = 0; i < mChanges.Length(); ++i) {
1.199 + mChanges[i].mTime += aDelta;
1.200 + }
1.201 + }
1.202 +
1.203 + /**
1.204 + * Replace the values of this function at aTimeOffset and later with the
1.205 + * values of aOther taken from zero, so if aOther is V at time T >= 0
1.206 + * then this function will be V at time T + aTimeOffset. aOther's current
1.207 + * time must be >= 0.
1.208 + */
1.209 + void Append(const TimeVarying& aOther, Time aTimeOffset)
1.210 + {
1.211 + NS_ASSERTION(aOther.mChanges.IsEmpty() || aOther.mChanges[0].mTime >= 0,
1.212 + "Negative time not allowed here");
1.213 + NS_ASSERTION(&aOther != this, "Can't self-append");
1.214 + SetAtAndAfter(aTimeOffset, aOther.mCurrent);
1.215 + for (uint32_t i = 0; i < aOther.mChanges.Length(); ++i) {
1.216 + const Entry& e = aOther.mChanges[i];
1.217 + SetAtAndAfter(aTimeOffset + e.mTime, e.mValue);
1.218 + }
1.219 + }
1.220 +
1.221 + size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
1.222 + {
1.223 + return mChanges.SizeOfExcludingThis(aMallocSizeOf);
1.224 + }
1.225 +
1.226 +private:
1.227 + struct Entry {
1.228 + Entry(Time aTime, const T& aValue) : mTime(aTime), mValue(aValue) {}
1.229 +
1.230 + // The time at which the value changes to mValue
1.231 + Time mTime;
1.232 + T mValue;
1.233 + };
1.234 + nsAutoTArray<Entry, ReservedChanges> mChanges;
1.235 + T mCurrent;
1.236 +};
1.237 +
1.238 +}
1.239 +
1.240 +#endif /* MOZILLA_TIMEVARYING_H_ */
