projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | .. Algorithms/Concepts//Reversible Algorithm |
| 2 | ||
| 3 | Reversible Algorithm | |
| 4 | ==================== | |
| 5 | ||
| 6 | Description | |
| 7 | ----------- | |
| 8 | ||
| 9 | A |Reversible Algorithm| is a member of a pair of | |
| 10 | transformation algorithms that iterate over their input sequence(s) | |
| 11 | in opposite directions. For each reversible | |
| 12 | algorithm ``x`` there exists a *counterpart* algorithm ``reverse_x``, | |
| 13 | that exhibits the exact semantics of ``x`` except that the elements | |
| 14 | of its input sequence argument(s) are processed in the reverse | |
| 15 | order. | |
| 16 | ||
| 17 | ||
| 18 | Expression 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 | ||
| 43 | Expression 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 | ||
| 129 | Example | |
| 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 | ||
| 152 | Models | |
| 153 | ------ | |
| 154 | ||
| 155 | * |transform| | |
| 156 | * |remove| | |
| 157 | * |replace| | |
| 158 | ||
| 159 | See also | |
| 160 | -------- | |
| 161 | ||
| 162 | |Transformation Algorithms|, |Inserter| | |
| 163 | ||
| 164 | ||
| 165 |