C++'s std::rotate

[Andrei Alexandrescu via Digitalmars-d]

On 8/17/14, 9:06 AM, Fool wrote:
> On Monday, 11 August 2014 at 15:04:52 UTC, Andrei Alexandrescu wrote:
>> http://dpaste.dzfl.pl/a0effbaee0a9
>
> Is your design final with respect to handling degenerate cases?
>
> What do you think about
>
>   http://dpaste.dzfl.pl/8fc83cb06de8
>
> ?

Yah, it's a good option. Relevant code:

if (right is whole)
{
     //writeln("case identical");
     return tuple(right, whole.dropExactly(whole.length));
}

(Prolly it would be better to use "whole.sameHead(right)" instead of 
"right is whole". Also whole may not define length so the actual algo is 
just a tad different.)

Trouble is it takes O(n) for that trivial case and for what may be in 
all likelihood a useless return (iterate right all the way through the 
end and return the empty balance).

On the bright side, client code does have the option to make the test 
before calling rotateTail so in a way the function is more 
consistent/complete while still leaving the caller the option to avoid 
the corner case.

Not sure what's the best call here yet.

Loosely related, Xinok wrote a nice piece on in-place merge: 
http://goo.gl/AS2P4A. A great use of rotateTail.


Andrei