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,SomeDataType> BinaryNodeWithCount; You can augment them with your own statistical properties (as long as they model Boost.Accumulators concepts), e.g.: typedef with_accumulation,SomeDataType,accumulation_keyboost::accumulators::tag::max > NaryNodeWithMaxValue; And of course, it's possible to combine augmentations: typedef with_count<     with_accumulation_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