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/config.hpp>
25 #include <boost/range/begin.hpp>
26 #include <boost/range/end.hpp>
27
28 namespace boost { namespace algorithm
29 {
30
31 /// \fn apply_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin )
32 /// \brief Reorder item sequence with index sequence order
33 ///
34 /// \param item_begin The start of the item sequence
35 /// \param item_end One past the end of the item sequence
36 /// \param ind_begin The start of the index sequence.
37 ///
38 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
39 /// Complexity: O(N).
40 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
41 void
apply_permutation(RandomAccessIterator1 item_begin,RandomAccessIterator1 item_end,RandomAccessIterator2 ind_begin,RandomAccessIterator2 ind_end)42 apply_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end,
43 RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end)
44 {
45 typedef typename std::iterator_traits<RandomAccessIterator1>::difference_type Diff;
46 typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Index;
47 using std::swap;
48 Diff size = std::distance(item_begin, item_end);
49 for (Diff i = 0; i < size; i++)
50 {
51 Diff current = i;
52 while (i != ind_begin[current])
53 {
54 Index next = ind_begin[current];
55 swap(item_begin[current], item_begin[next]);
56 ind_begin[current] = current;
57 current = next;
58 }
59 ind_begin[current] = current;
60 }
61 }
62
63 /// \fn apply_reverse_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin )
64 /// \brief Reorder item sequence with index sequence order
65 ///
66 /// \param item_begin The start of the item sequence
67 /// \param item_end One past the end of the item sequence
68 /// \param ind_begin The start of the index sequence.
69 ///
70 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
71 /// Complexity: O(N).
72 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
73 void
apply_reverse_permutation(RandomAccessIterator1 item_begin,RandomAccessIterator1 item_end,RandomAccessIterator2 ind_begin,RandomAccessIterator2 ind_end)74 apply_reverse_permutation(
75 RandomAccessIterator1 item_begin,
76 RandomAccessIterator1 item_end,
77 RandomAccessIterator2 ind_begin,
78 RandomAccessIterator2 ind_end)
79 {
80 typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Diff;
81 using std::swap;
82 Diff length = std::distance(item_begin, item_end);
83 for (Diff i = 0; i < length; i++)
84 {
85 while (i != ind_begin[i])
86 {
87 Diff next = ind_begin[i];
88 swap(item_begin[i], item_begin[next]);
89 swap(ind_begin[i], ind_begin[next]);
90 }
91 }
92 }
93
94 /// \fn apply_permutation ( Range1 item_range, Range2 ind_range )
95 /// \brief Reorder item sequence with index sequence order
96 ///
97 /// \param item_range The item sequence
98 /// \param ind_range The index sequence
99 ///
100 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
101 /// Complexity: O(N).
102 template<typename Range1, typename Range2>
103 void
apply_permutation(Range1 & item_range,Range2 & ind_range)104 apply_permutation(Range1& item_range, Range2& ind_range)
105 {
106 apply_permutation(boost::begin(item_range), boost::end(item_range),
107 boost::begin(ind_range), boost::end(ind_range));
108 }
109
110 /// \fn apply_reverse_permutation ( Range1 item_range, Range2 ind_range )
111 /// \brief Reorder item sequence with index sequence order
112 ///
113 /// \param item_range The item sequence
114 /// \param ind_range The index sequence
115 ///
116 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
117 /// Complexity: O(N).
118 template<typename Range1, typename Range2>
119 void
apply_reverse_permutation(Range1 & item_range,Range2 & ind_range)120 apply_reverse_permutation(Range1& item_range, Range2& ind_range)
121 {
122 apply_reverse_permutation(boost::begin(item_range), boost::end(item_range),
123 boost::begin(ind_range), boost::end(ind_range));
124 }
125
126 }}
127 #endif //BOOST_ALGORITHM_APPLY_PERMUTATION_HPP
128