Query of Interest in annotated tree extensions to Boost.Intrusive
Hi All, I've been working on some extensions to allow users to add annotations to tree data structures (explanation of the idea here: http://je4d.blogspot.co.uk/2013/01/boostintrusive-annotated-trees-part-1.htm...). This isn't a new library submission, but it's a fairly substantial modification to Boost.Intrusive, so I've got the following questions on my mind: 1. Is there interest in having such functionality in boost? 2. If so, should the changes go through the formal review process? Regarding the level of interest: To the best of my knowledge, no one has yet released a library that provides this functionality. I have, however, come across a few things that indicate that the technique is in use: http://is.gd/PA1Lhm (Evidence of demand for such a library) http://is.gd/Lepzrq (A binary tree with a 'pixel height' annotation) http://is.gd/PMb6Fy (A node-count annotation on B-trees) http://is.gd/RHjpeQ (Paper about a "count" annotation on suffix trees) http://is.gd/lHVhC0 (About the usefulness of annotations. Separates the data from annotations, unlike the proposed library) Many thanks, Jeff Snyder (aka je4d)
On 18-01-2013 01:49, Jeff Snyder wrote:
Hi All,
I've been working on some extensions to allow users to add annotations to tree data structures (explanation of the idea here: http://je4d.blogspot.co.uk/2013/01/boostintrusive-annotated-trees-part-1.htm...).
Very intesting and useful. So +1 for interest. Question: have you thought about how difficult this is to add to Boost.MultiIndex/Boost.Bimap? -Thorsten
Thorsten Ottosen <thorsten.ottosen <at> dezide.com> writes:
Very intesting and useful. So +1 for interest.
Ta!
Question: have you thought about how difficult this is to add to Boost.MultiIndex/Boost.Bimap?
I haven't given it any thought until now. In principle I don't see any problem with adding it to either.
From a MultiIndex user's perspective, you'd be adding augmentations to specific ordered indexes.
I expect the main difficulty would just be the duplication of effort. I don't think that having the Intrusive augmentations code available would make the task of adding augmentations to MultiIndex/Bimap much quicker. But I could be wrong on that last point - I'll take a look at multi-index sometime (no promises of when) to get a better idea. It's a pity that these libraries aren't built upon Boost.Intrusive; that'd make it rather easy! Cheers, Jeff
on Thu Jan 17 2013, Jeff Snyder <jeff-boostlists-AT-caffeinated.me.uk> wrote:
Hi All,
I've been working on some extensions to allow users to add annotations to tree data structures (explanation of the idea here: http://je4d.blogspot.co.uk/2013/01/boostintrusive-annotated-trees-part-1.htm...).
This isn't a new library submission, but it's a fairly substantial modification to Boost.Intrusive, so I've got the following questions on my mind:
1. Is there interest in having such functionality in boost?
+1
2. If so, should the changes go through the formal review process?
+0 Like Thorsten, I'm going to suggest that you look at another library already in Boost. http://boost.org/libs/icl Interval containers are implemented using annotated trees IIRC. -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost
Dave, Dave Abrahams wrote:
Like Thorsten, I'm going to suggest that you look at another library already in Boost.
Interval containers are implemented using annotated trees IIRC.
No, you don't recall correctly. ICL is not implemented using augmented trees, but somehow it got approved anyway. </rant> (BTW, "augmented tree" is the normal terminology, not "annotated tree", ) Phil.
Hi Jeff, Jeff Snyder wrote:
I've been working on some extensions to allow users to add annotations to tree data structures (explanation of the idea here: http://je4d.blogspot.co.uk/2013/01/boostintrusive-annotated-trees-part-1.htm...).
"Augmented trees". There are been several recent proposals of this sort. I last posted here: http://thread.gmane.org/gmane.comp.lib.boost.devel/236328 That has links to the other proposals on this list.
1. Is there interest in having such functionality in boost?
Yes, but we need to get it right. In my opinion, we need something that's sufficiently generic to cover the about-3 use cases. I'm unclear why this should be added to Boost.Intrusive, rather than being a top-level library in its own right. Regards, Phil.
On Sat, Jan 19, 2013 at 3:17 AM, Phil Endecott < spam_from_boost_dev@chezphil.org> wrote:
Hi Jeff,
Jeff Snyder wrote:
I've been working on some extensions to allow users to add annotations to tree data structures (explanation of the idea here: http://je4d.blogspot.co.uk/**2013/01/boostintrusive-** annotated-trees-part-1.html<http://je4d.blogspot.co.uk/2013/01/boostintrusive-annotated-trees-part-1.html> ).
"Augmented trees".
+1 I agree, this and other links in the very first message refer to variants of augmented data structures.
There are been several recent proposals of this sort. I last posted here:
That has links to the other proposals on this list.
This is another recent discussion of augmented data structures, mostly red-black trees: http://boost.2283326.n4.nabble.com/new-proposal-order-statistics-tree-td4640...
1. Is there interest in having such functionality in boost?
Yes, but we need to get it right. In my opinion, we need something that's sufficiently generic to cover the about-3 use cases.
I'm unclear why this should be added to Boost.Intrusive, rather than being a top-level library in its own right.
Unlike, basic data structures, the augmented data structures can efficiently support both copy and move semantics. This is why I also wonder why Boost.Intrusive only? Regards, Vadim Stadnik
El 18/01/2013 20:27, Vadim Stadnik escribió:
Unlike, basic data structures, the augmented data structures can efficiently support both copy and move semantics. This is why I also wonder why Boost.Intrusive only?
Maybe because Boost.Intrusive algorithms don't require a concrete data-structure, so anyone could write its own container (even multi-index one) using Boost.Intrusive utilities. As Boost.Container is based on Boost.Intrusive creating non-intrusive augmented trees would be quite easy. Best, Ion
On 18/01/13 19:27, Vadim Stadnik wrote:
On Sat, Jan 19, 2013 at 3:17 AM, Phil Endecott < spam_from_boost_dev@chezphil.org> wrote:
"Augmented trees".
+1
I agree, this and other links in the very first message refer to variants of augmented data structures.
Agreed.
1. Is there interest in having such functionality in boost?
Yes, but we need to get it right. In my opinion, we need something that's sufficiently generic to cover the about-3 use cases.
Absolutely. What I've got currently is generic enough to support all of these use cases.
I'm unclear why this should be added to Boost.Intrusive, rather than being a top-level library in its own right.
An augmented tree library would still have to provide a fully-featured binary tree, and you can't just write it as a wrapper around another library's tree implementation. If my modified Boost.Intrusive were added as a library in its own right, then Boost.Intrusive itself[1] could just become a wrapper that removed support for augmentations. I don't see a lot of value in having that split. I'm not saying that boost.intrusive should gain an augmented-tree-based interval tree, or countertrees. Those seem like good candidates for top-level libraries to me, but built upon a container library with generic support for augmentations. So, why Boost.Intrusive instead of any other container library? Ion covered my main reasons for this in his reply. - There were circumstantial reasons; the project I needed an augmented tree for also needed it to be an intrusive tree. - Intrusive containers are the lowest common denominator. Someone wanting a conventional tree can make do with an intrusive tree, but not the other way around. This makes the functionality available to the widest audience. - Support can easily be extended to non-intrusive containers via Boost.Container, since it's built upon Intrusive. - Support for augmented trees can be easily and seamlessly added to Intrusive's existing API
Unlike, basic data structures, the augmented data structures can efficiently support both copy and move semantics. This is why I also wonder why Boost.Intrusive only?
I'm not sure I get the point about copy/move semantics here - how does augmenting the data structures alter the efficiency of copies and/or moves? Cheers, Jeff [1] Except the bits of Intrusive that aren't binary trees
On Tue, Jan 22, 2013 at 12:47 AM, Jeff Snyder < jeff-boostlists@caffeinated.me.uk> wrote:
Unlike, basic data structures, the augmented data structures can
efficiently support both copy and move semantics. This is why I also wonder why Boost.Intrusive only?
I'm not sure I get the point about copy/move semantics here - how does augmenting the data structures alter the efficiency of copies and/or moves?
My question was mostly concerning copy semantics. Intrusive containers do not store copies of values and they are not copyable, but copy semantics is must for STL compliant containers and for many C++ algorithms. Ion and you have already explained how it can be achieved with Boost.Container. For trees the group of move semantics functions and operations includes not only swap, but also join and split. The last two operations provide more efficient support for STL interfaces in augmented data structures than in basic ones, since they avoid linear time re-counting of moved elements. Copying one element and moving any number of consecutive elements have in theory the same logarithmic complexity. Thus, intrusive containers should benefit from augmented trees. This is a predictable advantage. Regards, Vadim Stadnik
participants (6)
-
Dave Abrahams -
Ion Gaztañaga -
Jeff Snyder -
Phil Endecott -
Thorsten Ottosen -
Vadim Stadnik