// (C) Copyright Jeremy Siek 2001.

 // Distributed under the Boost Software License, Version 1.0. (See

 // accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 #ifndef BOOST_PERMUTATION_HPP

 #define BOOST_PERMUTATION_HPP

 #include <vector>

 #include <memory>

 #include <functional>

 #include <algorithm>

 #include <boost/graph/detail/shadow_iterator.hpp>

 namespace boost {

 template <class Iter1, class Iter2>

 void permute_serial(Iter1 permuter, Iter1 last, Iter2 result)

 {

 #ifdef BOOST_NO_STD_ITERATOR_TRAITS

   typedef std::ptrdiff_t D:

 #else

   typedef typename std::iterator_traits<Iter1>::difference_type D;

 #endif

   D n = 0;

   while (permuter != last) {

     std::swap(result[n], result[*permuter]);

     ++n;

     ++permuter;

   }

 }

 template <class InIter, class RandIterP, class RandIterR>

 void permute_copy(InIter first, InIter last, RandIterP p, RandIterR result)

 {

 #ifdef BOOST_NO_STD_ITERATOR_TRAITS

   typedef std::ptrdiff_t i = 0;

 #else

   typename std::iterator_traits<RandIterP>::difference_type i = 0;

 #endif

   for (; first != last; ++first, ++i)

     result[p[i]] = *first;

 }

 namespace detail {

 template <class RandIter, class RandIterPerm, class D, class T>

 void permute_helper(RandIter first, RandIter last, RandIterPerm p, D, T)

 {

   D i = 0, pi, n = last - first, cycle_start;

   T tmp;

   std::vector<int> visited(n, false);

   while (i != n) { // continue until all elements have been processed

     cycle_start = i;

     tmp = first[i];

     do { // walk around a cycle

       pi = p[i];

       visited[pi] = true;

       std::swap(tmp, first[pi]);

       i = pi;

     } while (i != cycle_start);

     // find the next cycle

     for (i = 0; i < n; ++i)

       if (visited[i] == false)

         break;

   }

 }

 } // namespace detail

 template <class RandIter, class RandIterPerm>

 void permute(RandIter first, RandIter last, RandIterPerm p)

 {

   detail::permute_helper(first, last, p, last - first, *first);

 }

 // Knuth 1.3.3, Vol. 1 p 176

 // modified for zero-based arrays

 // time complexity?

 //

 // WARNING: T must be a signed integer!

 template <class PermIter>

 void invert_permutation(PermIter X, PermIter Xend)

 {

 #ifdef BOOST_NO_STD_ITERATOR_TRAITS

   typedef std::ptrdiff_t T:

 #else

   typedef typename std::iterator_traits<PermIter>::value_type T;

 #endif

   T n = Xend - X;

   T m = n;

   T j = -1;

   while (m > 0) {

     T i = X[m-1] + 1;

     if (i > 0) {

       do {

         X[m-1] = j - 1;

         j = -m;

         m = i;

         i = X[m-1] + 1;

       } while (i > 0);

       i = j;

     }

     X[m-1] = -i - 1;

     --m;

   }

 }

 // Takes a "normal" permutation array (and its inverse), and turns it

 // into a BLAS-style permutation array (which can be thought of as a

 // serialized permutation).

 template <class Iter1, class Iter2, class Iter3>

 inline void serialize_permutation(Iter1 q, Iter1 q_end, Iter2 q_inv, Iter3 p)

 {

 #ifdef BOOST_NO_STD_ITERATOR_TRAITS

   typedef std::ptrdiff_t P1;

   typedef std::ptrdiff_t P2;

   typedef std::ptrdiff_t D;

 #else

   typedef typename std::iterator_traits<Iter1>::value_type P1;

   typedef typename std::iterator_traits<Iter2>::value_type P2;

   typedef typename std::iterator_traits<Iter1>::difference_type D;

 #endif

   D n = q_end - q;

   for (D i = 0; i < n; ++i) {

     P1 qi = q[i];

     P2 qii = q_inv[i];

     *p++ = qii;

     std::swap(q[i], q[qii]);

     std::swap(q_inv[i], q_inv[qi]);

   }

 }

 // Not used anymore, leaving it here for future reference.

 template <typename Iter, typename Compare>

 void merge_sort(Iter first, Iter last, Compare cmp)

 {

   if (first + 1 < last) {

     Iter mid = first + (last - first)/2;

     merge_sort(first, mid, cmp);

     merge_sort(mid, last, cmp);

     std::inplace_merge(first, mid, last, cmp);

   }

 }

 // time: N log N + 3N + ?

 // space: 2N

 template <class Iter, class IterP, class Cmp, class Alloc>

 inline void sortp(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)

 {

   typedef typename std::iterator_traits<IterP>::value_type P;

   typedef typename std::iterator_traits<IterP>::difference_type D;

   D n = last - first;

   std::vector<P, Alloc> q(n);

   for (D i = 0; i < n; ++i) 

     q[i] = i;

   std::sort(make_shadow_iter(first, q.begin()),

             make_shadow_iter(last, q.end()),

             shadow_cmp<Cmp>(cmp));

   invert_permutation(q.begin(), q.end());

   std::copy(q.begin(), q.end(), p);

 }

 template <class Iter, class IterP, class Cmp>

 inline void sortp(Iter first, Iter last, IterP p, Cmp cmp)

 {

   typedef typename std::iterator_traits<IterP>::value_type P;  

   sortp(first, last, p, cmp, std::allocator<P>());

 }

 template <class Iter, class IterP>

 inline void sortp(Iter first, Iter last, IterP p)

 {

   typedef typename std::iterator_traits<Iter>::value_type T;  

   typedef typename std::iterator_traits<IterP>::value_type P;  

   sortp(first, last, p, std::less<T>(), std::allocator<P>());

 }

 template <class Iter, class IterP, class Cmp, class Alloc>

 inline void sortv(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)

 {

   typedef typename std::iterator_traits<IterP>::value_type P;

   typedef typename std::iterator_traits<IterP>::difference_type D;

   D n = last - first;

   std::vector<P, Alloc> q(n), q_inv(n);

   for (D i = 0; i < n; ++i) 

     q_inv[i] = i;

   std::sort(make_shadow_iter(first, q_inv.begin()), 

             make_shadow_iter(last, q_inv.end()), 

             shadow_cmp<Cmp>(cmp));

   std::copy(q_inv, q_inv.end(), q.begin());

   invert_permutation(q.begin(), q.end());

   serialize_permutation(q.begin(), q.end(), q_inv.end(), p);

 }

 } // namespace boost

 #endif // BOOST_PERMUTATION_HPP