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

See also

Transformation Algorithms, Inserter