Re: [boost] A generic tree manipulation library

From: Rene Rivera (grafik666_at_[hidden])
Date: 2003-03-15 14:35:57

[2003-03-15] Reece Dunn wrote:

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

No. But there was some previous discussion about Kasper Peeters tree
implementation...  

http://lists.boost.org/MailArchives/boost/msg36876.php
Boost Mailing List Archive -- [boost] any interest in a 'tree' container?

I'm very interested in having tree container concepts in Boost. It's my plan
to submit such a thing to Boost in the summer. Currently I only have a
rank_tree implementation (log2 n, or better on all ops) so having someone
else work on other types of tree implementations would be awsome ;-)

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

Haven't seen such a proposal here, yet. Along those same lines I also have a
specialized version of a trie container, hex_part_dictionary, which stores
nibles at each level of tree. But it would require a complete rewrite to be
usefull to anyone, even to myself ;-\

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

My equivalent idea was to introduce a "cursor" concept that has all the
various tree navigation operations. It would return clasic linear iterators
for some things, like the children of the current node. Here are some ops
for such a cursor: parent(), children(), rchildren(), left_children(),
left_rchildren(), right_children(), right_rchildren(), etc. It then becomes
very easy to write classical traversal algos in a generic form.

>Will it be better just to have the down and the updown iterators so it is 
>more like the forward and bidirectional iterators? 

I'm of the opinion that the closer a tree container interface is to the
standard linear iterators the less usefull it becomes as a tree structure.

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

Given the variety of ways to implement trees, both in storage and behaviour,
I would lean towards making a generic tree concept that gets implemented by
the variety of trees. As opposed to using a generic tree implementation to
store other types of trees. This is because many of the tree implementations
get their advantages from very special storage to improve speed. For example
my hex_part_dictionary stores only 4bits of the data at each level to reduce
the size of nodes and to reduce the single level branching to fit in a 16bit
field. I need to be that efficient because I need to literally store a
dictionary, as in something like Oxford English.

Other things I've thought about include:

* Having both functional and iterator versions of traversals. For example
having both: inorder_traversal_iterator class, and inorder_traversal
algorithm. The iterator would be constructed from a cursor and the algorithm
would take a cursor and visitor function.

...I had others, but they escape me right at this moment :-( ...

-- grafik - Don't Assume Anything
-- rrivera_at_[hidden] - grafik_at_[hidden]
-- 102708583_at_icq