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

Subject: Re: [boost] [intrusive] More features for treap?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2014-10-20 10:21:32

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/intrusive

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?

Best,

Ion