michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-*/
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
michael@0:  * You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef MOZILLA_TIMEVARYING_H_
michael@0: #define MOZILLA_TIMEVARYING_H_
michael@0: 
michael@0: #include "nsTArray.h"
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: /**
michael@0:  * This is just for CTOR/DTOR tracking. We can't put this in
michael@0:  * TimeVarying directly because the different template instances have
michael@0:  * different sizes and that confuses things.
michael@0:  */
michael@0: class TimeVaryingBase {
michael@0: protected:
michael@0:   TimeVaryingBase()
michael@0:   {
michael@0:     MOZ_COUNT_CTOR(TimeVaryingBase);
michael@0:   }
michael@0:   ~TimeVaryingBase()
michael@0:   {
michael@0:     MOZ_COUNT_DTOR(TimeVaryingBase);
michael@0:   }
michael@0: };
michael@0: 
michael@0: /**
michael@0:  * Objects of this class represent values that can change over time ---
michael@0:  * a mathematical function of time.
michael@0:  * Time is the type of time values, T is the value that changes over time.
michael@0:  * There are a finite set of "change times"; at each change time, the function
michael@0:  * instantly changes to a new value. ReservedChanges should be set to the
michael@0:  * expected number of change events that the object is likely to contain.
michael@0:  * This value should be 0 for all consumers unless you know that a higher value
michael@0:  * would be a benefit.
michael@0:  * There is also a "current time" which must always advance (not go backward).
michael@0:  * The function is constant for all times less than the current time.
michael@0:  * When the current time is advanced, the value of the function at the new
michael@0:  * current time replaces the values for all previous times.
michael@0:  *
michael@0:  * The implementation records a mCurrent (the value at the current time)
michael@0:  * and an array of "change times" (greater than the current time) and the
michael@0:  * new value for each change time. This is a simple but dumb implementation.
michael@0:  * We maintain the invariant that each change entry in the array must have
michael@0:  * a different value to the value in the previous change entry (or, for
michael@0:  * the first change entry, mCurrent).
michael@0:  */
michael@0: template <typename Time, typename T, uint32_t ReservedChanges>
michael@0: class TimeVarying : public TimeVaryingBase {
michael@0: public:
michael@0:   TimeVarying(const T& aInitial) : mCurrent(aInitial) {}
michael@0:   /**
michael@0:    * This constructor can only be called if mCurrent has a no-argument
michael@0:    * constructor.
michael@0:    */
michael@0:   TimeVarying() : mCurrent() {}
michael@0: 
michael@0:   /**
michael@0:    * Sets the value for all times >= aTime to aValue.
michael@0:    */
michael@0:   void SetAtAndAfter(Time aTime, const T& aValue)
michael@0:   {
michael@0:     for (int32_t i = mChanges.Length() - 1; i >= 0; --i) {
michael@0:       NS_ASSERTION(i == int32_t(mChanges.Length() - 1),
michael@0:                    "Always considering last element of array");
michael@0:       if (aTime > mChanges[i].mTime) {
michael@0:         if (mChanges[i].mValue != aValue) {
michael@0:           mChanges.AppendElement(Entry(aTime, aValue));
michael@0:         }
michael@0:         return;
michael@0:       }
michael@0:       if (aTime == mChanges[i].mTime) {
michael@0:         if ((i > 0 ? mChanges[i - 1].mValue : mCurrent) == aValue) {
michael@0:           mChanges.RemoveElementAt(i);
michael@0:           return;
michael@0:         }
michael@0:         mChanges[i].mValue = aValue;
michael@0:         return;
michael@0:       }
michael@0:       mChanges.RemoveElementAt(i);
michael@0:     }
michael@0:     if (mCurrent == aValue) {
michael@0:       return;
michael@0:     }
michael@0:     mChanges.InsertElementAt(0, Entry(aTime, aValue));
michael@0:   }
michael@0:   /**
michael@0:    * Returns the final value of the function. If aTime is non-null,
michael@0:    * sets aTime to the time at which the function changes to that final value.
michael@0:    * If there are no changes after the current time, returns INT64_MIN in aTime.
michael@0:    */
michael@0:   const T& GetLast(Time* aTime = nullptr) const
michael@0:   {
michael@0:     if (mChanges.IsEmpty()) {
michael@0:       if (aTime) {
michael@0:         *aTime = INT64_MIN;
michael@0:       }
michael@0:       return mCurrent;
michael@0:     }
michael@0:     if (aTime) {
michael@0:       *aTime = mChanges[mChanges.Length() - 1].mTime;
michael@0:     }
michael@0:     return mChanges[mChanges.Length() - 1].mValue;
michael@0:   }
michael@0:   /**
michael@0:    * Returns the value of the function just before time aTime.
michael@0:    */
michael@0:   const T& GetBefore(Time aTime) const
michael@0:   {
michael@0:     if (mChanges.IsEmpty() || aTime <= mChanges[0].mTime) {
michael@0:       return mCurrent;
michael@0:     }
michael@0:     int32_t changesLength = mChanges.Length();
michael@0:     if (mChanges[changesLength - 1].mTime < aTime) {
michael@0:       return mChanges[changesLength - 1].mValue;
michael@0:     }
michael@0:     for (uint32_t i = 1; ; ++i) {
michael@0:       if (aTime <= mChanges[i].mTime) {
michael@0:         NS_ASSERTION(mChanges[i].mValue != mChanges[i - 1].mValue,
michael@0:                      "Only changed values appear in array");
michael@0:         return mChanges[i - 1].mValue;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0:   /**
michael@0:    * Returns the value of the function at time aTime.
michael@0:    * If aEnd is non-null, sets *aEnd to the time at which the function will
michael@0:    * change from the returned value to a new value, or INT64_MAX if that
michael@0:    * never happens.
michael@0:    * If aStart is non-null, sets *aStart to the time at which the function
michael@0:    * changed to the returned value, or INT64_MIN if that happened at or
michael@0:    * before the current time.
michael@0:    *
michael@0:    * Currently uses a linear search, but could use a binary search.
michael@0:    */
michael@0:   const T& GetAt(Time aTime, Time* aEnd = nullptr, Time* aStart = nullptr) const
michael@0:   {
michael@0:     if (mChanges.IsEmpty() || aTime < mChanges[0].mTime) {
michael@0:       if (aStart) {
michael@0:         *aStart = INT64_MIN;
michael@0:       }
michael@0:       if (aEnd) {
michael@0:         *aEnd = mChanges.IsEmpty() ? INT64_MAX : mChanges[0].mTime;
michael@0:       }
michael@0:       return mCurrent;
michael@0:     }
michael@0:     int32_t changesLength = mChanges.Length();
michael@0:     if (mChanges[changesLength - 1].mTime <= aTime) {
michael@0:       if (aEnd) {
michael@0:         *aEnd = INT64_MAX;
michael@0:       }
michael@0:       if (aStart) {
michael@0:         *aStart = mChanges[changesLength - 1].mTime;
michael@0:       }
michael@0:       return mChanges[changesLength - 1].mValue;
michael@0:     }
michael@0: 
michael@0:     for (uint32_t i = 1; ; ++i) {
michael@0:       if (aTime < mChanges[i].mTime) {
michael@0:         if (aEnd) {
michael@0:           *aEnd = mChanges[i].mTime;
michael@0:         }
michael@0:         if (aStart) {
michael@0:           *aStart = mChanges[i - 1].mTime;
michael@0:         }
michael@0:         NS_ASSERTION(mChanges[i].mValue != mChanges[i - 1].mValue,
michael@0:                      "Only changed values appear in array");
michael@0:         return mChanges[i - 1].mValue;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0:   /**
michael@0:    * Advance the current time to aTime.
michael@0:    */
michael@0:   void AdvanceCurrentTime(Time aTime)
michael@0:   {
michael@0:     for (uint32_t i = 0; i < mChanges.Length(); ++i) {
michael@0:       if (aTime < mChanges[i].mTime) {
michael@0:         mChanges.RemoveElementsAt(0, i);
michael@0:         return;
michael@0:       }
michael@0:       mCurrent = mChanges[i].mValue;
michael@0:     }
michael@0:     mChanges.Clear();
michael@0:   }
michael@0:   /**
michael@0:    * Make all currently pending changes happen aDelta later than their
michael@0:    * current change times.
michael@0:    */
michael@0:   void InsertTimeAtStart(Time aDelta)
michael@0:   {
michael@0:     for (uint32_t i = 0; i < mChanges.Length(); ++i) {
michael@0:       mChanges[i].mTime += aDelta;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Replace the values of this function at aTimeOffset and later with the
michael@0:    * values of aOther taken from zero, so if aOther is V at time T >= 0
michael@0:    * then this function will be V at time T + aTimeOffset. aOther's current
michael@0:    * time must be >= 0.
michael@0:    */
michael@0:   void Append(const TimeVarying& aOther, Time aTimeOffset)
michael@0:   {
michael@0:     NS_ASSERTION(aOther.mChanges.IsEmpty() || aOther.mChanges[0].mTime >= 0,
michael@0:                  "Negative time not allowed here");
michael@0:     NS_ASSERTION(&aOther != this, "Can't self-append");
michael@0:     SetAtAndAfter(aTimeOffset, aOther.mCurrent);
michael@0:     for (uint32_t i = 0; i < aOther.mChanges.Length(); ++i) {
michael@0:       const Entry& e = aOther.mChanges[i];
michael@0:       SetAtAndAfter(aTimeOffset + e.mTime, e.mValue);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
michael@0:   {
michael@0:     return mChanges.SizeOfExcludingThis(aMallocSizeOf);
michael@0:   }
michael@0: 
michael@0: private:
michael@0:   struct Entry {
michael@0:     Entry(Time aTime, const T& aValue) : mTime(aTime), mValue(aValue) {}
michael@0: 
michael@0:     // The time at which the value changes to mValue
michael@0:     Time mTime;
michael@0:     T mValue;
michael@0:   };
michael@0:   nsAutoTArray<Entry, ReservedChanges> mChanges;
michael@0:   T mCurrent;
michael@0: };
michael@0: 
michael@0: }
michael@0: 
michael@0: #endif /* MOZILLA_TIMEVARYING_H_ */