JavaScript组件:编码实现和算法(3)

嗯，我们继续推进，我们要实现 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();

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

本期贴出的代码都是一些局部片段，部分 helper 方法代码没有贴出来。查看完整的代码请访问 这里 。后面我们将介绍如何管理组件文件，以及构建组件，下期不见不散哦。

    var T = SmartQueue.Task = function(fn, level, name, dependencies) {
        if(typeof fn !== FUNCTION) {
            throw new Error('Invalid argument type: fn.');
        }
        this.fn = fn;
        this.level =  _validateLevel(level) ? level : LEVEL_NORMAL;

        // detect type of name
        this.name = typeof name === STRING && name ? name : 't' + _id++;

        // dependencies could be retrieved as an 'Object', so use instanceof instead.
        this.dependencies = dependencies instanceof Array ? dependencies : [];
    };