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

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-22 23:13:20

"Jason Hise" <chaos_at_[hidden]> wrote in message 
news:421BF5C5.2050507_at_ezequal.com...
> Justin Gottschlich wrote:
>
> I haven't looked at the code, so please correct me if I am off base.  But 
> isn't having iterators which behave like stl iterators the only way to 
> make the tree work with generic algorithms?  I think that your 
> multi-purpose iterator could be very convenient for the code that is 
> hardwired to use trees, but I think that it would also be nice if the 
> other iterators were provided, so that you could for_each over a single 
> level in the tree, or over the whole tree, etc...
>

Hi Jason -

You're right on target. With my current base tree iterator, I only supply 
increment and decrement over a single level and in order to get access to 
depths within deeper levels of the tree, I'd have to use the iterator to 
step "in()" / "begin()" - thus standard algorithms would only work for a 
single level based on the single-level iteration functionality of the 
current iterator (but, keep reading).

You could still use for_each for the tree that way, but only a single level 
would be covered.

So, if you had a tree/iterator with 10 direct children, each of which had 10 
direct children, if you did this (which would be perfectly legal with my 
current implementation):

/////////////////////////////////////////////////////////////////////////////
void outputBranch(int i) { std::cout << i << std::endl; }

/////////////////////////////////////////////////////////////////////////////
int main()
{
    core::tree<int> t;

    for (int i = 0; i < 10; ++i)
    {
       core::tree<int>::iterator iter = t.push_back(i);
       for (int j = 0; j < 10; ++j) iter.push_back(j);
    }

    std::for_each(t.begin(), t.end(), outputBranch);
}

it would simply output all the elements of the first level - not the entire 
tree.

In order to iterate over the whole tree (your second point), I would simply 
have to create an additional iterator which iterated recursively through the 
tree using ++ and it would require a minor change to the above code:

/////////////////////////////////////////////////////////////////////////////
int main()
{
    core::tree<int> t;

    for (int i = 0; i < 10; ++i)
    {
       core::tree<int>::iterator iter = t.push_back(i);
       for (int j = 0; j < 10; ++j) iter.push_back(j);
    }

    core::tree<int>::recursive_depth_iterator riter = t.begin();

    std::for_each(riter, t.end(), outputBranch);
}

I don't currently have a recursive_depth_iterator, because in the past I 
haven't really needed it. But as you pointed out, it'd really do a lot of 
good having a full tree iterator for standard algorithm usage.

The point I was really trying to make in the previous post (which I can see 
I did a rather poor job of) is that based on the way I designed the tree and 
its iterator, any type of iterator can be constructed from the current 
implementation without changing the design of the tree or its iterator - 
thus, allowing full standard algorithm usage. Since the one basic iterator 
performs fully as a tree and an iterator, any kind of iterator can be 
constructed just from that one iterator (because the iterator has the 
ability to step into itself or out of itself, just like the tree can). My 
initial driving idea behind the tree was to create a framework generic 
enough that any kind of tree could be constructed from its base 
functionality (rather than trying to guess at every kind of tree people 
would need).

Thus, any programmer using the tree could create an iterator for the tree to 
perform any kind of iteration they like (level iteration, tree-depth 
iteration, backwards tree-breadth iteration) and have standard algorithms 
work on that iterator exactly as they had coded. Thus, I wouldn't have to 
"pre-determine" all possible types of iterations (nor tree types) the end 
coder needs.

Some basic types of tree iteration clearly need to be available that I 
currently don't have. After the great points made today, I most certainly 
will add them. =)

Thanks for the discussion and point for clarification Jason,
Justin