Re: [boost] A generic tree manipulation library
Darren Cook wrote:
I'm using new/delete currently, but was planning to use boost.Pool once my
design has settled down.
I was considering using some sort of pooling/block allocation method to
improve allocation efficiency, but was leaving that as an optimization
consideration for when I got the design sorted.
A std::map would be too much overhead for my particular application (which
tends to have deep trees with few branches).
I'm aware of that. I used a std::map to show an example implementation
without worrying about the actual details.
I was also planning to write an implementation of the tree_node interface
for an n-ary tree; something like:
template< typename T, long n >
class nary_tree_node
{
public:
typedef nary_tree_node * node_pointer;
typedef nary_tree_node * iterator;
private:
node_pointer nodes[ n ];
T data;
public:
inline iterator first_child()
{
return( nodes );
}
inline iterator last_child()
{
return( nodes + n );
}
public:
inline iterator operator[]( index_type it )
{
// range checks?
// compatible index type??
return( nodes[ it ]);
}
};
The other methods and typedefs would be implemented to be consistent with
the other implementation. This was the idea: you can supply your own
implementation or use one of the tree node implementations provided.
Since you are using a binary tree node type, you can use something like:
typedef nary_tree_node< std::string, 2 > binary_node;
Finding the previous sibling or parent in my tree requires starting from
the root node (or keeping a stack of nodes visited).
Would it be more efficient to have a pointer to the parent node as well?
This would allow you to move up to the parent and then along to the next
node without having to start again from the root.
Do you have any example usage?
The trie class is an example of how to use the tree class and I have a test
program for this, but I do not have any other examples at the moment.
I wonder if it would be better to approach this from the
algorithms/iterators side and come to the containers later? I.e. what
operations do you need to do on the trees?
That is a good suggestion.
There should be an iterator for the tree node that will iterate along the
siblings; this has already been accounted for. I was also thinking about
extending this iterator to provide "up" and "down" iterator types to move up
to the parent and down to the first child. I use the names up and down so
that the types could be used in other 2D iterator types.
The tree should provide several navigational iterators:
[1] inorder_iterator: for in order traversal;
[2] preorder_iterator: for pre-order traversal;
[3] postorder_iterator: for post-order traversal;
[4] iterator: for navigating along the leaf nodes inorder.
There may be others that I have not thought of. As for the algorithms that
are to be supported, there are several points:
[1] It should be easy to use the standard algorithms with the tree
implementation wherever possible, e.g.
std::for_each(
tree.inorder_begin(),
tree.inorder_end(),
...
);
Could it be possible to use iterator adaptors like are used for containers
and the functors (with binder1st, etc.)?
As a couple of examples I need:
1. for_each() of first child at each node.
2. display all node values in the tree on stdout.
This may be possible through iterator adaptors:
std::for_each(
tl::iter::first_child( tree.preorder_begin()),
tl::iter::first_child( tree.preorder_end()),
...
);
std::for_each(
tl::iter::indentor( tree.preorder_begin()),
tl::iter::indentor( tree.preorder_end()),
...
);
NOTE: This is experimental at the moment. I do not have an implemetnation of
the above, it is just a preliminary look at a possible solution to the above
problem.
The idea for the indentor is to keep a track of the level that the iterator
is on in the depth of the tree, and provide an output method something along
the lines of:
indent according to level
output the data to the output stream
I have an implementation of some indentation technology that I have used for
my own tracing functionality. I am looking at submitting that to the boost
mailing list later this week (both the indentation stuff and the tracing
stuff), I just need to prepare it for submission.
[2] There should be specializations of the standard algorithms to provide
proper integration with the STL. The most noticable example of this would be
std::swap.
[3] There should be a whole set of algorithms that are designed to fit in
with a tree structure. An example would me tl::mirror to transform a tree to
the mirror image of itself.
-
There should be the ability to construct a tree from another tree (copying
the entire tree) or constructing it from a tree node (making that node the
root of the new tree).
BTW, I'm new to Boost. Is it normal to include all the Allocator stuff
early on when discussi
Re: [boost] A generic tree manipulation library
I'm very interested in having tree container concepts in Boost. 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). I've been implementing a tree class recently where each node has: Node* first_child; Node* next_sibling; I'm using new/delete currently, but was planning to use boost.Pool once my design has settled down. A std::map would be too much overhead for my particular application (which tends to have deep trees with few branches). I briefly played with one block of memory per branch and doing away with the first_child pointer, but decided to come back to that idea later. It has a problem with identifying the last node; either you need to store "branch length", or a flag to mark the end (in which case you've saved no memory; still may have a speed advantage however). Finding the previous sibling or parent in my tree requires starting from the root node (or keeping a stack of nodes visited). 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. Do you have any example usage? I wonder if it would be better to approach this from the algorithms/iterators side and come to the containers later? I.e. what operations do you need to do on the trees? As a couple of examples I need: 1. for_each() of first child at each node. 2. display all node values in the tree on stdout. I'm not yet clear what I want from the second option there. Some kind of indenting I guess. BTW, I'm new to Boost. Is it normal to include all the Allocator stuff early on when discussing designs? I thought it would be grafted on at the end. Darren ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] A generic tree manipulation library
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
#ifndef __STL__TRIE
#define __STL__TRIE
# include
# include
# include
# define null NULL
namespace stl
{
template< typename T, typename Index = int, class Allocator =
std::allocator< T > >
class tree_node_map
{
public:
typedef T value_type;
typedef Allocator
allocator_type;
typedef Index index_type;
public:
typedef typename Allocator::template rebind< T >::other
value_allocator;
public:
typedef typename value_allocator::reference reference;
typedef typename value_allocator::const_reference
const_reference;
typedef typename value_allocator::pointer pointer;
typedef typename value_allocator::const_pointer
const_pointer;
public:
typedef typename value_allocator::size_type size_type;
typedef typename value_allocator::difference_type
difference_type;
public:
typedef std::map< index_type, tree_node_map * >
child_container;
public:
class iterator
{
friend class tree_node_map;
private:
typename child_container::iterator node;
public:
inline iterator & operator++()
{
++node;
return( *this );
}
inline iterator & operator--()
{
--node;
return( *this );
}
public:
inline typename tree_node_map & operator*()
{
return( *( node -> second ));
}
inline typename tree_node_map * operator->()
{
return( node -> second );
}
public:
inline bool operator==( const iterator & i )
{
return( node == i.node );
}
inline bool operator!=( const iterator & i )
{
return( n
Re: [boost] A generic tree manipulation library
[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
[boost] A generic tree manipulation library
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 in it). 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) 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 -rhd- mailto:[EMAIL PROTECTED] _ MSN Messenger - fast, easy and FREE! http://messenger.msn.co.uk ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
