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

Subject: Re: [boost] [tree] Reviving the tree library
From: Erik Erlandson (eerlands_at_[hidden])
Date: 2011-05-06 17:46:12

> > Some common tree-related methods like parent(), depth(),
> > ply() seem like they would be good additions.  Maintaining
> > them adds some overhead, but I found I was able to keep
> > things logarithmic in complexity.
> 
> The functions are useful.  But perhaps depth() and ply() are better suited to be free functions, so that new concept-conforming tree models don't need to re-implement them the same way.

ply() could easily be a free function, and would have O(depth)
complexity.   The problem I saw with depth() as a stateless
function is that its complexity would be linear on the size of the
(sub)tree, unless I'm missing something.   (I mitigated that problem by
maintaining some depth-histogram structures that can be updated in
O(depth) time for various operations)

> 
> > I found that I wanted to support what I called 'storage
> > models' for child nodes.  I ended up with three of them:
> > 
> > 1) a vector<>-like model, where node[j] gives the
> > jth-child
> > 2) a map<>-like model, where node[key] gives the
> > child indexed by (key)
> > 3) a multiset<>-like model where children are
> > automatically maintained in a sorted order.
> 
> Do these storage models wrap around their respective STL containers?  (From previous posts I gather that they weren't.)  In my TreeNode library, I use the container_gen metafunction that's currently part of the BGL.  I'd be happy to hear how users would like to select their underlying containers.

My storage models are effectively wrappers around the underlying
containers (the container is a member of the node type).  I originally
thought it would be nice to allow a user to somehow drop in any
container they wanted, but I was unable to find a way to make that work
properly.  As it is, the user chooses a storage model with a template
parameter:

tree<data_type, raw<> >::node_type  // a node that stores its children
as a random-access vector
tree<data_type, ordered<data_compare_type> >::node_type // a node that
stores children ordered (multiset)
tree<data_type, keyed<key_type, key_compare_type> >::node_type // a node
that indexes children by a key

Template parameters have default values, so for example you can declare
a simple tree of integers like this:
tree<int> t;

It's pretty easy to support additional child-node container models, but
I have to implement them and give them a template parameter to select
them like above.  Perhaps container_gen would allow it to be more fully
automated