Boost logo

Boost :

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at