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.