Re: [boost] [sandbox] [tree_node] Major update

Subject: Re: [boost] [sandbox] [tree_node] Major update
From: Erik Erlandson (eje_at_[hidden])
Date: 2013-03-03 11:47:42

On Fri, 2013-03-01 at 19:24 -0800, Cromwell Enage wrote:
> Hello, fellow Boosters.
> 
> In the hope that some of you here are still interested in easily extensible / augmented tree implementations, I've updated my Boost.TreeNode library in the sandbox.  It provides adaptors for augmenting counts (a la countertree), heights, and even Boost.Accumulator values (which can solve the use cases mentioned in <http://je4d.blogspot.com/2013/01/boostintrusive-annotated-trees-part-1.html>), as well as concepts against which you can write your own adaptors.  For a quick glance, documentation is at <http://svn.boost.org/svn/boost/sandbox/tree_node/libs/tree_node/doc/html/index.html>.
> 
> I'm still looking at the other two proposals.  They have performance benchmarks which my library does not currently possess.  However, at first glance I see no comparably straightforward way to augment user-defined data (e.g. Boost.Accumulator features) in either library.
> 

This seems like a really well-developed package.  A few initial thoughts
in no particular order:

*: Since there are already standard adaptors named things like 'stack'
and 'queue', it seems like it would be consistent to provide some kind
of adaptor named 'tree' (although it raises the question of what subset
of the tree feature space is available through that).

*: I see that binode_container<> assumes that the client wants a
balancer, and must provide a node-generator type.   I know I would not
always want a balancer, and I might want a default node generator type
to be available, so I could invoke just: binode_container<T> instead of
binode_container<generator, T>  (or even better tree<T>, see above).
Maybe there could be some kind of null_balancer for default?

*: I had been toying with the idea of somehow allowing this kind of
invocation using an adaptor: 

tree< vector<int> >  t;  
// declare a tree whose nodes store their children internally as a
// vector, exposing a random-access-container interface, and having an 
// integer data payload

tree< map<string, int> > t;
// tree whose nodes store their children in a map, using a string
// as the key, and having int as the data payload, exposing a 
// paired-associative-container interface.

tree< array<int> > t;
// tree using array for internal child storage, exposing 
// random-access-container interface, integer payload

*: I think the above might be achievable using your container_gen MPL
predicates for dispatching based on which container concept a given type
models, e.g. is_random_access_selector and friends.

*: Instead of tree_node::red_black_balancer, maybe
tree_node::balancer::red_black ? (some other naming conventions might be
similarly sub-scoped)