JavaScript组件之旅:编码实现和算法 2

嗯，我们继续推进，我们要实现 SmartQueue 的具体功能。上期分析过，SmartQueue 只有一个实例，因此我们决定直接在 SmartQueue 下面创建方法：

SmartQueue.init = function() {
Q.forEach(function(queue) {
queue.length = 0;
});
};

这里用到 JavaScript 1.6 为 Array 对象提供的遍历方法 forEach. 之所以这样写是因为我们假定“外部代码”已经在前面运行过了。设置 Array 对象的 length 属性为 0 导致，它被清空并且释放所有的项（数组单元）。

最后一个方法 fire, 是整个组件最主要的方法，它负责对所有任务队列进行排序，并逐个执行。由于代码稍长了一点，这里只介绍排序使用的算法和实现方式，完整代码在这里。

var _dirty = true, // A flag indicates weather the Queue need to be fired.
_sorted = [], index;
// Sort all Queues.
// ref: http://en.wikipedia.org/wiki/Topological_sorting
var _visit = function(queue, task) {
if(task._visited >= 1) {
task._visited++;
return;
}
task._visited = 1;
// find out and visit all dependencies.
var dependencies = [], i;
task.dependencies.forEach(function(dependency) {
i = _findTask(queue, dependency);
if(i != -1) {
dependencies.push(queue[i]);
}
});
dependencies.forEach(function(t) {
_visit(queue, t);
});
if(task._visited === 1) {
_sorted[index].push(task);
}
},
_start = function(queue) {
queue.forEach(function(task) {
_visit(queue, task);
});
},
_sort = function(suppress) {
for(index = LEVEL_LOW; index <= LEVEL_HIGH; index++) {
var queue = Q[index];
_sorted[index] = [];
_start(queue);
if(!suppress && queue.length > _sorted[index].length) {
throw new Error('Cycle found in queue: ' + queue);
}
}
};

我们将按任务指定的依赖关系对同一优先级内的任务进行排序，确保被依赖的任务在设置依赖的任务之前运行。这是一个典型的深度优先的拓扑排序问题，维基百科提供了一个深度优先排序算法，大致描述如下：

1. 访问待排序的每一个节点
   1. 如果已经访问过了，则返回
   2. 否则标记为已访问
   3. 找出它连接（在这里是依赖）的每个节点
   4. 跳到内层1递归访问这些节点
   5. 访问完了就把当前节点加入已排序列表
2. 继续访问下一个

如果 A 依赖 B, B 依赖 C, C 依赖 A, 那么这 3 个节点形成了循环依赖。 文中指出这个算法并不能检测出循环依赖。通过标记节点是否已访问，可以解决循环依赖造成的递归死循环。我们来分析一下循环依赖的场景：

从节点 A 出发的时候，它被标记为已访问，当从节点 C 再回到节点 A 的时候，它已经被访问过了。不过这个时候 C 并不知道 A 是否在自己的上游链上，所以不能直接判定发生了循环依赖，因为 A 可能是其他已“处理”（跑完了内层递归）过的节点。如果我们知道节点是不是第一次被访问过，就可以判断是哪一种情况。

改造一下上面的算法，将“是否已访问”改成“访问计数” (task._visited++)。仅当节点被访问过 1 次的时候 (task._visited === 1)，才将其加入到已排序列表，全部遍历完之后，如果待排序的节点数比已排序的多 (queue.length > _sorted[index].length)，则表明待排序中多出的节点发生了循环依赖。

至此，队列管理组件的编码实现已经完成。什么？怎么使用？很简单啦：

var t1 = new SmartQueue.Task(function() {
alert("Hello, world!");
}), t2 = new SmartQueue.Task(function() {
alert("High level task has name");
}, 2, 'myname');
t1.register(); t2.register();
SmartQueue.fire();

更多功能，如任务的依赖，等待你去发掘哦。