Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk