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

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
containers?

----- 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

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost