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
  using monoidal_zip_cardinality =
    std::integral_constant= 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
struct iter_monoidal_zip_view
  : view_facade,
                detail::monoidal_zip_cardinality,
                                                 range_cardinality>::value>
{
  ...
  template 
  struct cursor
  {
    ...
  private:
    friend struct sentinel;
    // add a const if I am const
    template 
    using constify_if = meta::apply, T>;
    // pointer to my view
    using monoidal_zip_view_t = constify_if;
    monoidal_zip_view_t *rng_;
    // iterators I use
    range_iterator_t> it1_;
    range_iterator_t> 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 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(),
                                    (bool) BoundedRange()>;

  cursor begin_cursor()
  {
    return {*this, fun_, begin_tag{}};
  }
  meta::if_, sentinel>
  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
using Concept = meta::and_<
  InputRange, InputRange,
  Callable &&, range_reference_t &&>>;

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())>
monoidal_zip_view, all_t> operator()(
    Fun fun, R1 && r1, R2 && r2) const
{ ... }

// "concept failed" version
template())>
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 begins, 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.