Retrieving the traversed range

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Thu Aug 26 10:29:16 PDT 2010


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


More information about the Digitalmars-d mailing list