[boost] Re: RB Trees with extra information

From: David B. Held (dheld_at_[hidden])
Date: 2003-09-16 02:23:50

"Igor Maximchuk" <sp4sp_at_[hidden]> wrote in message
news:bk6b0t$nrp$1_at_sea.gmane.org...
> [...]
> I need the abiity to add extra information in tree node.
> This is not typical "node data".

My policy-based design supports the use of custom node
policies which can define whatever extra data that they need.
I use this policy to provide normal and "indexed" set/maps
which allow a log n index lookup, which actually sounds
similar to what you are doing.

> [...]
> something like this, maybe
> tmplate<calss data_type, class extra_info_type, class
>     maintaner_functor>
> class _rb_tree

Take a look here:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/boost-sandbox/boost-sandbox/boost/map.hpp?rev=1.2&content-type=text/vnd.viewcvs-markup

And here:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/boost-sandbox/boost-sandbox/boost/detail/tree.hpp?rev=1.2&content-type=text/vnd.viewcvs-markup

And here:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/boost-sandbox/boost-sandbox/libs/map/src/tree.cpp?rev=1.2&content-type=text/vnd.viewcvs-markup

Note that it's built on the STLport implementation (but
de-uglified, since I was going to submit it for review, but
never got around to it).  Perhaps my implementation
already does what you are looking for?  Take a look at
IndexedNode, in particular.

Dave