Re: [boost] [tree?] STL like tree data structure in boost?

Subject: Re: [boost] [tree?] STL like tree data structure in boost?
From: Bernhard Reiter (ockham_at_[hidden])
Date: 2009-11-02 20:10:01

Am Montag, den 02.11.2009, 21:28 +0100 schrieb Thomas Klimpel:
> Bernhard Reiter seems to be actively developing a Boost.Tree library:

yes i am! (see below)

> https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree
> 
> https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/doc/html
> 
> Does anyone know whether it is a good idea to use this library?

well, sort of. since i started working on this, there've been a lot of
changes and refinements in my design, which lead to delays. anyway, i'd
sure appreciate if people tried out the current state -- binary_tree
should work quite ok now, as should forest, though the latter is still
lacking algorithms due to some previous issues and recent restructuring.

> The following thread might also be interesting:
> http://lists.boost.org/Archives/boost/2009/07/153719.php

i didn't follow that discussion, but i'm about doing what people seem to
have been asking for back then: focus on an actual tree api (built
around concepts), ie provide data structures like binary_tree (and eg
forest built around it), algorithms such as successor(preorder, cursor),
and cursors as the tree equivalent to stl iterators. 

most tree designs i've seen out there give you a (n-ary) tree and a
rather fat interface with iterators for any given purpose (ordering),
while i'm rather trying to untangle things -- which has been tedious at
times, but rewards you with components that are supposed to be more
generic, such as forest being a binary_tree based adaptor, or the
ascending_cursor adaptor (which implements the textbook example of an
explicit stack based ascending cursor as an adaptor wrapped around a
descending cursor, allowing it to be used in algorithms requiring
ascending cursors). For balanced trees, there will be balance (also
wrapped around binary_tree)

so yeah, i hope my attempt is what is closer to the boost way, but i'm
afraid there's still some (sometimes pioneering) work ahead in order to
refine the design (and concepts) while optimising the implementation --
the past two weeks svn logs can possibly give you an idea.

that said, i'd be more than happy about some feedback about my work!

kind regards,
bernhard

> Regards,
> Thomas