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


[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
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.


 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
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.


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


 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.
Aug 28 2010
prev sibling 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 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