1[/ File apply_permutation.qbk] 2 3[section:apply_permutation apply_permutation] 4 5[/license 6Copyright (c) 2017 Alexander Zaitsev 7 8Distributed under the Boost Software License, Version 1.0. 9(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 10] 11 12The header file [^[link header.boost.algorithm.apply_permutation_hpp apply_permutation.hpp]] contains two algorithms, `apply_permutation` and `apply_reverse_permutation`. There are also range-based versions. 13The algorithms transform the item sequence according to index sequence order. 14 15The routine `apply_permutation` takes a item sequence and a order sequence. It reshuffles item sequence according to order sequence. Every value in order sequence means where the item comes from. Order sequence needs to be exactly a permutation of the sequence [0, 1, ... , N], where N is the biggest index in the item sequence (zero-indexed). 16The routine `apply_reverse_permutation` takes a item sequence and a order sequence. It will reshuffle item sequence according to order sequence. Every value in order sequence means where the item goes to. Order sequence needs to be exactly a permutation of the sequence [0, 1, ... , N], where N is the biggest index in the item sequence (zero-indexed). 17 18Implementations are based on these articles: 19https://blogs.msdn.microsoft.com/oldnewthing/20170102-00/?p=95095 20https://blogs.msdn.microsoft.com/oldnewthing/20170103-00/?p=95105 21https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115 22https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=95145 23https://blogs.msdn.microsoft.com/oldnewthing/20170110-00/?p=95155 24https://blogs.msdn.microsoft.com/oldnewthing/20170111-00/?p=95165 25 26The routines come in 2 forms; the first one takes two iterators to define the item range and one iterator to define the beginning of index range. The second form takes range to define the item sequence and range to define index sequence. 27 28 29[heading interface] 30 31There are two versions of algorithms: 321) takes four iterators. 332) takes two ranges. 34`` 35template<typename RandomAccessIterator1, typename RandomAccessIterator2> 36void apply_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, 37 RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end); 38template<typename Range1, typename Range2> 39void apply_permutation(Range1& item_range, Range2& ind_range); 40template<typename RandomAccessIterator1, typename RandomAccessIterator2> 41void apply_reverse_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end, 42 RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end); 43template<typename Range1, typename Range2> 44void apply_reverse_permutation(Range1& item_range, Range2& ind_range); 45`` 46 47 48[heading Examples] 49 50Given the containers: 51std::vector<int> emp_vec, emp_order, 52std::vector<int> one{1}, one_order{0}, 53std::vector<int> two{1,2}, two_order{1,0}, 54std::vector<int> vec{1, 2, 3, 4, 5}, 55std::vector<int> order{4, 2, 3, 1, 0}, then 56`` 57 58apply_permutation(emp_vec, emp_order)) --> no changes 59apply_reverse_permutation(emp_vec, emp_order)) --> no changes 60apply_permutation(one, one_order) --> no changes 61apply_reverse_permutation(one, one_order) --> no changes 62apply_permutation(two, two_order) --> two:{2,1} 63apply_reverse_permutation(two, two_order) --> two:{2,1} 64apply_permutation(vec, order) --> vec:{5, 3, 4, 2, 1} 65apply_reverse_permutation(vec, order) --> vec:{5, 4, 2, 3, 1} 66`` 67 68[heading Iterator Requirements] 69 70`apply_permutation` and 'apply_reverse_permutation' work only on RandomAccess iterators. RandomAccess iterators required both for item and index sequences. 71 72[heading Complexity] 73 74All of the variants of `apply_permutation` and `apply_reverse_permutation` run in ['O(N)] (linear) time. 75More 76 77[heading Exception Safety] 78 79All of the variants of `apply_permutation` and `apply_reverse_permutation` take their parameters by iterators or reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee. 80 81[heading Notes] 82* If ItemSequence and IndexSequence are not equal, behavior is undefined. 83 84* `apply_permutation` and `apply_reverse_permutation` work also on empty sequences. 85 86* Order sequence must be zero-indexed. 87 88* Order sequence gets permuted. 89 90[endsect] 91 92[/ File apply_permutation.qbk 93Copyright 2017 Alexander Zaitsev 94Distributed under the Boost Software License, Version 1.0. 95(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt). 96] 97