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
