On 8/25/10 6:55 PDT, Peter Alexander wrote:
> Thanks for the replies Andrei, Steven.
>
> It's a bit disappointing that there is no solution to this,
> although I think you already know what I'll suggest as a
> solution :) (cursors/iterators)
>
> It's quite funny really, because I had decided to drop the whole
> iterator thing and just accept that the occassional small
> performance/memory drop wasn't that big of an issue.
>
> In order to try an appreciate ranges more I decided to try my hand
> at writing a generic combinatorics library. Unfortunately, the
> first function I tried to write (nextPermutation) requires exactly
[message was cut]

Peter --


Here's a thought. There are two possibilities I see to do this without disrupting anything and without requiring everybody to implement a new primitive.

1. Require random access for your nextPermutation. This is of course imperfect, but something that we can live with. I do that in a couple of places in Phobos.

2. Define a function like this:

R allBefore(R)(R all, R tail) if (isRandomAccessRange!R && hasLength!R)
{
    // assume tail starts somewhere inside all and ends where all ends
    enforce(all.length >= tail.length);
    return all[0 .. all.length - tail.length);
}

R allBefore(R)(R all, R tail)
        if (isBidirectionalRange!R &&
            is(typeof(all.allBeforeImpl(tail)) : R))
{
    return all.allBeforeImpl(tail);
}

Now in your code you can guard the definition of nextPermutation with is(typeof(allBefore(r, r)). Then bidirectional ranges who want to support nextPermutation will have to implement allBeforeImpl as a primitive.

I think we should do this for Phobos too.


Andrei

Andrei Alexandrescu wrote:

> we should do this for Phobos too

Why is it undesirable to be able to retro in O(1)?

-manfred

On 8/26/10 18:11 PDT, Manfred_Nowak wrote:
> Andrei Alexandrescu wrote:
>
>> we should do this for Phobos too
>
> Why is it undesirable to be able to retro in O(1)?

I've seen your other post, but couldn't connect the dots. retro is O(1) today.

Andrei

Andrei Alexandrescu wrote:

> retro is O(1) today.

Thx, but then I am missing the whole point of this thread.

-manfred

On 8/27/10 16:38 PDT, Manfred_Nowak wrote:
> Andrei Alexandrescu wrote:
>
>> retro is O(1) today.
>
> Thx, but then I am missing the whole point of this thread.

It's simple: the OP wanted this:

- start with a bidir range r

- move from the LEFT in it for a while

- then reverse whatever is to the LEFT of the walking point

This is impossible in today's D without extra walks. You can reverse what's to the RIGHT of the walking point. You can also reverse what's to the LEFT of the walking point IF you start the walk from the right.

The more I think of it, the more I think beforeAll(r, postfix) and afterAll(r, prefix) are two optional primitives that should cover this need very nicely and safely. In my previous unslept nights when I was tormented by this I couldn't see that these primitives are actually provably save in O(1) time.


Andrei

Andrei Alexandrescu wrote:

>> Thx, but then I am missing the whole point of this thread.
> It's simple: the OP wanted this:
> - start with a bidir range r
> - move from the LEFT in it for a while
    (prefix, postfix)= inPlaceSplit( r, predicate, Move.RIGHT)
      // == O(prefix.len)
> - then reverse whatever is to the LEFT of the walking point
    retro( prefix)
      // == O(1)

Please note:
even if the runtime of `retro' would be Theta(n) the runtime would still be
limited by O(prefix.len)
-manfred

On 28/08/10 12:03 PM, Manfred_Nowak wrote:
> Andrei Alexandrescu wrote:
>
>>> Thx, but then I am missing the whole point of this thread.
>> It's simple: the OP wanted this:
>> - start with a bidir range r
>> - move from the LEFT in it for a while
>      (prefix, postfix)= inPlaceSplit( r, predicate, Move.RIGHT)
>        // == O(prefix.len)
>> - then reverse whatever is to the LEFT of the walking point
>      retro( prefix)
>        // == O(1)
>
> Please note:
> even if the runtime of `retro' would be Theta(n) the runtime would still be
> limited by O(prefix.len)
> -manfred

That would be all well and good if inPlaceSplit actually existed :)

