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
