Boost logo

Boost :

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: ___B +--+--+ A_____C If this were stored in a sorted binary tree, one might expect binary_tree::iterator to output the elements in this order: A B C 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? _________I +-----+--+--+-----+ A_____E_____O_____U My current depth-first iterator would output the following: I pre_order A pre_order A post_order E pre_order E post_order O pre_order O post_order U pre_order U post_order I post_order 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. Thoughts? 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