Re: [boost] A generic tree manipulation library

From: Darren Cook (darren_at_[hidden])
Date: 2003-03-23 20:06:57

>> I'm very interested in having tree container concepts in Boost. 

> The tree_node_map class provides an implementation to a basic tree node 
> of variable branching size. The implementation here uses the std::map to 
> implement the children, but this could equally be a std::list, 
> std::vector or any suitable container; it could even be a low-level 
> implementation (for performance) or a fixed-size array (for n-ary nodes).

I've been implementing a tree class recently where each node has:
   Node* first_child;
   Node* next_sibling;

I'm using new/delete currently, but was planning to use boost.Pool once my 
design has settled down.

A std::map would be too much overhead for my particular application (which 
tends to have deep trees with few branches).

I briefly played with one block of memory per branch and doing away with the 
first_child pointer, but decided to come back to that idea later. It has a 
problem with identifying the last node; either you need to store "branch 
length", or a flag to mark the end (in which case you've saved no memory; 
still may have a speed advantage however).

Finding the previous sibling or parent in my tree requires starting from the 
root node (or keeping a stack of nodes visited).

> The tree class is just a wrapper around a tree node that provides access 
> to a root element. This would need some major work and additional 
> support (e.g. post/pre/in-order traversal iterators) if it were to be 
> useful.

Do you have any example usage?

I wonder if it would be better to approach this from the 
algorithms/iterators side and come to the containers later? I.e. what 
operations do you need to do on the trees?

As a couple of examples I need:
  1. for_each() of first child at each node.
  2. display all node values in the tree on stdout.

I'm not yet clear what I want from the second option there. Some kind of 
indenting I guess.

BTW, I'm new to Boost. Is it normal to include all the Allocator stuff early 
on when discussing designs? I thought it would be grafted on at the end.

Darren