Subject: Re: [boost] [tree] Reviving the tree library
From: Cromwell Enage (sponage_at_[hidden])
Date: 2011-05-09 10:58:49
--- On Fri, 5/6/11, Rene Rivera wrote:
> On 5/6/2011 4:22 PM, Cromwell Enage wrote:
> > What are your thoughts on a generalized depth-first
> > iterator that also indicates whether it's currently
> > in pre-order traversal mode, post-order traversal mode,
> > or neither? I've found it useful for implementing
> > scene graphs, for example.
> The goal was to make it possible to have any kind of
> iteration. The ones in the TR are the simple common
> ones. So yes, other iterations would be good to add.
> I'm all for generalization. Are you thinking of the
> static kind, as in traits, etc.? Or are you thinking
> of something run-time?
I was originally thinking of run-time generalization, i.e. the depth-first iterator being a functional superset of pre-order, post-order, and in-order iteration. But now that I look at the implementation, it might not necessarily be so. For a simple illustration, consider this ASCII rendition of the following tree:
If this were stored in a sorted binary tree, one might expect binary_tree::iterator to output the elements in this order:
However, if we expect an unsorted nary_tree::iterator to behave the same way (in-order, in this case), then what is the correct output for the following tree?
My current depth-first iterator would output the following:
One could filter by pre_order or post_order to obtain the corresponding output, so in that respect my depth-first iterator would be a functional superset. However, it traverses every node exactly twice, and definitely not in the same way as a sorted binary_tree::iterator. Therefore, while I agree that my depth-first iterator could make a fine addition, it may not necessarily serve well as an nary_tree::iterator.
Cromwell D. Enage
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk