On Wed, Feb 23, 2005 at 05:42:12AM -0800, Jeff Mirwaisi <jeff_mirwaisi@yahoo.com> 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