inquiry about proposing a new Boost library for a tree template container class
Hello, I recently completed an STL-compliant template container class for storing data in an arbitrary tree structure. It seemed like it might be a useful component of Boost, and I wanted to ask about how new projects are submitted for consideration. The current incarnation of the project is called 'st_tree', and resides here: https://github.com/erikerlandson/st_tree/wiki Regards, Erik Erlandson
Erik Erlandson wrote:
Hello,
I recently completed an STL-compliant template container class for storing data in an arbitrary tree structure. It seemed like it might be a useful component of Boost, and I wanted to ask about how new projects are submitted for consideration.
The current incarnation of the project is called 'st_tree', and resides here: https://github.com/erikerlandson/st_tree/wiki
Hi, In your case, one of the first things you can do is to compare your library with the Boost.Tree (not official) in the sandbox (https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/) and see how your library compares with. A quick look at your documentation let me think that there is not a tutorial. It is usual that the people proposing new libraries to Boost uses the Boost Build system and that the documentation looks like the already accepted libraries. Most of the people use now quickbook for the documentation (some use doxigen for the reference section). I think that Boost.Tree is orphaned so maybe you could see how to make a better libraries from both. Welcome to Boost, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/inquiry-about-proposing-a-new-Boost-libra... Sent from the Boost - Dev mailing list archive at Nabble.com.
--- On Wed, 5/4/11, Vicente Botet wrote:
Erik Erlandson wrote:
Hello,
I recently completed an STL-compliant template container class for storing data in an arbitrary tree structure. It seemed like it might be a useful component of Boost, and I wanted to ask about how new projects are submitted for consideration.
The current incarnation of the project is called 'st_tree', and resides here: https://github.com/erikerlandson/st_tree/wiki
[snip]
I think that Boost.Tree is orphaned so maybe you could see how to make a better libraries from both.
It's orphaned!? Shoot, I'd like to help out with this too...maybe merge my TreeNode stuff if possible. Cromwell D. Enage
On Wed, 2011-05-04 at 14:37 -0700, Cromwell Enage wrote:
I think that Boost.Tree is orphaned so maybe you could see how to make a better libraries from both.
It's orphaned!? Shoot, I'd like to help out with this too...maybe merge my TreeNode stuff if possible.
If you have any thoughts on integration, I would be interested -- I'm a Boost user, but as a Boost developer I'm an utter n00b. Erik
On 5/4/2011 4:37 PM, Cromwell Enage wrote:
--- On Wed, 5/4/11, Vicente Botet wrote:
Erik Erlandson wrote:
Hello,
I recently completed an STL-compliant template container class for storing data in an arbitrary tree structure. It seemed like it might be a useful component of Boost, and I wanted to ask about how new projects are submitted for consideration.
The current incarnation of the project is called 'st_tree', and resides here: https://github.com/erikerlandson/st_tree/wiki
[snip]
I think that Boost.Tree is orphaned so maybe you could see how to make a better libraries from both.
It's orphaned!? Shoot, I'd like to help out with this too...maybe merge my TreeNode stuff if possible.
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
On Wed, May 4, 2011 at 3:17 PM, Rene Rivera <grafikrobot@gmail.com> wrote:
On 5/4/2011 4:37 PM, Cromwell Enage wrote:
--- On Wed, 5/4/11, Vicente Botet wrote:
Erik Erlandson wrote:
Hello,
I recently completed an STL-compliant template container class for storing data in an arbitrary tree structure. It seemed like it might be a useful component of Boost, and I wanted to ask about how new projects are submitted for consideration.
The current incarnation of the project is called 'st_tree', and resides here: https://github.com/erikerlandson/st_tree/wiki
[snip]
I think that Boost.Tree is orphaned so maybe you
could see how to make a better libraries from both.
It's orphaned!? Shoot, I'd like to help out with this too...maybe merge my TreeNode stuff if possible.
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2.
I could maybe help. I developed some general binary search tree, red-black tree, and avl tree algorithms not too long ago, both recursive and non-recursive variants (where applicable) and all policy-based. I had a need for the algorithms to be separated from the data structures since the comparison function could be supplied dynamically, hence needn't (and probably couldn't) be maintained by the data structure. And I thought it would be a fun exercise. I will take a look at these other tree data structures in the near future... - Jeff
On Wed, 2011-05-04 at 17:17 -0500, Rene Rivera wrote:
On 5/4/2011 4:37 PM, Cromwell Enage wrote:
--- On Wed, 5/4/11, Vicente Botet wrote:
Erik Erlandson wrote:
Hello,
I recently completed an STL-compliant template container class for storing data in an arbitrary tree structure. It seemed like it might be a useful component of Boost, and I wanted to ask about how new projects are submitted for consideration.
The current incarnation of the project is called 'st_tree', and resides here: https://github.com/erikerlandson/st_tree/wiki
[snip]
I think that Boost.Tree is orphaned so maybe you could see how to make a better libraries from both.
It's orphaned!? Shoot, I'd like to help out with this too...maybe merge my TreeNode stuff if possible.
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2.
Can anybody point me to the TR proposal for Boost.Tree? I can't find a link to it.
On 5/4/2011 6:07 PM, Erik Erlandson wrote:
Can anybody point me to the TR proposal for Boost.Tree? I can't find a link to it.
<http://svn.boost.org/svn/boost/sandbox/tree/libs/tree/proposal/proposal.qbk> <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html> -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
--- On Wed, 5/4/11, Rene Rivera wrote:
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2.
I'm willing to help out. I have some proposal questions that I'll shoot in a later e-mail. Cromwell D. Enage
On Wed, 2011-05-04 at 17:17 -0500, Rene Rivera wrote:
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2.
I have a few questions regarding the TR2 tree iterators 1) I would recommend a breadth-first iterator 2) What is the semantic of in-order traversal for a non-binary tree? 3) I don't feel like I'm understanding the motivation for cursors versus iterators. Is there an "elevator pitch" for that? Also, a question regarding the definition of 'multi-way' tree: My reaction to 'multi-way' is: 'synonym for n-ary', but that appears to not be the idea. What makes a binary tree "multi-way" and an nary tree not multi-way?
Erik Erlandson <eerlands <at> redhat.com> writes:
I have a few questions regarding the TR2 tree iterators
2) What is the semantic of in-order traversal for a non-binary tree?
For flexibility, there needs to be a walk that generalizes preorder, inorder and postorder as well as handedness of the walk. The user should be able to specify a left-side visitor, a bottom visitor (that can be aware of how many times the bottom has been visited to deal with non-binary trees), and a right visitor. In addition, a traversal should be able to be either left handed or right handed. The traversal should be able to stop after meeting some precondition and return a reference to the node stopped at. Finally, the traversal should be able to be started at any node in the tree. Joel
On 5/5/2011 6:46 PM, Erik Erlandson wrote:
On Wed, 2011-05-04 at 17:17 -0500, Rene Rivera wrote:
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2.
I have a few questions regarding the TR2 tree iterators
1) I would recommend a breadth-first iterator
Right. There are many additional traversal algorithms possible. And the specification of the pre-defined ones is one of the week points of the current TR.
2) What is the semantic of in-order traversal for a non-binary tree?
Even though it's only implied I think it's left-to-right in-order traversal.
3) I don't feel like I'm understanding the motivation for cursors versus iterators. Is there an "elevator pitch" for that?
Single sentence: Cursors provide an abstraction for *all* the possible traversals of trees vs. the linear only traversals of iterators in a single object making it possible to base the expanse of tree algorithms solely on cursors. Longer: Because of the additional cardinality of trees the current std model of iterators doesn't allow for a compact mapping to trees. Even though it's possible to define a group of iterator, node, and function interfaces to accomplish the same task it makes it harder to conceptualize algorithms when one has to deal with two or three types of iterators at once. Essentially it's possible to write generic algorithms entirely on the single cursor concept without really having to think about the particular context. And I'm not talking only about user visible algorithms here. I'm also including usually internal algorithms. For example it's possible to write generic tree balancing algorithms using cursors that would be rather mind bending with just iterators (and usually would require direct access to the nodes). Note, it's likely the current TR doesn't actually deliver on the entirety of the above though ;-)
Also, a question regarding the definition of 'multi-way' tree: My reaction to 'multi-way' is: 'synonym for n-ary', but that appears to not be the idea. What makes a binary tree "multi-way" and an nary tree not multi-way?
Don't have an answer for that.. multi-way is a term Bernhard came up with. Which I never really understood either. So I'll have to get back to you on that. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
--- On Fri, 5/6/11, Rene Rivera wrote:
On 5/5/2011 6:46 PM, Erik Erlandson wrote:
I have a few questions regarding the TR2 tree iterators
1) I would recommend a breadth-first iterator
Right. There are many additional traversal algorithms possible. And the specification of the pre-defined ones is one of the week points of the current TR.
2) What is the semantic of in-order traversal for a non-binary tree?
Even though it's only implied I think it's left-to-right in-order traversal.
What are your thoughts on a generalized depth-first iterator that also indicates whether it's currently in pre-order traversal mode, post-order traversal mode, or neither? I've found it useful for implementing scene graphs, for example. Cromwell D. Enage
On 5/6/2011 4:22 PM, Cromwell Enage wrote:
--- On Fri, 5/6/11, Rene Rivera wrote:
On 5/5/2011 6:46 PM, Erik Erlandson wrote:
I have a few questions regarding the TR2 tree iterators
1) I would recommend a breadth-first iterator
Right. There are many additional traversal algorithms possible. And the specification of the pre-defined ones is one of the week points of the current TR.
2) What is the semantic of in-order traversal for a non-binary tree?
Even though it's only implied I think it's left-to-right in-order traversal.
What are your thoughts on a generalized depth-first iterator that also indicates whether it's currently in pre-order traversal mode, post-order traversal mode, or neither? I've found it useful for implementing scene graphs, for example.
The goal was to make it possible to have any kind of iteration. The ones in the TR are the simple common ones. So yes, other iterations would be good to add. I'm all for generalization. Are you thinking of the static kind, as in traits, etc.? Or are you thinking of something run-time? -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
Rene Rivera wrote:
On 5/6/2011 4:22 PM, Cromwell Enage wrote:
--- On Fri, 5/6/11, Rene Rivera wrote:
On 5/5/2011 6:46 PM, Erik Erlandson wrote:
I have a few questions regarding the TR2 tree iterators
1) I would recommend a breadth-first iterator
Right. There are many additional traversal algorithms possible. And the specification of the pre-defined ones is one of the week points of the current TR.
2) What is the semantic of in-order traversal for a non-binary tree?
Even though it's only implied I think it's left-to-right in-order traversal.
What are your thoughts on a generalized depth-first iterator that also indicates whether it's currently in pre-order traversal mode, post-order traversal mode, or neither? I've found it useful for implementing scene graphs, for example.
The goal was to make it possible to have any kind of iteration. The ones in the TR are the simple common ones. So yes, other iterations would be good to add. I'm all for generalization. Are you thinking of the static kind, as in traits, etc.? Or are you thinking of something run-time?
Different kind of traversals could be organized in a way of views/ranges to avoid many methods of similar names. Iterators would be generated by some operator, e.g. operator|. It could look like this: BOOST_FOREACH(node &n, tree | inordered) { if ( is_level(n, 33) ) { BOOST_FOREACH(node &ln, n | levelordered) { // do something } break; } } It could be possible to use filters: BOOST_FOREACH(node &n, tree | inordered | filters::leafs_only) { // do something with leafs } BOOST_FOREACH(node &n, tree | postordered | filters::leafs_only) { // do something with leafs } If inorder_iterator was bidirectional it would be possible to reverse the traversal: BOOST_FOREACH(node &n, tree | inordered | filters::reversed) { // do something with nodes } Moreover, it could be nice to separate data from algorithms that various types of nodes could be used. Structure of node could depend on what traversals user want to use. Or in more simple form types of traversals would depend on which nodes someone used. Different node should be used if user wants just to traverse depth-first than when he wants 3 different types of traversals. I recall that there is nice example of generic tree in one of the "Game Programming Gems" books, possibly 6. Their nodes containing 4 pointers allows to simply implement inorder, postorder and levelorder iterators. Regards, Adam
On Fri, 2011-05-06 at 14:38 -0500, Rene Rivera wrote:
3) I don't feel like I'm understanding the motivation for cursors versus iterators. Is there an "elevator pitch" for that?
Single sentence:
Cursors provide an abstraction for *all* the possible traversals of trees vs. the linear only traversals of iterators in a single object making it possible to base the expanse of tree algorithms solely on cursors.
I've been trying to sort out the semantics of tree cursors. One thing seems fairly clear: cursors embody the semantics for what more traditionally are defined as 'nodes': A cursor has 'begin()' and 'end()' methods that refer to the children of that cursor. The Cursor concept inherits from the Container concept, since a cursor (like a "node") is, recursively, a container of cursors. As far as that goes, it makes sense as an abstraction and seems like a really useful extension of the STL Concept hierarchy. Given the above, I get a bit confused about the meaning of methods like inorder_first(). A cursor, as defined above, seems to not mesh with any particular traversal mode. And the increment operators '++' seem to make sense only as 'increment to the next sibling.' I don't know if this is an ambiguity of the design, or just the documentation, or my incomplete understanding. Does anybody have insight?
--- On Mon, 5/9/11, Erik Erlandson wrote:
On Fri, 2011-05-06 at 14:38 -0500, Rene Rivera wrote:
Single sentence:
Cursors provide an abstraction for *all* the possible traversals of trees vs. the linear only traversals of iterators in a single object making it possible to base the expanse of tree algorithms solely on cursors.
I've been trying to sort out the semantics of tree cursors. One thing seems fairly clear: cursors embody the semantics for what more traditionally are defined as 'nodes': A cursor has 'begin()' and 'end()' methods that refer to the children of that cursor. The Cursor concept inherits from the Container concept, since a cursor (like a "node") is, recursively, a container of cursors.
To me, a cursor is a hierarchical node iterator: an iterator that is itself a range of its children.
Given the above, I get a bit confused about the meaning of methods like inorder_first(). A cursor, as defined above, seems to not mesh with any particular traversal mode. And the increment operators '++' seem to make sense only as 'increment to the next sibling.'
I couldn't find inorder_first() in the tree proposal. Did you mean inorder::begin(), which is a namespace-level algorithm? And yes, it doesn't look like a cursor is meant to be a drop-in replacement for a breadth-first or depth-first iterator, but that both can be defined in terms of cursors.
I don't know if this is an ambiguity of the design, or just the documentation, or my incomplete understanding.
The documentation looks sparse, which is probably why Rene Rivera called for improvements to it. HTH, Cromwell D. Enage
On Tue, 2011-05-10 at 12:11 -0700, Cromwell Enage wrote:
Given the above, I get a bit confused about the meaning of methods like inorder_first(). A cursor, as defined above, seems to not mesh with any particular traversal mode. And the increment operators '++' seem to make sense only as 'increment to the next sibling.'
I couldn't find inorder_first() in the tree proposal. Did you mean inorder::begin(), which is a namespace-level algorithm?
I saw it here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierar... http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierar... It looks like this: cursor inorder_first(); const_cursor inorder_cfirst() const; * Returns: A cursor to the binary_tree's first element in inorder (see [tr.order.iterators], §4). Perhaps it means "if you were going to traverse this tree in-order, here is the cursor that points to the first node you would visit in that traversal" I'm a little skeptical that such a thing is necessary. If I want in-order traversal, or breadth-first traversal, or any other particular kind of traversal, I'd use an appropriate iterator for that (which might very well be implemented on top of a cursor).
And yes, it doesn't look like a cursor is meant to be a drop-in replacement for a breadth-first or depth-first iterator, but that both can be defined in terms of cursors.
That is also a semantic that makes sense to me.
--- On Tue, 5/10/11, Erik Erlandson wrote:
It looks like this:
cursor inorder_first(); const_cursor inorder_cfirst() const; * Returns: A cursor to the binary_tree's first element in inorder (see [tr.order.iterators], §4).
Perhaps it means "if you were going to traverse this tree in-order, here is the cursor that points to the first node you would visit in that traversal"
That sounds about right.
I'm a little skeptical that such a thing is necessary. If I want in-order traversal, or breadth-first traversal, or any other particular kind of traversal, I'd use an appropriate iterator for that (which might very well be implemented on top of a cursor).
I agree that these methods aren't necessary, but they could make certain traversal initializations more efficient (pre-order comes to mind). The question becomes whether the efficiency is worth the update cost of inorder_first() et al. Cromwell D. Enage
On Wed, 2011-05-04 at 17:17 -0500, Rene Rivera wrote:
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2.
A couple other observations: Some common tree-related methods like parent(), depth(), ply() seem like they would be good additions. Maintaining them adds some overhead, but I found I was able to keep things logarithmic in complexity. I found that I wanted to support what I called 'storage models' for child nodes. I ended up with three of them: 1) a vector<>-like model, where node[j] gives the jth-child 2) a map<>-like model, where node[key] gives the child indexed by (key) 2) a multiset<>-like model where children are automatically maintained in a sorted order. I'm not sure if that has a role in a Hierarchical Container concept definition -- such things might just be instantiations of such a concept.
--- On Thu, 5/5/11, Erik Erlandson wrote:
A couple other observations:
Some common tree-related methods like parent(), depth(), ply() seem like they would be good additions. Maintaining them adds some overhead, but I found I was able to keep things logarithmic in complexity.
The functions are useful. But perhaps depth() and ply() are better suited to be free functions, so that new concept-conforming tree models don't need to re-implement them the same way.
I found that I wanted to support what I called 'storage models' for child nodes. I ended up with three of them:
1) a vector<>-like model, where node[j] gives the jth-child 2) a map<>-like model, where node[key] gives the child indexed by (key) 3) a multiset<>-like model where children are automatically maintained in a sorted order.
Do these storage models wrap around their respective STL containers? (From previous posts I gather that they weren't.) In my TreeNode library, I use the container_gen metafunction that's currently part of the BGL. I'd be happy to hear how users would like to select their underlying containers.
I'm not sure if that has a role in a Hierarchical Container concept definition -- such things might just be instantiations of such a concept.
In my TreeNode library, I currently distinguish between associative tree nodes and ones that provide random access to their child nodes because they lend themselves to somewhat different use cases (and therefore different interfaces). Otherwise, whatever storage model I use is left as an implementation detail. Cromwell D. Enage
Some common tree-related methods like parent(), depth(), ply() seem like they would be good additions. Maintaining them adds some overhead, but I found I was able to keep things logarithmic in complexity.
The functions are useful. But perhaps depth() and ply() are better suited to be free functions, so that new concept-conforming tree models don't need to re-implement them the same way.
ply() could easily be a free function, and would have O(depth) complexity. The problem I saw with depth() as a stateless function is that its complexity would be linear on the size of the (sub)tree, unless I'm missing something. (I mitigated that problem by maintaining some depth-histogram structures that can be updated in O(depth) time for various operations)
I found that I wanted to support what I called 'storage models' for child nodes. I ended up with three of them:
1) a vector<>-like model, where node[j] gives the jth-child 2) a map<>-like model, where node[key] gives the child indexed by (key) 3) a multiset<>-like model where children are automatically maintained in a sorted order.
Do these storage models wrap around their respective STL containers? (From previous posts I gather that they weren't.) In my TreeNode library, I use the container_gen metafunction that's currently part of the BGL. I'd be happy to hear how users would like to select their underlying containers.
My storage models are effectively wrappers around the underlying containers (the container is a member of the node type). I originally thought it would be nice to allow a user to somehow drop in any container they wanted, but I was unable to find a way to make that work properly. As it is, the user chooses a storage model with a template parameter: tree<data_type, raw<> >::node_type // a node that stores its children as a random-access vector tree<data_type, ordered<data_compare_type> >::node_type // a node that stores children ordered (multiset) tree<data_type, keyed<key_type, key_compare_type> >::node_type // a node that indexes children by a key Template parameters have default values, so for example you can declare a simple tree of integers like this: tree<int> t; It's pretty easy to support additional child-node container models, but I have to implement them and give them a template parameter to select them like above. Perhaps container_gen would allow it to be more fully automated
--- On Fri, 5/6/11, Erik Erlandson wrote:
ply() could easily be a free function, and would have O(depth) complexity. The problem I saw with depth() as a stateless function is that its complexity would be linear on the size of the (sub)tree, unless I'm missing something. (I mitigated that problem by maintaining some depth-histogram structures that can be updated in O(depth) time for various operations)
Interesting. BTW, what's the difference between depth and ply? I thought they were interchangeable (and other users might think so, too). Cromwell D. Enage
On Mon, 2011-05-09 at 07:25 -0700, Cromwell Enage wrote:
--- On Fri, 5/6/11, Erik Erlandson wrote:
ply() could easily be a free function, and would have O(depth) complexity. The problem I saw with depth() as a stateless function is that its complexity would be linear on the size of the (sub)tree, unless I'm missing something. (I mitigated that problem by maintaining some depth-histogram structures that can be updated in O(depth) time for various operations)
Interesting. BTW, what's the difference between depth and ply? I thought they were interchangeable (and other users might think so, too).
I should make sure to document those definitions thoroughly. Ply is the "layer," or distance from root. So the ply(root) = 0. The ply of root's children is 1, The ply of root's grandchildren is 2, etc. Depth of a (sub)tree is "1 + the maximum ply"
--- On Mon, 5/9/11, Erik Erlandson wrote:
On Mon, 2011-05-09 at 07:25 -0700, Cromwell Enage wrote:
Interesting. BTW, what's the difference between depth and ply? I thought they were interchangeable (and other users might think so, too).
I should make sure to document those definitions thoroughly. Ply is the "layer," or distance from root. So the ply(root) = 0. The ply of root's children is 1, The ply of root's grandchildren is 2, etc. Depth of a (sub)tree is "1 + the maximum ply"
So ply is defined in terms of ancestors, while depth is defined in terms of descendants, right? To illustrate then, given the following tree: ____A __+-+-+ __B___C +-+-+ D___E __+-+-+ __F___G ply(B) == 1, while depth(B) == 3 Correct? Cromwell D. Enage
On Mon, 2011-05-09 at 09:41 -0700, Cromwell Enage wrote:
I should make sure to document those definitions thoroughly. Ply is the "layer," or distance from root. So the ply(root) = 0. The ply of root's children is 1, The ply of root's grandchildren is 2, etc. Depth of a (sub)tree is "1 + the maximum ply"
So ply is defined in terms of ancestors, while depth is defined in terms of descendants, right?
Exactly.
To illustrate then, given the following tree:
____A __+-+-+ __B___C +-+-+ D___E __+-+-+ __F___G
ply(B) == 1, while depth(B) == 3
Correct. The data structures I used to maintain depth information make any call to depth() constant-time. Updating them is O(tree-depth). The storage cost is bounded above by (n)log(n) on tree size. I can see how a tree designer might or might not be OK with adding an (n)log(n) storage cost just to make depth() fast. Which is an argument for not requiring it in any interface spec, or not requiring it to be faster than linear-time.
--- On Fri, 5/6/11, Erik Erlandson wrote:
ply() could easily be a free function, and would have O(depth) complexity. The problem I saw with depth() as a stateless function is that its complexity would be linear on the size of the (sub)tree, unless I'm missing something. (I mitigated that problem by maintaining some depth-histogram structures that can be updated in O(depth) time for various operations.)
Ah, I see now. In that case, storing the depth variable as part of the tree node would make the depth() member function most efficient...for those applications that actually need it. This leads to the question of whether or not applications that don't need depth() can live with the memory overhead. I suspect so, but that's just a guess. BTW, I've started a new discussion on container_gen, archived here: <http://article.gmane.org/gmane.comp.lib.boost.devel/219238> Cromwell D. Enage
On Wed, 2011-05-04 at 17:17 -0500, Rene Rivera wrote:
It looks like Bernhard stopped development 1.5 years ago. Which sure sounds like it's orphaned. Given that I've copied it over to sandbox/tree location (the last trunk state for it). I'm willing to help out in moving the library forward, especially since it's based on some of the core concepts I suggested. Who else is willing to help out in improving and finishing this lib? Note, that helping out involves thinking about adjusting the TR proposal so that it can be submitted for the soon to start up again TR2.
I propose renaming 'nary_tree' to just 'tree.' We have 'vector', 'list', 'map', etc. There should be a thing simply called 'tree', and I think it should be whatever becomes the platonic ideal of an n-ary tree.
participants (7)
-
Adam Wulkiewicz -
Cromwell Enage -
Erik Erlandson -
Jeffrey Lee Hellrung, Jr. -
Joel Young -
Rene Rivera -
Vicente Botet