RFC on range design for D2

[Russell Lewis]

Benji Smith wrote:
> Bill Baxter wrote:
>> Ok, but I have yet to hear an actual use case that demands blazing
>> fast iteration both forwards and backwards.  In your shuffling video
>> there's no way moving the iterator back and forth is going to be the
>> bottleneck.  In my undo/redo stack example it is also far from being
>> on the critical path.    I think it goes back to the fact that going
>> back and forth randomly isn't a property of many algorithms.  In all
>> the examples I can think of it's more a property of how humans
>> interact with data.  And humans are slow compared to how long it takes
>> to update a few extra values.
> 
> Oh!! I thought of one!!
> 
> Parsers & regex engines move both forward and backward, as they try to 
> match characters to a pattern.

They do backtracking, which is different than iterating backward.  I 
would suggest that a parser should use a stack of forward iterators 
instead.  That's my $.02, at least.

> Really, anything that uses an NFA or DFA to define patterns would 
> benefit from fast bidirectional iteration...

DFAs can't backtrack, so they don't require backward movement through 
the input.  NFAs might, depending on the implementation (are you going 
to use guess-and-backtrack, or parallel execution?) but I would again 
suggest that a stack (or "TODO list") of forward iterators might work 
better than backtracking.