142 lines
3.8 KiB
JavaScript
142 lines
3.8 KiB
JavaScript
// 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;
|
|
};
|