Rene Rivera wrote
I've mentioned this type of container here in the past, under the name of "rank_tree". Very soon now I will have the version I wrote, and use, ported to the framework that Bernhard produced for the SoC tree project. You can look at the draft TR <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/libs/tree/doc/html/d2102.html?format=raw> that mentions it, and other trees.
I don't have time to look at your implementation right now. But perhaps you could comment on how you think your implementation might fit within the above. And of course if there's something we haven't thought about.
From the beginning, I designed the avl_array with the clear intention of hiding the tree nature of the implementation to the user's eyes. In
I've taken a look at your code in <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trunk/boost/tree/augmentors/rank.hpp> Now I see what you call rank: for every node, the rank is one plus the number of nodes in its left subtree. Is this right? In avl-array I use the count approach: for every node, the count is the total number of nodes in its subtree (including himself and the nodes in both left and right subtrees). For implementing the "Non-Proportional Sequence View" in SoC trees, a new augmentor would be necessary. Optionally, it might include also a normal rank augmentor. For the NPSV, it would need two variables of a parametric type (say W). One of them would be the width (in your rank and my count, every node counts as one, but in NPSV it is not necessarily one, and it can be changed). The other variable would be a sum of widths. Here, a rank-like sum would be prone to cumulative errors (if W is a float, for example), so I would use a count-like sum. In avl_array, those fields are called node_width and total_width respectively. In avl_array I get a low algorithmic complexity (O(1) instead of O(log n), or O(n) instead of O(n log n)) in many operations by having all nodes of the tree linked in-order in a circular doubly linked list. Have you considered adding such feature to soc trees? (Sorry, I don't have too much time to search for it either) I think it would be an important advantage. Massive insertions/removals, assignment and most constructors are O(n) thanks to the method avl_array::build_known_size_tree(), which builds a perfectly balanced tree taking the nodes in sequence order, and without function call recursion. this concrete case, I can't think of any benefit coming out of exposing the tree hierarchy. In part because of the banlance operations. I'm rather skeptic regarding the relation performance/maintainability/usability of a possible integration with a tree library. Though, I must recognize I still don't know the internals of the SoC project, so if you think it's a good idea to add these features (all, or just some of them) to the SoC tree project, I'll be glad to collaborate. Regards, Martin Knoblauch Revuelta