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.

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

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

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

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

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

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

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

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

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