On Monday, 11 August 2014 at 13:55:07 UTC, Ary Borenszweig wrote:
> On 8/11/14, 12:29 AM, Andrei Alexandrescu wrote:
>> Hello,
>
> In which algorithms would one use std::rotate?

Pushing N items to the front of a vector is implemented as pushing N to the back then rotating them to the front.

On 8/11/14, 2:11 AM, "Nordlöw" wrote:
> On Monday, 11 August 2014 at 06:56:52 UTC, Dragos Carp wrote:
>> bool sliceOf(T)(in T[] whole, in T[] slice)
>> {
>>     return whole.ptr <= slice.ptr &&
>>         whole.ptr + slice.length <= whole.ptr + slice.length;
>> }
>
> Shouldn't the function arguments of sliceOf be reversed to given a more
> intuitive UCFS as
>
>      if (slice.sliceOf(whole) { ... }

isSliceOf -> yum

On 8/11/14, 6:55 AM, Ary Borenszweig wrote:
> On 8/11/14, 12:29 AM, Andrei Alexandrescu wrote:
>> Hello,
>
> In which algorithms would one use std::rotate?

Depends on whom you ask :o). I think it's a fairly obscure algorithm, better suited as representative of a class rather than frequently useful. Facebook's C++ code base only has few uses, all in the same pattern rotate(b, b + 1, e) i.e. bubble the front all the way to the back with random iterators. (The result is not used and is trivially e - 1.)

(One frequent use is in ranges/iterators debates; out of the woodwork come people whose livelihood apparently depends on rotate, in particular on using rotate with non-random iterators (random access ranges make it easy to implement) AND needing the result.)

I do think that, like partition or partialSort, std::rotate is one of those algorithms that's good to know about because it may save some otherwise awkward solutions. Sean Parent has a nice talk http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning on such.

For my money I think http://dpaste.dzfl.pl/a0effbaee0a9 is fine (after being of course productionized to take advantage of random access if available, improve on the recursion, etc). Requiring sameHead or random access seems to me a good sweet spot.


Andrei

>
> isSliceOf -> yum

PR created:

https://github.com/D-Programming-Language/phobos/pull/2416

On Monday, 11 August 2014 at 14:45:09 UTC, Andrei Alexandrescu wrote:
isSliceOf -> yum

Can you elaborate on that?

On Monday, 11 August 2014 at 18:11:19 UTC, Nordlöw wrote:
> On Monday, 11 August 2014 at 14:45:09 UTC, Andrei Alexandrescu wrote:
> isSliceOf -> yum
>
> Can you elaborate on that?

I get it, Andrei :)

On 8/11/14, 11:12 AM, "Nordlöw" wrote:
> On Monday, 11 August 2014 at 18:11:19 UTC, Nordlöw wrote:
>> On Monday, 11 August 2014 at 14:45:09 UTC, Andrei Alexandrescu wrote:
>> isSliceOf -> yum
>>
>> Can you elaborate on that?
>
> I get it, Andrei :)

Yah, all about making "a.isSliceOf(b)" a nice phrase and keeping the tradition of other isXxx names in Phobos. -- Andrei

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

?

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

On Monday, 11 August 2014 at 03:29:56 UTC, Andrei Alexandrescu wrote:
>[...] 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;
> }

This doesn't work for ranges that visit the same element twice, e.g.

cycle(arr).take(arr.length + 1)
[0, 0].map!(i => arr[i])

I suspect most ranges will have to implement the sameFront primitive manually, usually forwarding to the underlying range.

Related: most mutating algorithms won't work for these kinds of ranges, as we usually presume lvalue ranges never visit the same lvalue twice. Perhaps this needs to be mentioned on affected algorithms?