ceph/src/boost/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
  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