From: Joao Abecasis (jpabecasis_at_[hidden])
Date: 2005-02-24 05:49:29
First of all I want to say I'm definitely interested in generic Tree
Containers. I started developing a tree library of my own not that long
ago but got buried in the details and had to put it on hold for a while.
I did not take the time to read your code, but went through the
discussion and wanted to share the approach and options I took in the
design of my (still to be completed) Oak Leaf library.
The first decision I made was to try to approach STL containers as much
as possible, but not where it interferes with a "nice" design. Like
STL::Containers, Trees are containers of objects. However, unlike them,
Trees are not Sequences and IMO it is an error to try to make them
behave like that "by design".
The basic concepts I came up with are:
This can be further refined into: k-ary tree container, binary tree
container, search tree container, ... In my design the binary and
ternary tree containers are given a special status but all expose the
basic TreeContainer interface.
The TreeContainer owns its nodes meaning it is solely responsible for
their lifetime. You use the container to insert, copy and erase nodes
TreeIterators are categorized according to vertical (parent-child) and
horizontal traversal (among _siblings_).
The vertical traversal category is one of ForwardVerticalTraversal
(parent to child only) or BidirectionalVerticalTraversal (both ways).
While horiontal traversal among siblings of a node follows the STL
Sequence and Iterator concepts. That is, children of a node are viewed
like an STL Sequence.
The TreeNode contains the values and color information, as well as
information on how to access other nodes like siblings, parent and
children. Not all Nodes will grant access to its siblings and parent but
all are supposed to grant access to children.
This is more an implementation detail but my trees took the Node as
template parameter so could provide different traversal/complexity
tradeoffs. As the TreeNode is not supposed to be part of the user
interface, TreeContainers and TreeIterators could be implemented with
other node types.
The User interface is made up by TreeContainers and the TreeIterators
they expose. Each TreeContainer exposes at least a
ForwardVerticalTraversal TreeIterator and this iterator should also
expose a SiblingIterator to traverse the children of the current node.
To keep the design clean and simple, depth, level, and other types of
iteration would be provided outside the containers by iterator adaptors
and by reusing BGL's algorithms. IMO interaction with the BGL is an
important point to consider for Boost Tree Library because Trees are
also Graphs and any generic Boost Tree Library should harvest what's
available in BGL.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk