Chris@16: // (C) Copyright Jeremy Siek 2001.
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_PERMUTATION_HPP
Chris@16: #define BOOST_PERMUTATION_HPP
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <memory>
Chris@16: #include <functional>
Chris@16: #include <algorithm>
Chris@16: #include <boost/graph/detail/shadow_iterator.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: template <class Iter1, class Iter2>
Chris@16: void permute_serial(Iter1 permuter, Iter1 last, Iter2 result)
Chris@16: {
Chris@16: #ifdef BOOST_NO_STD_ITERATOR_TRAITS
Chris@16:   typedef std::ptrdiff_t D:
Chris@16: #else
Chris@16:   typedef typename std::iterator_traits<Iter1>::difference_type D;
Chris@16: #endif
Chris@16: 
Chris@16:   D n = 0;
Chris@16:   while (permuter != last) {
Chris@16:     std::swap(result[n], result[*permuter]);
Chris@16:     ++n;
Chris@16:     ++permuter;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <class InIter, class RandIterP, class RandIterR>
Chris@16: void permute_copy(InIter first, InIter last, RandIterP p, RandIterR result)
Chris@16: {
Chris@16: #ifdef BOOST_NO_STD_ITERATOR_TRAITS
Chris@16:   typedef std::ptrdiff_t i = 0;
Chris@16: #else
Chris@16:   typename std::iterator_traits<RandIterP>::difference_type i = 0;
Chris@16: #endif
Chris@16:   for (; first != last; ++first, ++i)
Chris@16:     result[p[i]] = *first;
Chris@16: }
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <class RandIter, class RandIterPerm, class D, class T>
Chris@16: void permute_helper(RandIter first, RandIter last, RandIterPerm p, D, T)
Chris@16: {
Chris@16:   D i = 0, pi, n = last - first, cycle_start;
Chris@16:   T tmp;
Chris@16:   std::vector<int> visited(n, false);
Chris@16: 
Chris@16:   while (i != n) { // continue until all elements have been processed
Chris@16:     cycle_start = i;
Chris@16:     tmp = first[i];
Chris@16:     do { // walk around a cycle
Chris@16:       pi = p[i];
Chris@16:       visited[pi] = true;
Chris@16:       std::swap(tmp, first[pi]);
Chris@16:       i = pi;
Chris@16:     } while (i != cycle_start);
Chris@16:     
Chris@16:     // find the next cycle
Chris@16:     for (i = 0; i < n; ++i)
Chris@16:       if (visited[i] == false)
Chris@16:         break;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: template <class RandIter, class RandIterPerm>
Chris@16: void permute(RandIter first, RandIter last, RandIterPerm p)
Chris@16: {
Chris@16:   detail::permute_helper(first, last, p, last - first, *first);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // Knuth 1.3.3, Vol. 1 p 176
Chris@16: // modified for zero-based arrays
Chris@16: // time complexity?
Chris@16: //
Chris@16: // WARNING: T must be a signed integer!
Chris@16: template <class PermIter>
Chris@16: void invert_permutation(PermIter X, PermIter Xend)
Chris@16: {
Chris@16: #ifdef BOOST_NO_STD_ITERATOR_TRAITS
Chris@16:   typedef std::ptrdiff_t T:
Chris@16: #else
Chris@16:   typedef typename std::iterator_traits<PermIter>::value_type T;
Chris@16: #endif
Chris@16:   T n = Xend - X;
Chris@16:   T m = n;
Chris@16:   T j = -1;
Chris@16: 
Chris@16:   while (m > 0) {
Chris@16:     T i = X[m-1] + 1;
Chris@16:     if (i > 0) {
Chris@16:       do {
Chris@16:         X[m-1] = j - 1;
Chris@16:         j = -m;
Chris@16:         m = i;
Chris@16:         i = X[m-1] + 1;
Chris@16:       } while (i > 0);
Chris@16:       i = j;
Chris@16:     }
Chris@16:     X[m-1] = -i - 1;
Chris@16:     --m;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: // Takes a "normal" permutation array (and its inverse), and turns it
Chris@16: // into a BLAS-style permutation array (which can be thought of as a
Chris@16: // serialized permutation).
Chris@16: template <class Iter1, class Iter2, class Iter3>
Chris@16: inline void serialize_permutation(Iter1 q, Iter1 q_end, Iter2 q_inv, Iter3 p)
Chris@16: {
Chris@16: #ifdef BOOST_NO_STD_ITERATOR_TRAITS
Chris@16:   typedef std::ptrdiff_t P1;
Chris@16:   typedef std::ptrdiff_t P2;
Chris@16:   typedef std::ptrdiff_t D;
Chris@16: #else
Chris@16:   typedef typename std::iterator_traits<Iter1>::value_type P1;
Chris@16:   typedef typename std::iterator_traits<Iter2>::value_type P2;
Chris@16:   typedef typename std::iterator_traits<Iter1>::difference_type D;
Chris@16: #endif
Chris@16:   D n = q_end - q;
Chris@16:   for (D i = 0; i < n; ++i) {
Chris@16:     P1 qi = q[i];
Chris@16:     P2 qii = q_inv[i];
Chris@16:     *p++ = qii;
Chris@16:     std::swap(q[i], q[qii]);
Chris@16:     std::swap(q_inv[i], q_inv[qi]);
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: // Not used anymore, leaving it here for future reference.
Chris@16: template <typename Iter, typename Compare>
Chris@16: void merge_sort(Iter first, Iter last, Compare cmp)
Chris@16: {
Chris@16:   if (first + 1 < last) {
Chris@16:     Iter mid = first + (last - first)/2;
Chris@16:     merge_sort(first, mid, cmp);
Chris@16:     merge_sort(mid, last, cmp);
Chris@16:     std::inplace_merge(first, mid, last, cmp);
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // time: N log N + 3N + ?
Chris@16: // space: 2N
Chris@16: template <class Iter, class IterP, class Cmp, class Alloc>
Chris@16: inline void sortp(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
Chris@16: {
Chris@16:   typedef typename std::iterator_traits<IterP>::value_type P;
Chris@16:   typedef typename std::iterator_traits<IterP>::difference_type D;
Chris@16:   D n = last - first;
Chris@16:   std::vector<P, Alloc> q(n);
Chris@16:   for (D i = 0; i < n; ++i) 
Chris@16:     q[i] = i;
Chris@16:   std::sort(make_shadow_iter(first, q.begin()),
Chris@16:             make_shadow_iter(last, q.end()),
Chris@16:             shadow_cmp<Cmp>(cmp));
Chris@16:   invert_permutation(q.begin(), q.end());
Chris@16:   std::copy(q.begin(), q.end(), p);
Chris@16: }
Chris@16: 
Chris@16: template <class Iter, class IterP, class Cmp>
Chris@16: inline void sortp(Iter first, Iter last, IterP p, Cmp cmp)
Chris@16: {
Chris@16:   typedef typename std::iterator_traits<IterP>::value_type P;  
Chris@16:   sortp(first, last, p, cmp, std::allocator<P>());
Chris@16: }
Chris@16: 
Chris@16: template <class Iter, class IterP>
Chris@16: inline void sortp(Iter first, Iter last, IterP p)
Chris@16: {
Chris@16:   typedef typename std::iterator_traits<Iter>::value_type T;  
Chris@16:   typedef typename std::iterator_traits<IterP>::value_type P;  
Chris@16:   sortp(first, last, p, std::less<T>(), std::allocator<P>());
Chris@16: }
Chris@16: 
Chris@16: template <class Iter, class IterP, class Cmp, class Alloc>
Chris@16: inline void sortv(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
Chris@16: {
Chris@16:   typedef typename std::iterator_traits<IterP>::value_type P;
Chris@16:   typedef typename std::iterator_traits<IterP>::difference_type D;
Chris@16:   D n = last - first;
Chris@16:   std::vector<P, Alloc> q(n), q_inv(n);
Chris@16:   for (D i = 0; i < n; ++i) 
Chris@16:     q_inv[i] = i;
Chris@16:   std::sort(make_shadow_iter(first, q_inv.begin()), 
Chris@16:             make_shadow_iter(last, q_inv.end()), 
Chris@16:             shadow_cmp<Cmp>(cmp));
Chris@16:   std::copy(q_inv, q_inv.end(), q.begin());
Chris@16:   invert_permutation(q.begin(), q.end());
Chris@16:   serialize_permutation(q.begin(), q.end(), q_inv.end(), p);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_PERMUTATION_HPP