]>
Commit | Line | Data |
---|---|---|
92f5a8d4 TL |
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> | |
92f5a8d4 TL |
22 | |
23 | #include <boost/config.hpp> | |
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 | |
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 | |
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 | |
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 | |
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 |