www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Retrieving the traversed range

reply Peter Alexander <peter.alexander.au gmail.com> writes:
Maybe I'm missing something, but I can't think of anyway *at all* to do 
this generically.

Lets say I have some arbitrary bidirectional range, R, and I want to 
find the first element that satisfies some predicate. After that, I want 
to reverse the part of the range up to that element.

Essentially, I'd like to do something along the lines of:

   reverse(until!(pred)(R));

but Until is (correctly) not bidirectional, so I can't do that.

Use indexing and slicing is not an option because the range isn't 
necessary random-access.

This isn't about what std.algorithm and std.range can do -- I can't even 
think of a way to do this using primitive range operations.

Also note that popping off from the back of the range is not an option 
either because the range could be arbitrarily long and the predicate is 
usually satisfied very early in the range.

Thanks in advance.
Aug 25 2010
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Peter Alexander <peter.alexander.au gmail.com> wrote:

 Maybe I'm missing something, but I can't think of anyway *at all* to do  
 this generically.

 Lets say I have some arbitrary bidirectional range, R, and I want to  
 find the first element that satisfies some predicate. After that, I want  
 to reverse the part of the range up to that element.

 Essentially, I'd like to do something along the lines of:

    reverse(until!(pred)(R));

 but Until is (correctly) not bidirectional, so I can't do that.

 Use indexing and slicing is not an option because the range isn't  
 necessary random-access.

 This isn't about what std.algorithm and std.range can do -- I can't even  
 think of a way to do this using primitive range operations.

 Also note that popping off from the back of the range is not an option  
 either because the range could be arbitrarily long and the predicate is  
 usually satisfied very early in the range.

 Thanks in advance.

Does this do it? reverse( array( until!pred( R ) ) ); Seeing as how you cannot use indexing, there is no lazy way to do this. -- Simen
Aug 25 2010
parent Peter Alexander <peter.alexander.au gmail.com> writes:
Sorry, I should have mentioned this, but creating a copy of the
range into a newly allocated array is absolutely not acceptable
(this operation should require zero memory overhead).

For reference, this is trivially achievable in C++:

std::reverse(R.begin(), std::find_if(R.begin(), R.end(), pred));
Aug 25 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 25 Aug 2010 04:08:00 -0400, Peter Alexander  
<peter.alexander.au gmail.com> wrote:

 Maybe I'm missing something, but I can't think of anyway *at all* to do  
 this generically.

 Lets say I have some arbitrary bidirectional range, R, and I want to  
 find the first element that satisfies some predicate. After that, I want  
 to reverse the part of the range up to that element.

 Essentially, I'd like to do something along the lines of:

    reverse(until!(pred)(R));

 but Until is (correctly) not bidirectional, so I can't do that.

 Use indexing and slicing is not an option because the range isn't  
 necessary random-access.

 This isn't about what std.algorithm and std.range can do -- I can't even  
 think of a way to do this using primitive range operations.

 Also note that popping off from the back of the range is not an option  
 either because the range could be arbitrarily long and the predicate is  
 usually satisfied very early in the range.

 Thanks in advance.

I don't think this is possible generically, because there is no generic way to dissect a range into its end points or compose a range from end points. Ranges only provide common interface to traverse them. I would imagine something might be possible like this: auto range2 = find!(pred)(range1); auto range3 = range1.allBefore(range2); where allBefore (or whatever you want to call it) verifies trivially that range2 and range1 have identical ends. But this has to be implemented by the range, since a generic representation of a range end point is not defined. dcollections' ranges provide a method to compose them using cursors, and to decompose them into two cursors, so what you want is possible, but there are some limitations. I never want to be able to create an invalid range, so I throw an exception when you try to compose a range that I can't verify in at least O(lgn) time. For example: reverse(container[container.begin..find!(pred)(container[]).begin]); This should work no matter what collection you are using. If you want to slice arbitrary ranges, only ArrayList and Tree* work because of the quick verification requirement. -Steve
Aug 25 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/25/10 1:08 PDT, Peter Alexander wrote:
 Maybe I'm missing something, but I can't think of anyway *at all* to do
 this generically.

 Lets say I have some arbitrary bidirectional range, R, and I want to
 find the first element that satisfies some predicate. After that, I want
 to reverse the part of the range up to that element.

 Essentially, I'd like to do something along the lines of:

 reverse(until!(pred)(R));

 but Until is (correctly) not bidirectional, so I can't do that.

 Use indexing and slicing is not an option because the range isn't
 necessary random-access.

 This isn't about what std.algorithm and std.range can do -- I can't even
 think of a way to do this using primitive range operations.

 Also note that popping off from the back of the range is not an option
 either because the range could be arbitrarily long and the predicate is
 usually satisfied very early in the range.

 Thanks in advance.

