#ifndef __JTOOLS__JCOMBINATORICS__
#define __JTOOLS__JCOMBINATORICS__

#include <utility>
#include <vector>
#include <algorithm>


/**
 * \author mdejong
 */

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

namespace JTOOLS {


  /**
   * Auxiliary class to convert pair of indices to unique index and back.
   */
  class JCombinatorics {
  public:

    /**
     * Data structure for a pair of indices.
     */
    typedef std::pair<int, int>  pair_type;


    /**
     * Default constructor.
     */
    JCombinatorics() 
    {}


    /**
     * Constructor.
     *
     * \param  numberOfIndices       number of indices
     */
    JCombinatorics(const int numberOfIndices) 
    {
      configure(numberOfIndices);
    }


    /**
     * Get combinatorics.
     *
     * \return                       combinatorics
     */
    const JCombinatorics& getCombinatorics() const
    {
      return *this;
    }


    /**
     * Configure.
     *
     * \param  numberOfIndices       number of indices
     */
    void configure(const int numberOfIndices) 
    {
      zbuf1D.clear();

      zbuf2D.resize(numberOfIndices);

      for (int i = 0; i != numberOfIndices; ++i) {
	zbuf2D[i].resize(numberOfIndices);
      }

      for (int i = 0; i != numberOfIndices; ++i) {

	zbuf2D[i][i] = -1;

	for (int j = i; ++j != numberOfIndices; ) {

	  zbuf2D[i][j] = zbuf1D.size();
	  zbuf2D[j][i] = zbuf1D.size();

	  zbuf1D.push_back(pair_type(i,j));
	}
      }
    }


    /**
     * Get number of indices.
     *
     * \return                       number of indices
     */
    size_t getNumberOfIndices() const
    {
      return zbuf2D.size();
    }


    /**
     * Get number of pairs.
     *
     * \return                       number of pairs
     */
    size_t getNumberOfPairs() const
    {
      return zbuf1D.size();
    }
  
  
    /**
     * Get index of pair of indices.
     *
     * \param  first                 first  address
     * \param  second                second address
     * \return                       index (-1 if first and second address are equal)
     */
    int getIndex(const int first, const int second) const
    {
      return zbuf2D[first][second];
    }


    /**
     * Get pair of indices for given index.
     *
     * \param  index                 index
     * \return                       pair of indices
     */
    const pair_type& getPair(const int index) const
    {
      return zbuf1D[index];
    }


    /**
     * Sort address pairs.
     *
     * \param  comparator            comparator for pairs
     */
    template<class JComparator_t>
    void sort(JComparator_t comparator)
    {
      std::stable_sort(zbuf1D.begin(), zbuf1D.end(), comparator);

      for (int i = 0; i != (int) zbuf1D.size(); ++i) {
	
	const pair_type pair = zbuf1D[i];

	zbuf2D[pair.first][pair.second] = i;
	zbuf2D[pair.second][pair.first] = i;
      }

      for (int i = 0; i != (int) zbuf2D.size(); ++i) {
	zbuf2D[i][i] = -1;
      }
    }


    /**
     * Sign of pair of indices.
     *
     * \param  first                 first  address
     * \param  second                second address
     * \return                       +1 if second >= first; else -1
     */
    static int getSign(const int first, const int second)
    {
      return (second >= first ? +1 : -1);
    }


    /**
     * Sign of pair of indices.
     *
     * \param  pair                  pair of indices
     * \return                       +1 if second >= first; else -1
     */
    static int getSign(const pair_type& pair)
    {
      return getSign(pair.first, pair.second);
    }


  protected:
    std::vector<pair_type>         zbuf1D;
    std::vector<std::vector<int> > zbuf2D;
  };
}

#endif