The rfind challenge

[Phil Lavoie]

On Tuesday, 15 January 2013 at 05:51:16 UTC, Andrei Alexandrescu 
wrote:
> (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

Interesting problem. One possibility would be to add a CLASS 
primitive like this: Range.merge( Range start, Range end ) 
//Takes the start of the start and the end of end.

Pseudo:
   original = range.save
   resPos = range.retro.find
   return Range.merge( resPos, original ) //DOES NOT WORK

The problem with this solution is that:
Retro returns a different range type and it would be more 
complicated to
have the merge function work with this type.

An addition to this solution could be another new primitive: 
reverse:

Pseudo:
   original = range.save
   reversed = range.reverse //Permanently invert start an end. I 
think this is feasible for all bidirectional ranges. Still a 
bidirectional range.
   reversed.find( needle ) //In haystack :)
   return Range.merge( reversed, original ) //Ok, start of 
reversed is on needle and end of original hasn't moved. The order 
of the range returned is the same as the one received.

This is just a suggestion and any primitive could be renamed. 
However, I think reverse is a good place to start.

Phil