[sandbox] [tree_node] Major update
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 <http://je4d.blogspot.com/2013/01/boostintrusive-annotated-trees-part-1.html>), as well as concepts against which you can write your own adaptors. For a quick glance, documentation is at <http://svn.boost.org/svn/boost/sandbox/tree_node/libs/tree_node/doc/html/index.html>. 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. Feedback appreciated! Cromwell D. Enage
I was hoping to get something similar for my graphics library. Great. I will try it out for my use. On Sat, Mar 2, 2013 at 8:54 AM, Cromwell Enage <sponage@yahoo.com> 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 < http://je4d.blogspot.com/2013/01/boostintrusive-annotated-trees-part-1.html>), as well as concepts against which you can write your own adaptors. For a quick glance, documentation is at < http://svn.boost.org/svn/boost/sandbox/tree_node/libs/tree_node/doc/html/ind...
.
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.
Feedback appreciated! Cromwell D. Enage
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Fri, 2013-03-01 at 19:24 -0800, Cromwell Enage 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 <http://je4d.blogspot.com/2013/01/boostintrusive-annotated-trees-part-1.html>), as well as concepts against which you can write your own adaptors. For a quick glance, documentation is at <http://svn.boost.org/svn/boost/sandbox/tree_node/libs/tree_node/doc/html/index.html>.
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.
This seems like a really well-developed package. A few initial thoughts in no particular order: *: Since there are already standard adaptors named things like 'stack' and 'queue', it seems like it would be consistent to provide some kind of adaptor named 'tree' (although it raises the question of what subset of the tree feature space is available through that). *: I see that binode_container<> assumes that the client wants a balancer, and must provide a node-generator type. I know I would not always want a balancer, and I might want a default node generator type to be available, so I could invoke just: binode_container<T> instead of binode_container<generator, T> (or even better tree<T>, see above). Maybe there could be some kind of null_balancer for default? *: I had been toying with the idea of somehow allowing this kind of invocation using an adaptor: tree< vector<int> > t; // declare a tree whose nodes store their children internally as a // vector, exposing a random-access-container interface, and having an // integer data payload tree< map<string, int> > t; // tree whose nodes store their children in a map, using a string // as the key, and having int as the data payload, exposing a // paired-associative-container interface. tree< array<int> > t; // tree using array for internal child storage, exposing // random-access-container interface, integer payload *: I think the above might be achievable using your container_gen MPL predicates for dispatching based on which container concept a given type models, e.g. is_random_access_selector and friends. *: Instead of tree_node::red_black_balancer, maybe tree_node::balancer::red_black ? (some other naming conventions might be similarly sub-scoped)
On Sunday, March 3, 2013 at 11:47 AM, Erik Erlandson wrote:
This seems like a really well-developed package.
Thanks.
A few initial thoughts in no particular order: *: Since there are already standard adaptors named things like 'stack' and 'queue', it seems like it would be consistent to provide some kind of adaptor named 'tree' (although it raises the question of what subset of the tree feature space is available through that).
I had been mulling over this very idea for some time. Ideally it would model at least one of the concepts proposed here: <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html>. However, I still have some questions regarding the specifications of the programming interfaces that the concepts define; I will pose these questions in another thread. In the meantime, I've decided to wait until the answers materialize.
*: I see that binode_container<> assumes that the client wants a balancer, and must provide a node-generator type. I know I would not always want a balancer, and I might want a default node generator type to be available, so I could invoke just: binode_container<T> instead of binode_container<generator, T> (or even better tree<T>, see above). Maybe there could be some kind of null_balancer for default?
Both the binode_container<> and binode_associative_container<> templates are in the experimental stage. I'll happily change the template argument interfaces once I implement a null_balancer and write a working test case using it and binary_node_gen<> (the most likely candidate for default node generator type).
*: I had been toying with the idea of somehow allowing this kind of invocation using an adaptor: tree< vector<int> > t; // declare a tree whose nodes store their children internally as a // vector, exposing a random-access-container interface, and having an // integer data payload tree< map<string, int> > t; // tree whose nodes store their children in a map, using a string // as the key, and having int as the data payload, exposing a // paired-associative-container interface. tree< array<int> > t; // tree using array for internal child storage, exposing // random-access-container interface, integer payload *: I think the above might be achievable using your container_gen MPL predicates for dispatching based on which container concept a given type models, e.g. is_random_access_selector and friends.
I'd be more inclined to use nary_node_gen<> and other NodeTypeGenerators as selectors, the same way binary_node_gen<> and BaseTypeGenerators inheriting from binary_node_base_gen<> would be used in binode_container<> and binode_associative_container<>, e.g.: tree< int, nary_node_gen<vecS> > t1; tree< string, int, associative_node_gen<mapS> > t2; tree< int, nary_node_gen<array_selector<4> > > t3;
*: Instead of tree_node::red_black_balancer, maybe tree_node::balancer::red_black ? (some other naming conventions might be similarly sub-scoped)
I'm rather agnostic wrt these naming conventions. Others may have stronger opinions on the matter. Perhaps we can cast votes when the time comes. Cromwell D. Enage
On Sat, Mar 2, 2013 at 8:24 AM, Cromwell Enage <sponage@yahoo.com> 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. [..]
I'm still looking at the other two proposals.[..]
Maybe you are also interested in earlier proposals. I provided some links and commented some ideas in the thread "[boost] Review managers wanted for augmented data structures" started by Vadim Stadnik several days ago (Feb 27, 2013). I hope it helps. Best regards, Martín Knoblauch Revuelta
On Monday, March 4, 2013 at 2:11 AM, Martin Knoblauch Revuelta wrote:
Maybe you are also interested in earlier proposals. I provided some links and commented some ideas in the thread "[boost] Review managers wanted for augmented data structures" started by Vadim Stadnik several days ago (Feb 27, 2013).
The "Hierarchical Data Structures" proposal is one of the major directions I intend to point my library. The other proposals seem similar in functionality to a binode_container<>, one whose NodeTypeGenerator derives from binary_node_base_gen<> and either is a with_count_gen<> or derives from with_count_base_gen<>. However, at some point I'll write an AllocatorSelector that selects the Countertree suballocator as-is so that I can test its performance. Cromwell D. Enage
On Sat, Mar 2, 2013 at 2:24 PM, Cromwell Enage <sponage@yahoo.com> 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 < http://je4d.blogspot.com/2013/01/boostintrusive-annotated-trees-part-1.html>), as well as concepts against which you can write your own adaptors. For a quick glance, documentation is at < http://svn.boost.org/svn/boost/sandbox/tree_node/libs/tree_node/doc/html/ind...
.
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. Regards, Vadim Stadnik
participants (5)
-
Cromwell Enage -
Erik Erlandson -
Martin Knoblauch Revuelta -
Shakti Misra -
Vadim Stadnik