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

From: Rene Rivera (grafik.list_at_[hidden])
Date: 2005-02-23 00:01:46

Justin Gottschlich wrote:
> Dear Boost library members -
>  
> My name is Justin Gottschlich and have just recently joined the boost
> mailing list. Since this is my first post, I would first like to apologize
> in advance for any e-mail inequities I manage to include in this e-mail.
>  
> I'm e-mailing is to ask if there may be interest in a generic tree container
> for addition to Boost.

Obviously there's interest ;-) But..

Like Thorsten I would think it a requirement that some basic 
interfaces/concepts come ahead of an implementation. What I don't see 
from your proposal, nor Kaspers tree, is some consideration for what 
makes a container a tree. I think we desperately need some definitions 
of what operations should be part of a tree, n_ary_tree, binary_tree, 
rank_tree, b_tree, etc.

Additionally, I'm also of the opinion that the "iterator" concept should 
be kept as it's currently used in STL. An object that does more than an 
iterator, because it happens to be an iterator in a tree should be 
called something else, "cursor" comes to mind. If it's really 
masquerading as a sub-tree, or a tree, then call it a tree. If it's a 
pointer to a node in the tree, then perhaps a "node_pointer". Mixing the 
terms will just cause more confusion than it's worth. Reading some of 
your later posts I can see the confusion already creeping in. My 
suggestion would be for you to formalize the different parts of a tree:

* node; Holder for the value, structure pointers, and tree coloring 
information

* cursor; pointer to a node with tree specific operations to move the 
cursor within the tree and to interrogate the tree

* iterator; linear traversal of the nodes in the tree

* tree; the container of nodes and producer of cursors and iterators, 
and the needed allocators

With those terms you can hopefully see how one could implement each in 
terms of the others. For example iterators would be implemented in terms 
of cursors such that they would be orthogonal to the type of tree they 
are traversing.

But to not talk in a complete vacuum here's my implementation of a 
rank_tree..

        http://redshift-software.com/~grafik/RankTree.h

It demonstrates how if you separate out the node you can write an 
iterator independent of the tree itself. I only have one type of 
iterator, really an in-order iteration, but it would be straight forward 
to reformulate it in terms of a cursor.

I think the most important aspect we need to keep in mind is that having 
a tree container, or a set of tree containers, is not to have basic 
n-ary tree to build from. But to have generic algorithms, programs, 
iterators, mutators, etc. that can operate on different kinds of tree 
implementations so that programmers can make storage and algorithmic 
trade offs in programs. Having a n-ary tree in STL doesn't help me much 
because I would never use it. But having various tree implementations in 
STL such that I can write an algorithm that works regardless of which 
type of tree i use it on is the real win.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq