Re: [Boost-Users] Re: Re: n-ary ordered tree template in boost ??

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-09-03 16:06:38

Hi Marc,

Currently you're thinking about detailed implementation issues and
particular data-structures. However, my comments were not directed towards
these details, but instead towards what kind of *concepts* we will need to
have for a complete framework of tree data structures and algorithms. Of
course, you may only be interested in a particular kind of tree and tree
implementation, which is fine, but it would be nice if that fit into a
broader framework which could at a later time include other kinds of trees
and tree implementations.

On Tue, 3 Sep 2002, Marc Cromme wrote:
yg-boo> On Tue, 03 Sep 2002 04:54:19 +0200, Jeremy Siek wrote:
yg-boo>
yg-boo> > I for one would like to see trees in boost. There's several variations
yg-boo> > that would be nice
yg-boo> >
yg-boo> >   both ordered and unordered
yg-boo> >   N-ary, where N is fixed at compile time, and the same for every node
yg-boo> >   N-ary, where each node can have a different run-time specified
yg-boo> >     number of children
yg-boo>
yg-boo> I think the most useful is a rooted ordered compile-time fixed
yg-boo> N-ary tree to start with: ordering is no great hassle and can just
yg-boo> be neglected when you do not need it.
yg-boo>
yg-boo> The notion of a run-time node dependent n-ary tree is in praxis
yg-boo> the same as a tree with nodes of arbitrary children count. How
yg-boo> often do we really need this ?? Can we lay this out linear in
yg-boo> memory space?? Or do we need nodes containing std::vectors of
yg-boo> pointers to children nodes ??  Sounds ugly to me ...

There are lots of uses for this. How about representing XML? How about
representing the results of a breadth-first search of a graph. I could go
on and on... True, you (or whoever implements this kind of tree) won't be
able to use some of the fun tricks for reducing memory consumption, but
they are still important.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------