Re: [boost] [tree] Reviving the tree library

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