#ifndef __JTOOLS__JQUANTILE__
#define __JTOOLS__JQUANTILE__

#include <ostream>
#include <iomanip>
#include <cmath>
#include <limits>
#include <algorithm>
#include <map>

#include "JLang/JException.hh"
#include "JLang/JTitle.hh"
#include "JLang/JVectorize.hh"
#include "JLang/JManip.hh"

#include "JMath/JMath.hh"


/**
 * \author mdejong
 */

namespace JTOOLS {}
namespace JPP { using namespace JTOOLS; }

namespace JTOOLS {

  using JMATH::JMath;
  using JLANG::JTitle;
  using JLANG::JDivisionByZero;
  using JLANG::JNoValue;
  using JLANG::array_type;
  using JLANG::make_array;


  /**
   * Auxiliary data structure for running average, standard deviation and quantiles.
   *
   * See Knuth TAOCP vol 2, 3rd edition, page 232.\n
   * This class acts as a zero-dimensional histogram.\n
   * Note that if a weight is used, it should strictly be positive.
   */
  struct JQuantile :
    public JTitle,
    public JMath<JQuantile>
  {
    /**
     * Constructor.
     *
     * \param  title            title
     * \param  quantiles        quantiles
     */
    JQuantile(const JTitle& title     = "",
	      const bool    quantiles = false) :
      JTitle(title),
      quantiles(quantiles)
    {
      reset();
    }


    /**
     * Constructor.
     *
     * \param  title            title
     * \param  buffer           input data
     * \param  quantiles        quantiles
     * \param  w                weight
     */
    template<class JElement_t, class JAllocator_t>
    JQuantile(const JTitle& title,
	      const array_type<JElement_t, JAllocator_t>& buffer,
	      const bool    quantiles = false,
	      const double  w         = 1.0) :
      JTitle(title),
      quantiles(quantiles)
    {
      reset();

      put(buffer, w);
    }


    /**
     * Reset.
     */
    void reset()
    {
      mean  = 0.0;
      sigma = 0.0;
      total = 0.0;
      count = 0;
      xmin  = std::numeric_limits<double>::max();
      xmax  = std::numeric_limits<double>::lowest();
      wmin  = std::numeric_limits<double>::max();
      wmax  = std::numeric_limits<double>::lowest();

      buffer.clear();
    }


    /**
     * Add quantile.
     *
     * \param  Q           quantile
     * \return             this quantile
     */
    JQuantile& add(const JQuantile& Q)
    {
      mean  += Q.mean;
      sigma += Q.sigma;
      total += Q.total;
      count += Q.count;
      xmin   = std::min(xmin, Q.xmin);
      xmax   = std::max(xmax, Q.xmax);
      wmin   = std::min(wmin, Q.wmin);
      wmax   = std::max(wmax, Q.wmax);

      if (quantiles) {
	std::copy(Q.buffer.begin(), Q.buffer.end(), std::inserter(buffer, buffer.end()));
      }

      return *this;
    }


    /**
     * Put value.
     *
     * \param  x           value
     * \param  w           weight
     */
    void put(const double x, const double w = 1.0)
    {
      total += w;
      count += 1;

      if (count == 1) {

	mean  = x;
	sigma = 0.0;

      } else {

	const double new_mean  = mean   +  w * (x - mean) / total;
	const double new_sigma = sigma  +  w * (x - mean) * (x - new_mean);
    
	// set up for next iteration

	mean  = new_mean; 
	sigma = new_sigma;
      }

      xmin = std::min(xmin, x);
      xmax = std::max(xmax, x);
      wmin = std::min(wmin, w);
      wmax = std::max(wmax, w);

      if (quantiles) {
	buffer.insert(std::make_pair(x,w));
      }
    }


    /**
     * Put data.
     *
     * \param  buffer           input data
     * \param  w                weight
     */
    template<class JElement_t, class JAllocator_t>
    void put(const array_type<JElement_t, JAllocator_t>& buffer,
	     const double w = 1.0)
    {
      for (typename array_type<JElement_t, JAllocator_t>::const_iterator i = buffer.begin(); i != buffer.end(); ++i) {
	put(*i, w);
      }
    }


    /**
     * Get total count.
     *
     * \return             count
     */
    long long int getCount() const
    {
      return count;
    }


    /**
     * Get total weight.
     *
     * \return             weight
     */
    double getTotal() const
    {
      return total;
    }


    /**
     * Get minimum value.
     *
     * \return             minimum value
     */
    double getXmin() const
    {
      return xmin;
    }


    /**
     * Get maximum value.
     *
     * \return             maximum value
     */
    double getXmax() const
    {
      return xmax;
    }


    /**
     * Get minimum weight.
     *
     * \return             minimum weight
     */
    double getWmin() const
    {
      return wmin;
    }


    /**
     * Get maximum weight.
     *
     * \return             maximum weight
     */
    double getWmax() const
    {
      return wmax;
    }


    /**
     * Get mean value.
     *
     * \return             mean value
     */
    double getMean() const
    {
      if (count != 0.0)
	return mean;
      else
	THROW(JDivisionByZero, "JQuantile::getMean()");
    }


    /**
     * Get standard deviation
     *
     * \return             standard deviation
     */
    double getSTDev() const
    {
      if (count > 1)
	return sqrt(count * sigma/(total * (count - 1)));
      else
	THROW(JDivisionByZero, "JQuantile::getSTDev()");
    }


    /**
     * Get maximal deviation from average.
     *
     * \param  relative    if true, relative to average, else absolute
     * \return             deviation
     */
    double getDeviation(const bool relative = true) const
    {
      if (relative)
	return std::max(getXmax() - getMean(), getMean() - getXmin());
      else
	return getXmax() - getXmin();
    }


    /**
     * Test relative accuracy.
     *
     * \param  precision   relative precision
     * \return             true if reached accuracy; else false
     */
    bool hasAccuracy(const double precision) const
    {
      return getCount() > 1 && getSTDev() < precision * getMean();
    }


    /**
     * Options for evaluation of quantile.
     */
    enum Quantile_t {
      forward_t    = +1,     //!< forward
      symmetric_t  =  0,     //!< symmatric
      backward_t   = -1      //!< backward
    };

    
    /**
     * Get quantile.
     *
     * \param  Q           quantile 
     * \param  option      option
     * \return             value
     */
    double getQuantile(const double Q, const Quantile_t option = forward_t) const
    {
      if (quantiles) {

	double W = 0.0;

	for (std::map<double, double>::const_iterator i = buffer.begin(); i != buffer.end(); ++i) {
	  W += i->second;
	}

	switch (option) {
	case forward_t:
	  return (getQuantile(buffer. begin(), buffer. end(), Q*W));
	case symmetric_t:
	  return (getQuantile(buffer.rbegin(), buffer.rend(), 0.5*(1.0 - Q)*W)  -
		  getQuantile(buffer. begin(), buffer. end(), 0.5*(1.0 - Q)*W));
	case backward_t:
	  return (getQuantile(buffer.rbegin(), buffer.rend(), Q*W));
	default:
	  THROW(JNoValue, "Invalid option " << option);
	}
      }

      THROW(JNoValue, "Option 'quantiles' at JQuantile() incompatible with method getQuantile().");
    }


    /**
     * Print quantile.
     *
     * \param  out         output stream
     * \param  lpr         long print
     */
    std::ostream& print(std::ostream& out, bool lpr = true) const
    {
      using namespace std;

      const int nc = getTitle().size();

      if (lpr) {
	out << setw(nc) << left  << " "             << ' '
	    << setw(12) << left  << "    mean"      << ' '
	    << setw(12) << left  << "    STD"       << ' '
	    << setw(12) << left  << "  deviation"   << endl;
      }

      out << setw(nc) << left << getTitle()          << ' '
	  << SCIENTIFIC(12,5) << getMean()           << ' '
	  << SCIENTIFIC(12,5) << getSTDev()          << ' '
	  << SCIENTIFIC(12,5) << getDeviation(false) << endl;

      return out;
    }


    /**
     * Print quantile.
     *
     * \param  out           output stream
     * \param  quantile      quantile
     * \return               output stream
     */
    friend inline std::ostream& operator<<(std::ostream& out, const JQuantile& quantile)
    {
      return quantile.print(out, getLongprint(out));
    }

  protected:
    /**
     * Get quantile.
     *
     * \param  __begin     begin of data
     * \param  __end       end   of data
     * \param  W           weight
     * \return             value
     */
    template<class T>
    static double getQuantile(T __begin, T __end, const double W)
    {
      double w = 0.0;

      for (T i = __begin; i != __end; ++i) {

	w += i->second;

	if (w >= W) {
	  return i->first;
	}
      }

      THROW(JNoValue, "Invalid weight " << W);
    }


    bool          quantiles;
    double        mean;
    double        sigma;
    double        total;
    long long int count;
    double        xmin;
    double        xmax;
    double        wmin;
    double        wmax;
    std::multimap<double, double> buffer;
  };
}

#endif