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

From: christopher diggins (cdiggins_at_[hidden])
Date: 2005-02-24 22:29:04

----- Original Message ----- 
From: "Joao Abecasis" <jpabecasis_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, February 24, 2005 3:02 PM
Subject: [boost] Re: Boost library inclusion: generic tree containers?

> christopher diggins wrote:
>> Why not have just one kind of iterator:
>>
>> template<typename T, typename Iter_T>
>> struct tree {
>>  typedef typename Iter_T iterator;
>>  iterator preorder_begin();
>>  iterator postorder_end();
>>  iterator inorder_end();
>>  iterator end();
>>  iterator begin(); // calls inorder_begin()
>> }
>>
>> ?
>
> Hm... That looks too much like a Sequence to me ;)
>
> I think this is not feasible in the general case. Consider a minimal node 
> containing only a pointer to the next sibling and to the first child. Or a 
> binary tree that keeps pointers to its left and right children.

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?

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

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

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

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.

best,
Christopher