Re: [boost] any interest in a 'tree' container?

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-10-10 12:24:28

OK, now I've read (very briefly, and not in-depth). A short comment
about the documentation: it ends after merge, without details. And the
semantics of sort() or equal() is really strange without further
introduction. I suspect that you would clear up a lot of minds if you
added a section about the intended use of your class. I can't understand
how it would be useful as a data structure (say for implementing set),
but to model filesystems certainly.

On Thu, Oct 10, 2002 at 10:55:58AM +0200, Kasper Peeters wrote:
> Despite the emphasis of the STL on 'one-dimensional' containers, I
> have tried my best to keep the tree class as compatible as possible
> with the STL algorithms. In cases where this is impossible (sort and
> compare for instance), alternative algorithms have been provided.

What's missing to me is the concept of a tree. While it's easy to come up
with one implementation of tree, and many people do, it's much harder to
provide a unified interface (a concept) which can be used by all those
implementations. Such a concept is necessary if you want to write a
generic algorithm (e.g. a parser that uses a tree) which is templated by
the tree class (say to allow different tree implementations).

If you had given the freedom to store the children as a container, say,
you would allow implementations that store the children as an array
instead of a doubliy linked list (which is hardwired in your design).

What's missing most to me in your library is the abstraction. I don't
even know from the documentation if you're modeling an n-ary arbitrary
tree, or a search tree (it seems not the case). But if it's not the
search tree, what's the semantics of equal() for trees, and why is this
useful?

Anyway, I'm not trying to write a formal review, merely to illustrate
the problems I perceive with your library. It's very likely such
problems would crop up during a formal review so I thought I might echo
them in advance to prepare you for what's to come.

> Several users have suggested I offer this for inclusion in Boost.  I
> am willing to re-license 'tree.hh' and offer it for inclusion if there
> is any interest. Let me know.

After a first reading, while I'm sure there is an interest in such a
class (and especially in connection with the filesystem library), it
doesn't come close to what I would expect of a Boost.Tree library.
To illustrate the difference, I would simply mention the Boost Graph
library, which has concepts and generic algorithms, wouldn't have been
the same if all it provided was a simple adjacency_graph class. There
might be such a class added as a separate library, and indeed it could
be useful, but the contribution of the BGL is so much more because of
the design.

Nevertheless, I would welcome an addition of a class tree, if it was
clear that it's not a Boost.Tree library and if it's useful to some
people (but not to me in this case). I hope I didn't discourage you,
but just focused your efforts away from the pereived pitfalls.
Best,
-- 
Herve'