Retrieving the traversed range
Steven Schveighoffer
schveiguy at yahoo.com
Wed Aug 25 05:51:22 PDT 2010
On Wed, 25 Aug 2010 04:08:00 -0400, Peter Alexander
<peter.alexander.au at 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
More information about the Digitalmars-d
mailing list