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

From: Joao Abecasis (jpabecasis_at_[hidden])
Date: 2005-02-24 05:49:29

Hi!

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:

1) TreeContainer

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 
and sub-trees.

2) TreeIterator

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.

3) TreeNode

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.

Best regards,

João Abecasis