Iterating through a tree

Question

I'm trying to figure out how I can iterate in reverse, and forward through this, or atleast call a method in reverse.

Here is how it works.

Widgets have a std::vector of Widget* which are that control's children. The child vector is z ordered which means that child[0] is behind child[1] (in render order). Each control has a pointer to its parent except for the root (dummy) widget whos parent is NULL.

For my rendering, I need to sort of do a staircase sort of iteration (back to front) ex:

root->child[0];
root->child[0]->child[0];
root->child[0]->child[1];
root->child[1];
root->child[1]->child[0];
root->child[1]->child[1];

However to find which widget is under the mouse, I must do my point in rectangle test from front to back:

   root->child[9]->child[1];
    root->child[9]->child[0];
    root->child[9];
    root->child[8]->child[2];
    root->child[8]->child[1];
    root->child[8]->child[0];
    root->child[8];

What sort of iteration would I need to efficiently do the above 2 types of iterations? (back to front, front to back).

Thanks

Answer 1

Forward iteration:

void blah_forward(const Widget *p)
{
    p->do_something();
    std::for_each(p->children.begin(), p->children.end(), blah_forward);
}

Reverse iteration:

void blah_reverse(const Widget *p)
{
    std::for_each(p->children.rbegin(), p->children.rend(), blah_reverse);
    p->do_something();
}

(untested, but hopefully you get the idea).

Answer 2

What you really have here is a tree with ordered children. And if I understand correctly, what you want to traverse them using Depth First Search visiting the children in reverse order. So you just need some recursive function widgetUnderMouse(Widget*) that traverses the tree in the order you want and checks if the current widget is under the mouse. Something like this I think.

Widget* widgetUnderMouse(Widget* root)
{
    if (root->hasChildren) 
    {
        vector<Widget*>::reverse_iterator rit;
        for (rit = root->child.rbegin(); rit < root->child.rend(); ++rit)
        {
            if (isWidgetUnderMouse(*rit)
            {
                return widgetUnderMouse(*rit);
            }
        }
    }
    else
    {
        return root;
    }
}

Where isWidgetUnderMouse returns true or false if the passed in widget is under the mouse