## Exercising Ranges (part 3)

(Start at the beginning of the series if you want more context.)

So, I was going to implement `monoidal_zip`

, and to do that, I would clone zip_with.hpp. So I did that. Eric’s a great library author, and the ranges code is pretty easy to read. For the most part I found it concise, well-expressed and clear. The parts I didn’t immediately understand were owing to my own (temporary) ignorance and not a result of murky code.

Since `zip_with`

takes N ranges and an n-ary function, it’s written with variadic templates and folding operations over parameter packs. A monoid by definition only uses a binary operation, so I immediately simplified that. Then I worked through each part of the file, adapting it to my use case.

**Range cardinality**

The first things in zip_with.hpp are a bunch of `constexpr`

functions in a detail namespace, and then a cardinality calculation. Range cardinality turns out to be an enumeration with three members – `infinite`

(-3), `unknown`

(-2), and `finite`

(-1) – and then a value of zero or above is a known cardinality such as might be obtained at compile-time from an array.

Aside: I didn’t think about/realise until much later that the cardinality of a vector isn’t known at compile time. Perhaps it could be in some cases – a shortcoming of the STL re `constexpr`

?

In the case of known cardinalities, `zip_with`

uses the minimum of the N ranges; I needed the maximum. Simple, if verbose to deal with the other possible enum values.

namespace detail { template<typename C1, typename C2> using monoidal_zip_cardinality = std::integral_constant<cardinality, C1::value == infinite || C2::value == infinite ? infinite : C1::value == unknown || C2::value == unknown ? unknown : C1::value >= 0 && C2::value >= 0 ? max_(C1::value, C2::value) : finite>; } // namespace detail |

(The function `max_`

is one of Eric’s existing `constexpr`

functions in zip_with.hpp.)

**Cursors and sentinels**

The main work in writing any view is of course, defining the `cursor`

and the `sentinel`

(internal representations of iterators: the view provides `begin_cursor`

and `end_cursor`

functions – in const and mutable forms – which return a `cursor`

and a `sentinel`

respectively).

There are a few simplifying implementation patterns I found in several views that I adopted. Commonly the `cursor`

and the `sentinel`

are templated on a bool representing constness. And it’s also common for the cursor to need a pointer back to the range it’s iterating over, and that pointer needs the right constness, so we end up with code like:

template<typename Fun, typename R1, typename R2> struct iter_monoidal_zip_view : view_facade<iter_monoidal_zip_view<Fun, R1, R2>, detail::monoidal_zip_cardinality<range_cardinality<R1>, range_cardinality<R2>>::value> { ... template <bool IsConst> struct cursor { ... private: friend struct sentinel<IsConst>; // add a const if I am const template <typename T> using constify_if = meta::apply<meta::add_const_if_c<IsConst>, T>; // pointer to my view using monoidal_zip_view_t = constify_if<iter_monoidal_zip_view>; monoidal_zip_view_t *rng_; // iterators I use range_iterator_t<constify_if<R1>> it1_; range_iterator_t<constify_if<R2>> it2_; ... }; ... }; |

**Satisfying the Concepts**

I wanted a reversible range. That meant I needed my `cursor`

to be bidirectional. Every cursor must implement `current`

, `next`

and `equal`

, and of course a bidirectional cursor must implement `prev`

:

auto current() const; void next(); void prev(); bool equal(cursor const& that) const; |

Every sentinel implements comparison with a cursor:

bool equal(cursor<IsConst> const &pos) const; |

And the range itself implements `begin_cursor`

and `end_cursor`

, with `end_cursor`

returning either a cursor or a sentinel depending on whether the underlying ranges are bounded:

using are_bounded_t = meta::and_c<(bool) BoundedRange<R1>(), (bool) BoundedRange<R2>()>; cursor<false> begin_cursor() { return {*this, fun_, begin_tag{}}; } meta::if_<are_bounded_t, cursor<false>, sentinel<false>> end_cursor() { return {*this, fun_, end_tag{}}; } |

(I omitted the const versions of these functions which use the `CONCEPT_REQUIRES`

macro as a nice wrapper for `enable_if`

style functionality.)

**Nice conventions**

In order that views work on containers-as-ranges, various views simply use `view::all`

to turn whatever container is passed in into a range. If actual ranges are passed in, `view::all`

just forwards them, unaffected. This is very handy.

There is a convention in the ranges code that deals with reporting concept violations to the user: separate out the concept as a template alias, eg:

template<typename Fun, typename R1, typename R2> using Concept = meta::and_< InputRange<R1>, InputRange<R2>, Callable<Fun, range_reference_t<R1> &&, range_reference_t<R2> &&>>; |

And write the required function with an overloaded version which uses the CONCEPT_REQUIRES_ macro in an inverted sense from the “normal” version:

// "normal" version template<typename R1, typename R2, typename Fun, CONCEPT_REQUIRES_(Concept<Fun, R1, R2>())> monoidal_zip_view<Fun, all_t<R1>, all_t<R2>> operator()( Fun fun, R1 && r1, R2 && r2) const { ... } // "concept failed" version template<typename Fun, typename R1, typename R2, CONCEPT_REQUIRES_(!Concept<Fun, R1, R2>())> void operator()(Fun, R1 &&, R2 &&) const { CONCEPT_ASSERT_MESSAGE(...); } |

**The actual work**

So, how does the cursor actually work? The idea is fairly simple. Keep an iterator to each range that the view is considering. Usually they advance together. When we run out of one range, keep track of the difference between the iterators, to enable reverse iteration. The rest is bookkeepping. (Error-prone, exacting bookkeeping: I didn’t get reverse iteration working properly until I gave the whole thing a proper workout with unit tests. Off-by-one errors, one of the three hardest things in computer science.)

The `monoidal_zip`

view’s `begin`

is when both iterators are at their respective `begin`

s, and the corresponding thing is true for `end`

. You can find the implementation on github – it’s too much for an already long post.

Writing `current`

is easy, we just need to check the iterators to do the monoid identity thing if needed:

auto current() const RANGES_DECLTYPE_AUTO_RETURN_NOEXCEPT ( diff_ == 0 ? fun_(it1_, it2_) : diff_ > 0 ? *it1_ : *it2_ ) |

And that’s it. Now we have `monoidal_zip`

, which fulfils the needs of adding power series (and also subtracting them). It works on anything that’s a monoid, not just addition. And it’s reversible. In implementing this, I discovered that the result of reversing `zip_with`

may be surprising: because the ranges are lazily traversed, effectively it’s as if the ranges were reversed *inside* the zip. If the ranges are different lengths, that may not be what you want, but if you think about it, it sort of has to be that way?

After that lengthy workout, in the next instalment something easier: pretty-printing power series.

July 1st, 2015 at 11:12 pm

> In implementing this, I discovered that the result of reversing

> zip_with may be surprising: because the ranges are lazily

> traversed, effectively it’s as if the ranges were reversed inside

> the zip. If the ranges are different lengths, that may not be

> what you want

Huh. I had never considered that. It might be a precondition on the decrement operator of the end iterator that the ranges are of equal lengths. It’s weird.