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