[boost] Re: Boost library inclusion: generic tree containers?

From: Joao Abecasis (jpabecasis_at_[hidden])
Date: 2005-02-24 15:02:54

christopher diggins wrote:
> Why not have just one kind of iterator:
> 
> template<typename T, typename Iter_T>
> struct tree {
>  typedef typename Iter_T iterator;
>  iterator preorder_begin();
>  iterator postorder_end();
>  iterator inorder_end();
>  iterator end();
>  iterator begin(); // calls inorder_begin()
> }
> 
> ?

Hm... That looks too much like a Sequence to me ;)

I think this is not feasible in the general case. Consider a minimal 
node containing only a pointer to the next sibling and to the first 
child. Or a binary tree that keeps pointers to its left and right children.

Inorder, preorder and postorder traversals are possible using a stack of 
ancestors. In the general case, though you shouldn't have to pay for 
this extra overhead at all times.

IMO a tree container should be just that. Preorder, postorder and 
inorder are ways to turn a tree into a sequence, I see them as views of 
the tree. This is the main reason I'd prefer to have them as separate 
entities.

Btw, here's my short view of a tree:

     template <typename T>
     struct Tree
     {
         typedef /**/ tree_iterator;
         typedef /**/ const_tree_iterator;
         typedef /**/ sibling_iterator;
         typedef /**/ const_sibling_iterator;

         tree_iterator root();
         tree_const_iterator root() const;
     };

sibling_iterators are provided by the tree_iterator (they may be the 
same type). A set of tree_iterator_traits would describe their 
capabilities. Here's a taste of what I have in mind and partially in code...

     typedef tree<int> tree;
     typedef tree<int>::tree_iterator tree_iterator;
     typedef inorder_iterator<tree_iterator> inorder_iterator;

     tree t;

     ... insert data somehow ...

     tree_iterator it = t.root();

     // traversal of level 1
     for_each(
         it.children_begin(),
         it.children_end(),
         print_out("first generation"));

     it.descend();
     assert(it); // implicit bool checks if we're a leaf

     // inorder traversal of subtree through iterators
     for_each(
         inorder_iterator(it),
         inorder_iterator(),
         print_out("subtree inorder"));

     // functional traversal
     inorder_traversal(it,
         print_out("subtree inorder (again)"));

Best,

João