From: Brian Braatz (brianb_at_[hidden])
Date: 2005-02-24 17:36:02
I am working on a similar thing.
Except I am doing this-
the iterators take policies which tell how to get the parent and
children of a node
I am sorry I have not dug DEEP into either bodies of work yet.
But in a nutshell, I am holding a tree of objects, and then using a
template library (similar to BIL- except it is "classical Interface
based programming") to QueryInterface (QI) the objects. (this is the
opposite of how BIL works)
I have gotten working the ability to QI the objects and apply operations
to anything in the tree from X node down based on interface supported.
This very curious technique is one I am working to evolve into something
for controlling dynamic UI objects.
In any case, I am writing this to share what I have been working on.
Maybe it will give you some ideas.
[mailto:boost-bounces_at_[hidden]] On Behalf Of Richard Peters
Sent: Wednesday, February 23, 2005 12:44 AM
Subject: Re: [boost] Re: Boost library inclusion: generic tree
----- Original Message -----
From: "Rene Rivera" <grafik.list_at_[hidden]>
> Additionally, I'm also of the opinion that the "iterator" concept
> be kept as it's currently used in STL. An object that does more than
> 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
> 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
> * 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
I think these formalizations of different parts of the tree is a very
start, but I'd like to see the iterator eliminated for a while, or at
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
the tree class should provide functions to navigate through the tree,
functions to alter the structure of a tree, like insertion, deletion,
rotation. These functions should probably work on things like the
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
course a lot of options: depth first, breadth first, only a single
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
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
any iterator type, because it doesn't have a proper meaning: a tree is
structure, not about sequence. Translating that structure into a
can be done outside the tree.
Unsubscribe & other changes:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk