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

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-24 01:49:49

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

Hi Thorsten - I agree with Richard's comments as well (if you have time, 
please see my comments replying to his post, so we're on the same page).

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

Yeah, I was playing around with having tree and iterator functionality 
behave the same, thus I created operator* for the tree to behave as it would 
the iterator. Pretty silly, although we will need some vehicle to set the 
data in that root node (whatever that ends up being). =)

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

Hmmm, yeah, I'll investigate that some.

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

Roger that. =)

At this point, I'm ready to step back and say, "ok, so ... let's figure out 
what we need to build." As I was discussing with Richard, I think we have 
two primary trees to develop:

    1) trees as containers
    2) trees as algorithms

I think we need to figure out a design that is inherently inclusive to both 
groups (so everyone is happy). That being said, what do you think the best 
format to do that is?

I envision a single base class that encapsulates all "basic" tree 
functionality and with that basic tree functionality, implementations that 
very clearly demonstrate both types of trees can be used seamlessly with it. 
Then, to further drive home that point, I think we should implement at least 
the first most obvious derivation of each type of tree from that basic tree 
definition.

For example:

    class basic_tree {};

    // proof of concept for containment and algorithms
    class container_tree : public basic_tree {};
    class algorithmic_tree: public basic_tree {};

What do you think? And boy is this fun. =)

Justin