On Thu, Oct 08, 2015 at 02:46:05PM +0000, John Colvin via Digitalmars-d wrote: > On Thursday, 8 October 2015 at 14:36:03 UTC, Kagamin wrote: > >On Thursday, 8 October 2015 at 13:10:24 UTC, John Colvin wrote: > >>What you're effectively describing is a trio of iterators wrapped to > >>give an interface of two linked ranges. popFront grows the first one > >>and shrinks the second. I'd be interested to see how to construct > >>that, given a generic range as input. > > > >The C++ example doesn't work with generic iterators, it needs a > >specific ability to iterate in both directions, hence a bidirectional > >range. > > Of course. > > >The way ranges are used for iteration, they can be seen as adapters > >for iterators providing various consistent interfaces depending on > >their capabilities. In this example we need a bidirectional range > >that can go back and forth, one way to do it is to provide undo > >mechanism like undoPopFront and frontUndoEmpty to allow the range > >grow back, thus remaining a range that is a list of items and not an > >iterator. > > I much prefer this second version: > > >Another way is to provide a reverse range of previously popped items > >- this can be seen as iterator or not, more like a range with history > >rather than an undoable input range, so maybe the getter should be > >`history`. > > my question is: How, in practice, does one take a bidirectional range > and make one of these new things? I foresee some difficulty, but > perhaps I'm just not being imaginative enough.
Bidirectional ranges do have a fundamental lack in their definition, in that the bidirectionality is weaker than the C++ form of bidirectionality. For example, suppose you're given some bidirectional range r, with swappable elements. Clearly, reverse(r) is easily implementable (just swap .front and .back, then popFront() and popBack() until the range is empty). However, suppose you want to reverse the last n elements of r. How would you do it? Conceptually speaking, if the range is bidirectional, then its last segment of n elements ought to be bidirectional too, right? However, there is currently no (easy) way to get a bidirectional subrange out of r, using the current range primitives. One brute force way to do it, is to iterate a .save'd copy of r (since bidirectionality implies forward range) from the front, until there are only n elements left, then perform the reverse() operation. However, this is horribly inefficient if n is relatively small w.r.t. the total number of elements in r. It gets worse if r does not have .length, so you may have to iterate over *two* .save'd copies of r so that you know the subrange you end up with has exactly n elements (since you can't tell how many elements are in the subrange until you reach the end). Ideally, though, we'd like to be able to iterate from the end of r, so that we only incur the cost of calling .popBack n times. However, no amount of trickery with the current bidirectional range API is going to get you this subrange by iterating from the back. The problem is that once you call .popBack n times, there's no way to turn .back into the new .front of the subrange. You can't unpop .back once you've called popBack(), so you can't implement .front on the subrange. Whereas with iterators, you *could* just do iter-- n times, then use iter with the original .end() to form the n element subrange. So D's bidirectional ranges are inherently weaker than a pair of C++ bidirectional iterators, because D's bidirectional ranges are, under the hood, a pair of *uni-directional* iterators in opposite directions. Once you advance either iterator, you can't go back anymore without resorting to ugly inefficient hacks (e.g., allocate a stack of .save'd positions), whereas in C++ both ends are bidirectional, and can go forward/back at anytime. If we were to add an .unpop primitive to bidirectional ranges, though, then we could solve this problem. However, I'm not sure how this fits in with the overall concept of ranges. T -- Век живи - век учись. А дураком помрёшь.
