Re: [boost] [intrusive] More features for treap?

Ion Gazta?aga wrote: El 20/10/2014 15:16, Phil Endecott escribi?:

...

Dear All,

I've been looking at Boost.Intrusive's treap, and finding that it doesn't quite do what I need.

Here's an example: say I have data about earthquakes in the form (date, magnitude, description). I can store that in a treap with date as the key and magnitude as the priority. Now I'd like to be able to do operations like:

- Find the strongest earthquake between dates A and B. - Iterate over all the earthquakes with magnitude > X in date order. - For each year (or month, or decade etc) find the strongest quake.

The first two are straightforward in a treap, but the current Boost.Intrusive API doesn't (AFAICT) let me do it. (The third one is less obvious.)

I have been wondering how the API could most easily be extended to support this sort of thing, and I'm coming to the conclusion that it is probably best to expose the actual tree structure so that the algorithms for these operations can be implemented explicitly by the user code. I have had similar thoughts in the past about other trees i.e. augmented trees to implement interval trees; the choice is either (a) implement these things inside Boost.Intrusive; (b) don't use Boost.Intrusive at all; (c) extend the intrusive API to expose the actual tree structure. In cases like these extensions to treap, the new operations are simple compared to the complexities of inserting and erasing elements; being able to use the existing implementations of those operations while adding other (non-mutating?) features would save a lot of work.

Any thoughts anyone?

There are several proposals to implement augmented trees in Boost.Intrusive. I haven't reviewed them because I don't know much about augmented data structures and because of lack of time. Boost.Intrusive tree-like containers reuse binary search tree algorithms and implementing augmented data structures for all containers could be feasible. Matei David did the last effort:

https://github.com/mateidavid/intrusive/tree/augmented-bstree/include/boost/...

Looking at that, I find it really hard to see what has been added. I think my git skills are lacking.

I haven't reviewed the implementation because of lack of time but it sounds promising.

In any case, accessing tree internals might be useful in newer use cases. When you talk about "exposing the tree structure", what do you have in mind? Which kind of information do you need?

I was imagining left(), right() and parent() on either the nodes or the iterators. Regards, Phil.