//===-- 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 <algorithm>
#include <array>
#include <limits>
#include <vector>

namespace rosa {
namespace agent {

// @benedikt: todo: assert in history, which checks if push_back worked

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

template <typename T, HistoryPolicy P> class History : public Functionality {

public:
  History(void) noexcept {}

  /// Destroys \p this object.
  virtual ~History(void) = default;

  /// Tells the retention policy applied to \p this object.
  ///
  /// \return \c rosa::agent::History::P
  static constexpr HistoryPolicy policy(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 The max number of entries that may be recorded
  virtual size_t maxLength(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
  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() == maxLength(); }

  /// 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
  virtual const T &entry(const size_t I = 0) const noexcept = 0;

  /// Removes all entries recorded in \p this object.
  virtual void clear() noexcept = 0;

private:
  /// Pushes a new entry into the history.
  ///
  /// \note The earliest entry gets overwritten if the history 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 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()) {
        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<T>::value && std::is_signed<T>::value
  /// \endcode Dynamically, \p D is a valid number of steps to take:\code
  /// 0 <= D && D < lengthOfHistory()
  /// \endcode
  template <typename X = T>
  typename std::enable_if<
      std::is_arithmetic<X>::value && std::is_signed<X>::value, X>::type
  trend(const size_t D) const noexcept {
    STATIC_ASSERT((std::is_same<X, T>::value), "not default template arg");
    ASSERT(0 <= D && D < maxLength()); // 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<T>::value
  /// \endcode Dynamically, \p D is a valid number of steps to take:\code
  /// 0 <= D && D < lengthOfHistory()
  /// \endcode
  template <typename X = T>
  typename std::enable_if<std::is_arithmetic<X>::value, size_t>::type
  averageAbsDiff(const size_t D) const noexcept {
    STATIC_ASSERT((std::is_same<X, T>::value), "not default template arg");
    ASSERT(0 <= D && D < maxLength()); // 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;
    }
  }

  /// Tells the average of all entries recorded by \p this object
  ///
  /// \tparam R type of the result
  template <typename R> R average() const noexcept {
    R Average = 0;
    for (size_t I = 0; I < numberOfEntries(); I++) {
      Average += entry(I);
    }
    Average /= numberOfEntries();
    return Average;
  }
};

/// 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 <typename T, size_t N, HistoryPolicy P>
class StaticLengthHistory : public History<T, P>, private std::array<T, N + 1> {

  // Bring into scope inherited functions that are used.
  using std::array<T, N + 1>::max_size;
  using std::array<T, N + 1>::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<T, P>::policy;
  using History<T, P>::empty;
  using History<T, P>::full;
  using History<T, P>::addEntry;
  using History<T, P>::trend;
  using History<T, P>::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) override = 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 maxLength(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<const size_t>::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];
  }

  /// Removes all entries recorded in \p this object.
  void clear() noexcept override {
    Data = 0;
    Space = 0;
  }

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 <typename T, size_t N, HistoryPolicy P>
StaticLengthHistory<T, N, P> &operator<<(StaticLengthHistory<T, N, P> &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 <typename T, HistoryPolicy P>
class DynamicLengthHistory : public History<T, P>, private std::vector<T> {

private:
  // Bring into scope inherited functions that are used.
  using std::vector<T>::size;
  using std::vector<T>::resize;
  using std::vector<T>::push_back;
  using std::vector<T>::pop_back;
  using std::vector<T>::max_size;
  /// The current length of the DynamicLengthHistory.
  size_t Length;

public:
  // Bring into scope inherited functions that are used.
  using std::vector<T>::erase;
  using std::vector<T>::begin;
  using std::vector<T>::end;
  using std::vector<T>::rbegin;
  using std::vector<T>::rend;
  using std::vector<T>::operator[];

  // Bring into scope inherited functions that are used.
  using History<T, P>::policy;
  using History<T, P>::empty;
  using History<T, P>::full;
  using History<T, P>::addEntry;
  using History<T, P>::trend;
  using History<T, P>::averageAbsDiff;

  /// Creates an instances by setting an initial length
  DynamicLengthHistory(size_t Length) noexcept : Length(Length) {}

  /// Destroys \p this object.
  ~DynamicLengthHistory(void) override = 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::DynamicLengthHistory::N
  size_t maxLength(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 override { return size(); }

  /// 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.
    return this->operator[](size() - I - 1);
  }

  /// Removes all entries recorded in \p this object.
  void clear() noexcept override { erase(begin(), end()); }

  /// Sort all entries in ascending order.
  void sortAscending(void) noexcept { std::sort(begin(), end()); }

  /// Sort all entries in descending order.
  void sortDescending(void) noexcept { std::sort(rbegin(), rend()); }

  /// Delets one element of the history.
  ///
  /// \param V the element which shall be deleted.
  void deleteEntry(T &V) {
    auto it = std::find(begin(), end(), V);

    if (it != end()) {
      erase(it);
    }
  }

  /// Gives back the lowest entry of the history.
  ///
  /// \return the lowest entry. In case of an empty history, the maximum value
  /// of the chosen data type is returned.
  T lowestEntry() {
    auto it = std::min_element(begin(), end());

    if (it == end()) {
      return std::numeric_limits<T>::max();
    } else {
      return *it;
    }
  }

  /// Gives back the highest entry of the history.
  ///
  /// \return the highest entry. In case of an empty history, the minimum value
  /// of the chosen data type is returned.
  T highestEntry() {
    auto it = std::max_element(begin(), end());

    if (it == end()) {
      return std::numeric_limits<T>::min();
    } else {
      return *it;
    }
  }

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 {
    if (full()) {
      erase(begin());
    }
    push_back(V);
  }

  /// 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 {
    (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);
  }
};

/// 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 <typename T, HistoryPolicy P>
DynamicLengthHistory<T, P> &operator<<(DynamicLengthHistory<T, P> &H,
                                       const T &V) noexcept {
  H.addEntry(V);
  return H;
}
} // End namespace agent
} // End namespace rosa

#endif // ROSA_AGENT_HISTORY_HPP