graph/detail/permutation.hpp

0001 // (C) Copyright Jeremy Siek 2001.
0002 // Distributed under the Boost Software License, Version 1.0. (See
0003 // accompanying file LICENSE_1_0.txt or copy at
0004 // http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_PERMUTATION_HPP
0007 #define BOOST_PERMUTATION_HPP
0008
0009 #include <vector>
0010 #include <memory>
0011 #include <functional>
0012 #include <algorithm>
0013 #include <boost/graph/detail/shadow_iterator.hpp>
0014
0015 namespace boost
0016 {
0017
0018 template < class Iter1, class Iter2 >
0019 void permute_serial(Iter1 permuter, Iter1 last, Iter2 result)
0020 {
0021 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0022     typedef std::ptrdiff_t D :
0023 #else
0024     typedef typename std::iterator_traits< Iter1 >::difference_type D;
0025 #endif
0026
0027         D n
0028         = 0;
0029     while (permuter != last)
0030     {
0031         std::swap(result[n], result[*permuter]);
0032         ++n;
0033         ++permuter;
0034     }
0035 }
0036
0037 template < class InIter, class RandIterP, class RandIterR >
0038 void permute_copy(InIter first, InIter last, RandIterP p, RandIterR result)
0039 {
0040 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0041     typedef std::ptrdiff_t i = 0;
0042 #else
0043     typename std::iterator_traits< RandIterP >::difference_type i = 0;
0044 #endif
0045     for (; first != last; ++first, ++i)
0046         result[p[i]] = *first;
0047 }
0048
0049 namespace detail
0050 {
0051
0052     template < class RandIter, class RandIterPerm, class D, class T >
0053     void permute_helper(RandIter first, RandIter last, RandIterPerm p, D, T)
0054     {
0055         D i = 0, pi, n = last - first, cycle_start;
0056         T tmp;
0057         std::vector< int > visited(n, false);
0058
0059         while (i != n)
0060         { // continue until all elements have been processed
0061             cycle_start = i;
0062             tmp = first[i];
0063             do
0064             { // walk around a cycle
0065                 pi = p[i];
0066                 visited[pi] = true;
0067                 std::swap(tmp, first[pi]);
0068                 i = pi;
0069             } while (i != cycle_start);
0070
0071             // find the next cycle
0072             for (i = 0; i < n; ++i)
0073                 if (visited[i] == false)
0074                     break;
0075         }
0076     }
0077
0078 } // namespace detail
0079
0080 template < class RandIter, class RandIterPerm >
0081 void permute(RandIter first, RandIter last, RandIterPerm p)
0082 {
0083     detail::permute_helper(first, last, p, last - first, *first);
0084 }
0085
0086 // Knuth 1.3.3, Vol. 1 p 176
0087 // modified for zero-based arrays
0088 // time complexity?
0089 //
0090 // WARNING: T must be a signed integer!
0091 template < class PermIter > void invert_permutation(PermIter X, PermIter Xend)
0092 {
0093 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0094     typedef std::ptrdiff_t T :
0095 #else
0096     typedef typename std::iterator_traits< PermIter >::value_type T;
0097 #endif
0098         T n
0099         = Xend - X;
0100     T m = n;
0101     T j = -1;
0102
0103     while (m > 0)
0104     {
0105         T i = X[m - 1] + 1;
0106         if (i > 0)
0107         {
0108             do
0109             {
0110                 X[m - 1] = j - 1;
0111                 j = -m;
0112                 m = i;
0113                 i = X[m - 1] + 1;
0114             } while (i > 0);
0115             i = j;
0116         }
0117         X[m - 1] = -i - 1;
0118         --m;
0119     }
0120 }
0121
0122 // Takes a "normal" permutation array (and its inverse), and turns it
0123 // into a BLAS-style permutation array (which can be thought of as a
0124 // serialized permutation).
0125 template < class Iter1, class Iter2, class Iter3 >
0126 inline void serialize_permutation(Iter1 q, Iter1 q_end, Iter2 q_inv, Iter3 p)
0127 {
0128 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
0129     typedef std::ptrdiff_t P1;
0130     typedef std::ptrdiff_t P2;
0131     typedef std::ptrdiff_t D;
0132 #else
0133     typedef typename std::iterator_traits< Iter1 >::value_type P1;
0134     typedef typename std::iterator_traits< Iter2 >::value_type P2;
0135     typedef typename std::iterator_traits< Iter1 >::difference_type D;
0136 #endif
0137     D n = q_end - q;
0138     for (D i = 0; i < n; ++i)
0139     {
0140         P1 qi = q[i];
0141         P2 qii = q_inv[i];
0142         *p++ = qii;
0143         std::swap(q[i], q[qii]);
0144         std::swap(q_inv[i], q_inv[qi]);
0145     }
0146 }
0147
0148 // Not used anymore, leaving it here for future reference.
0149 template < typename Iter, typename Compare >
0150 void merge_sort(Iter first, Iter last, Compare cmp)
0151 {
0152     if (first + 1 < last)
0153     {
0154         Iter mid = first + (last - first) / 2;
0155         merge_sort(first, mid, cmp);
0156         merge_sort(mid, last, cmp);
0157         std::inplace_merge(first, mid, last, cmp);
0158     }
0159 }
0160
0161 // time: N log N + 3N + ?
0162 // space: 2N
0163 template < class Iter, class IterP, class Cmp, class Alloc >
0164 inline void sortp(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
0165 {
0166     typedef typename std::iterator_traits< IterP >::value_type P;
0167     typedef typename std::iterator_traits< IterP >::difference_type D;
0168     D n = last - first;
0169     std::vector< P, Alloc > q(n);
0170     for (D i = 0; i < n; ++i)
0171         q[i] = i;
0172     std::sort(make_shadow_iter(first, q.begin()),
0173         make_shadow_iter(last, q.end()), shadow_cmp< Cmp >(cmp));
0174     invert_permutation(q.begin(), q.end());
0175     std::copy(q.begin(), q.end(), p);
0176 }
0177
0178 template < class Iter, class IterP, class Cmp >
0179 inline void sortp(Iter first, Iter last, IterP p, Cmp cmp)
0180 {
0181     typedef typename std::iterator_traits< IterP >::value_type P;
0182     sortp(first, last, p, cmp, std::allocator< P >());
0183 }
0184
0185 template < class Iter, class IterP >
0186 inline void sortp(Iter first, Iter last, IterP p)
0187 {
0188     typedef typename std::iterator_traits< Iter >::value_type T;
0189     typedef typename std::iterator_traits< IterP >::value_type P;
0190     sortp(first, last, p, std::less< T >(), std::allocator< P >());
0191 }
0192
0193 template < class Iter, class IterP, class Cmp, class Alloc >
0194 inline void sortv(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
0195 {
0196     typedef typename std::iterator_traits< IterP >::value_type P;
0197     typedef typename std::iterator_traits< IterP >::difference_type D;
0198     D n = last - first;
0199     std::vector< P, Alloc > q(n), q_inv(n);
0200     for (D i = 0; i < n; ++i)
0201         q_inv[i] = i;
0202     std::sort(make_shadow_iter(first, q_inv.begin()),
0203         make_shadow_iter(last, q_inv.end()), shadow_cmp< Cmp >(cmp));
0204     std::copy(q_inv, q_inv.end(), q.begin());
0205     invert_permutation(q.begin(), q.end());
0206     serialize_permutation(q.begin(), q.end(), q_inv.end(), p);
0207 }
0208
0209 } // namespace boost
0210
0211 #endif // BOOST_PERMUTATION_HPP