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 discussing designs? I thought it would be grafted on at the end.
I am new to the submission procedure and to the boost mailing list, so I don't know the answer to this question. I added the Allocator stuff to make it more compatible with the standard library *as early as possible* without worring about rewriting a lot of code to make it Allocator-enabled.
Thanks for your thoughts, suggestions and comments, Reece H Dunn
-rhd- mailto:[EMAIL PROTECTED]
_________________________________________________________________ Stay in touch with MSN Messenger http://messenger.msn.co.uk
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
