Queueing timeouts in JavaScript

I wanted to create a simple animation to illustrate sorting algorithms, using SVG and JavaScript. The basic idea was to present a simple JavaScript API that sorting implementations could use. It turned out I had to implement my own timeout queueing contraption for this.

I was aiming for being able to write something like the following code:

function bubble ()
{
    for (var i = array.length - 1; i != 0; --i)
    {
        for (var j = 0; j != i; ++j)
        {
            if (less (j + 1, j))
                swap (j + 1, j);
        }
        mark_as_done (i);
    }
    mark_as_done (0);
}

Looks pretty straight-forward, doesn't it? One just needs to write less(), swap() and mark_as_done() to change/animate certain SVG objects, and it's all done, right? Well, I'm certainly no Javascript wizard, so that's what I thought too.

However, since JavaScript is not run in a thread separate from the browser, you can't just implement animation by modifying values and wait()'ing for a couple of milliseconds. In fact, it turns out, there's no explicit way to wait for a given time at all. What you can, and should, do, is set up a callback to be executed after a certain amount of time. The JavaScript API for this is a function called setTimeout(), and there's also a separate function called setInterval() that sets up the callback to be run every n milliseconds.

The APIs are string-based, that is, callback functions and arguments are passed as JavaScript text. That alone calls for some quite un-intentional coding, for example, check out the source code for this SVG file:

function start_animation()
{        
    setTimeout("anim_down('subject', 10)", 25);
}

function anim_down (id, n)
{
    var elem = document.getElementById(id);
    translate (elem, 0, 10);

    if (n)
        setTimeout("anim_down('" + id + "'," + (n - 1) + ")", 25);
    else
        setTimeout("anim_left('" + id + "', 20)", 25);
}

As you can see, it's a pain in the ass to make sure everything is nicely representable as a string – e. g., XML element ID's are passed around instead of pointers to the actual elements. But you can always store state in some global variable, that's not the real problem. To see what the problem is, try clicking repeatedly on the button and see how the animation gets deformed. It's not hard to guess what's happening: a second timeout-cascade is set up before the first one had time to finish.

So in the bubble() function defined above, all swapping animations would start simultaneously. And there's no way to select() or join() or whatever until a certain timeout has run. We need to create a timeout queue.

Look at the code below for a minimalistic approach. Timeouts that register timeouts themselves should set/clear current_timeout, like in this example.

var timeout_queue = [];
var timeout_queue_timeout = 0;
var current_timeout = null; 
var timeout_queue_freq = 100;

function pop_timeout ()
{
    if (!timeout_queue.length)
    {
        clearInterval(timeout_queue_timeout);
        timeout_queue_timeout = 0;
        return;
    }
    
    if (!current_timeout)
    {
        var timeout = timeout_queue.shift();
        timeout.run ();
    }
}

function queue_timeout(timeout)
{
    timeout_queue.push(timeout);
    if (!timeout_queue_timeout)
        timeout_queue_timeout = setInterval("pop_timeout()", timeout_queue_freq);

    pop_timeout ();
}

Try clicking multiple times in quick succession in the second example: you won't see any corruption in the animation this time. Also, if you look at the code, thanks to the pseudo-synchronization, the animation can be expressed more intentionally:

function start_animation()
{
    animate('subject', 0, 10, 10);
    animate('subject', 10, 0, 20);
    animate('subject', 0, -10, 10);
}