[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 -- [EMAIL PROTECTED] - [EMAIL PROTECTED] -- [EMAIL PROTECTED] _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
