Visualizing tree traversal with queues and generators
It not uncommon to encounter asynchronous tasks which need to be synchronized to follow some order. Typically, this is where you execute a callback function or enter a promise. You may even want to set up queues even when things usually seem to work.[1] Here I'll cover how to set up a queue with setTimeouts so that they execute in order.
Trees are
In my initial pass, I naively wrote following to highlight the nodes:
setTimeout(function(){
for (var i = 0; i < node.children.length; i++) {
node.style.backgroundColor = 'green';
setTimeout(function() {
node.style.backgroundColor = 'white';
}, 1000);
}, 1000);
This of course did not work. The for loop runs immediately and sets up functions to run at around the same time. Chastened, I pushed the functions which needed to be delayed into an array and bound the arguments which would otherwise not be available:
for (var i = 0; i < currentTree.children.length; i++) {
// several lines omitted
this.tasks.push(highlightTree.bind(node,node.children[i]));
// several lines omitted
In the setTimeout, I then executed the first item in the array, and so on. In between this step (not shown), child nodes were added to the parent's queue.
node.tasks.shift()();
The animation shows that this is a breadth-first search, and a breadth-first search requires a queue (or at least cannot be achieved recursively using the call stack). However, in this case the queue achieves something different, and we can use this queue and do a depth-first search. The bind above binds the this keyword to the parent tree and additional code (not shown) ensures that the parent tree's tasks are completed before its children. If instead the tasks are queued on the current (internal branch) node element, the search can quickly become depth-first. It is hard to follow without the code: you are welcome to view it.
This can be done with generators as well. I won't cover generators in detail quite yet, but refactoring my original naive for loop can be refactored into a for...of loop with a generator:
function* genHighlightTree(currentTree) {
currentTree.node.style.backgroundColor = 'green';
for (let child of currentTree.children) {
setTimeout(function() {
currentTree.node.style.backgroundColor = 'white';
child.node.style.backgroundColor = 'green';
if (typeof priorChild !== 'undefined') {
priorChild.node.style.backgroundColor = 'white';
}
iterateHighlightTree.next(child);
}, 1000);
var priorChild = yield;
}
return currentTree;
}
var iterateHighlightTree = genHighlightTree(tree);
iterateHighlightTree.next();
The for...of loops are designed to work with generators. The yield expression at the bottom of the loop stops the execution, which is then picked up again when the setTimeout fires, which passes in the current element which is saved in priorChild. This works OK for iterating over the immediate children, but there's no recursive traversal. Let's add that. Here's what I came up with:
if (currentTree.children.length >= 1) {
currentTree.node.style.backgroundColor = 'green';
setTimeout(function() {
currentTree.node.style.backgroundColor = 'white';
}, 1000);
yield sleep(1000, iterateHighlightTree);
yield* genHighlightTree(child);
}
Yield* creates a new generator recursively. Above that line is a sleep function which is necessary since I wanted to mimic the effect of a visual delay in the highlighting shown in the animation. Without it, the recursive function executes immediately. Javascript has no native sleep function, but we can create one with a generator:
var sleep = function (delay, generator) {
function* generateSleep() {
yield;
}
var iterableSleep = generateSleep();
return setTimeout(function () {
generator.next();
}, delay);
}
This isn't quite perfect and the generator solution is depth-first rather than breadth-first, but it gets close enough. This little exercise demonstrates the use of generators in a useful but not exceedingly complex environment, as opposed to many tutorials which dive into APIs, servers, and promises. It can be helpful to learn things in isolation.