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:
, 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk