The rfind challenge

[Andrei Alexandrescu]

(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