Boost logo

Boost :

From: Brian Braatz (brianb_at_[hidden])
Date: 2005-02-24 17:36:02

Extremely interesting.

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.

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Richard Peters
Sent: Wednesday, February 23, 2005 12:44 AM
To: boost_at_[hidden]
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
> 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
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
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
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
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.

best regards,

Richard Peters

Unsubscribe & other changes:

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