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

Subject: Re: [boost] [sandbox] [tree_node] Major update
From: Cromwell Enage (sponage_at_[hidden])
Date: 2013-03-11 01:25:56

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