#ifndef _utl_BinomialCache_h_
#define _utl_BinomialCache_h_

#include <vector>
#include <utl/Singleton.h>


namespace utl {

  /**
    \class BinomialCoefficients BinomialCoefficients.h "utl/BinomialCoefficients.h"

    \brief Calculates binomial coefficients and caches the results

    Call to the class' operator(n, k) is equivalent to binomial
    coefficient \f${n \choose k}\f$.

    Due to rounding errors for the explicit formula with factorials
    (division of large numbers) this generator is using the
    Pascal triangle relations instead, i.e.
    \f[
      {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k},
    \f]
    where only addition of moderate sized numbers can be maintained
    even for fairly large n.

    Usage:
    \code
    BinomialCoefficients& binomial = BinomialCoefficients::GetInstance();
    const double b_4_2 = binomial(4, 2);
    \endcode

    \author Darko Veberic
    \date 05 Sep 2009
    \version $Id$
    \ingroup math
  */

  class BinomialCoefficients : public Singleton<BinomialCoefficients> {
  public:
    BinomialCoefficients(const int initialN = 3)
      : fMaxN(0), fCoefficients(1, 1) { Generate(initialN); }

    double
    operator()(const int n, const int k)
    {
      if (k < 0 || k > n)
        return 0;
      if (n > fMaxN)
        Generate(n);
      return GetUnchecked(n, k);
    }

  private:
    double& GetUnchecked(const int n, const int k)
    { return fCoefficients[n*(n+1)/2 + k]; }

    void Generate(const int n);

    int fMaxN;
    std::vector<double> fCoefficients;
  };

}


#endif