ceph/src/boost/libs/graph/include/boost/graph/detail/permutation.hpp

   1 // (C) Copyright Jeremy Siek 2001.
   2 // Distributed under the Boost Software License, Version 1.0. (See
   3 // accompanying file LICENSE_1_0.txt or copy at
   4 // http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #ifndef BOOST_PERMUTATION_HPP
   7 #define BOOST_PERMUTATION_HPP
   8
   9 #include <vector>
  10 #include <memory>
  11 #include <functional>
  12 #include <algorithm>
  13 #include <boost/graph/detail/shadow_iterator.hpp>
  14
  15 namespace boost {
  16
  17 template <class Iter1, class Iter2>
  18 void permute_serial(Iter1 permuter, Iter1 last, Iter2 result)
  19 {
  20 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
  21   typedef std::ptrdiff_t D:
  22 #else
  23   typedef typename std::iterator_traits<Iter1>::difference_type D;
  24 #endif
  25
  26   D n = 0;
  27   while (permuter != last) {
  28     std::swap(result[n], result[*permuter]);
  29     ++n;
  30     ++permuter;
  31   }
  32 }
  33
  34 template <class InIter, class RandIterP, class RandIterR>
  35 void permute_copy(InIter first, InIter last, RandIterP p, RandIterR result)
  36 {
  37 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
  38   typedef std::ptrdiff_t i = 0;
  39 #else
  40   typename std::iterator_traits<RandIterP>::difference_type i = 0;
  41 #endif
  42   for (; first != last; ++first, ++i)
  43     result[p[i]] = *first;
  44 }
  45
  46 namespace detail {
  47
  48 template <class RandIter, class RandIterPerm, class D, class T>
  49 void permute_helper(RandIter first, RandIter last, RandIterPerm p, D, T)
  50 {
  51   D i = 0, pi, n = last - first, cycle_start;
  52   T tmp;
  53   std::vector<int> visited(n, false);
  54
  55   while (i != n) { // continue until all elements have been processed
  56     cycle_start = i;
  57     tmp = first[i];
  58     do { // walk around a cycle
  59       pi = p[i];
  60       visited[pi] = true;
  61       std::swap(tmp, first[pi]);
  62       i = pi;
  63     } while (i != cycle_start);
  64
  65     // find the next cycle
  66     for (i = 0; i < n; ++i)
  67       if (visited[i] == false)
  68         break;
  69   }
  70 }
  71
  72 } // namespace detail
  73
  74 template <class RandIter, class RandIterPerm>
  75 void permute(RandIter first, RandIter last, RandIterPerm p)
  76 {
  77   detail::permute_helper(first, last, p, last - first, *first);
  78 }
  79
  80
  81 // Knuth 1.3.3, Vol. 1 p 176
  82 // modified for zero-based arrays
  83 // time complexity?
  84 //
  85 // WARNING: T must be a signed integer!
  86 template <class PermIter>
  87 void invert_permutation(PermIter X, PermIter Xend)
  88 {
  89 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
  90   typedef std::ptrdiff_t T:
  91 #else
  92   typedef typename std::iterator_traits<PermIter>::value_type T;
  93 #endif
  94   T n = Xend - X;
  95   T m = n;
  96   T j = -1;
  97
  98   while (m > 0) {
  99     T i = X[m-1] + 1;
 100     if (i > 0) {
 101       do {
 102         X[m-1] = j - 1;
 103         j = -m;
 104         m = i;
 105         i = X[m-1] + 1;
 106       } while (i > 0);
 107       i = j;
 108     }
 109     X[m-1] = -i - 1;
 110     --m;
 111   }
 112 }
 113
 114 // Takes a "normal" permutation array (and its inverse), and turns it
 115 // into a BLAS-style permutation array (which can be thought of as a
 116 // serialized permutation).
 117 template <class Iter1, class Iter2, class Iter3>
 118 inline void serialize_permutation(Iter1 q, Iter1 q_end, Iter2 q_inv, Iter3 p)
 119 {
 120 #ifdef BOOST_NO_STD_ITERATOR_TRAITS
 121   typedef std::ptrdiff_t P1;
 122   typedef std::ptrdiff_t P2;
 123   typedef std::ptrdiff_t D;
 124 #else
 125   typedef typename std::iterator_traits<Iter1>::value_type P1;
 126   typedef typename std::iterator_traits<Iter2>::value_type P2;
 127   typedef typename std::iterator_traits<Iter1>::difference_type D;
 128 #endif
 129   D n = q_end - q;
 130   for (D i = 0; i < n; ++i) {
 131     P1 qi = q[i];
 132     P2 qii = q_inv[i];
 133     *p++ = qii;
 134     std::swap(q[i], q[qii]);
 135     std::swap(q_inv[i], q_inv[qi]);
 136   }
 137 }
 138
 139 // Not used anymore, leaving it here for future reference.
 140 template <typename Iter, typename Compare>
 141 void merge_sort(Iter first, Iter last, Compare cmp)
 142 {
 143   if (first + 1 < last) {
 144     Iter mid = first + (last - first)/2;
 145     merge_sort(first, mid, cmp);
 146     merge_sort(mid, last, cmp);
 147     std::inplace_merge(first, mid, last, cmp);
 148   }
 149 }
 150
 151
 152 // time: N log N + 3N + ?
 153 // space: 2N
 154 template <class Iter, class IterP, class Cmp, class Alloc>
 155 inline void sortp(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
 156 {
 157   typedef typename std::iterator_traits<IterP>::value_type P;
 158   typedef typename std::iterator_traits<IterP>::difference_type D;
 159   D n = last - first;
 160   std::vector<P, Alloc> q(n);
 161   for (D i = 0; i < n; ++i)
 162     q[i] = i;
 163   std::sort(make_shadow_iter(first, q.begin()),
 164             make_shadow_iter(last, q.end()),
 165             shadow_cmp<Cmp>(cmp));
 166   invert_permutation(q.begin(), q.end());
 167   std::copy(q.begin(), q.end(), p);
 168 }
 169
 170 template <class Iter, class IterP, class Cmp>
 171 inline void sortp(Iter first, Iter last, IterP p, Cmp cmp)
 172 {
 173   typedef typename std::iterator_traits<IterP>::value_type P;
 174   sortp(first, last, p, cmp, std::allocator<P>());
 175 }
 176
 177 template <class Iter, class IterP>
 178 inline void sortp(Iter first, Iter last, IterP p)
 179 {
 180   typedef typename std::iterator_traits<Iter>::value_type T;
 181   typedef typename std::iterator_traits<IterP>::value_type P;
 182   sortp(first, last, p, std::less<T>(), std::allocator<P>());
 183 }
 184
 185 template <class Iter, class IterP, class Cmp, class Alloc>
 186 inline void sortv(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
 187 {
 188   typedef typename std::iterator_traits<IterP>::value_type P;
 189   typedef typename std::iterator_traits<IterP>::difference_type D;
 190   D n = last - first;
 191   std::vector<P, Alloc> q(n), q_inv(n);
 192   for (D i = 0; i < n; ++i)
 193     q_inv[i] = i;
 194   std::sort(make_shadow_iter(first, q_inv.begin()),
 195             make_shadow_iter(last, q_inv.end()),
 196             shadow_cmp<Cmp>(cmp));
 197   std::copy(q_inv, q_inv.end(), q.begin());
 198   invert_permutation(q.begin(), q.end());
 199   serialize_permutation(q.begin(), q.end(), q_inv.end(), p);
 200 }
 201
 202
 203 } // namespace boost
 204
 205 #endif // BOOST_PERMUTATION_HPP