This is an annoying limitation of bidirectional ranges that we don't have a solid solution to. Let me put on the table the unacceptable solution as a baseline: auto n = walkLength(r) - walkLength(until!pred(r)); popBackN(r, n); reverse(r); Of all ranges, bidirectional ranges suffer of this limitation because they clearly have two underlying "ends" that are inaccessible in separation from the range. Andrei
Aug 25 2010
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 25 Aug 2010 09:10:18 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 8/25/10 1:08 PDT, Peter Alexander wrote:
 Maybe I'm missing something, but I can't think of anyway *at all* to do
 this generically.

 Lets say I have some arbitrary bidirectional range, R, and I want to
 find the first element that satisfies some predicate. After that, I want
 to reverse the part of the range up to that element.

 Essentially, I'd like to do something along the lines of:

 reverse(until!(pred)(R));

 but Until is (correctly) not bidirectional, so I can't do that.

 Use indexing and slicing is not an option because the range isn't
 necessary random-access.

 This isn't about what std.algorithm and std.range can do -- I can't even
 think of a way to do this using primitive range operations.

 Also note that popping off from the back of the range is not an option
 either because the range could be arbitrarily long and the predicate is
 usually satisfied very early in the range.

 Thanks in advance.

This is an annoying limitation of bidirectional ranges that we don't have a solid solution to. Let me put on the table the unacceptable solution as a baseline: auto n = walkLength(r) - walkLength(until!pred(r)); popBackN(r, n); reverse(r); Of all ranges, bidirectional ranges suffer of this limitation because they clearly have two underlying "ends" that are inaccessible in separation from the range.

*cough* cursors *cough* ;) -Steve
Aug 25 2010
prev sibling next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
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
what I have described here (you need to search for an out-of-order
pair then reverse the end of the range after that pair)! Doing the
popBackN thing you described changes nextPermutation's average
case performance from O(1) to O(n) (well, I think it's O(1), I
haven't really done the math yet, but it seems right at a glance).
Aug 25 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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

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
Aug 26 2010
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Andrei Alexandrescu wrote:

 we should do this for Phobos too

Why is it undesirable to be able to retro in O(1)? -manfred
Aug 26 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Aug 26 2010
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Andrei Alexandrescu wrote:

 retro is O(1) today.

Thx, but then I am missing the whole point of this thread. -manfred
Aug 27 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Aug 27 2010
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Andrei Alexandrescu wrote:

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

- start with a bidir range r - move from the LEFT in it for a while

// == O(prefix.len)
 - then reverse whatever is to the LEFT of the walking point

// == 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
Aug 28 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
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.

- start with a bidir range r - move from the LEFT in it for a while

// == O(prefix.len)
 - then reverse whatever is to the LEFT of the walking point

// == 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.
Aug 28 2010
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
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
Aug 28 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Aug 28 2010
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 29/08/10 2:01 AM, Andrei Alexandrescu wrote:
 On 08/28/2010 07:06 PM, Manfred_Nowak wrote:
 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.

Is that implying that Until will become bidirectional when/if allBefore is added? How? Until is supposed to be lazy, so how could you retrieve until!pred(r).back without walking the range until pred is satisfied? Or have I misinterpreted you, and Until is going to remain a forward range?
Aug 29 2010
prev sibling next sibling parent "Manfred_Nowak" <svv1999 hotmail.com> writes:
Andrei Alexandrescu wrote:

 Of all ranges, bidirectional ranges suffer of this limitation because 
 they clearly have two underlying "ends" that are inaccessible in 
 separation from the range.

Therefore one has to access them within the range. As far as I can see the current implementation misses a data structure which enables a `constRetro' operation that reverses a bidirectional range in time O(1). -manfred
Aug 25 2010
prev sibling next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

 This is an annoying limitation of bidirectional ranges that we don't  
 have a solid solution to. Let me put on the table the unacceptable  
 solution as a baseline:

 auto n = walkLength(r) - walkLength(until!pred(r));
 popBackN(r, n);
 reverse(r);

 Of all ranges, bidirectional ranges suffer of this limitation because  
 they clearly have two underlying "ends" that are inaccessible in  
 separation from the range.

I seem to recall one of the original range RFCs you suggested some set functions be applicable on (some) ranges, and as such Range.allBefore( Range ) and its ilk should be possible. Was this rejected, or is it merely my memory being adjusted by cosmic rays? -- Simen
Aug 25 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/25/10 14:09 PDT, Simen kjaeraas wrote:
 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:

 This is an annoying limitation of bidirectional ranges that we don't
 have a solid solution to. Let me put on the table the unacceptable
 solution as a baseline:

 auto n = walkLength(r) - walkLength(until!pred(r));
 popBackN(r, n);
 reverse(r);

 Of all ranges, bidirectional ranges suffer of this limitation because
 they clearly have two underlying "ends" that are inaccessible in
 separation from the range.

I seem to recall one of the original range RFCs you suggested some set functions be applicable on (some) ranges, and as such Range.allBefore( Range ) and its ilk should be possible. Was this rejected, or is it merely my memory being adjusted by cosmic rays?

Your memory is accurate. I opted for going with the simplest interface and add stuff only if need arises later. Well, now seems to be later :o). Andrei
Aug 25 2010
prev sibling parent "Robert Jacques" <sandford jhu.edu> writes:
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.

- start with a bidir range r - move from the LEFT in it for a while

// == O(prefix.len)
 - then reverse whatever is to the LEFT of the walking point

// == 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.
Aug 28 2010