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

Subject: Re: [boost] [intrusive] More features for treap?
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2014-10-20 12:38:48

> Ion Gazta?aga <igaztanaga_at_[hidden]> 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/intrusive

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.