Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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