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
23#include <boost/config.hpp>
24#include <boost/range/begin.hpp>
25#include <boost/range/end.hpp>
26
27namespace 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).
39template<typename RandomAccessIterator1, typename RandomAccessIterator2>
40void
41apply_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).
71template<typename RandomAccessIterator1, typename RandomAccessIterator2>
72void
73apply_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).
101template<typename Range1, typename Range2>
102void
103apply_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).
117template<typename Range1, typename Range2>
118void
119apply_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

source code of boost/libs/algorithm/include/boost/algorithm/apply_permutation.hpp