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

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2005-02-23 09:24:24

"Justin Gottschlich" <jgottschlich_at_[hidden]> wrote in message 
news:cvgkdm$k3u$1_at_sea.gmane.org...
| "Thorsten Ottosen" <nesotto_at_[hidden]> wrote in message

First, I agree with Richard's comments about structure and structure
manipulatig operations--this is the important part.

| > One major issue with the design: I don't like that iterators are trees. It
| > must be possible to break the two concepts apart like in
|
| Thorsten, you're absolutely right - that's really the big "question", the
| one I've struggled with for months really. I could definitely design the
| tree so iterators are not trees, but I'm not sure that's correct.

[snip]

| 2) This example shows the how inserts are done into subtrees from iterators:
|
|    core::tree<char> t;
|    *t = 'a';
|    t.insert('b');
|    t.insert('c');

see, this seems just wierd that *t = ... is defined for a tree. I could accept 
the
fact that you iterate over subtrees, but the design would have to be like this

template< class T >
class tree
{
    T data;
    std::vector<tree*> children;
 ...
};

then it would be natural that operator->() (not operator.()) of an iterator
returns a tree*. So

i->insert('c');

would seem natural.

You might want to find out if that node-structure is not the best way to
implement the tree. The design above does not require any node concept.

| > For all iterators I would like to be able to say
| >
| > if( i.is_leaf() ).
|
| That's a great suggestion too - I don't have that as a direct function call,
| but can achieve it by this:
|
|    if (0 == i.size()) // it's a leaf if its size is 0, since it's checking
| the number of the elements it contains

yes, it should be fairly easy. I fell in my own trap an implemented is_leaf()
as a member function of the iterator. It could make sense to
have an is_leaf() member function as part of a tree-iterator concept, but
it should actually be a member function is a tree, so

i->is_leaf()

would be to prefer IMO.

br

-Thorsten