Re: [boost] A generic tree manipulation library

From: Reece Dunn (msclrhd_at_[hidden])
Date: 2003-03-21 07:07:51

Rene Rivera wrote:

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

I'd be happy to share ideas. I have included the implementation that I was 
referring to in the previous e-mail. I know that it needs a lot of work if 
it were to be submitted to boost, but I just wanted to gague reactions 
before I did any major work to it.

The tree_node_map class provides an implementation to a basic tree node of 
variable branching size. The implementation here uses the std::map to 
implement the children, but this could equally be a std::list, std::vector 
or any suitable container; it could even be a low-level implementation (for 
performance) or a fixed-size array (for n-ary nodes).

The tree class is just a wrapper around a tree node that provides access to 
a root element. This would need some major work and additional support (e.g. 
post/pre/in-order traversal iterators) if it were to be useful.

The trie class is an application of the tree class that provides operations 
for adding and looking for items in an associative container-like way. There 
is a bug with the word count (it does not track with std::map<>::size() on 
the same data).

The trie class operates on a key that is a sequence of elements. If the key 
is std::string, then the trie class will construct the tree operating on 
characters as lookup for the child nodes, e.g.

*-h-e-l-l-o-$ /-$
+-w-o-r-l-d--+-s-$

This is useful for associative lookup in two ways:
*  it should provide faster lookup than a std::map because it is iterating 
through the key as it moves down the list, therefore it does not need to 
recompare the strings every time it moves around the tree (unlike the 
red-black binary tree used in most std::map implementations)
*  it stores the strings in a compressed form (although this benefit is 
removed by the need for the space to store the tree structure)

The lookup function for the trie class will add an item if the key is not 
currently in the trie structure, whereas find will not. Both operate on a 
first to last iterator principle.

I hope this helps with your submission in the Summer. If you want we could 
combine forces to develop the library.

-rhd-

_________________________________________________________________
It's fast, it's easy and it's free. Get MSN Messenger today! 
http://messenger.msn.co.uk