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

On Monday, March 4, 2013 at 2:11 AM, Martin Knoblauch Revuelta  wrote:

Maybe you are also interested in earlier proposals.  I provided some links and commented some ideas in the thread "[boost] Review managers wanted for augmented data structures" started by Vadim Stadnik several days ago (Feb 27, 2013).

The "Hierarchical Data Structures" proposal is one of the major directions I intend to point my library.  The other proposals seem similar in functionality to a binode_container<>, one whose NodeTypeGenerator derives from binary_node_base_gen<> and either is a with_count_gen<> or derives from with_count_base_gen<>.  However, at some point I'll write an AllocatorSelector that selects the Countertree suballocator as-is so that I can test its performance. Cromwell D. Enage

On Monday, March 4, 2013 at 5:36 AM, Vadim Stadnik wrote:

After reading your blog and documentation I think that the name of the project [tree_node] is not sufficiently informative. It does not say anything that the tree is an augmented data structure that can support many useful algorithms.

I should clarify that the blog isn't mine.  The project simply addresses the use cases mentioned there.  Nevertheless, I'll do my best to provide the clarifications you requested.

Does this tree support multiple synchronized augmenting: both by counter of nodes and by "input values"?

Yes.  The basic data structures are binary_node<>, nary_node<>, and associative_node<>.  You can augment any of them with a counter, e.g.: typedef with_count<binary_node_base_gen<>,SomeDataType> BinaryNodeWithCount; You can augment them with your own statistical properties (as long as they model Boost.Accumulators concepts), e.g.: typedef with_accumulation<nary_node_base_gen<>,SomeDataType,accumulation_key<boost::accumulators::tag::max> > NaryNodeWithMaxValue; And of course, it's possible to combine augmentations: typedef with_count<     with_accumulation_base_gen<associative_node_base_gen<>,accumulation_key<> >   , SomeKeyType   , SomeDataType> AssociativeNodeWithCountAndSum;

Does this variant of augmented tree support logarithmic time operations: split, join and splice?

I've just added undocumented splice functionality to nary_node<>.  The range variant works with most underlying containers supported by the container_gen<> metafunction.  (I'm having some trouble with stable_vector<> and deque<> from Boost.Container.)  The single-element variant is a little more buggy: it currently doesn't work on random-access containers. No splitting or joining yet, sorry.

Are you planning the development of augmented trees that support interfaces of STL containers and iterators?

Yes.  Currently the library provides binode_container<> and binode_associative_container<>.  Next step in this vein will be n_node_associative_container<>, with which I could conceivably emulate a B-tree.  Ultimately I would like to come up with a back-end implementation of Rene Rivera's tree proposal: <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html> Cromwell D. Enage