The question now becomes: how do you define inPlaceSplit so that it runs in O(prefix.length)? This question is essentially equivalent to the original, and requires something like allBefore that Andrei describes (which as also something that currently does not exist).

The discussion is now focused around how to solve the problem. In an ideal world I would have liked to see something like the introduction of cursors/iterators, but I can sympathize with Andrei not wanting to introduce another primitive at this stage in the languages development.

Something like allBefore does seem like the best option, although I'm trying to figure out if it is sufficient i.e. are there more problems that are going to arise later on that allBefore does not solve? My gut says there will be, but I can't think of any yet.

On Sat, 28 Aug 2010 15:45:17 -0400, Peter Alexander <peter.alexander.au@gmail.com> wrote:

> On 28/08/10 12:03 PM, Manfred_Nowak wrote:
>> Andrei Alexandrescu wrote:
>>
>>>> Thx, but then I am missing the whole point of this thread.
>>> It's simple: the OP wanted this:
>>> - start with a bidir range r
>>> - move from the LEFT in it for a while
>>      (prefix, postfix)= inPlaceSplit( r, predicate, Move.RIGHT)
>>        // == O(prefix.len)
>>> - then reverse whatever is to the LEFT of the walking point
>>      retro( prefix)
>>        // == O(1)
>>
>> Please note:
>> even if the runtime of `retro' would be Theta(n) the runtime would still be
>> limited by O(prefix.len)
>> -manfred
>
> That would be all well and good if inPlaceSplit actually existed :)
>
> The question now becomes: how do you define inPlaceSplit so that it runs in O(prefix.length)? This question is essentially equivalent to the original, and requires something like allBefore that Andrei describes (which as also something that currently does not exist).
>
> The discussion is now focused around how to solve the problem. In an ideal world I would have liked to see something like the introduction of cursors/iterators, but I can sympathize with Andrei not wanting to introduce another primitive at this stage in the languages development.
>
> Something like allBefore does seem like the best option, although I'm trying to figure out if it is sufficient i.e. are there more problems that are going to arise later on that allBefore does not solve? My gut says there will be, but I can't think of any yet.
>

For what its worth, the FLAME project has implemented most of the high-order linear algebra operations using two iterations primitives (and BLAS of course): a 1D tuple equating to allBefore, the current range and allAfter; and a 2D tuple which is the 3x3 version of the 1D tuple.

Peter Alexander wrote:

> That would be all well and good if inPlaceSplit actually existed :)

In your OP you wrote:
> but Until is (correctly) not bidirectional

I recognize at least a misunderstanding in this sentence, because every bidirectionalRange _is_ an inputRange. Therefore `Until!' _should_ work on every bidirectionalRange.

If you are right, then there must be something wrong with the
implementation. And i was upset to see
  assert( isInputRange!( int[])) // ok
  typedef int[] T;
  assert( isInputRange!( T))     // isInputRange!(T) is false

-manfred

On 08/28/2010 07:06 PM, Manfred_Nowak wrote:
> Peter Alexander wrote:
>
>> That would be all well and good if inPlaceSplit actually existed :)
>
> In your OP you wrote:
>> but Until is (correctly) not bidirectional
>
> I recognize at least a misunderstanding in this sentence, because every
> bidirectionalRange _is_ an inputRange. Therefore `Until!' _should_ work on
> every bidirectionalRange.

It does, it just yields (only) a forward range. The allBefore() thing is only in the discussion stage.

> If you are right, then there must be something wrong with the
> implementation. And i was upset to see
>    assert( isInputRange!( int[])) // ok
>    typedef int[] T;
>    assert( isInputRange!( T))     // isInputRange!(T) is false
>
> -manfred

typedef? What's typedef? :o)


Andrei