DIV CSS 佈局教程網

尋找多個節點的最近共同祖先:實作思路與測試驅動
編輯:關於JavaScript     

先定義問題

DOM 本質上是一棵樹,根節點是 Document:

所謂「最近的共有祖先元素」,指的是:給定一組元素,在所有同時是它們祖先的元素中,樹中深度最大的那一個。

以上圖為例:I 與 G 的結果是 C;G 與 H 的結果是 A;D 與 E 的結果是 html;C 與 B 的結果是 html。

先寫測試,再寫實作

這類偏邏輯的題目,很難憑直覺保證正確,所以先構造測試用例:

function test() {
    var result;
    result = find('i', 'g');
    result.id !== 'c' && alert('fail (i, g)');
    result = find('g', 'h');
    result.id !== 'a' && alert('fail (g, h)');
    result = find('d', 'e');
    result.nodeName.toLowerCase() !== 'html' && alert('fail (d, e)');
    result = find('c', 'b');
    result.nodeName.toLowerCase() !== 'html' && alert('fail (c, b)');
}

測試用的 DOM 以 A 代表 body、B 代表 head,其餘節點都用 div,id 依圖標示。

基本邏輯

  1. 對每個給定元素,從父節點開始一路向上走到 document。
  2. 把經過的每個節點存進一個 map,鍵是節點、值是「被走訪到的次數」。
  3. 最後掃一遍 map,找出計數等於元素個數的第一項——那就是所有元素的共同祖先,也就是最近的共同祖先。

兩個細節陷阱

一、物件不能直接拿元素當鍵。必須轉成 number、string 等基本型別。HTML5 的 data-* 屬性正好適合承載這種唯一標識,可以大方掛上去。

二、Chrome 會對 object 的鍵自動排序。因此盡量別用純數字當鍵。解法很簡單:加個下底線前綴,或用 String.fromCharCode 轉成字元。

實作

function find() {
    var length  = arguments.length,
        i       = 0,
        node,        // 當前節點
        parent,      // 父節點
        counter = 0,
        uuid,        // DOM 的唯一標識
        hash  = {};  // 結果 map

    // 對每個元素向上遍歷至 document
    for (; i < length; i++) {
        node = arguments[i];
        if (typeof node == 'string') {
            node = document.getElementById(node);
        }
        while (parent = node.parentElement || node.parentNode) {
            if (parent.nodeType == 9) { break; }   // 到 document 就停,否則死循環
            uuid = parent.getAttribute('data-find');
            if (!uuid) {
                uuid = '_' + (++counter);          // 避開 Chrome 對數字鍵的重排序
                parent.setAttribute('data-find', uuid);
            }
            if (hash[uuid]) {
                hash[uuid].count++;
            } else {
                hash[uuid] = { node: parent, count: 1 };
            }
            node = parent;
        }
    }

    // hash 中只存父節點,量不大,這個迴圈很快
    for (i in hash) {
        if (hash[i].count == length) {
            return hash[i].node;
        }
    }
}

幾點省思

取父節點時寫成 parentElement || parentNode 是為了兼容 IE 的舊 BUG(剛建立但尚未進入 DOM 的元素沒有 parentNode)。但本函式已保證節點在樹中,其實 parentElement 就夠了。習慣性兼容碼不見得是好事,最貼合當前環境的程式碼才是好程式碼。

另外,雙層迴圈看似無法避免,但其實在向上走訪的過程中,一旦確定某節點已不可能是共同祖先,就可以停止遞增計數;最後那個 for...in 也可以嘗試在迴圈中即時維護「目前最佳候選」來省掉。

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