diff options
Diffstat (limited to 'src/third_party/boost-1.69.0/boost/algorithm/apply_permutation.hpp')
-rw-r--r-- | src/third_party/boost-1.69.0/boost/algorithm/apply_permutation.hpp | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/src/third_party/boost-1.69.0/boost/algorithm/apply_permutation.hpp b/src/third_party/boost-1.69.0/boost/algorithm/apply_permutation.hpp new file mode 100644 index 00000000000..b9de0ded7bb --- /dev/null +++ b/src/third_party/boost-1.69.0/boost/algorithm/apply_permutation.hpp @@ -0,0 +1,126 @@ +/* + Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.com>, 2017 + + Distributed under the Boost Software License, Version 1.0. (See + accompanying file LICENSE_1_0.txt or copy at + http://www.boost.org/LICENSE_1_0.txt) + + See http://www.boost.org/ for latest version. + + + Based on https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115 +*/ + +/// \file apply_permutation.hpp +/// \brief Apply permutation to a sequence. +/// \author Alexander Zaitsev + +#ifndef BOOST_ALGORITHM_APPLY_PERMUTATION_HPP +#define BOOST_ALGORITHM_APPLY_PERMUTATION_HPP + +#include <algorithm> +#include <type_traits> + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm +{ + +/// \fn apply_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin ) +/// \brief Reorder item sequence with index sequence order +/// +/// \param item_begin The start of the item sequence +/// \param item_end One past the end of the item sequence +/// \param ind_begin The start of the index sequence. +/// +/// \note Item sequence size should be equal to index size. Otherwise behavior is undefined. +/// Complexity: O(N). +template<typename RandomAccessIterator1, typename RandomAccessIterator2> +void +apply_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, + RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end) +{ + typedef typename std::iterator_traits<RandomAccessIterator1>::difference_type Diff; + typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Index; + using std::swap; + Diff size = std::distance(item_begin, item_end); + for (Diff i = 0; i < size; i++) + { + Diff current = i; + while (i != ind_begin[current]) + { + Index next = ind_begin[current]; + swap(item_begin[current], item_begin[next]); + ind_begin[current] = current; + current = next; + } + ind_begin[current] = current; + } +} + +/// \fn apply_reverse_permutation ( RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, RandomAccessIterator2 ind_begin ) +/// \brief Reorder item sequence with index sequence order +/// +/// \param item_begin The start of the item sequence +/// \param item_end One past the end of the item sequence +/// \param ind_begin The start of the index sequence. +/// +/// \note Item sequence size should be equal to index size. Otherwise behavior is undefined. +/// Complexity: O(N). +template<typename RandomAccessIterator1, typename RandomAccessIterator2> +void +apply_reverse_permutation( + RandomAccessIterator1 item_begin, + RandomAccessIterator1 item_end, + RandomAccessIterator2 ind_begin, + RandomAccessIterator2 ind_end) +{ + typedef typename std::iterator_traits<RandomAccessIterator2>::difference_type Diff; + using std::swap; + Diff length = std::distance(item_begin, item_end); + for (Diff i = 0; i < length; i++) + { + while (i != ind_begin[i]) + { + Diff next = ind_begin[i]; + swap(item_begin[i], item_begin[next]); + swap(ind_begin[i], ind_begin[next]); + } + } +} + +/// \fn apply_permutation ( Range1 item_range, Range2 ind_range ) +/// \brief Reorder item sequence with index sequence order +/// +/// \param item_range The item sequence +/// \param ind_range The index sequence +/// +/// \note Item sequence size should be equal to index size. Otherwise behavior is undefined. +/// Complexity: O(N). +template<typename Range1, typename Range2> +void +apply_permutation(Range1& item_range, Range2& ind_range) +{ + apply_permutation(boost::begin(item_range), boost::end(item_range), + boost::begin(ind_range), boost::end(ind_range)); +} + +/// \fn apply_reverse_permutation ( Range1 item_range, Range2 ind_range ) +/// \brief Reorder item sequence with index sequence order +/// +/// \param item_range The item sequence +/// \param ind_range The index sequence +/// +/// \note Item sequence size should be equal to index size. Otherwise behavior is undefined. +/// Complexity: O(N). +template<typename Range1, typename Range2> +void +apply_reverse_permutation(Range1& item_range, Range2& ind_range) +{ + apply_reverse_permutation(boost::begin(item_range), boost::end(item_range), + boost::begin(ind_range), boost::end(ind_range)); +} + +}} +#endif //BOOST_ALGORITHM_APPLY_PERMUTATION_HPP |