boost/algorithm/apply_permutation.hpp

0001 /*
0002   Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.com>, 2017
0003
0004   Distributed under the Boost Software License, Version 1.0. (See
0005   accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt)
0007
0008   See http://www.boost.org/ for latest version.
0009
0010
0011   Based on https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115
0012 */
0013
0014 /// \file  apply_permutation.hpp
0015 /// \brief Apply permutation to a sequence.
0016 /// \author Alexander Zaitsev
0017
0018 #ifndef BOOST_ALGORITHM_APPLY_PERMUTATION_HPP
0019 #define BOOST_ALGORITHM_APPLY_PERMUTATION_HPP
0020
0021 #include <algorithm>
0022
0023 #include <boost/config.hpp>
0024 #include <boost/range/begin.hpp>
0025 #include <boost/range/end.hpp>
0026
0027 namespace boost { namespace algorithm
0028 {
0029
0030 /// \fn apply_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin )
0031 /// \brief Reorder item sequence with index sequence order
0032 ///
0033 /// \param item_begin    The start of the item sequence
0034 /// \param item_end      One past the end of the item sequence
0035 /// \param ind_begin     The start of the index sequence.
0036 ///
0037 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
0038 ///       Complexity: O(N).
0039 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
0040 void
0041 apply_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end,
0042                   RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end)
0043 {
0044     typedef typename std::iterator_traits<RandomAccessIterator1>::difference_type Diff;
0045     typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Index;
0046     using std::swap;
0047     Diff size = std::distance(item_begin, item_end);
0048     for (Diff i = 0; i < size; i++)
0049     {
0050         Diff current = i;
0051         while (i != ind_begin[current])
0052         {
0053             Index next = ind_begin[current];
0054             swap(item_begin[current], item_begin[next]);
0055             ind_begin[current] = current;
0056             current = next;
0057         }
0058         ind_begin[current] = current;
0059     }
0060 }
0061
0062 /// \fn apply_reverse_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin )
0063 /// \brief Reorder item sequence with index sequence order
0064 ///
0065 /// \param item_begin    The start of the item sequence
0066 /// \param item_end      One past the end of the item sequence
0067 /// \param ind_begin     The start of the index sequence.
0068 ///
0069 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
0070 ///       Complexity: O(N).
0071 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
0072 void
0073 apply_reverse_permutation(
0074         RandomAccessIterator1 item_begin,
0075         RandomAccessIterator1 item_end,
0076         RandomAccessIterator2 ind_begin,
0077         RandomAccessIterator2 ind_end)
0078 {
0079     typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Diff;
0080     using std::swap;
0081     Diff length = std::distance(item_begin, item_end);
0082     for (Diff i = 0; i < length; i++)
0083     {
0084         while (i != ind_begin[i])
0085         {
0086             Diff next = ind_begin[i];
0087             swap(item_begin[i], item_begin[next]);
0088             swap(ind_begin[i], ind_begin[next]);
0089         }
0090     }
0091 }
0092
0093 /// \fn apply_permutation ( Range1 item_range, Range2 ind_range )
0094 /// \brief Reorder item sequence with index sequence order
0095 ///
0096 /// \param item_range    The item sequence
0097 /// \param ind_range     The index sequence
0098 ///
0099 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
0100 ///       Complexity: O(N).
0101 template<typename Range1, typename Range2>
0102 void
0103 apply_permutation(Range1& item_range, Range2& ind_range)
0104 {
0105     apply_permutation(boost::begin(item_range), boost::end(item_range),
0106                       boost::begin(ind_range), boost::end(ind_range));
0107 }
0108
0109 /// \fn apply_reverse_permutation ( Range1 item_range, Range2 ind_range )
0110 /// \brief Reorder item sequence with index sequence order
0111 ///
0112 /// \param item_range    The item sequence
0113 /// \param ind_range     The index sequence
0114 ///
0115 /// \note Item sequence size should be equal to index size. Otherwise behavior is undefined.
0116 ///       Complexity: O(N).
0117 template<typename Range1, typename Range2>
0118 void
0119 apply_reverse_permutation(Range1& item_range, Range2& ind_range)
0120 {
0121     apply_reverse_permutation(boost::begin(item_range), boost::end(item_range),
0122                               boost::begin(ind_range), boost::end(ind_range));
0123 }
0124
0125 }}
0126 #endif //BOOST_ALGORITHM_APPLY_PERMUTATION_HPP