Retrieving the traversed range

[Peter Alexander]

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.