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 17:13:23

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

Sorry, I pasted the wrong url. This is a bit more detailed:

https://github.com/boostorg/intrusive/pull/3

>
>> 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.

Ok. Right now you could obtain "node_ptr" using iterator.pointed_node() 
and use tree::node_traits::get_left/right/parent to obtain access to 
other nodes. We are missing something to convert a node into an 
iterator, though. You have:

explicit tree_iterator(const node_ptr & nodeptr, const 
const_value_traits_ptr &traits_ptr)

where you could use a null const_value_traits_ptr (non-null values are 
used when value traits are stateful). A lot of hacks, but at least you 
can try to go ahead.

In any case, we could add new members to the tree iterator so that we 
can move to parent, left or right. In case there is no left/right node 
we can choose to obtain a "null" iterator (returning "end" would be 
extremely expensive as iterators store a pointer to a node and we would 
need to climb the tree just to get the header node.

If we agree on some common operations, we can open a ticket and 
implement some basic operations for trees.

Best,

Ion