On 02/16/2011 06:22 PM, Andrej Mitrovic wrote:
Poor implementation, but wouldn't this work?:
import std.stdio;
import std.range;
import std.array;
auto findBack(alias pred = "a == b", R, E)(R haystack, E needle)
if (isBidirectionalRange!R)
{
R result;
size_t index;
auto reversed = retro(haystack);
foreach (item; reversed)
{
index++;
if (item == needle)
break;
}
while (index)
{
result ~= reversed.front;
reversed.popFront;
index--;
}
return retro(result);
}
void main()
{
auto orig = [5, 1, 2, 3, 4, 5, 1];
auto result = findBack(orig, 4);
assert(array(result) == [4, 5, 1]);
}
Of course, it would work (I mean the principle, didn't test). But isn't it
stupid to (1) reconstruct the result by stepping in reversed (2) reverse twice
to finally provide a forward result ;-)
The issue I see is the typical case find in an array, a list or another kind of
sequential collection. You wouldn't do that in any case with such collections.
Don't you find it foolish algorithmically? With a list (*), you would step
backward, then just return the node/list from there; with an array, ditto and
just slice from there.
(And note in you case find(orig, 4) returns the same result ;-)
Denis
(*) If singly-linked only, there could be a need for reverse, but actually this
would rather reveal a poor choice of data structure, non matching the needs.
--
_________________
vita es estrany
spir.wikidot.com