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