Subject: Re: [boost] [sandbox] [tree_node] Major update
From: Cromwell Enage (sponage_at_[hidden])
Date: 2013-03-05 00:31:48
On Sunday, March 3, 2013 at 11:47 AM, Erik Erlandson wrote:
> 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 had been mulling over this very idea for some time. Ideally it would model at least one of the concepts proposed here: <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html>. However, I still have some questions regarding the specifications of the programming interfaces that the concepts define; I will pose these questions in another thread. In the meantime, I've decided to wait until the answers materialize.
> *: 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?
Both the binode_container<> and binode_associative_container<> templates are in the experimental stage. I'll happily change the template argument interfaces once I implement a null_balancer and write a working test case using it and binary_node_gen<> (the most likely candidate for default node generator type).
> *: 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.
I'd be more inclined to use nary_node_gen<> and other NodeTypeGenerators as selectors, the same way binary_node_gen<> and BaseTypeGenerators inheriting from binary_node_base_gen<> would be used in binode_container<> and binode_associative_container<>, e.g.:
tree< int, nary_node_gen<vecS> > t1;
tree< string, int, associative_node_gen<mapS> > t2;
tree< int, nary_node_gen<array_selector<4> > > t3;
> *: Instead of tree_node::red_black_balancer, maybe
> tree_node::balancer::red_black ? (some other naming conventions might be
> similarly sub-scoped)
I'm rather agnostic wrt these naming conventions. Others may have stronger opinions on the matter. Perhaps we can cast votes when the time comes.
Cromwell D. Enage
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk