// stats module
// - min/max
// - average
// - percentile
//
// - asking for stats will trigger stats computation and results will be cached
//   until insert or clear is called
//   - percentile always gets the value from the array (percentil also interpolates)
// - calling finish will ignore future calls to insert unless clear is called

#ifndef __stats_h__
#define __stats_h__

template <class T> class CStats {
  public:
    CStats(int pSize);
    ~CStats();

    void clear();
    void insert(T pElement);
    void finish();

    T total();
    T min();
    T max();
    T average();
    T median();
    T percentile(double pValue);
    T sumToPercentile(double pValue);
    T averageToPercentile(double pValue);

    int numElements();
  
  protected:
    // array for storage
    T* mArray;
    int mArraySize;

    int mNumElements;

    bool mStatsReady;

    // cached stats
    T mTotal;
    T mMin;
    T mMax;
    T mAverage;
    T mMedian;

    void computeStats();
};

/////////////////////////////////////////////////////////////////////
// template implementation
/////////////////////////////////////////////////////////////////////

#include <algorithm>

/////////////////////////////////////////////////////////////////////
// c'tor / d'tor
/////////////////////////////////////////////////////////////////////

template <class T> CStats<T>::CStats(int pSize) {
  mArray = 0;
  mArraySize = pSize;

  if (mArraySize < 0) {
    mArraySize = 1;
  }

  clear();
}

template <class T> CStats<T>::~CStats() {
  finish();
}

/////////////////////////////////////////////////////////////////////
// public methods
/////////////////////////////////////////////////////////////////////

template <class T> void CStats<T>::clear() {
  if (!mArray) {
    mArray = new T[mArraySize];
  }

  mStatsReady = false;
  
  mTotal = 0;
  mMin = 0;
  mMax = 0;
  mAverage = 0;
  mMedian = 0;

  mNumElements = 0;
}

template <class T> void CStats<T>::insert(T pElement) {
  if (!mArray) {
    return;
  }
  
  if (mNumElements < mArraySize) {
    mArray[mNumElements] = pElement;
    mNumElements++;

    mStatsReady = false;
  }
}

template <class T> void CStats<T>::finish() {
  if (mArray) {
    delete mArray;
    mArray = 0;
  }
}

template <class T> T CStats<T>::total() {
  computeStats();
  return mTotal;
}

template <class T> T CStats<T>::min() {
  computeStats();
  return mMin;
}

template <class T> T CStats<T>::max() {
  computeStats();
  return mMax;
}

template <class T> T CStats<T>::average() {
  computeStats();
  return mAverage;
}

template <class T> T CStats<T>::median() {
  computeStats();
  return mMedian;
}

template <class T> T CStats<T>::percentile(double pValue) {
  // because percentile doesn't use cached values, it cannot be
  // calculated after the stats object is finished
  if ((!mArray) || (mNumElements < 1)) {
    return 0;
  }

  computeStats();

  // sanitize pValue
  if (pValue < 0) {
    pValue = 0;
  } else if (pValue > 1) {
    pValue = 1;
  }

  // calculate percentile
  double theFractionalPlace = pValue * (mNumElements - 1);
  int theFloor = (int)floor(theFractionalPlace);
  int theCeiling = (int)ceil(theFractionalPlace);

  T theFloorValue = mArray[theFloor];
  T theCeilingValue = mArray[theCeiling];

  double theFloorPortion = 1 - (theFractionalPlace - theFloor);
  double theCeilingPortion = 1 - theFloorPortion;

  // weighted average
  T theFloorContribution = (T)(theFloorValue * theFloorPortion);
  T theCeilingContribution = (T)(theCeilingValue * theCeilingPortion);
  return theFloorContribution + theCeilingContribution;
}

template <class T> T CStats<T>::sumToPercentile(double pValue) {
  // because percentile doesn't use cached values, it cannot be
  // calculated after the stats object is finished
  if ((!mArray) || (mNumElements < 1)) {
    return 0;
  }

  computeStats();

  // sanitize pValue
  if (pValue < 0) {
    pValue = 0;
  } else if (pValue > 1) {
    pValue = 1;
  }

  // calculate percentile
  double theFractionalPlace = pValue * (mNumElements - 1);
  int theFloor = (int)floor(theFractionalPlace);

  // summation loop
  T theAcc = 0;
  for (int i = 0; i < theFloor; i++) {
    theAcc += mArray[i];
  }

  return theAcc + percentile(pValue);
}

template <class T> T CStats<T>::averageToPercentile(double pValue) {
  // because percentile doesn't use cached values, it cannot be
  // calculated after the stats object is finished
  if ((!mArray) || (mNumElements < 1)) {
    return 0;
  }

  computeStats();

  // sanitize pValue
  if (pValue < 0) {
    pValue = 0;
  } else if (pValue > 1) {
    pValue = 1;
  }

  // get percentile value and divide by the number of elements
  double theFractionalPlace = pValue * (mNumElements - 1);
  if (theFractionalPlace <= 0) {
    return 0;
  }

  T theSumToPercentile = sumToPercentile(pValue);
  return (T)(theSumToPercentile / theFractionalPlace);
}

template <class T> int CStats<T>::numElements() {
  return mNumElements;
}

/////////////////////////////////////////////////////////////////////
// protected methods
/////////////////////////////////////////////////////////////////////

template <class T> void CStats<T>::computeStats() {
  if ((!mArray) || mStatsReady || (mNumElements < 1)) {
    return;
  }

  // sort array
  std::sort(mArray, mArray + mNumElements);

  // re-initialize stats
  mTotal = 0;

  // calculate
  for (int i = 0; i < mNumElements; i++) {
    mTotal += mArray[i];
  }

  mMin = mArray[0];
  mMax = mArray[mNumElements-1];
  mAverage = mTotal / mNumElements;

  // stats ready now
  mStatsReady = true;

  // can finally calculate median because if we call before we
  // set mStatsReady, we'll stack overflow
  mMedian = percentile(0.5);
}

#endif // __stats_h__