Boost logo

Boost :

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

* 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

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. -
-- rrivera/ - grafik/ - 102708583/icq

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