(Warning: this assumes a fair bit of background with ranges and the STL.)
We've had a long-standing weakness of ranges when compared with STL
iterators: in a find() call we get to access the balance of the range
from the found position (if any) through the end of the initial range.
In contrast, STL's find returns an iterator that can be combined with
the beginning of the initial range or the end of the initial range, thus
offering two ranges instead of one.
D offers the findSplit family which partially deals with this, but in an
arguably imperfect way because the range from the beginning of the
initial range to the found element has a different type than the initial
range.
In spite of that, things have worked out well.
Nowadays I've been thinking (inspired by an exchange on a C=+ mailing
list) that STL's rfind (http://goo.gl/Btg8s) is a real challenge for D's
ranges.
In D, r.rfind(e) should return a range starting with the last occurrence
of e in r and spanning through the rest of r.
If r is a forward range but not better, this is rather simple:
R rfind(R, E)(R range, E element)
{
for (;;)
{
auto ahead = range.save.find(element);
if (ahead.empty) return range;
range = ahead;
}
}
If the range is random-access, the algorithm is easy to implement
efficiently by scanning from the end and using indexing.
The tricky case is with bidirectional range. I was unable to define an
algorithm using the current primitives that: (a) scans the range from
the end, and (b) returns a range from the found position through the end.
Looks like rfind() would need one extra primitive for bidirectional
ranges. What would be a good one? I have a few starters, but don't want
to bias anyone. Please chime in!
Thanks,
Andrei
