diff --git a/include/rosa/agent/History.hpp b/include/rosa/agent/History.hpp index acebd3a..99e8596 100644 --- a/include/rosa/agent/History.hpp +++ b/include/rosa/agent/History.hpp @@ -1,571 +1,506 @@ //===-- rosa/agent/History.hpp ----------------------------------*- C++ -*-===// // // The RoSA Framework // //===----------------------------------------------------------------------===// /// /// \file rosa/agent/History.hpp /// /// \author David Juhasz (david.juhasz@tuwien.ac.at) /// /// \date 2017 /// /// \brief Definition of *history* *functionality*. /// //===----------------------------------------------------------------------===// #ifndef ROSA_AGENT_HISTORY_HPP #define ROSA_AGENT_HISTORY_HPP #include "rosa/agent/Functionality.h" #include "rosa/config/config.h" #include "rosa/support/debug.hpp" #include "rosa/support/type_helper.hpp" #include #include namespace rosa { namespace agent { /// Retention policies defining what a \c rosa::agent::History instance should /// do when the number of recorded entries reached its capacity. enum class HistoryPolicy { SRWF, ///< Stop Recording When Full -- no new entry is recorded when full FIFO, ///< First In First Out -- overwrite the earliest entry with a new one LIFO ///< Last In First Out -- overwrite the latest entry with a new one }; -/// Implements *history* by recording and storing values. -/// -/// \note Not thread-safe implementation, which should not be a problem as any -/// instance of \c rosa::agent::Functionality is an internal component of a -/// \c rosa::Agent, which is the basic unit of concurrency. -/// -/// \tparam T type of values to store -/// \tparam N number of values to store at most -/// \tparam P retention policy to follow when capacity is reached -/// -/// \invariant The size of the underlying \c std::array is `N + 1`:\code -/// max_size() == N + 1 && N == max_size() - 1 -/// \endcode -template -class StaticLengthHistory : public Functionality, private std::array { - - // Bring into scope inherited functions that are used. - using std::array::max_size; - using std::array::operator[]; - - /// The index of the first data element in the circular buffer. - size_t Data; - - /// The index of the first empty slot in the circular buffer. - size_t Space; +template class History : public Functionality { public: - /// Creates an instances by initializing the indices for the circular buffer. - StaticLengthHistory(void) noexcept : Data(0), Space(0) {} + History(void) noexcept {} /// Destroys \p this object. - ~StaticLengthHistory(void) = default; + ~History(void) = default; /// Tells the retention policy applied to \p this object. /// /// \return \c rosa::agent::History::P static constexpr HistoryPolicy policyOfHistory(void) noexcept { return P; } /// Tells how many entries may be recorded by \c this object. /// /// \note The number of entries that are actually recorded may be smaller. /// - /// \return \c rosa::agent::History::N - static constexpr size_t lengthOfHistory(void) noexcept { return N; } + /// \return The max number of entries that may be recorded + virtual size_t lengthOfHistory(void) const noexcept = 0; /// Tells how many entries are currently recorded by \p this object. /// /// \return number of entries currently recorded by \p this object. /// /// \post The returned value cannot be larger than the capacity of \p this /// object:\code /// 0 <= numberOfEntries() && numberOfEntries <= lengthOfHistory() /// \endcode - size_t numberOfEntries(void) const noexcept { - return Data <= Space ? Space - Data : max_size() - Data + Space; - } + virtual size_t numberOfEntries(void) const noexcept = 0; /// Tells if \p this object has not recorded anything yet. /// /// \return if \p this object has no entries recorded bool empty(void) const noexcept { return numberOfEntries() == 0; } + /// Tells if the history reached it's maximum length + /// + /// \return if the history reached it's maximum length. + bool full(void) const noexcept { + return numberOfEntries() == lengthOfHistory(); + } + /// Gives a constant lvalue reference to an entry stored in \p this object. /// /// \note The recorded entries are indexed starting from the latest one. /// /// \param I the index at which the stored entry to take from /// /// \pre \p I is a valid index:\code /// 0 <= I && I <= numberOfEntries() /// \endcode - const T &entry(const size_t I = 0) const noexcept { - ASSERT(0 <= I && I < numberOfEntries()); // Boundary check. - // Position counted back from the last recorded entry. - typename std::make_signed::type Pos = Space - (1 + I); - // Actual index wrapped around to the end of the buffer if negative. - return (*this)[Pos >= 0 ? Pos : max_size() + Pos]; - } + virtual const T &entry(const size_t I = 0) const noexcept = 0; private: - /// Tells if the circular buffer is full. + /// Pushes a new entry into the history. /// - /// \return if the circular buffer is full. - bool full(void) const noexcept { return numberOfEntries() == N; } - - /// Pushes a new entry into the circular buffer. + /// \note The earliest entry gets overwritten if the history is full. /// - /// \note The earliest entry gets overwritten if the buffer is full. + /// \param V value to push into the history + virtual void pushBack(const T &V) noexcept = 0; + + /// Replaces the most recent entry in the history. /// - /// \param V value to push into the buffer - void pushBack(const T &V) noexcept { - // Store value to the first empty slot and step Space index. - (*this)[Space] = V; - Space = (Space + 1) % max_size(); - if (Data == Space) { - // Buffer was full, step Data index. - Data = (Data + 1) % max_size(); - } - } + /// \param V value to replace the most current value with + virtual void replaceFront(const T &V) noexcept = 0; public: /// Adds a new entry to \p this object and tells if the operation was /// successful. /// /// \note Success of the operation depends on the actual policy. /// /// \param V value to store /// /// \return if \p V was successfully stored bool addEntry(const T &V) noexcept { switch (P) { default: ROSA_CRITICAL("unkown HistoryPolicy"); case HistoryPolicy::LIFO: if (full()) { - (*this)[(Space - 1) % max_size()] = V; + replaceFront(V); return true; } case HistoryPolicy::SRWF: if (full()) { return false; } // \note Fall through to FIFO which unconditionally pushes the new entry. case HistoryPolicy::FIFO: // FIFO and SRWF not full. pushBack(V); return true; } } /// Tells the trend set by the entries recorded by \p this object. /// /// The number of steps to go back when calculating the trend is defined as /// argument to the function. /// /// \note The number of steps that can be made is limited by the number of /// entries recorded by \p this object. /// /// \note The function is made a template only to be able to use /// \c std::enable_if. /// /// \tparam X always use the default! /// /// \param D number of steps to go back in *history* /// /// \return trend set by analyzed entries /// /// \pre Statically, \p this object stores signed arithmetic values:\code /// std::is_arithmetic::value && std::is_signed::value /// \endcode Dynamically, \p D is a valid number of steps to take:\code - /// 0 <= D && D < N + /// 0 <= D && D < lengthOfHistory() /// \endcode template typename std::enable_if< std::is_arithmetic::value && std::is_signed::value, X>::type - trend(const size_t D = N - 1) const noexcept { + trend(const size_t D) const noexcept { STATIC_ASSERT((std::is_same::value), "not default template arg"); - ASSERT(0 <= D && D < N); // Boundary check. + ASSERT(0 <= D && D < lengthOfHistory()); // Boundary check. if (numberOfEntries() < 2 || D < 1) { // No entries for computing trend. return {}; // Zero element of \p T } else { // Here at least two entries. // \c S is the number of steps that can be done. const size_t S = std::min(numberOfEntries() - 1, D); size_t I = S; // Compute trend with linear regression. size_t SumIndices = 0; T SumEntries = {}; T SumSquareEntries = {}; T SumProduct = {}; while (I > 0) { // \note Indexing for the regression starts in the past. const size_t Index = S - I; const T Entry = entry(--I); SumIndices += Index; SumEntries += Entry; SumSquareEntries += Entry * Entry; SumProduct += Entry * Index; } return (SumProduct * S - SumEntries * SumIndices) / (SumSquareEntries * S - SumEntries * SumEntries); } } /// Tells the average absolute difference between consecutive entries recorded /// by \p this object /// The number of steps to go back when calculating the average is defined as /// argument to the function. /// /// \note The number of steps that can be made is limited by the number of /// entries recorded by \p this object. /// /// \note The function is made a template only to be able to use /// \c std::enable_if. /// /// \tparam X always use the default! /// /// \param D number of steps to go back in *history* /// /// \pre Statically, \p this object stores arithmetic values:\code /// std::is_arithmetic::value /// \endcode Dynamically, \p D is a valid number of steps to take:\code - /// 0 <= D && D < N + /// 0 <= D && D < lengthOfHistory() /// \endcode template typename std::enable_if::value, size_t>::type - averageAbsDiff(const size_t D = N - 1) const noexcept { + averageAbsDiff(const size_t D) const noexcept { STATIC_ASSERT((std::is_same::value), "not default template arg"); - ASSERT(0 <= D && D < N); // Boundary check. + ASSERT(0 <= D && D < lengthOfHistory()); // Boundary check. if (numberOfEntries() < 2 || D < 1) { // No difference to average. return {}; // Zero element of \p T } else { // Here at least two entries. // \c S is the number of steps that can be done. const size_t S = std::min(numberOfEntries() - 1, D); // Sum up differences as non-negative values only, hence using an // unsigned variable for that. size_t Diffs = {}; // Init to zero. // Count down entry indices and sum up all the absolute differences. size_t I = S; T Last = entry(I); while (I > 0) { T Next = entry(--I); Diffs += Last < Next ? Next - Last : Last - Next; Last = Next; } // Return the average of the summed differences. return Diffs / S; } } }; +/// Implements *history* by recording and storing values. +/// The length of the underlying std::array is static and must be set at +/// compile-time +/// +/// \note Not thread-safe implementation, which should not be a problem as any +/// instance of \c rosa::agent::Functionality is an internal component of a +/// \c rosa::Agent, which is the basic unit of concurrency. +/// +/// \tparam T type of values to store +/// \tparam N number of values to store at most +/// \tparam P retention policy to follow when capacity is reached +/// +/// \invariant The size of the underlying \c std::array is `N + 1`:\code +/// max_size() == N + 1 && N == max_size() - 1 +/// \endcode +template +class StaticLengthHistory : public History, private std::array { + + // Bring into scope inherited functions that are used. + using std::array::max_size; + using std::array::operator[]; + + /// The index of the first data element in the circular buffer. + size_t Data; + + /// The index of the first empty slot in the circular buffer. + size_t Space; + +public: + using History::policyOfHistory; + using History::empty; + using History::full; + using History::addEntry; + using History::trend; + using History::averageAbsDiff; + + /// Creates an instances by initializing the indices for the circular buffer. + StaticLengthHistory(void) noexcept : Data(0), Space(0) {} + + /// Destroys \p this object. + ~StaticLengthHistory(void) = default; + + /// Tells how many entries may be recorded by \c this object. + /// + /// \note The number of entries that are actually recorded may be smaller. + /// + /// \return \c rosa::agent::History::N + size_t lengthOfHistory(void) const noexcept override { return N; } + + /// Tells how many entries are currently recorded by \p this object. + /// + /// \return number of entries currently recorded by \p this object. + /// + /// \post The returned value cannot be larger than the capacity of \p this + /// object:\code + /// 0 <= numberOfEntries() && numberOfEntries <= lengthOfHistory() + /// \endcode + size_t numberOfEntries(void) const noexcept override { + return Data <= Space ? Space - Data : max_size() - Data + Space; + } + + /// Gives a constant lvalue reference to an entry stored in \p this object. + /// + /// \note The recorded entries are indexed starting from the latest one. + /// + /// \param I the index at which the stored entry to take from + /// + /// \pre \p I is a valid index:\code + /// 0 <= I && I <= numberOfEntries() + /// \endcode + const T &entry(const size_t I = 0) const noexcept override { + ASSERT(0 <= I && I < numberOfEntries()); // Boundary check. + // Position counted back from the last recorded entry. + typename std::make_signed::type Pos = Space - (1 + I); + // Actual index wrapped around to the end of the buffer if negative. + return (*this)[Pos >= 0 ? Pos : max_size() + Pos]; + } + +private: + /// Pushes a new entry into the circular buffer. + /// + /// \note The earliest entry gets overwritten if the buffer is full. + /// + /// \param V value to push into the buffer + void pushBack(const T &V) noexcept override { + // Store value to the first empty slot and step Space index. + (*this)[Space] = V; + Space = (Space + 1) % max_size(); + if (Data == Space) { + // Buffer was full, step Data index. + Data = (Data + 1) % max_size(); + } + } + + /// Replaces the most recent entry in the history. + /// + /// \param V value to replace the most current value with + void replaceFront(const T &V) noexcept override { + (*this)[(Space - 1) % max_size()] = V; + } +}; + /// Adds a new entry to a \c rosa::agent::History instance. /// /// \note The result of \c rosa::agent::History::addEntry is ignored. /// /// \tparam T type of values stored in \p H /// \tparam N number of values \p H is able to store /// \tparam P retention policy followed by \p H when capacity is reached /// /// \param H to add a new entry to /// \param V value to add to \p H /// /// \return \p H after adding \p V to it template StaticLengthHistory &operator<<(StaticLengthHistory &H, const T &V) noexcept { H.addEntry(V); return H; } /// Implements *DynamicLengthHistory* by recording and storing values. /// /// \note Not thread-safe implementation, which should not be a problem as any /// instance of \c rosa::agent::Functionality is an internal component of a /// \c rosa::Agent, which is the basic unit of concurrency. /// /// \tparam T type of values to store /// \tparam P retention policy to follow when capacity is reached template -class DynamicLengthHistory : public Functionality, private std::vector { +class DynamicLengthHistory : public History, private std::vector { // Bring into scope inherited functions that are used. using std::vector::erase; using std::vector::begin; using std::vector::end; using std::vector::size; using std::vector::max_size; using std::vector::resize; using std::vector::push_back; + using std::vector::pop_back; using std::vector::operator[]; /// The current length of the DynamicLengthHistory. size_t Length; public: + using History::policyOfHistory; + using History::empty; + using History::full; + using History::addEntry; + using History::trend; + using History::averageAbsDiff; + /// Creates an instances by setting an initial length DynamicLengthHistory(size_t Length) noexcept : Length(Length) { this->resize(Length); } /// Destroys \p this object. ~DynamicLengthHistory(void) = default; - /// Tells the retention policy applied to \p this object. - /// - /// \return \c rosa::agent::DynamicLengthHistory::P - static constexpr HistoryPolicy policyOfDynamicLengthHistory(void) noexcept { - return P; - } - /// Tells how many entries may be recorded by \c this object. /// /// \note The number of entries that are actually recorded may be smaller. /// /// \return \c rosa::agent::DynamicLengthHistory::N - static constexpr size_t lengthOfHistory(void) noexcept { return max_size(); } + size_t lengthOfHistory(void) const noexcept override { return Length; } /// Tells how many entries are currently recorded by \p this object. /// /// \return number of entries currently recorded by \p this object. /// /// \post The returned value cannot be larger than the capacity of \p this /// object:\code /// 0 <= numberOfEntries() && numberOfEntries <= /// lengthOfHistory() \endcode size_t numberOfEntries(void) const noexcept { return size(); } - /// Tells if \p this object has not recorded anything yet. - /// - /// \return if \p this object has no entries recorded - bool empty(void) const noexcept { return numberOfEntries() == 0; } - /// Gives a constant lvalue reference to an entry stored in \p this object. /// /// \note The recorded entries are indexed starting from the latest one. /// /// \param I the index at which the stored entry to take from /// /// \pre \p I is a valid index:\code /// 0 <= I && I <= numberOfEntries() /// \endcode - const T &entry(const size_t I = 0) const noexcept { + const T &entry(const size_t I = 0) const noexcept override { ASSERT(0 <= I && I < numberOfEntries()); // Boundary check. return this->operator[](size() - I - 1); } private: - /// Tells if the buffer is full. - /// - /// \return if the buffer is full. - bool full(void) const noexcept { return numberOfEntries() == Length; } - /// Pushes a new entry into the circular buffer. /// /// \note The earliest entry gets overwritten if the buffer is full. /// /// \param V value to push into the buffer - void pushBack(const T &V) noexcept { + void pushBack(const T &V) noexcept override { if (full()) { erase(begin()); } push_back(V); } -public: - /// Adds a new entry to \p this object and tells if the operation was - /// successful. + /// Replaces the most recent entry in the history. /// - /// \note Success of the operation depends on the actual policy. - /// - /// \param V value to store - /// - /// \return if \p V was successfully stored - bool addEntry(const T &V) noexcept { - switch (P) { - default: - ROSA_CRITICAL("unkown HistoryPolicy"); - case HistoryPolicy::LIFO: - if (full()) { - erase(end()); - } - case HistoryPolicy::SRWF: - if (full()) { - return false; - } - // \note Fall through to FIFO which unconditionally pushes the new entry. - case HistoryPolicy::FIFO: - // FIFO and SRWF not full. - pushBack(V); - return true; - } + /// \param V value to replace the most current value with + void replaceFront(const T &V) noexcept override { + (void)pop_back(); + push_back(V); } +public: /// Resizes the History length. If the new length is smaller than the number /// of currently stored values, values are deleted according to the /// HistoryPolicy. /// /// @param NewLength The new Length of the History. void setLength(size_t NewLength) noexcept { Length = NewLength; if (NewLength < numberOfEntries()) { switch (P) { default: ROSA_CRITICAL("unkown HistoryPolicy"); case HistoryPolicy::LIFO: case HistoryPolicy::SRWF: // Delete last numberOfEntries() - NewLength items from the back erase(begin() + NewLength, end()); break; case HistoryPolicy::FIFO: // Delete last numberOfEntries() - NewLength items from the front erase(begin(), begin() + (numberOfEntries() - NewLength)); break; } } this->resize(Length); } - /// Tells the trend set by the entries recorded by \p this object. - /// - /// The number of steps to go back when calculating the trend is defined as - /// argument to the function. - /// - /// \note The number of steps that can be made is limited by the number of - /// entries recorded by \p this object. - /// - /// \note The function is made a template only to be able to use - /// \c std::enable_if. - /// - /// \tparam X always use the default! - /// - /// \param D number of steps to go back in *DynamicLengthHistory* - /// - /// \return trend set by analyzed entries - /// - /// \pre Statically, \p this object stores signed arithmetic values:\code - /// std::is_arithmetic::value && std::is_signed::value - /// \endcode Dynamically, \p D is a valid number of steps to take:\code - /// 0 <= D && D < Length - /// \endcode - template - typename std::enable_if< - std::is_arithmetic::value && std::is_signed::value, X>::type - trend(const size_t D) const noexcept { - STATIC_ASSERT((std::is_same::value), "not default template arg"); - ASSERT(0 <= D && D < Length); // Boundary check. - if (numberOfEntries() < 2 || D < 1) { - // No entries for computing trend. - return {}; // Zero element of \p T - } else { - // Here at least two entries. - // \c S is the number of steps that can be done. - const size_t S = std::min(numberOfEntries() - 1, D); - size_t I = S; - - // Compute trend with linear regression. - size_t SumIndices = 0; - T SumEntries = {}; - T SumSquareEntries = {}; - T SumProduct = {}; - while (I > 0) { - // \note Indexing for the regression starts in the past. - const size_t Index = S - I; - const T Entry = entry(--I); - SumIndices += Index; - SumEntries += Entry; - SumSquareEntries += Entry * Entry; - SumProduct += Entry * Index; - } - - return (SumProduct * S - SumEntries * SumIndices) / - (SumSquareEntries * S - SumEntries * SumEntries); - } - } - - /// Tells the average absolute difference between consecutive entries - /// recorded by \p this object The number of steps to go back when - /// calculating the average is defined as argument to the function. - /// - /// \note The number of steps that can be made is limited by the number of - /// entries recorded by \p this object. - /// - /// \note The function is made a template only to be able to use - /// \c std::enable_if. - /// - /// \tparam X always use the default! - /// - /// \param D number of steps to go back in *DynamicLengthHistory* - /// - /// \pre Statically, \p this object stores arithmetic values:\code - /// std::is_arithmetic::value - /// \endcode Dynamically, \p D is a valid number of steps to take:\code - /// 0 <= D && D < Length - /// \endcode - template - typename std::enable_if::value, size_t>::type - averageAbsDiff(const size_t D) const noexcept { - STATIC_ASSERT((std::is_same::value), "not default template arg"); - ASSERT(0 <= D && D < Length); // Boundary check. - if (numberOfEntries() < 2 || D < 1) { - // No difference to average. - return {}; // Zero element of \p T - } else { - // Here at least two entries. - // \c S is the number of steps that can be done. - const size_t S = std::min(numberOfEntries() - 1, D); - - // Sum up differences as non-negative values only, hence using an - // unsigned variable for that. - size_t Diffs = {}; // Init to zero. - // Count down entry indices and sum up all the absolute differences. - size_t I = S; - T Last = entry(I); - while (I > 0) { - T Next = entry(--I); - Diffs += Last < Next ? Next - Last : Last - Next; - Last = Next; - } - // Return the average of the summed differences. - return Diffs / S; - } - } }; /// Adds a new entry to a \c rosa::agent::DynamicLengthHistory instance. /// /// \note The result of \c rosa::agent::DynamicLengthHistory::addEntry is /// ignored. /// /// \tparam T type of values stored in \p H /// \tparam P retention policy followed by \p H when capacity is reached /// /// \param H to add a new entry to /// \param V value to add to \p H /// /// \return \p H after adding \p V to it template DynamicLengthHistory &operator<<(DynamicLengthHistory &H, const T &V) noexcept { H.addEntry(V); return H; } } // End namespace agent } // End namespace rosa #endif // ROSA_AGENT_HISTORY_HPP