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

Nice work!

> Implementation is at http://dpaste.dzfl.pl/a0effbaee0a9. For historical reasons I've reused an undocumented function sameHead.

sameHead is documented. I already use it a couple of times.

> The algorithm assumes that "right" is a subrange of "whole" sitting at its tail, ...

sameTail is also in the Phobos docs. overlap is not documented.

A couple of times writing contracts, I missed something like:

bool sliceOf(T)(in T[] whole, in T[] slice)
{
    return whole.ptr <= slice.ptr &&
        whole.ptr + slice.length <= whole.ptr + slice.length;
}

The alternative using overlap:

  overlap(whole, slice) is slice

is a little bit too expensive for my use case.

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) { ... }

?

This reminds me, we still need "allBefore" to implement nextPermutation correctly for bidirectional ranges.

https://issues.dlang.org/show_bug.cgi?id=12188

I think this would help here also.

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;
> }

Correction: This is what I think you mean:

bool sliceOf(T)(in T[] part,
                in T[] whole)
{
    return (whole.ptr <= part.ptr &&
            part.ptr + part.length <=
            whole.ptr + whole.length);
}

On Monday, 11 August 2014 at 10:09:53 UTC, 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;
>> }
>
> Correction: This is what I think you mean:
>
> bool sliceOf(T)(in T[] part,
>                 in T[] whole)
> {
>     return (whole.ptr <= part.ptr &&
>             part.ptr + part.length <=
>             whole.ptr + whole.length);
> }

Yes, of course. I had lhs, rhs and messed up the renaming of those.

>> Correction: This is what I think you mean:
>>
>> bool sliceOf(T)(in T[] part,
>>                in T[] whole)
>> {
>>    return (whole.ptr <= part.ptr &&
>>            part.ptr + part.length <=
>>            whole.ptr + whole.length);
>> }
>
> Yes, of course. I had lhs, rhs and messed up the renaming of those.

https://github.com/dcarp/phobos/compare/sliceOf

On Monday, 11 August 2014 at 11:00:41 UTC, Dragos Carp wrote:
> https://github.com/dcarp/phobos/compare/sliceOf

Why not use something like "part" and "whole" instead of "lhs" and "rhs"?

It is more self-documenting.

On 8/11/14, 12:29 AM, Andrei Alexandrescu wrote:
> Hello,

In which algorithms would one use std::rotate?

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?

http://en.wikipedia.org/wiki/Block_sort