1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/graph/detail/permutation.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,205 @@
1.4 +// (C) Copyright Jeremy Siek 2001.
1.5 +// Distributed under the Boost Software License, Version 1.0. (See
1.6 +// accompanying file LICENSE_1_0.txt or copy at
1.7 +// http://www.boost.org/LICENSE_1_0.txt)
1.8 +
1.9 +#ifndef BOOST_PERMUTATION_HPP
1.10 +#define BOOST_PERMUTATION_HPP
1.11 +
1.12 +#include <vector>
1.13 +#include <memory>
1.14 +#include <functional>
1.15 +#include <algorithm>
1.16 +#include <boost/graph/detail/shadow_iterator.hpp>
1.17 +
1.18 +namespace boost {
1.19 +
1.20 +template <class Iter1, class Iter2>
1.21 +void permute_serial(Iter1 permuter, Iter1 last, Iter2 result)
1.22 +{
1.23 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
1.24 + typedef std::ptrdiff_t D:
1.25 +#else
1.26 + typedef typename std::iterator_traits<Iter1>::difference_type D;
1.27 +#endif
1.28 +
1.29 + D n = 0;
1.30 + while (permuter != last) {
1.31 + std::swap(result[n], result[*permuter]);
1.32 + ++n;
1.33 + ++permuter;
1.34 + }
1.35 +}
1.36 +
1.37 +template <class InIter, class RandIterP, class RandIterR>
1.38 +void permute_copy(InIter first, InIter last, RandIterP p, RandIterR result)
1.39 +{
1.40 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
1.41 + typedef std::ptrdiff_t i = 0;
1.42 +#else
1.43 + typename std::iterator_traits<RandIterP>::difference_type i = 0;
1.44 +#endif
1.45 + for (; first != last; ++first, ++i)
1.46 + result[p[i]] = *first;
1.47 +}
1.48 +
1.49 +namespace detail {
1.50 +
1.51 +template <class RandIter, class RandIterPerm, class D, class T>
1.52 +void permute_helper(RandIter first, RandIter last, RandIterPerm p, D, T)
1.53 +{
1.54 + D i = 0, pi, n = last - first, cycle_start;
1.55 + T tmp;
1.56 + std::vector<int> visited(n, false);
1.57 +
1.58 + while (i != n) { // continue until all elements have been processed
1.59 + cycle_start = i;
1.60 + tmp = first[i];
1.61 + do { // walk around a cycle
1.62 + pi = p[i];
1.63 + visited[pi] = true;
1.64 + std::swap(tmp, first[pi]);
1.65 + i = pi;
1.66 + } while (i != cycle_start);
1.67 +
1.68 + // find the next cycle
1.69 + for (i = 0; i < n; ++i)
1.70 + if (visited[i] == false)
1.71 + break;
1.72 + }
1.73 +}
1.74 +
1.75 +} // namespace detail
1.76 +
1.77 +template <class RandIter, class RandIterPerm>
1.78 +void permute(RandIter first, RandIter last, RandIterPerm p)
1.79 +{
1.80 + detail::permute_helper(first, last, p, last - first, *first);
1.81 +}
1.82 +
1.83 +
1.84 +// Knuth 1.3.3, Vol. 1 p 176
1.85 +// modified for zero-based arrays
1.86 +// time complexity?
1.87 +//
1.88 +// WARNING: T must be a signed integer!
1.89 +template <class PermIter>
1.90 +void invert_permutation(PermIter X, PermIter Xend)
1.91 +{
1.92 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
1.93 + typedef std::ptrdiff_t T:
1.94 +#else
1.95 + typedef typename std::iterator_traits<PermIter>::value_type T;
1.96 +#endif
1.97 + T n = Xend - X;
1.98 + T m = n;
1.99 + T j = -1;
1.100 +
1.101 + while (m > 0) {
1.102 + T i = X[m-1] + 1;
1.103 + if (i > 0) {
1.104 + do {
1.105 + X[m-1] = j - 1;
1.106 + j = -m;
1.107 + m = i;
1.108 + i = X[m-1] + 1;
1.109 + } while (i > 0);
1.110 + i = j;
1.111 + }
1.112 + X[m-1] = -i - 1;
1.113 + --m;
1.114 + }
1.115 +}
1.116 +
1.117 +// Takes a "normal" permutation array (and its inverse), and turns it
1.118 +// into a BLAS-style permutation array (which can be thought of as a
1.119 +// serialized permutation).
1.120 +template <class Iter1, class Iter2, class Iter3>
1.121 +inline void serialize_permutation(Iter1 q, Iter1 q_end, Iter2 q_inv, Iter3 p)
1.122 +{
1.123 +#ifdef BOOST_NO_STD_ITERATOR_TRAITS
1.124 + typedef std::ptrdiff_t P1;
1.125 + typedef std::ptrdiff_t P2;
1.126 + typedef std::ptrdiff_t D;
1.127 +#else
1.128 + typedef typename std::iterator_traits<Iter1>::value_type P1;
1.129 + typedef typename std::iterator_traits<Iter2>::value_type P2;
1.130 + typedef typename std::iterator_traits<Iter1>::difference_type D;
1.131 +#endif
1.132 + D n = q_end - q;
1.133 + for (D i = 0; i < n; ++i) {
1.134 + P1 qi = q[i];
1.135 + P2 qii = q_inv[i];
1.136 + *p++ = qii;
1.137 + std::swap(q[i], q[qii]);
1.138 + std::swap(q_inv[i], q_inv[qi]);
1.139 + }
1.140 +}
1.141 +
1.142 +// Not used anymore, leaving it here for future reference.
1.143 +template <typename Iter, typename Compare>
1.144 +void merge_sort(Iter first, Iter last, Compare cmp)
1.145 +{
1.146 + if (first + 1 < last) {
1.147 + Iter mid = first + (last - first)/2;
1.148 + merge_sort(first, mid, cmp);
1.149 + merge_sort(mid, last, cmp);
1.150 + std::inplace_merge(first, mid, last, cmp);
1.151 + }
1.152 +}
1.153 +
1.154 +
1.155 +// time: N log N + 3N + ?
1.156 +// space: 2N
1.157 +template <class Iter, class IterP, class Cmp, class Alloc>
1.158 +inline void sortp(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
1.159 +{
1.160 + typedef typename std::iterator_traits<IterP>::value_type P;
1.161 + typedef typename std::iterator_traits<IterP>::difference_type D;
1.162 + D n = last - first;
1.163 + std::vector<P, Alloc> q(n);
1.164 + for (D i = 0; i < n; ++i)
1.165 + q[i] = i;
1.166 + std::sort(make_shadow_iter(first, q.begin()),
1.167 + make_shadow_iter(last, q.end()),
1.168 + shadow_cmp<Cmp>(cmp));
1.169 + invert_permutation(q.begin(), q.end());
1.170 + std::copy(q.begin(), q.end(), p);
1.171 +}
1.172 +
1.173 +template <class Iter, class IterP, class Cmp>
1.174 +inline void sortp(Iter first, Iter last, IterP p, Cmp cmp)
1.175 +{
1.176 + typedef typename std::iterator_traits<IterP>::value_type P;
1.177 + sortp(first, last, p, cmp, std::allocator<P>());
1.178 +}
1.179 +
1.180 +template <class Iter, class IterP>
1.181 +inline void sortp(Iter first, Iter last, IterP p)
1.182 +{
1.183 + typedef typename std::iterator_traits<Iter>::value_type T;
1.184 + typedef typename std::iterator_traits<IterP>::value_type P;
1.185 + sortp(first, last, p, std::less<T>(), std::allocator<P>());
1.186 +}
1.187 +
1.188 +template <class Iter, class IterP, class Cmp, class Alloc>
1.189 +inline void sortv(Iter first, Iter last, IterP p, Cmp cmp, Alloc alloc)
1.190 +{
1.191 + typedef typename std::iterator_traits<IterP>::value_type P;
1.192 + typedef typename std::iterator_traits<IterP>::difference_type D;
1.193 + D n = last - first;
1.194 + std::vector<P, Alloc> q(n), q_inv(n);
1.195 + for (D i = 0; i < n; ++i)
1.196 + q_inv[i] = i;
1.197 + std::sort(make_shadow_iter(first, q_inv.begin()),
1.198 + make_shadow_iter(last, q_inv.end()),
1.199 + shadow_cmp<Cmp>(cmp));
1.200 + std::copy(q_inv, q_inv.end(), q.begin());
1.201 + invert_permutation(q.begin(), q.end());
1.202 + serialize_permutation(q.begin(), q.end(), q_inv.end(), p);
1.203 +}
1.204 +
1.205 +
1.206 +} // namespace boost
1.207 +
1.208 +#endif // BOOST_PERMUTATION_HPP