Re: [boost] Re: Boost library inclusion: generic tree containers?

From: Andreas Pokorny (andreas.pokorny_at_[hidden])
Date: 2005-02-23 11:02:08

On Wed, Feb 23, 2005 at 05:42:12AM -0800, Jeff Mirwaisi <jeff_mirwaisi_at_[hidden]> wrote:
> It, perhaps foolishly, tries to present the building
> blocks for the construction of a large set of
> different tree types with different balancing and
> book-keeping requirements.

I would like to comment on the possiblities of that library. I already
investigated the implementation of jeffs library a few weeks ago. From a
very distant view point jeff does aspect oriented programing with
c++ templates. All features are implemented using aspects or mutators that
modifiy the result of the previous modifications ( the order is
important, and maybe still a design issue ). 

To present the flexibility of that library, I would like to present a 
case study.
At the time of my first deep look, I was looking for a tree type that
efficiently stores a set of integers, and usually many of these integers 
are adjacent. std::set needs a node for every integer, a better solution
would be to store ranges of integers in each node. 
  It is really simple to create the merge and split functions needed
when inserting and deleting elements is quite easy for these ranges. But 
as soon as you start adding things like balancing, the code gets really
complex. Here is where Jeffs library makes everything simpler, balancing
is already implemented, so you just need to hook into the insertion and
deletion process of a balanced binary tree, with a pair as key/value type. 
These hooks can be added by defining typedefs ( so called tags, in the 
terminology of the library), which notify the fact that there exisits an
insertion/deletion hook in the mutator. 

The provided features are really generic, it is for example possible to
redefine the link type, which might be a simple pointer to a node by 
default. E.g if you try to write a B*-tree for large datasets, you do 
not want to load the complete tree into the memory, you just want to
load a single node at once. So by turning the linktype into a special
pointer type you can load parts of the data on demand. boost::rel/rtl
could use that library to implement file based tables, by defining a 
mutator, that turns the plain pointer into a lazy pointer, and a mutator
that implements the load and save methods for boost::serialization
integration. 

So I really would like to see that library in boost. From all tree 
templates I have seen yet, this one is the only one that does not 
block the developer in any aspect. 

Maybe we should consider implementing other containers using the
techniques presented by Jeff. 

Regards
Andreas Pokorny