Boost logo

Boost :

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

"Jason Hise" <chaos_at_[hidden]> wrote in message
> 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

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,

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