/*******************************************************************************
 *
 * File:     History.hpp
 *
 * Contents: Definition of History Module.
 *
 * Copyright 2017
 *
 * Author: David Juhasz (david.juhasz@tuwien.ac.at)
 *
 ******************************************************************************/

#ifndef ROSA_AGENT_HISTORY_HPP
#define ROSA_AGENT_HISTORY_HPP

#include "rosa/agent/Module.h"

#include "rosa/config/config.h"

#include "rosa/support/debug.hpp"
#include "rosa/support/type_helper.hpp"

#include <array>

namespace rosa {
namespace agent {

// Retention policies defining what a 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
};

// NOTE: Not thread-safe implementation, which should not be a problem as a
// Module instance is an internal component of an Agent, which is the basic
// unit of concurrency.
template <typename T, size_t N, HistoryPolicy P>
class History : public Module, private std::array<T, N + 1> {

  // Bring into scope inherited functions that are used.
  // INV: max_size() == N + 1 && N == max_size() - 1
  using std::array<T, N + 1>::max_size;
  using std::array<T, N + 1>::operator[];

  // The indices of the first data element and the first empty slot in the
  // circular buffer.
  size_t Data, Space;

public:
  // Ctor. Initializes indices.
  History(void) noexcept : Data(0), Space(0) {}

  // Dtor.
  ~History(void) = default;

  // Tells the policy applied to the History.
  static constexpr HistoryPolicy policyOfHistory(void) noexcept { return P; }

  // Tells how many entries may be recorded by the History.
  // NOTE: The number of entries that are actually recorded may be smaller.
  static constexpr size_t lengthOfHistory(void) noexcept { return N; }

  // Tells how many entries are currently recorded by the History.
  // POST: 0 <= numberOfEntries() && numberOfEntries <= lengthOfHistory()
  inline size_t numberOfEntries(void) const noexcept {
    return Data <= Space ? Space - Data : max_size() - Data + Space;
  }

  // Tells if the History has not recorded any entries yet.
  inline bool empty(void) const noexcept {
    return numberOfEntries() == 0;
  }

  // Gives a constant lvalue reference to the I-th latest entry stored in the
  // History.
  // PRE: 0 <= I && I <= numberOfEntries()
  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<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];
  }

private:
  // Tells if the circular buffer is full.
  inline bool full(void) const noexcept { return numberOfEntries() == N; }

  // Pushes a new entry into the circular buffer, removing the earliest entry
  // if the buffer is full.
  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();
    }
  }

public:
  // Adds a new entry to the History and tells if the operation was successful.
  // NOTE: Success of the operation depends on the actual policy.
  bool addEntry(const T &V) noexcept {
    switch (P) {
    default:
      ROSA_CRITICAL("unkown HistoryPolicy");
    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 the History. The number of
  // steps to go back in the History is given as argument.
  // NOTE: The number of steps that can be made is limited by the number of
  // entries recorded by the History.
  // NOTE: The function is made a template only to be able to use enable_if.
  // STATIC PRE: std::is_arithmetic<T>::value && std::is_signed<T>::value
  // PRE: 0 <= D && D < N
  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 = N - 1) const noexcept {
    STATIC_ASSERT((std::is_same<X, T>::value), "not default template arg");
    ASSERT(0 <= D && D < N); // Boundary check.
    if (numberOfEntries() < 2 || D < 1) {
      // No entries for computing trend.
      return {}; // Zero element of T
    } else {
      // Here at least two entries.
      // 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 consequtive entries recorded
  // by the History. The number of steps to go back in the History is given as
  // argument.
  // NOTE: The number of steps that can be made is limited by the number of
  // entries recorded by the History.
  // NOTE: The function is made a template only to be able to use enable_if.
  // STATIC PRE: std::is_arithmetic<T>::value
  // PRE: 0 <= D && D < N
  template <typename X = T>
  typename std::enable_if<std::is_arithmetic<X>::value, unsigned_t<X>>::type
  averageAbsDiff(const size_t D = N - 1) const noexcept {
    STATIC_ASSERT((std::is_same<X, T>::value), "not default template arg");
    ASSERT(0 <= D && D < N); // Boundary check.
    if (numberOfEntries() < 2 || D < 1) {
      // No difference to average.
      return {}; // Zero element of T
    } else {
      // Here at least two entries.
      // 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.
      unsigned_t<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;
    }
  }

};

// Convenience operator to add new entries to a History instance.
// NOTE: The result of the member function addEntry is ignored by the operator.
template <typename T, size_t N, HistoryPolicy P>
History<T, N, P> &operator<<(History<T, N, P> &H, const T &V) noexcept {
  H.addEntry(V);
  return H;
}

} // End namespace agent
} // End namespace rosa

#endif // ROSA_AGENT_HISTORY_HPP