DIV CSS 佈局教程網

JavaScript 組件實作:Smart Queue 的編碼細節與拓撲排序
編輯:關於JavaScript     

上一回我們把這個隊列管理組件的藍圖畫完了,還替它取了個響亮又獨特的名字——Smart Queue。這一篇要做的,就是把設計稿真正落成可以運行的程式碼。

先決定檔案怎麼切

動手之前得先想清楚一件事:程式碼該如何拆分到不同檔案裡。為什麼要拆?還記得上集結尾提到的「外部程式碼」嗎?為了讓用途一眼就看得出來,起碼要分成兩部分——外部程式碼檔,以及 Smart Queue 本體。

區分用途只是其中一個理由。另一個理由是可維護性:哪天你想在既有的隊列基礎功能上加點新花樣,或是把它包裝成某個負責特定任務的組件,同時又希望內部實作與對外呼叫方式都不受影響,那麼把新程式碼寫進獨立檔案,就是最省事的選擇。

檔案配置留到下回細談,這裡先切入正題。

建立命名空間

第一步,替組件開一個自己的頂層命名空間,之後所有程式碼都收在裡面:

var SmartQueue = window.SmartQueue || {};
SmartQueue.version = '0.1';

初始化的時候如果遇到命名空間已被佔用,就直接拿來 reuse。這種碰撞通常是重複引入組件造成的,「拿來用」等於用相同實作再寫一遍;最壞的情況是頁面上剛好有另一個物件也叫 SmartQueue,那就只能抱歉地覆蓋掉對方的實作——只要後續沒有再撞名,兩個組件大致上仍能相安無事地跑下去。順手也把版本號記上。

三個優先級,三條隊列

var Q = SmartQueue.Queue = [[], [], []];

三個都是空陣列,因為目前還沒有任務被放進來。同時開個「快捷方式」,之後要取用直接寫 Q[n] 就好。

主角登場:Task 構造函數

接下來是 Task。怎樣 new 出一個 Task,定義在這裡:

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 : [];
};

細節就不逐一解釋了,該有的註解都在,程式碼本身也盡量做到自我說明。這裡要對使用者講清楚的是:想建立一個 SmartQueue.Task 實例,至少要傳一個參數給這個構造函數(後三個都可以省略並走預設值),否則就丟例外給你。

但光這樣還不夠。實務上使用者常會想從既有的 Task 複製一份新實例,或是拿一個只具備部分屬性的「殘缺物件」修補成完整的 Task。用上面的寫法就有點彆扭,得這樣:

var task1 = new SmartQueue.Task(obj.fn, 1, '', obj.dependencies);

但我很懶,只想傳 fn 和 dependencies 兩個屬性,不想做多餘的事。好吧,那就重構構造函數:

  var _setupTask = 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 : [];
  };
  var T = SmartQueue.Task = function(task) {
    if(arguments.length > 1) {
      _setupTask.apply(this, arguments);
    } else {
      _setupTask.call(this, task.fn, task.level, task.name, task.dependencies);
    }
    // init context/scope and data for the task.
    this.context = task.context || window;
    this.data = task.data || {};
  };

如此一来,原本的呼叫方式照樣能跑,而怕麻煩的人可以只丟一個「殘缺物件」進來:

var task1 = new SmartQueue.Task({fn: obj.fn, dependencies: obj.dependencies});

判斷邏輯很單純:參數超過一個就照舊方式處理,否則把唯一那個參數當成 Task 物件或殘缺物件看待。這裡靠 JavaScript 的 apply/call 把新實例的上下文(context,也有人叫 scope)交給重構後的 _setupTask——apply/call 正是 JavaScript 在方法之間傳遞上下文的法寶,值得細細體會。此外我們也允許使用者指定 task.fn 執行時的上下文,並把自訂資料傳進執行中的 fn。

經典的物件三段式

  1. 定義該物件的構造函數
  2. 在原型上定義屬性與方法
  3. new 出物件,拿去用

所以接著要替 SmartQueue.Task 的原型補上屬性與方法。上集分析過 Task 擁有的若干屬性與方法,其中一部分已在 _setupTask 裡處理掉了,原型這邊提供的是:

  T.prototype = {
    enabled: true,
    register: function() {
      var queue = Q[this.level];
      if(_findTask(queue, this.name) !== -1) {
        throw new Error('Specified name exists: ' + this.name);
      }
      queue.push(this);
    },
    changeTo: function(level) {
      if(!_validateLevel(level)) {
        throw new Error('Invalid argument: level');
      }
      level = parseInt(level, 10);
      if(this.level === level) {
        return;
      }
      Q[this.level].remove(this);
      this.level = level;
      this.register();
    },
    execute: function() {
      if(this.enabled) {
        // pass context and data
        this.fn.call(this.context, this.data);
      }
    },
    toString: function() {
      var str = this.name;
      if(this.dependencies.length) {
        str += ' depends on: [' + this.dependencies.join(', ') + ']';
      }
      return str;
    }
  };

如你所見,邏輯非常直白,說不定一分鐘就掃完了,嘴角還會浮現一絲心領神會的微笑。不過這裡要特別提的是那個簡單、卻最常被忽略的 toString。在一些高階語言裡,為自訂物件實作 toString 是被推薦的最佳實踐,原因很實際:它能在除錯器裡立刻給出有參考價值的信息,能讓物件的關鍵資料輕易寫進日誌;在統一的開發模式下,有了 toString 你反而能少寫幾行程式碼。

把功能補上

接著實作 SmartQueue 的具體行為。上集分析過它只有一個實例,因此我們直接把方法掛在 SmartQueue 底下:

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

這裡用到 JavaScript 1.6 為 Array 提供的遍歷方法 forEach。之所以這樣寫,是因為我們假定「外部程式碼」已經在更前面執行過了。把 length 設為 0,陣列會被清空並釋放所有元素。

fire:排序與依序執行

最後的 fire 是整個組件最核心的方法,負責對所有任務隊列排序,再逐個執行。程式碼稍長,這裡只談排序所用的算法與實作,完整版本請見文末連結。

var _dirty = true, // A flag indicates weather the Queue need to be fired.
  _sorted = [], index;
// Sort all Queues.
// ref: https://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,這三個節點就構成了循環依賴。文中指出這個算法本身並偵測不出循環依賴,但透過標記節點是否已拜訪,可以避免循環依賴造成的遞歸死循環。我們來還原一下循環依賴發生的過程:

從節點 A 出發時它被標記為已拜訪,而當路徑從 C 繞回 A 時,A 已經拜訪過了。問題是,此刻 C 並不知道 A 是否就在自己的上游鏈上,所以無從直接判定發生了循環——A 也可能只是另一個早已「處理」完畢(跑完了內層遞歸)的節點。要分辨這兩種情況,我們需要知道這個節點是不是第一次被拜訪。

於是把算法改一下:把「是否已拜訪」改成「拜訪計數」(task._visited++)。只有在節點被拜訪恰好一次的時候(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 方法的程式碼沒有列出,完整版本請見原文連結。後面我們會談組件檔案的管理與建置,下回見。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved