Front Page / Algorithms / Concepts / Reversible Algorithm

# Reversible Algorithm

### Description

A Reversible Algorithm is a member of a pair of transformation algorithms that iterate over their input sequence(s) in opposite directions. For each reversible algorithm `x` there exists a counterpart algorithm `reverse_x`, that exhibits the exact semantics of `x` except that the elements of its input sequence argument(s) are processed in the reverse order.

### Expression requirements

In the following table and subsequent specifications, `x` is a placeholder token for the actual Reversible Algorithm's name, s1,s2,...sn are Forward Sequences, and `in` is an Inserter.

Expression | Type | Complexity
--- | --- | ---
`x<`s1,s2,...sn, ...`>::type` | Forward Sequence | Unspecified.
`x<`s1,s2,...sn, ... `in>::type` | Any type | Unspecified.
`reverse_x<`s1,s2,...sn, ...`>::type` | Forward Sequence | Unspecified.
`reverse_x<`s1,s2,...sn, ... `in>::type` | Any type | Unspecified.

### Expression semantics

    typedef x<s1,s2,...sn,...>::type t;

Precondition: | s1 is an Extensible Sequence.

Semantics:

`t` is equivalent to

    x<
          s1,s2,...sn,...
        , back_inserter< clear<s1>::type >
        >::type

if `has_push_back<`s1`>::value == true` and

    reverse_x<
          s1,s2,...sn,...
        , front_inserter< clear<s1>::type >
        >::type

otherwise.

    typedef x<s1,s2,...sn,...in>::type t;

Semantics: | `t` is the result of an `x` invocation with arguments s1,s2,... sn,...`in`.

    typedef reverse_x<s1,s2,... sn,... >::type t;

Precondition: | s1 is an Extensible Sequence.

Semantics:

`t` is equivalent to

    x<
          s1,s2,...sn,...
        , front_inserter< clear<s1>::type >
        >::type

if `has_push_front<`s1`>::value == true` and

    reverse_x<
          s1,s2,...sn,...
        , back_inserter< clear<s1>::type >
        >::type

otherwise.

    typedef reverse_x<s1,s2,...sn,... in>::type t;

Semantics: | `t` is the result of a `reverse_x` invocation with arguments s1,s2,...sn,...`in`.

### Example

    typedef transform<
          range_c<int,0,10>
        , plus<_1,int_<7> >
        , back_inserter< vector0<> >
        >::type r1;

    typedef transform< r1, minus<_1,int_<2> > >::type r2;
    typedef reverse_transform<
          r2
        , minus<_1,5>
        , front_inserter< vector0<> >
        >::type r3;

    BOOST_MPL_ASSERT(( equal<r1, range_c<int,7,17> > ));
    BOOST_MPL_ASSERT(( equal<r2, range_c<int,5,15> > ));
    BOOST_MPL_ASSERT(( equal<r3, range_c<int,0,10> > ));

### Models

- `transform`
- `remove`
- `replace`

### See also

Transformation Algorithms, Inserter