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@gmx.de> 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.