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