Boost logo

Boost :

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
useful algorithms.

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.

Vadim Stadnik

Boost list run by bdawes at, gregod at, cpdaniel at, john at