JPermutation.hh

Go to the documentation of this file.

#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