libs/algorithm/doc/apply_permutation.qbk

   1 [/ File apply_permutation.qbk]
   2
   3 [section:apply_permutation apply_permutation]
   4
   5 [/license
   6 Copyright (c) 2017 Alexander Zaitsev
   7
   8 Distributed 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
  12 The 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.
  13 The algorithms transform the item sequence according to index sequence order.
  14
  15 The 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).
  16 The 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
  18 Implementations are based on these articles:
  19 https://blogs.msdn.microsoft.com/oldnewthing/20170102-00/?p=95095
  20 https://blogs.msdn.microsoft.com/oldnewthing/20170103-00/?p=95105
  21 https://blogs.msdn.microsoft.com/oldnewthing/20170104-00/?p=95115
  22 https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=95145
  23 https://blogs.msdn.microsoft.com/oldnewthing/20170110-00/?p=95155
  24 https://blogs.msdn.microsoft.com/oldnewthing/20170111-00/?p=95165
  25
  26 The 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
  31 There are two versions of algorithms:
  32 1) takes four iterators.
  33 2) takes two ranges.
  34 ``
  35 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
  36 void apply_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end,
  37                   RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end);
  38 template<typename Range1, typename Range2>
  39 void apply_permutation(Range1& item_range, Range2& ind_range);
  40 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
  41 void apply_reverse_permutation(RandomAccessIterator1 item_begin, RandomAccessIterator1 item_end,
  42                   RandomAccessIterator2 ind_begin, RandomAccessIterator2 ind_end);
  43 template<typename Range1, typename Range2>
  44 void apply_reverse_permutation(Range1& item_range, Range2& ind_range);
  45 ``
  46
  47
  48 [heading Examples]
  49
  50 Given the containers:
  51 std::vector<int> emp_vec, emp_order,
  52 std::vector<int> one{1}, one_order{0},
  53 std::vector<int> two{1,2}, two_order{1,0},
  54 std::vector<int> vec{1, 2, 3, 4, 5},
  55 std::vector<int> order{4, 2, 3, 1, 0}, then
  56 ``
  57
  58 apply_permutation(emp_vec, emp_order))  --> no changes
  59 apply_reverse_permutation(emp_vec, emp_order))  --> no changes
  60 apply_permutation(one, one_order)  --> no changes
  61 apply_reverse_permutation(one, one_order)  --> no changes
  62 apply_permutation(two, two_order)  --> two:{2,1}
  63 apply_reverse_permutation(two, two_order)  --> two:{2,1}
  64 apply_permutation(vec, order)  --> vec:{5, 3, 4, 2, 1}
  65 apply_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
  74 All of the variants of `apply_permutation` and `apply_reverse_permutation` run in ['O(N)] (linear) time.
  75 More
  76
  77 [heading Exception Safety]
  78
  79 All 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
  93 Copyright 2017 Alexander Zaitsev
  94 Distributed 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 ]