The rfind challenge

[monarch_dodra]

On Tuesday, 15 January 2013 at 20:59:17 UTC, Andrei Alexandrescu 
wrote:
> On 1/15/13 2:07 PM, Phil Lavoie wrote:
>> Continuing with reversible ranges:
>
> I don't think .reverse will take us far enough. Won't work with 
> arrays which kinda puts a monkey wrench into everything. 
> r1.before(r2) works much better:
>
> R rfind(R, E)(R r, E e) {
>   auto original = r.save;
>   for (; !r.empty; r.popBack) {
>     if (r.endsWith(e)) break;
>   }
>   return original.before(r);
> }
>
> The generic implementation of before is trivial:
>
> auto before(R)(R theBuck, R stopsHere) {
>   static struct Result {
>     bool empty() { return r1 is r2; }
>     auto ref front() { return r1.front; }
>     void popFront() { r1.popFront; }
>     private R r1, r2;
>   }
>   return Result(theBuck, stopsHere);
> }
>
> For random-access ranges:
>
> auto before(R)(R theBuck, R stopsHere) {
>   return theBuck[0 .. theBuck.length - stopsHere.length];
> }
>
> (Glossing over checks and balances etc.)
>
> Bidirectional ranges would need to implement before natively to 
> return the same type as the original range.
>
> The question is whether before() is enough for many other 
> algorithms we'd want to define.
>
>
> Andrei

But the goal was having a range that start at needle, and ends at 
haystackEnd. Your implementation doesn't do that. It would have 
to use a "after" instead of a "before".

Your "before" proposal is similar to a take, but instead of being 
"index" based, it is "sentinel" based. This does have its 
strengths too, but doesn't solve the problem.

The problem is that "after", just like the would be "takeBack", 
can't offer the front primitive for bidirectional ranges.

I think that long story short, and regardless of return types:
Unless the range has some sort of built-in primitive that allows 
some form of extracting a subrange from it, there is no way to 
obtain a range from the back of a bidirectional range.