Re: [boost] Re: boost::tree advice?

From: Dan Rosen (dan.rosen_at_[hidden])
Date: 2005-03-29 01:35:36

Hi again,

I had the chance to review Jeff's treelib docs and code this evening.
I have a basic understanding of template metaprogramming, but no real
experience with it. So I can't comment in much detail on Jeff's design
and implementation, other than to say that the "feature-oriented
programming" technique seems like a very interesting approach to
design in general (though I imagine the paradigm might be more elegant
if implemented as a brand new language).

The one thing of substance I can say after having read through treelib
is that it both solves some problems I believe don't need solving, and
fails to solve some problems that I believe do. I'll address one at a
time.

First, problems that don't need solving. The tree design goes out of
its way to provide an elegant system of mix-and-match descriptors.
Four of these descriptor categories are key, order, balance and search
optimization. I believe these four to be unnecessary, for the
following reasons:

  - Specifying a sort ordering for the tree other than what the
library refers to as "oriented" (i.e. elements stay where you put
them) implies that you care not about the tree structure itself, but
the strict ordering of elements in the tree. This need is already met
by std::set and std::multiset (or in concept terms, "Sorted
Associative Container").

  - Specifying a balance or a search optimization for the tree (if I
understand these concepts correctly) implies that you care not about
the relative position of elements in the tree, but the algorithmic
complexity of operations in the tree (such as insert, remove, find,
etc.). This need is also already met by Sorted Associative Container.

  - Specifying a key type separate from value type could maybe be
construed to imply that you're using the tree primarily as a fast
search mechanism. I'm less confident about this assertion, but it
seems like client's uses might well be met by std::map here.

In short, my belief is that programmers only want to use a tree when
it's the tree structure in particular that's important to them.
Otherwise they will go with something like std::map, which may be a
facade to a red-black tree, but offers a simpler interface isolated
from implementation details. So eliminating these four descriptors
leaves behind -- at least in the documentation -- "primary" (i.e.
binary tree, k-ary tree, multi-way tree), value type, and allocation
descriptors. But this is a manageable number of axes to represent
using the more traditional model of template programming exemplified
by the C++ standard library. Or, more concretely, it's reasonable with
only these three axes to provide a few tree types (tree<>,
binary_tree<>, k_ary_tree<>) parametrized on value and allocator type.

Now, on to problems that do need solving. To restate my assumptions, I
believe the most significant use case for trees is direct manipulation
and traversal of the tree structure. For example, my personal interest
in seeing a good generic tree container implemented is so I can
represent turn-based games (where the data stored at each node is a
player's turn, and players can undo turns or explore variations when
reviewing games). Part of the value that I think would be provided by
a well-designed tree structure is a set of concepts that can operate
nicely with standard algorithms, such as std::find(),
std::remove_if(), etc. Those needs don't seem to be a primary concern
for treelib. Of course, that's not to say that a feature-oriented
design and interoperability on the "concept" level with standard
algorithms are mutually exclusive, and I also recognize that treelib
is a proof of concept illustrating the successful application of a
fairly radical approach to design. My only complaint is that treelib's
area of focus seems orthogonal to the problems I'm hoping to address.

If you think I might be glossing over or missing some important,
applicable points in treelib, or if you disagree with my assessment,
please do let me know! At this point, I'm a willing student. What I
hope to get out of this exercise are learning, first and foremost, and
a boost::tree to benefit everybody.

Thanks very much for your help!
dr

On Mon, 28 Mar 2005 21:35:30 +0200, Andreas Pokorny
<andreas.pokorny_at_[hidden]> wrote:
> 
> http://boost-sandbox.sourceforge.net/vault/index.php
> 
> The tree type is composed out of a set of feature. A feature is a set of
> fragment, or a single fragment. The feature type list is specified by the
> user. `A fragment is a binary meta function that produces a step-wise
> refinement of a base type by adding, hiding,overloading or overriding
> member data and member functions resulting in an augmented version of
> the base.' [JM05]. The user is allowed to add his own fragments, so it
> is possible to change the internals even after the library has been
> ``shipped'' to the user. That is also the main difference to policy
> based design, which would define a fixed set of extension points.