...
素材网 品牌美学馆标志
主站 营销美学 品牌设计 免费素材
830

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();

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

>

品牌风云最新热文

房地产的VI做起来,就像是在搞艺术 唱片封面设计 | 看得见的音乐艺术 “美味酒廊”VI设计欣赏 美学茶话:读懂齐白石的画,我放弃了画画

访问手机站
© Copyright 素材公社tooopen.com 本站部份内容收集于网络,如有侵犯您权益请告知删除| 湘ICP备11010972号-1