[boost] Re: Boost library inclusion: generic tree containers?

From: Joao Abecasis (jpabecasis_at_[hidden])
Date: 2005-02-25 08:07:47

christopher diggins wrote:
> You do bring up very good points, and I am not sure what my position is 
> yet so I will play the Devil's advocate for now. A useful tree iterator, 
> in my view should provide access to the parent node from a given 
> position in the tree. Without that algorithms, etc. are harder to write, 
> and the tree is much harder to manage. Being able to move to a parent 
> node makes the various traversals trivial (and without overhead as far 
> as I can tell). I also do not believe that implementation should dictate 
> interface. Implementations that try to save a pointer by not providing a 
> pointer to the parent, are really just making life complicated for the 
> sake of a few bytes. Arguably if space is that much of a concern perhaps 
> the tree is not the right data structure for the job?

I agree with some of the points you make but perhaps I didn't make 
myself completely clear in the first place. I was not trying to make 
space or efficiency constraints limit the interface. My point was that 
the Concepts themselves should allow different implementations, the same 
way a you can have single- and double-linked lists implementations of a 
Sequence.

Sure, for many applications you'll want every kind of traversal 
possible. But not in all important applications. For example, searching 
a binary search tree only requires parent-to-child traversal. My point 
is that you can have different trees, all exposing the same basic 
interface that can provide different traversal possibilities and 
different complexity tradeoffs.

In my design a tree_iterator is categorized according to a 
VerticalTraversalCategory which can be Forward (only parent-to-child) or 
Bidirectional. So if a tree_iterator supports it you could:

     it.ascend();
     it.descend();
     ++it /* next sibling */;
     --it /* previous sibling */;

A separate traits class tells us the particular traversal category of a 
tree_iterator. Based on this any algorithm can choose an implementation 
for the particular traversal categories or require tree_iterators of a 
specific category.

>> Inorder, preorder and postorder traversals are possible using a stack 
>> of ancestors. In the general case, though you shouldn't have to pay 
>> for this extra overhead at all times.
> 
> 
> I am not convinced that there is *significant* overhead.

Well, IMO, *if and when* a tree_iterator does not provide access to the 
parent, keeping a stack of pointers to allow for traversals I may not 
need is significant overhead for a tree_iterator. If we also allow 
traversals to be reversible we would end up with an iterator that holds 
a pointer to every node in the tree.

But my point is not that the overhead is significant in all cases. Only 
that it may be in some, so we cannot assume that every tree 
implementation will provide a single iterator for 
inorder/preorder/postorder and general tree traversal.

>> IMO a tree container should be just that. Preorder, postorder and 
>> inorder are ways to turn a tree into a sequence, I see them as views 
>> of the tree.
> 
> 
> Yes. However traversing a tree is a rather common and important task for 
> a tree data structure.
> 
>> This is the main reason I'd prefer to have them as separate entities.
> 
> 
> That or the overhead? If there is no *significant* overhead then why not 
> allow a tree to provide a direct treatment as a sequence. Clearly the 
> question becomes, what overhead is significant?

IMO, if this can be provided in a general way outside the tree it would 
keep the interface of a tree simpler. I see no reason why linear 
traversals cannot be provided in a general way outside trees without 
loss of efficiency or added overhead. Still, Thorsten makes the point 
that this will make for more cryptic error messages and less "pleasant" 
code. I'm not sure I agree with him on that, but only an implementation 
will tell ;)

>> Btw, here's my short view of a tree:
>>
>>     template <typename T>
>>     struct Tree
>>     {
>>         typedef /**/ tree_iterator;
>>         typedef /**/ const_tree_iterator;
>>         typedef /**/ sibling_iterator;
>>         typedef /**/ const_sibling_iterator;
>>
>>         tree_iterator root();
>>         tree_const_iterator root() const;
>>     };
> 
> 
> This appears to be good code (upon cursory examination) however I am 
> really at only concerned with binary trees at this point. They are in my 
> view very separate things from k-ary trees and mandate separate 
> implementations. Do you agree?

I think we can single out binary trees and give them a specific 
interface (I did!) where it makes sense to do so, but without putting 
aside the general tree interface. I also think a Boost Tree library 
should not lose the opportunity to define general concepts that can work 
with different trees and not only k-ary trees.

> As I said before, you make excellent points but I am not *yet* convinced 
> that a tree should not be inherently treatable as a sequence.

If you can have a tree that is only a tree and outside means of 
linearizing the tree (as in a LinearView or something) can be provided 
only once in a general way, what keeps us from doing that? I view this 
as the member/non-member functions debate.

Best,

João