1 /*
2 Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.com>, 2017
3
4 Distributed under the Boost Software License, Version 1.0. (See
5 accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7
8 See http://www.boost.org/ for latest version.
9
10
11 Based on https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115
12 */
13
14 /// \file apply_permutation.hpp
15 /// \brief Apply permutation to a sequence.
16 /// \author Alexander Zaitsev
17
18 #ifndef BOOST_ALGORITHM_APPLY_PERMUTATION_HPP
19 #define BOOST_ALGORITHM_APPLY_PERMUTATION_HPP
20
21 #include <algorithm>
22 #include <type_traits>
23
24 #include <boost/range/begin.hpp>
25 #include <boost/range/end.hpp>
26
27 namespace boost { namespace algorithm
28 {
29
30 /// \fn apply_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin )
31 /// \brief Reorder item sequence with index sequence order
32 ///
33 /// \param item_begin The start of the item sequence
34 /// \param item_end One past the end of the item sequence
35 /// \param ind_begin The start of the index sequence.
36 ///
37 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
38 /// Complexity: O(N).
39 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
40 void
apply_permutation(RandomAccessIterator1 item_begin,RandomAccessIterator1 item_end,RandomAccessIterator2 ind_begin,RandomAccessIterator2 ind_end)41 apply_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end,
42 RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end)
43 {
44 typedef typename std::iterator_traits<RandomAccessIterator1>::difference_type Diff;
45 typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Index;
46 using std::swap;
47 Diff size = std::distance(item_begin, item_end);
48 for (Diff i = 0; i < size; i++)
49 {
50 Diff current = i;
51 while (i != ind_begin[current])
52 {
53 Index next = ind_begin[current];
54 swap(item_begin[current], item_begin[next]);
55 ind_begin[current] = current;
56 current = next;
57 }
58 ind_begin[current] = current;
59 }
60 }
61
62 /// \fn apply_reverse_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin )
63 /// \brief Reorder item sequence with index sequence order
64 ///
65 /// \param item_begin The start of the item sequence
66 /// \param item_end One past the end of the item sequence
67 /// \param ind_begin The start of the index sequence.
68 ///
69 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
70 /// Complexity: O(N).
71 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
72 void
apply_reverse_permutation(RandomAccessIterator1 item_begin,RandomAccessIterator1 item_end,RandomAccessIterator2 ind_begin,RandomAccessIterator2 ind_end)73 apply_reverse_permutation(
74 RandomAccessIterator1 item_begin,
75 RandomAccessIterator1 item_end,
76 RandomAccessIterator2 ind_begin,
77 RandomAccessIterator2 ind_end)
78 {
79 typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Diff;
80 using std::swap;
81 Diff length = std::distance(item_begin, item_end);
82 for (Diff i = 0; i < length; i++)
83 {
84 while (i != ind_begin[i])
85 {
86 Diff next = ind_begin[i];
87 swap(item_begin[i], item_begin[next]);
88 swap(ind_begin[i], ind_begin[next]);
89 }
90 }
91 }
92
93 /// \fn apply_permutation ( Range1 item_range, Range2 ind_range )
94 /// \brief Reorder item sequence with index sequence order
95 ///
96 /// \param item_range The item sequence
97 /// \param ind_range The index sequence
98 ///
99 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
100 /// Complexity: O(N).
101 template<typename Range1, typename Range2>
102 void
apply_permutation(Range1 & item_range,Range2 & ind_range)103 apply_permutation(Range1& item_range, Range2& ind_range)
104 {
105 apply_permutation(boost::begin(item_range), boost::end(item_range),
106 boost::begin(ind_range), boost::end(ind_range));
107 }
108
109 /// \fn apply_reverse_permutation ( Range1 item_range, Range2 ind_range )
110 /// \brief Reorder item sequence with index sequence order
111 ///
112 /// \param item_range The item sequence
113 /// \param ind_range The index sequence
114 ///
115 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
116 /// Complexity: O(N).
117 template<typename Range1, typename Range2>
118 void
apply_reverse_permutation(Range1 & item_range,Range2 & ind_range)119 apply_reverse_permutation(Range1& item_range, Range2& ind_range)
120 {
121 apply_reverse_permutation(boost::begin(item_range), boost::end(item_range),
122 boost::begin(ind_range), boost::end(ind_range));
123 }
124
125 }}
126 #endif //BOOST_ALGORITHM_APPLY_PERMUTATION_HPP
127