Algorithm to sort parents before children

Question

I'm writing a drawing application that includes shapes that can have children. When I need to redraw the canvas, I would like to sort the shapes to draw so that the parents appear before their children. That way, a parent shape won't be drawn on top of a child shape. Here is the relevant function (written in JavaScript). Variables prefixed with my. are instance variables. my.draw_order is an array of shape indexes that need to be redrawn (populated by the code below), my.ctx is the HTML canvas context where the shapes are drawn, my.shapes is an array of shapes in an arbitrary order, my.update_rects is an array of dirty rectangles that can optionally be used by a very large shape to only do a partial redraw.

redraw = function () {
    var i, shape_count, shape;

    shape_count = 0;
    for (i = 0; i < my.shapes.length; i++) {
        shape = my.shapes[i];

        if (shape.visible && shape.dirty) {
            my.draw_order[shape_count] = i;
            shape_count++;
        }
    }

    my.draw_order.length = shape_count;

    // sort shapes to draw so that parents appear before children ???
    my.draw_order.sort(shape_sort);

    for (i = 0; i < my.draw_order.length; i++) {
        shape = my.shapes[my.draw_order[i]];

        shape.draw(my.ctx, my.update_rects);
        shape.dirty = false;
    }

    my.update_rects.length = 0;
};

My question is: what's the best way to implement shape_sort as referenced by the code? This is a routine that will be called often, so efficiency might be a concern. Each shape has a parent property that contains a reference to its parent's shape. Suggestions for a better design are welcome. Maintaining the my.shapes array in sorted order is an undesirable option.

Answer 1

I would maintain the shapes as a tree. Create a single root (representing the entire screen), and give parents pointers to their children. Then a simple preorder traversal of the tree would suffice.

To implement in terms of your existing design, you don't need to ditch the my.shapes array. Just add a my.root, add pointers from parents to children, and traverse:

function preorder_draw(root) {

    //do stuff with root
    draw(root);

    for (child in root.children) {
        preorder_draw(child);
    }

}

Answer 2

Should you require data structures that are more complex than trees, you should check a Topological Sort algorithm.