1.. Algorithms/Concepts//Reversible Algorithm 2 3Reversible Algorithm 4==================== 5 6Description 7----------- 8 9A |Reversible Algorithm| is a member of a pair of 10transformation algorithms that iterate over their input sequence(s) 11in opposite directions. For each reversible 12algorithm ``x`` there exists a *counterpart* algorithm ``reverse_x``, 13that exhibits the exact semantics of ``x`` except that the elements 14of its input sequence argument(s) are processed in the reverse 15order. 16 17 18Expression requirements 19----------------------- 20 21.. |s1...sn| replace:: *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n` 22 23.. |s1...sn>::type| replace:: |s1...sn|, ...\ ``>::type`` 24.. |s1...sn,in>::type| replace:: |s1...sn|, ... ``in>::type`` 25 26|In the following table...| ``x`` is a placeholder token for the actual 27|Reversible Algorithm|'s name, |s1...sn| are 28|Forward Sequence|\ s, and ``in`` is an |Inserter|. 29 30+---------------------------------------+-----------------------+-------------------+ 31| Expression | Type | Complexity | 32+=======================================+=======================+===================+ 33|``x<``\ |s1...sn>::type| | |Forward Sequence| | Unspecified. | 34+---------------------------------------+-----------------------+-------------------+ 35|``x<``\ |s1...sn,in>::type| | Any type | Unspecified. | 36+---------------------------------------+-----------------------+-------------------+ 37|``reverse_x<``\ |s1...sn>::type| | |Forward Sequence| | Unspecified. | 38+---------------------------------------+-----------------------+-------------------+ 39|``reverse_x<``\ |s1...sn,in>::type| | Any type | Unspecified. | 40+---------------------------------------+-----------------------+-------------------+ 41 42 43Expression semantics 44-------------------- 45 46.. parsed-literal:: 47 48 typedef x<\ *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,...>::type t; 49 50:Precondition: 51 *s*\ :sub:`1` is an |Extensible Sequence|. 52 53:Semantics: 54 ``t`` is equivalent to 55 56 .. parsed-literal:: 57 58 x< 59 *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,... 60 , back_inserter< clear<\ *s*\ :sub:`1`>::type > 61 >::type 62 63 if ``has_push_back<``\ *s*\ :sub:`1`\ ``>::value == true`` and 64 65 .. parsed-literal:: 66 67 reverse_x< 68 *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,... 69 , front_inserter< clear<\ *s*\ :sub:`1`>::type > 70 >::type 71 72 otherwise. 73 74.. .......................................................................... 75 76 77.. parsed-literal:: 78 79 typedef x<\ *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,...\ in>::type t; 80 81:Semantics: 82 ``t`` is the result of an ``x`` invocation with arguments 83 *s*\ :sub:`1`,\ *s*\ :sub:`2`,... \ *s*\ :sub:`n`,...\ ``in``. 84 85 86.. .......................................................................... 87 88 89.. parsed-literal:: 90 91 typedef reverse_x<\ *s*\ :sub:`1`,\ *s*\ :sub:`2`,... \ *s*\ :sub:`n`,... >::type t; 92 93:Precondition: 94 *s*\ :sub:`1` is an |Extensible Sequence|. 95 96:Semantics: 97 ``t`` is equivalent to 98 99 .. parsed-literal:: 100 101 x< 102 *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,... 103 , front_inserter< clear<\ *s*\ :sub:`1`>::type > 104 >::type 105 106 if ``has_push_front<``\ *s*\ :sub:`1`\ ``>::value == true`` and 107 108 .. parsed-literal:: 109 110 reverse_x< 111 *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,... 112 , back_inserter< clear<\ *s*\ :sub:`1`>::type > 113 >::type 114 115 otherwise. 116 117 118.. .......................................................................... 119 120.. parsed-literal:: 121 122 typedef reverse_x<\ *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,... in>::type t; 123 124:Semantics: 125 ``t`` is the result of a ``reverse_x`` invocation with arguments 126 *s*\ :sub:`1`,\ *s*\ :sub:`2`,...\ *s*\ :sub:`n`,...\ ``in``. 127 128 129Example 130------- 131 132.. parsed-literal:: 133 134 typedef transform< 135 range_c<int,0,10> 136 , plus<_1,int_<7> > 137 , back_inserter< vector0<> > 138 >::type r1; 139 140 typedef transform< r1, minus<_1,int_<2> > >::type r2; 141 typedef reverse_transform< 142 r2 143 , minus<_1,5> 144 , front_inserter< vector0<> > 145 >::type r3; 146 147 BOOST_MPL_ASSERT(( equal<r1, range_c<int,7,17> > )); 148 BOOST_MPL_ASSERT(( equal<r2, range_c<int,5,15> > )); 149 BOOST_MPL_ASSERT(( equal<r3, range_c<int,0,10> > )); 150 151 152Models 153------ 154 155* |transform| 156* |remove| 157* |replace| 158 159See also 160-------- 161 162|Transformation Algorithms|, |Inserter| 163 164 165.. copyright:: Copyright � 2001-2009 Aleksey Gurtovoy and David Abrahams 166 Distributed under the Boost Software License, Version 1.0. (See accompanying 167 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 168