Retrieving the traversed range

[Robert Jacques]

On Sat, 28 Aug 2010 15:45:17 -0400, Peter Alexander  
<peter.alexander.au at 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.