Boost logo

Boost :

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




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk