Monday, December 13, 2010

Range adaptors

Range adaptors

I seem to like doing blogs in series... (Or ranges ;-) .) See my previous blog about ranges here. This is a short bonus.

Since Boost 1.43 released in May 2010, just before BoostCon'10, the Boost.Range library has Range Adaptors. Range adaptors enable users to change range behaviour on the fly, for example traverse it in reverse order.

Reversing through geometries

See this small and working snippet.

using namespace boost;
geometry::model::linestring<P> ls;
geometry::read_wkt("linestring(1 1,2 2,3 3,4 4)", ls);
std::cout << geometry::wkt(ls) << std::endl;
std::cout << geometry::wkt(ls | adaptors::reversed) << std::endl;

This  will print out:

LINESTRING(1 1,2 2,3 3,4 4)
LINESTRING(4 4,3 3,2 2,1 1)

So the original one and the reversed one. Works great, and great syntax.

To let this work, I had to adapt the Boost.Range reverse_range to Boost.Geometry, such that Boost.Geometry knows the adapted range is a linestring. In this case it is a linestring, but it might also be a ring (also a range) or a multi-point (also a range), etc. So I adapted it like this:

namespace traits

template<typename Geometry>
struct tag<boost::range_detail::reverse_range<Geometry> >
    typedef typename geometry::tag<Geometry>::type type;


Just meta-programming, if a reverse_range is specified, it defines its tag as it is for the unreversed geometry. This should work for all these geometries because all of them are very light-weight, essentially only requiring the tag metafunction in namespace traits. (Well, one exception, the linear_ring (ring for short) also might optionally define point order and closure.)

We do the same for the other Boost.Range adaptors, where relevant, and then have filtered, sliced, strided, uniqued, reversed all out of the box. Great! I already liked Boost.Range, and this new feature is cool either.

Why ranges are cool, revisited

We see here again why ranges can be preferred above iterators, and make some other statements:

First we state in another way (than in the previous blog) that ranges are like normal objects:
Ranges are first class citizens, while iterators should be implementation details

And then we make a statement about the cool adaptors we encountered in Boost.Range:
A range allows overloading operators, in contrast with iterators


Before ranges were there in May 2010, I developed a small utility class called reversed_view, where ranges are traversed in either forward or backward direction.

This reversed_view class is still there, but now greatly simplified, the reverse one expressed in terms of the reversed_range adaptor. It is now defined like this:

enum iterate_direction { iterate_forward, iterate_reverse };

template <typename Range, iterate_direction Direction>
struct reversible_view {};

template <typename Range>
struct reversible_view<Range, iterate_forward>
    typedef identity_view<Range> type;

template <typename Range>
struct reversible_view<Range, iterate_reverse>
    typedef boost::range_detail::reverse_range<Range> type;

All meta-functions. Seeming empty classes, but of great value. In the first version it were not meta-functions but normal classes, derived from something or defining something. Therefore they needed an own constructor etc. These are only typedef's, do not define any code, therefore simpler and therefore better. In this case they exist because templated typedefs are not there.


Boost.Geometry also has a closeable view but alas I didn't find this in Boost.Range adaptors, for obvious reasons (the adaptors strip, replace or adapt, but do not add things). So the closeable_view is still there, but now also expressed as meta-functions, the actively-closing one is a real implementation, the already-closed on is another type definition.


  1. Just wanted to say that your posts about meta-functions etc rock