D's rotateTail [was: C++'s std::rotate]

[Fool via Digitalmars-d]

After having some fun with rotateTail and friends a draft 
implementation [2] is now available and ready for comments aiming 
at formal specification, algorithmics, and implementation details.

While most ideas were taken from [1], all mistakes are mine. 
Since this is my first D code, more or less, please take it with 
a grain of salt and don't hesitate to express the obvious.

Summary

The original recursive algorithm applicable to ForwardRange 
experienced another pass [B]. It was put out of contention by an 
iterative transcription [D] which turned out to be notably faster.

For bidirectional iterators, there is a beautiful reduction to 
three calls of the reverse function. It was not hard to come up 
with a corresponding version for BidirectionalRange [E].

Finally, I looked at a third approach which prefers moving to 
swapping. My implementation [C], however, does not seem to be 
competitive in practice.

Compared to their iterator analogues, the class of range based 
rotation algorithms considered comprise a certain amount of 
additional cost. Practice will show whether it is relevant. On 
the other hand it seems to me that this cost could be minimized 
if ranges were based on iterators.

At this point, I refrain from posting results of my biased 
performance tests. It is safe to assume that the implementation 
can be tuned based on profiling information.

All algorithms preliminarily handle degenerate cases as proposed 
by myself. I believe now that rotateTail(r, r) should return 
r.popFrontAll [A] if and only if it is not more expensive than 
returning some empty range. Is there a way to check whether 
r.popFrontExactly(r.walkLength) is O(1)?

Fool

--

[1] A. Stepanov: Rotate - Lecture 19. in Notes on Programming, 
2007, pp.154--167
     URL http://www.stepanovpapers.com/notes.pdf

[2] http://dpaste.dzfl.pl/514a1ef77d0a

[A] popFrontAll, ll.47ff
[B] rotateTailRecursive, ll.75ff
[C] rotateTailCycle, ll.147ff
[D] rotateTail, ll.227ff, and rotateTailAux, ll.325ff
[E] rotateTail, ll.227ff, and rotateTailAux, ll.407ff