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

Subject: Re: [boost] [tree] Reviving the tree library
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2011-05-07 06:34:39

Rene Rivera wrote:
> On 5/6/2011 4:22 PM, Cromwell Enage wrote:
>> --- On Fri, 5/6/11, Rene Rivera wrote:
>>> On 5/5/2011 6:46 PM, Erik Erlandson wrote:
>>>> I have a few questions regarding the TR2 tree iterators
>>>>
>>>> 1) I would recommend a breadth-first iterator
>>>
>>> Right. There are many additional traversal algorithms possible.
>>> And the specification of the pre-defined ones is one of the week
>>> points of the current TR.
>>>
>>>> 2) What is the semantic of in-order traversal for a non-binary
>>>> tree?
>>>
>>> Even though it's only implied I think it's left-to-right in-order
>>> traversal.
>>
>> 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?

Different kind of traversals could be organized in a way of views/ranges 
to avoid many methods of similar names. Iterators would be generated by 
some operator, e.g. operator|. It could look like this:

BOOST_FOREACH(node &n, tree | inordered)
{
   if ( is_level(n, 33) )
   {
     BOOST_FOREACH(node &ln, n | levelordered)
     {
        // do something
     }
     break;
   }
}

It could be possible to use filters:

BOOST_FOREACH(node &n, tree | inordered | filters::leafs_only)
{
   // do something with leafs
}

BOOST_FOREACH(node &n, tree | postordered | filters::leafs_only)
{
   // do something with leafs
}

If inorder_iterator was bidirectional it would be possible to reverse 
the traversal:

BOOST_FOREACH(node &n, tree | inordered | filters::reversed)
{
   // do something with nodes
}

Moreover, it could be nice to separate data from algorithms that various 
types of nodes could be used. Structure of node could depend on what 
traversals user want to use. Or in more simple form types of traversals 
would depend on which nodes someone used. Different node should be used 
if user wants just to traverse depth-first than when he wants 3 
different types of traversals.

I recall that there is nice example of generic tree in one of the "Game 
Programming Gems" books, possibly 6. Their nodes containing 4 pointers 
allows to simply implement inorder, postorder and levelorder iterators.

Regards,
Adam