[boost] rtl (Range Template Library)

From: John Torjo (john.lists_at_[hidden])
Date: 2003-11-19 15:07:44

Dear boosters,

Matt Wilson and me have developed the rtl (Range template library), in order
to ease working with iterators/container.

So far, it's been compiled and tested with CodeWarrior 8.0, Comeau 4.3.2,
GCC 3.2, VC6, and VC7.1. It does not work with Borland, though we expect to
get workarounds for its tragic failings happening in the near future.

To get you interested, heres' some code that works at this time:

std::ifstream in( "./using_resort.cpp");
std::vector< std::string> words;
// read all words from the file, and insert them into the array
rng::copy( istream_range<std::string>(in), std::back_inserter(words));

// resorts the words, case insensitive, then filters only those that begin
with letter 'b',
// and shows them in uppercase (the original array - words is NOT modified)
rng::copy( transformed_f( filtered( resorted(words, less_insensitive),
begins_with_b), in_uppercase),
    std::ostream_iterator<std::string>(std::cout," ") );

The rtl (Range Template Library) is meant to ease working with iterators and
containers.
The purpose of RTL is to eliminate redundant code.
Example:
Instead of the redundant:
std::copy( cont.begin(), const.end(), wherever);
you could simply write:
rng::copy( cont, wherever);

Of course, real code is much more complicated, so using rtl will usually
save you quite
a few keystrokes, and the code will be more readable.

The rtl consists of the following big parts:
1. range classes
2. range algorithms
3. range adaptors

1. range classes
A range is roughly a pair of iterators.

A range class exposes the following:
* the begin() and end() functions.
  There is only one begin() function and one end() function
  (no different const/non-const versions).
* typedefs for 'iterator', 'value_type', 'reference', 'pointer'.
  These are taken from the underlying iterator.
  There's no const_iterator, const_reference, etc, since a range
  is just a pair of iterators. So, if the iterator is const,
  'iterator', 'value_type', 'reference' and 'pointer' will reflect that.

A range can be used in STL algorithms (shown below), or you can
decide to manually walk through it. Walking through a range is a blast.
Example:

typedef std::vector<int> array;
array v;
// ... fill it
crange<const array> r(v);
while( r)
    std::cout << *r++ << std::endl;

You can also manually set the beginning and end of a range:
// ignore first and last 5 elements
r.begin( v.begin() + 5);
r.end( v.end() - 5);
while( r)
    std::cout << *r++ << std::endl;

The basic range classes are:
template< class container> class crange;
template< class iterator> class irange;

Examples of usage:
crange< const container> r(...); // const range
crange< container> nr( ...); // non-const range
irange< iterator_type> ir(...); // from iterator

A range can be created from a container/const container/2 iterators.
crange< container> r( cont); // const or non-const container
crange< container> r( beg, end); // two iterators

A range preserves the underlying iterator properties.

Every overloaded operator applied to the range modifies the begin iterator.
The end() is never modified. Thus, we allow for:
while( r)
    std::cout << *r++ << std::endl;

2. range algorithms
All STL algorithms are implemented for ranges as well.
(note: currently we have not implemented mismatch and partial_sort_copy).

For the purpose of ALL range algorithms, a container IS a range.
Therefore, the following is possible:

typedef std::list<int> array;
array l;
l.resize( 50);
rng::generate( l, next() ); // next() is a functor
rng::reverse( l);
// prints the given list to console
rng::copy( l, std::ostream_iterator<int>(std::cout," ") );

Some algorithms return ranges (ex: rng::find_if), but this will be discussed
in more details another time.

3. range adaptors.
A lot of iterator classes have been written so far, that adapt existing
iterators/containers.
In other words, given an iterator class X, you can have an adaptor_class<X>,
which
takes the original iterator, transforms it in some way, and returs that
result.

They have been difficult to use, especially because you will need to type a
lot of redundant code.

Example:
bool is_even(int i) { return (i%2) == 0; }

typedef std::vector<int> array;
array v;
// ... fill it
filter_iterator< bool(*)(int), array::const_iterator> beg( &is_even,
v.begin(), v.end() );
filter_iterator< bool(*)(int), array::const_iterator> end( &is_even,
v.end(), v.end() );
// copy only even numbers
std::copy( beg, end, wherever);

By adapting existing iterator classes to ranges, you get simpler and more
readable code.
The above can be written as:
rng::copy( filtered(v,&is_even), wherever);

We have provided adaptors for existing classes found in <boost/iterator>:
* filtered (adaptor for ::boost::filter_iterator)
* reversed (adaptor for ::boost::reverse_iterator)
* indirected (adaptor for ::boost::indirect_iterator)
* transformed (adaptor for ::boost::transform_iterator)
* resorted (creates a view of the container, by resorting it in some way.
  The original container remains unchanged, while the range is the one
  that is internally re-sorted)
* generated - adapts a function/functor object, creating an range of two
  input iterators. It's quite cool. For instance, you can create a range
  with the first 20 fibonacci numbers, like this:
  generated(fibonacci(), gen_n(20)); // see example

(you'll find examples for each type of adaptor)

There's are more features we want to implement, but the library is usable.

We are also still debating the precise definition of the Range Concept,
and anticipate that your opinions will help cement the matter. We're hoping
that the range concept can be applied to other languages, and are envisaging
looking at C#(.NET) and D at a future time.

Help and interest is deeply appreciated.

Best,
John, Matthew

P.S. comeau gives quite a few warnings:
"initial value of reference to non-const must be an lvalue", although we
think they're unjustified.
Any help is deeply appreciated.