boost/algorithm/apply_permutation.hpp

   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
  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
  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
 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
 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