// 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: 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: // 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 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;

};