{"id":1130,"date":"2015-07-01T00:26:56","date_gmt":"2015-07-01T07:26:56","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1130"},"modified":"2015-07-01T23:08:31","modified_gmt":"2015-07-02T06:08:31","slug":"exercising-ranges-part-3","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1130","title":{"rendered":"Exercising Ranges (part 3)"},"content":{"rendered":"

(Start at the beginning of the series<\/a> if you want more context.)<\/p>\n

So, I was going to implement monoidal_zip<\/code>, 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.<\/p>\n

Since zip_with<\/code> 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.<\/p>\n

Range cardinality<\/strong><\/p>\n

The first things in zip_with.hpp are a bunch of constexpr<\/code> functions in a detail namespace, and then a cardinality calculation. Range cardinality turns out to be an enumeration with three members – infinite<\/code> (-3), unknown<\/code> (-2), and finite<\/code> (-1) – and then a value of zero or above is a known cardinality such as might be obtained at compile-time from an array. <\/p>\n

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<\/code>?<\/p>\n

In the case of known cardinalities, zip_with<\/code> uses the minimum of the N ranges; I needed the maximum. Simple, if verbose to deal with the other possible enum values.<\/p>\n

\r\nnamespace detail\r\n{\r\n  template\r\n  using monoidal_zip_cardinality =\r\n    std::integral_constant= 0 && C2::value >= 0 ?\r\n            max_(C1::value, C2::value) :\r\n            finite>;\r\n} \/\/ namespace detail\r\n<\/pre>\n
(The function max_<\/code> is one of Eric’s existing constexpr<\/code> functions in zip_with.hpp.)<\/p>\n
Cursors and sentinels<\/strong><\/p>\n
The main work in writing any view is of course, defining the cursor<\/code> and the sentinel<\/code> (internal representations of iterators: the view provides begin_cursor<\/code> and end_cursor<\/code> functions – in const and mutable forms – which return a cursor<\/code> and a sentinel<\/code> respectively).<\/p>\n
There are a few simplifying implementation patterns I found in several views that I adopted. Commonly the cursor<\/code> and the sentinel<\/code> 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:<\/p>\n
\r\ntemplate\r\nstruct iter_monoidal_zip_view\r\n  : view_facade,\r\n                detail::monoidal_zip_cardinality,\r\n                                                 range_cardinality>::value>\r\n{\r\n  ...\r\n  template \r\n  struct cursor\r\n  {\r\n    ...\r\n  private:\r\n    friend struct sentinel;\r\n    \/\/ add a const if I am const\r\n    template \r\n    using constify_if = meta::apply, T>;\r\n    \/\/ pointer to my view\r\n    using monoidal_zip_view_t = constify_if;\r\n    monoidal_zip_view_t *rng_;\r\n    \/\/ iterators I use\r\n    range_iterator_t> it1_;\r\n    range_iterator_t> it2_;\r\n    ...\r\n  };\r\n  ...\r\n};\r\n<\/pre>\n
Satisfying the Concepts<\/strong><\/p>\n
I wanted a reversible range. That meant I needed my cursor<\/code> to be bidirectional. Every cursor must implement current<\/code>, next<\/code> and equal<\/code>, and of course a bidirectional cursor must implement prev<\/code>:<\/p>\n
\r\nauto current() const;\r\nvoid next();\r\nvoid prev();\r\nbool equal(cursor const& that) const;\r\n<\/pre>\n
Every sentinel implements comparison with a cursor:<\/p>\n
\r\nbool equal(cursor const &pos) const;\r\n<\/pre>\n
And the range itself implements begin_cursor<\/code> and end_cursor<\/code>, with end_cursor<\/code> returning either a cursor or a sentinel depending on whether the underlying ranges are bounded:<\/p>\n
\r\n  using are_bounded_t = meta::and_c<(bool) BoundedRange(),\r\n                                    (bool) BoundedRange()>;\r\n\r\n  cursor begin_cursor()\r\n  {\r\n    return {*this, fun_, begin_tag{}};\r\n  }\r\n  meta::if_, sentinel>\r\n  end_cursor()\r\n  {\r\n    return {*this, fun_, end_tag{}};\r\n  }\r\n<\/pre>\n
(I omitted the const versions of these functions which use the CONCEPT_REQUIRES<\/code> macro as a nice wrapper for enable_if<\/code> style functionality.)<\/p>\n
Nice conventions<\/strong><\/p>\n
In order that views work on containers-as-ranges, various views simply use view::all<\/code> to turn whatever container is passed in into a range. If actual ranges are passed in, view::all<\/code> just forwards them, unaffected. This is very handy.<\/p>\n
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: <\/p>\n
\r\ntemplate\r\nusing Concept = meta::and_<\r\n  InputRange, InputRange,\r\n  Callable &&, range_reference_t &&>>;\r\n<\/pre>\n
And write the required function with an overloaded version which uses the CONCEPT_REQUIRES_ macro in an inverted sense from the “normal” version:<\/p>\n
\r\n\/\/ \"normal\" version\r\ntemplate())>\r\nmonoidal_zip_view, all_t> operator()(\r\n    Fun fun, R1 && r1, R2 && r2) const\r\n{ ... }\r\n\r\n\/\/ \"concept failed\" version\r\ntemplate())>\r\nvoid operator()(Fun, R1 &&, R2 &&) const\r\n{ CONCEPT_ASSERT_MESSAGE(...); }\r\n<\/pre>\n
The actual work<\/strong><\/p>\n
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.)<\/p>\n
The monoidal_zip<\/code> view’s begin<\/code> is when both iterators are at their respective begin<\/code>s, and the corresponding thing is true for end<\/code>. You can find the implementation on github<\/a> – it’s too much for an already long post.<\/p>\n
Writing current<\/code> is easy, we just need to check the iterators to do the monoid identity thing if needed:<\/p>\n
\r\nauto current() const\r\nRANGES_DECLTYPE_AUTO_RETURN_NOEXCEPT\r\n(\r\n  diff_ == 0 ?\r\n    fun_(it1_, it2_) :\r\n    diff_ > 0 ? *it1_ : *it2_\r\n)\r\n<\/pre>\n
And that’s it. Now we have monoidal_zip<\/code>, 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<\/code> may be surprising: because the ranges are lazily traversed, effectively it’s as if the ranges were reversed inside<\/em> 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?<\/p>\n
After that lengthy workout, in the next instalment<\/a> something easier: pretty-printing power series.<\/p>\n","protected":false},"excerpt":{"rendered":"
(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…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22,8],"tags":[],"class_list":["post-1130","post","type-post","status-publish","format-standard","hentry","category-cpp","category-programming"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1130"}],"version-history":[{"count":11,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1130\/revisions"}],"predecessor-version":[{"id":1190,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1130\/revisions\/1190"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}