Bartosz Milewski seems to like D more than C++ now :)

[H. S. Teoh]

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