Subject: Re: [boost] [sandbox] [tree_node] Major update
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-03-04 05:36:57
On Sat, Mar 2, 2013 at 2:24 PM, Cromwell Enage <sponage_at_[hidden]> wrote:
> Hello, fellow Boosters.
> In the hope that some of you here are still interested in easily
> extensible / augmented tree implementations, I've updated my Boost.TreeNode
> library in the sandbox. It provides adaptors for augmenting counts (a la
> countertree), heights, and even Boost.Accumulator values (which can solve
> the use cases mentioned in <
> as well as concepts against which you can write your own adaptors. For a
> quick glance, documentation is at <
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
The generalization that is described in the blog looks like a modified
variant of single augmenting that replaces previously described augmenting
by the counter of nodes. This is why I would like to clarify the following:
Does this tree support multiple synchronized augmenting: both by counter of
nodes and by "input values"?
Does this variant of augmented tree support logarithmic time operations:
split, join and splice?
> I'm still looking at the other two proposals. They have performance
> benchmarks which my library does not currently possess. However, at first
> glance I see no comparably straightforward way to augment user-defined data
> (e.g. Boost.Accumulator features) in either library.
Are you planning the development of augmented trees that support interfaces
of STL containers and iterators?
I will be happy to discuss your comments, suggestions and ideas.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk