On Fri, Sep 20, 2013 at 04:55:40PM +0200, Craig Dillabaugh wrote: > On Friday, 20 September 2013 at 14:49:21 UTC, H. S. Teoh wrote: > > snip > >[...] > > > >Some trees do, like document trees. But yeah, in general, you don't > >have a natural ordering to trees. > > > >But then again, the whole point of ranges is *linear* traversal. If > >you're not doing that, then it's probably the wrong abstraction to > >use. (FWIW, while SortedRange is a neat hack, I haven't actually > >found it that useful in practice. Most of the ranges I actually use > >are for the cases where it's an input/forward range and you don't > >want to store the whole thing, so random access is impractical. The > >cases where I actually have random access usually turn out to be > >plain ole arrays anyway, so the SortedRange abstraction isn't really > >necessary.) > > > >So for trees, I'd argue that you need a tree-specific iteration > >abstraction, not ranges, which are linear. It's a clear case of > >structure conflict. ;-) > > > > > >T > > Excuse my lack of knowledge on Ranges, so maybe what I am proposing > is infeasible, for a binary tree for example couldn't you have a > InOrderRange, PreOrderRange, and PostOrderRange or alternately > DepthFirstRange, and BreadFirstRange. From a consumers view those > would be linear operations? [...]
Well, of course you can have these ranges. But they have to be separate from the container. And they won't be able to take advantage of the tree structure, for example, prune the children of the current node from the iteration. To do that with a range you'd have to skip over all the descendent nodes manually, which is tedious and also a waste of time. Incidentally, I did recently write a PreorderRange API for my own code, which provides an additional method called pruneFront() that efficiently skips over descendent nodes. In retrospect, though, I'm questioning the value of doing this, since that makes assumptions about the range that require too much knowledge about the underlying container, which makes the abstraction nothing more than mere formality. I might as well come out and say "this is a tree" and work with a full-fledged tree abstraction rather than try to shoehorn it into a linear range API. T -- Why is it that all of the instruments seeking intelligent life in the universe are pointed away from Earth? -- Michael Beibl
