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

From: Richard Peters (r.a.peters_at_[hidden])
Date: 2005-02-23 03:43:37

----- Original Message ----- 
From: "Rene Rivera" <grafik.list_at_[hidden]>

> 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

I think these formalizations of different parts of the tree is a very good
start, but I'd like to see the iterator eliminated for a while, or at least
totally decoupled from the tree: The reason for this is Separation of
Concerns. A tree class is a container quite similar like the standard
containers in that it stores values, but the big difference is that the
structure of the tree matters, instead of the sequence. Therefore, I think
the tree class should provide functions to navigate through the tree, and
functions to alter the structure of a tree, like insertion, deletion, and
rotation. These functions should probably work on things like the
above-defined cursor.

Once this tree class is built, then it is time to start thinking how the
structure of the tree should be translated to flat sequences. There are of
course a lot of options: depth first, breadth first, only a single level, or
from top to a single node. Navigating in this way is done via 'normal'
iterators. These iterators work on cursors, and should not be a part of the
tree class itself (the iterator type should not be a member of the tree
class). These iterators are like 'cursor-to-iterator adaptors'.

So I guess my point is this: The tree doesn't need a normal or default or
any iterator type, because it doesn't have a proper meaning: a tree is about
structure, not about sequence. Translating that structure into a sequence
can be done outside the tree.

best regards,

Richard Peters