Hello,
In the discussion of iterators vs. ranges in D, ranges "won" in the
sense that there hasn't been strong evidence of a need for iterators to
complement ranges; people have merrily used std.algorithm and friends
and all was good.
However, it has been long acknowledged that iterators are sometimes more
expressive/economical than ranges, in the same way pointers are more so
than slices: iterators are a lower-level building block so they can be
used to build ranges and also other things. There's an inclusion
relationship between what can be done with iterators and what can be
done with ranges.
Amid these observations, C++'s std::rotate (http://goo.gl/z8FjV) and
derivative algorithms have been a prime category of examples. C++'s
std::rotate takes a "three-legged range", i.e. three iterators begin,
middle, and end, and rotates the range [middle, end) to precede [begin,
middle). It returns (as of C++11) the new middle. For example, given the
range [0, 1, 2, 3, 4, 5] with begin -> 0, mid -> 2, and end -> just past
5, rotate rearranges elements as [2, 3, 4, 5, 0, 1, 2] and returns a
pointer to the new position of 0.
This is a very challenging algorithm for ranges because it's difficult
to express both the input and the output appropriately. My first insight
into the matter has been that the ranges [begin, middle) and [middle,
end) don't even need to be adjacent, so I defined bringToFront
(http://goo.gl/5HUCiV) as a slightly different take on std::rotate. It
rotates any two ranges, adjacent or not, and returns the number of
elements in the right-hand range.
That's in a way more general than std::rotate but at the same time less
satisfactory because it returns only a number, giving no access to the
new positions of the two elements.
Following an exchange with Eric Niebler I've scored one more
mini-breakthrough today: a variant of std::rotate that rivals C++'s one,
without needing iterators. The only abstraction needed is
r1.sameFront(r2), which returns true iff the forward ranges r1 and r2
have fronts pointing to the same element. The function can be
implemented generically for ranges that offer front as a reference:
bool sameFront(R1, R2)(R1 r1, R2 r2) {
return &r1.front == &r2.front;
}
Ranges that offer rvalues from front (proxying etc) must implement
sameFront as a primitive.
Implementation is at http://dpaste.dzfl.pl/a0effbaee0a9. For historical
reasons I've reused an undocumented function sameHead. It has the
meaning of sameFront above. Signature is:
Tuple!(typeof(whole.takeExactly(0)), R)
rotateTail(R)(R whole, R right);
The algorithm assumes that "right" is a subrange of "whole" sitting at
its tail, i.e. calling while.popFront a number of times will make
whole.sameFront(right) true. It moves right to the front of whole and
returns (here's the beauty of it) the new positions of the two subranges.
For example, say whole = [0, 1, 2, 3, 4, 5] and right = whole[4 .. $].
Then rotateTail(whole, right) makes whole = [4, 5, 0, 1, 2, 3] and
returns tuple(whole[0 .. 2], whole[2 .. $]).
An essential role in this all is takeExactly (just like take, but knows
the length in O(1)). It's been an essential component in a few
range-based algorithms and it seems an important abstraction that closes
the circle on rotateTail as well, almost too fittingly. Eric mentioned
that he independently saw a need for it and defined what he calls
SizedIteratorRange.
Andrei
