#ifndef __JTOOLS__JPERMUTATION__
#define __JTOOLS__JPERMUTATION__

#include <iterator>


/**
 * \author mdejong
 */

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

namespace JTOOLS {

  /**
   * Implementation of method next_permutation for bidirectional iterators.
   */
  template<class T, class JComparator_t>
  inline bool next_permutation(T             __begin,
			       T             __last,
			       T             __end,
			       JComparator_t compare,
			       std::bidirectional_iterator_tag)
  {
    using namespace std;

    T __rend = __begin;
    --__rend;

    for (T __i = __last; --__i != __rend; ) {

      T __j;

      for (__j = __last; __j != __end && !compare(*__i,*__j); ++__j) {}

      if (__j != __end) {

        iter_swap(__i,__j);

        if (++__i != __last && ++__j != __end) {

          reverse(__i,__last);
          reverse(__j,__end);

          T __k = __end;

          while (__k != __j && __i != __last)
            iter_swap(__i++,--__k);

          reverse(__i,__last);
          reverse(__j,__k);
	}

        return true;
      }
    }

    reverse(__begin, __last);
    reverse(__last,  __end);
    reverse(__begin, __end);

    return false;
  }


  /**
   * Permutations of sub-set of data.
   * The first template argument refers to a bidirectional iterator and
   * the second template argument to the comparator.
   *
   * \param   __begin        begin of input  data
   * \param   __last         end   of output data
   * \param   __end          end   of input  data
   * \param   compare        comparison operator
   * \return                 true if another permutation exists; else false
   */
  template<class T, class JComparator_t>
  inline bool next_permutation(T             __begin,
			       T             __last,
			       T             __end,
			       JComparator_t compare)
  {
    return next_permutation(__begin, __last, __end, compare, typename std::iterator_traits<T>::iterator_category());
  }
}

#endif