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

From: Andreas Pokorny (andreas.pokorny_at_[hidden])
Date: 2005-03-29 12:09:01

On Mon, Mar 28, 2005 at 10:35:36PM -0800, Dan Rosen <dan.rosen_at_[hidden]> wrote:

>   - 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.

Well, From my point of view these three aspects are important, I
already had uses for that in my applications. E.g. sometimes std::set
could be improved by if you know that the key space is restricted. Then
I would appreciate the fact that such a library exists, allowing me to
reuse lots of code, and just adding my special optimization. 
  My point in this case is, that you do not have to use these features. 
You can just not specify them. From what I know from Jeff, he
implemented these features because the untangled tree template paper by
Matt Austern, Stroustrup et al. included them too.

> 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. 

So you are here talking about a tree iterator that represents the
contents as an ordered sequence (sequence in terms of being accessible by 
calling ++it)? In the treelib that would be a: 

struct depth_first {
  templat<typename,typename Base> 
  struct appy : public Base { 
    struct depth_first_iterator : public boost::iterator_facade<...> {
      ...
    };
  } 
};

or breadth first, or maybe some templated fragments which provides a 
dynamic iteration concept. Maybe I misconceive your needs, but I believe
that these problems are solvable with the design of the treelib. 

> 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.

I fully agree with you! Due to the orthognal views, I beliebe a 
combination of both efforts could create a really versatile overhead free
tree library. Even though you do not need the features cited above,
there are people that would like to use them, and there is still more
that can be done with the library. 
  Lets say someone wants to serializer a big tree into a file, but not 
keep the full tree in memory. By defining a link_type feature, that 
turns the previous link_type into a lazy pointer, which would get the 
node structure from a file using boost::serialization, one could reuse 
lots of code, provided that the other features do not make assumptions 
that break with the new link_type.

  So in general I did not want to imply that the treelib solves your
problems, but that it provides a flexibility that I would really like
to see in boost::tree. Your points are valid, these issues (missing
iteration concept, or algorithm concept) need to be addressed, and 
solved. 

Regards 
Andreas Pokorny