32 lines
706 B
JavaScript
32 lines
706 B
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;
|
|
};
|