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

From: Joao Abecasis (jpabecasis_at_[hidden])
Date: 2005-02-24 11:33:46

Joaquín Mª López Muñoz wrote:
> |I agree with Thorste here. Thinking about the relation between a tree
> |structure and its various iterators, maybe we can adopt a similar conceptual
> |approach as Boost.MultiIndex: a tree container is the underyling data 
> structure,
> |on top of which several "indices" are provided with different iteration 
> policies:
> |
> |typedef tree<element> tree_t;
> |tree_t tr;
> |
> |tree_t::iterator<inorder>::type it1=tr.get<inorder>().begin; // inorder 
> iteration
> |tree_t::iterator<preorder>::type it2=tr.get<preorder>().begin; // preorder
> |iteration
> |
> |// convertibility between different types of iterators
> |it2=tr.project<preorder>(it1);

Thorsten Ottosen wrote:
> I'm not to keen on the idea that iterators are parameterized with an iteration 
> policy.
> It would be more natural just to have
> 
> tree_t::inorder_iterator i = tr.inorder_begin();
> tree_t::preorder_iterator i2 = tr.preorder_begin();

I think a generic tree should only be required to provide basic tree 
traversal iterators like from parent to child and among children or 
siblings.

 From the basic iterators other types of traversal are possible. In my 
unfinished tree library (see my other post) the same effect would be 
accomplished with:

     inorder_iterator<tree_t::tree_iterator> i = tr.root();
     preorder_iterator<tree_t::tree_iterator> i2 = tr.root();

This keeps the interface and the implementation of the tree cleaner. One 
could also use BGL algorithms here if the tree exposes a Graph interface.

Best,

João