Boost logo

Boost :

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:

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



Boost list run by bdawes at, gregod at, cpdaniel at, john at