Re: [boost] proposal for tree container

Subject: Re: [boost] proposal for tree container
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-07-06 10:39:42

>
> On a regular basis, users of my 'tree.hh' library ask me whether I
> would be interested in submitting it to boost. As you may have guessed
> from the name, tree.hh is a templated n-ary tree container class in
> the spirit of the STL, but of course deviating from it in the sense of
> offering various ways of iterating over the tree. More info at
>
>   http://www.aei.mpg.de/~peekas/tree/
>

>
> Back in 2002 I tried to estimate the interest for inclusion in boost,
> see
>
>   http://lists.boost.org/Archives/boost/2002/10/37383.php
>
> The most serious criticism back then was the 'lack of abstraction'
> (for more details please consult the original thread), and I didn't
> have the time to address that.
>

I've actually looked at your implementation several times over the last... I
don't know... 5 years? and wondered if it would ever become part of a larger
library. I certainly seems like a viable addition to Boost.

If you're referring to comments about a generic tree abstractions (i.e.,
tree concepts), then I have to admit that I am farly disappointed in results
of the previous discussion. Obviously, you aren't suggesting the
implementation of a generic tree library (a la BGL), just one particular
implementation.

The development of concepts (in the SGI/BGL/C++0x sense) is best done if you
have a collection of generic tree algorihms, which would allow you to
classify generic trees, and abstract their commonalities. So while we all
know that there are tons of kinds of trees (red-black, avl, binary, n-ary,
multiway, b-trees, b+-trees, treaps, splay trees, tries, suffix trees, radix
trees, etc., etc., ad nauseum) we don't really have a list of generic tree
algorithms, nor do we have a lot of tree data structures to throw at them.

If there is going to be a discussion about adding tree.hh to Boost, then I
would hope that the discussion focuses on your implementation as a
standalone data structure, and not as a complete generic library.
Comparisons of tree.hh to the STL or BGL seem inappropriate to me.

Given the continuing interest by users of tree.hh to propose it for
> inclusion in boost, I would like to give this another shot and see
> what's the current opinion. While I would be happy to clean up the
> code, I do not have the time to do a substantial rewrite (along the
> lines suggested in 2002), but would be interested to help someone else
> do that.

Along these lines, I think it might be a good idea to put tree.hh in the
sandbox along with Reiter's 2006 work and see how things develop from there.
Comparisons with Adobe's forest class are also interesting.

Andrew Sutton
andrew.n.sutton_at_[hidden]