[boost] A generic tree manipulation library

From: Reece Dunn (msclrhd_at_[hidden])
Date: 2003-03-15 06:40:02

Is there a library in boost that allows the manipulation of n-ary trees 
(including binary trees and arbitary branching trees as subsets of this).

If so, does this have support for trie structures (a dictionary-like object 
where each level of the tree represents the nth letter in a word contained 
in it).

Also, how do the iterators work? Is there a concept of moving across the 
siblings and moving up/down the tree?

I have had a few ideas about implementing a library along these lines if 
none already exists. The idea is to add a new set of iterator categories:
   up_iterator --> has a function up() that moves the iterator *up* the 
container (in a kind of 2D space).
   down_iterator --> has a function down() to move the iterator *down* the 
container.
   updown_iterator --> has both an up() and down() function for moving 
across the y-axis of the container (like what the bidirectional_iterator is 
to the forward_iterator)

Will it be better just to have the down and the updown iterators so it is 
more like the forward and bidirectional iterators? Can these types be added 
to other 2D-like containers (vector2d anyone???)

The idea is to have general requirements for what constitutes a *tree node* 
that allows them to be manipulated and accessed in a common way - whether it 
is a binary tree node, an n-ary tree node using an array or an arbitary 
branching node using a linked list for siblings.

There is plans to have a tree class that uses an implementation of a tree 
node, giving access to the root of the tree and possibly additional stuff.

The tree class can then be used to implement a trie data structure, possibly 
as a trie_map (using the associative container interface to give the 
container very fast lookup) or as a seperate class that is used to implement 
trie_map, trie_multimap, trie_set and trie_multiset containers.

Feedback would be greatly appreciated,
   Reece H Dunn

-rhd-
mailto:msclrhd_at_[hidden]

_________________________________________________________________
MSN Messenger - fast, easy and FREE! http://messenger.msn.co.uk