C++'s std::rotate

[Andrei Alexandrescu via Digitalmars-d]

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