| // removeSubsets |
| // Given an array of nodes, remove any member that is contained by another. |
| exports.removeSubsets = function(nodes) { |
| var idx = nodes.length, node, ancestor, replace; |
| |
| // Check if each node (or one of its ancestors) is already contained in the |
| // array. |
| while (--idx > -1) { |
| node = ancestor = nodes[idx]; |
| |
| // Temporarily remove the node under consideration |
| nodes[idx] = null; |
| replace = true; |
| |
| while (ancestor) { |
| if (nodes.indexOf(ancestor) > -1) { |
| replace = false; |
| nodes.splice(idx, 1); |
| break; |
| } |
| ancestor = ancestor.parent; |
| } |
| |
| // If the node has been found to be unique, re-insert it. |
| if (replace) { |
| nodes[idx] = node; |
| } |
| } |
| |
| return nodes; |
| }; |
| |
| // Source: http://dom.spec.whatwg.org/#dom-node-comparedocumentposition |
| var POSITION = { |
| DISCONNECTED: 1, |
| PRECEDING: 2, |
| FOLLOWING: 4, |
| CONTAINS: 8, |
| CONTAINED_BY: 16 |
| }; |
| |
| // Compare the position of one node against another node in any other document. |
| // The return value is a bitmask with the following values: |
| // |
| // document order: |
| // > There is an ordering, document order, defined on all the nodes in the |
| // > document corresponding to the order in which the first character of the |
| // > XML representation of each node occurs in the XML representation of the |
| // > document after expansion of general entities. Thus, the document element |
| // > node will be the first node. Element nodes occur before their children. |
| // > Thus, document order orders element nodes in order of the occurrence of |
| // > their start-tag in the XML (after expansion of entities). The attribute |
| // > nodes of an element occur after the element and before its children. The |
| // > relative order of attribute nodes is implementation-dependent./ |
| // Source: |
| // http://www.w3.org/TR/DOM-Level-3-Core/glossary.html#dt-document-order |
| // |
| // @argument {Node} nodaA The first node to use in the comparison |
| // @argument {Node} nodeB The second node to use in the comparison |
| // |
| // @return {Number} A bitmask describing the input nodes' relative position. |
| // See http://dom.spec.whatwg.org/#dom-node-comparedocumentposition for |
| // a description of these values. |
| var comparePos = exports.compareDocumentPosition = function(nodeA, nodeB) { |
| var aParents = []; |
| var bParents = []; |
| var current, sharedParent, siblings, aSibling, bSibling, idx; |
| |
| if (nodeA === nodeB) { |
| return 0; |
| } |
| |
| current = nodeA; |
| while (current) { |
| aParents.unshift(current); |
| current = current.parent; |
| } |
| current = nodeB; |
| while (current) { |
| bParents.unshift(current); |
| current = current.parent; |
| } |
| |
| idx = 0; |
| while (aParents[idx] === bParents[idx]) { |
| idx++; |
| } |
| |
| if (idx === 0) { |
| return POSITION.DISCONNECTED; |
| } |
| |
| sharedParent = aParents[idx - 1]; |
| siblings = sharedParent.children; |
| aSibling = aParents[idx]; |
| bSibling = bParents[idx]; |
| |
| if (siblings.indexOf(aSibling) > siblings.indexOf(bSibling)) { |
| if (sharedParent === nodeB) { |
| return POSITION.FOLLOWING | POSITION.CONTAINED_BY; |
| } |
| return POSITION.FOLLOWING; |
| } else { |
| if (sharedParent === nodeA) { |
| return POSITION.PRECEDING | POSITION.CONTAINS; |
| } |
| return POSITION.PRECEDING; |
| } |
| }; |
| |
| // Sort an array of nodes based on their relative position in the document and |
| // remove any duplicate nodes. If the array contains nodes that do not belong |
| // to the same document, sort order is unspecified. |
| // |
| // @argument {Array} nodes Array of DOM nodes |
| // |
| // @returns {Array} collection of unique nodes, sorted in document order |
| exports.uniqueSort = function(nodes) { |
| var idx = nodes.length, node, position; |
| |
| nodes = nodes.slice(); |
| |
| while (--idx > -1) { |
| node = nodes[idx]; |
| position = nodes.indexOf(node); |
| if (position > -1 && position < idx) { |
| nodes.splice(idx, 1); |
| } |
| } |
| nodes.sort(function(a, b) { |
| var relative = comparePos(a, b); |
| if (relative & POSITION.PRECEDING) { |
| return -1; |
| } else if (relative & POSITION.FOLLOWING) { |
| return 1; |
| } |
| return 0; |
| }); |
| |
| return nodes; |
| }; |