6
\$\begingroup\$

In my first iterative algorithm, I do this

for (auto &widget : controls.getWidgets())
{
    if (!widget->visible) continue;

    widget->draw();

    for (auto &widget_component : widget->components)
    {
        if (!widget_component->visible) continue;

        widget_component->draw();

        for (auto &ww : widget_component->components)
        {
            if (!ww->visible) continue;

            ww->draw();
        }
    }
}

Now, I see the flaw in this algorithm because of the repetition of code.

I try to write a recursive function call to handle this thing.

void swcApplication::recursiveDisplay(swcWidget *next)
{
    if (next == nullptr) return;

    if ((next->parent != nullptr) &&
        !next->parent->visible) return;

    if (next->visible)
        next->draw();

    for (auto &i : next->components)
    {
        recursiveDisplay(i);
    }
}

void display()
{
    for (auto &widget : controls.getWidgets())
    {
        recursiveDisplay(widget);
    }
}

Display first the parent before all other children, if parent is not visible, then don't draw its children

Is the above phrase satisfy by this algorithm (As far as I can see, it is)? Is this optimal? I don't know what drawbacks might occur here because I just write in a few seconds.

If you didn't find anything wrong here, now, how can I put it back in iterative way? I know iteration is better.

Update

I didn't use any z attribute here and instead I go for painter's algorithm.

The flaw I am referring in my iteration version is that, it is limited to draw widgets depends on how deep I will code for iteration.

\$\endgroup\$
4
\$\begingroup\$

You can modify the recursive code to use an explicit stack:

#include <stack>

void display_widgets(control& controls)
{
    std::stack<widget*> widgets;
    for(auto &widget : controls.getWidgets()) {
        widgets.push(widget);
    }

    while(!widgets.empty()) {
        widget* w = widgets.top();
        widgets.pop();
        if(!widget->visible) {
            continue;
        }
        widget->draw();
        for(auto& component : widget->components) {
            widgets.push(component);
        }
    }
}

I know iteration is better.

This is highly dependent on language and usage. It is "better" in that recursion can use O(n) stack space (although not always - tail call optimization gets rid of this limitation), and won't blow your stack. However, in this case, assuming the recursive algorithm actually did what you wanted, it would be better and easier.

You can always turn a recursive solution into an iterative one by replacing the call stack with an actual stack of your own, as above. For very deeply nested recursive calls, this may save you from stack overflows, however, it is more fiddly to code, and in this case, doesn't gain you anything.

Having written the code above, my advice would be to stick with the recursive solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ The original non-recursive version also doesn't paint all parents before painting any children; maybe that's not a requirement; maybe parent widgets are non-overlapping; or if they overlap, maybe get_widgets returns them in Z-order, and the overlapping parent and its children should be painted after the overlapped parent and its children. \$\endgroup\$ – ChrisW Feb 18 '14 at 1:44
  • \$\begingroup\$ @ChrisW Yeah, I think I misread (or misinterpreted) the requirement. \$\endgroup\$ – Yuushi Feb 18 '14 at 1:51
  • \$\begingroup\$ @ChrisW I've modified my answer. Thanks for pointing that out. \$\endgroup\$ – Yuushi Feb 18 '14 at 1:56
4
\$\begingroup\$

There are three ways in which your recursive version doesn't match your non-recursive version.

  1. The recursive version will go deeper: it will paint great-grandchild widgets (if there are any)

  2. The following tests exist in the recursive version but not in the non-recursive version:

      if (next == nullptr) return;
    
      if ((next->parent != nullptr) &&
          !next->parent->visible) return;
    
  3. Most importantly (this is probably a bug), your recursive version displays children even if the parent is not visible. The if (!widget->visible) continue; in your non-recursive version should be if (!next->visible) return; in your recursive version.

I don't see why your parameter name is next: I think I'd call it widget.

\$\endgroup\$
  • \$\begingroup\$ #1 That is what I wanted; #3 I don't think its a bug. How could I know if the underlying parent is visible or not? If the parent is not visible, then don't draw its underlying children. \$\endgroup\$ – mr5 Feb 18 '14 at 4:48
  • \$\begingroup\$ Also I think checking for if (next == nullptr) isn't necessary anymore? \$\endgroup\$ – mr5 Feb 18 '14 at 4:49
  • \$\begingroup\$ Um sorry, yes you are right. \$\endgroup\$ – mr5 Feb 18 '14 at 4:55
  • \$\begingroup\$ No, I was wrong: your test of next->parent->visible prevents children being displayed. Still, removing that statement and not recursing into children of invisible parents would be clearer. \$\endgroup\$ – ChrisW Feb 18 '14 at 10:39
0
\$\begingroup\$

You don't need quite so much checking and complexity in your recursive display function.

recursiveDisplay(swcWidget * widget)
{
    // don't draw the widget or any of it's children if it is not visible
    if(widget != nullptr && widget->visible)
    {
        // draw the current widget first
        widget->draw();

        // then draw the children
        // we already know at this point the parent of these children is visible.
        for(auto & widgetComponent : widget->components)
        {
            recursiveDisplay(widgetComponent);
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.