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.
Thanks.
> 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