Re: [boost] A generic tree manipulation library

From: Reece Dunn (msclrhd_at_[hidden])
Date: 2003-03-24 08:06:46

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 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:msclrhd_at_[hidden]

_________________________________________________________________
Stay in touch with MSN Messenger http://messenger.msn.co.uk