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
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
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
MSN Messenger - fast, easy and FREE! 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