Last active
August 9, 2020 13:49
-
-
Save benpickles/4059636 to your computer and use it in GitHub Desktop.
Written as a response to a Stack Overflow question "How to find the nearest common ancestors of two or more nodes?" https://stackoverflow.com/a/5350888/194664
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function parents(node) { | |
var nodes = [node] | |
for (; node; node = node.parentNode) { | |
nodes.unshift(node) | |
} | |
return nodes | |
} | |
function commonAncestor(node1, node2) { | |
var parents1 = parents(node1) | |
var parents2 = parents(node2) | |
if (parents1[0] != parents2[0]) throw "No common ancestor!" | |
for (var i = 0; i < parents1.length; i++) { | |
if (parents1[i] != parents2[i]) return parents1[i - 1] | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<title>Common Ancestor Tests</title> | |
<link rel="stylesheet" href="http://code.jquery.com/qunit/qunit-1.10.0.css"> | |
<script src="./common-ancestor.js"></script> | |
</head> | |
<body> | |
<div id="qunit"></div> | |
<script src="http://code.jquery.com/qunit/qunit-1.10.0.js"></script> | |
<script src="./test.js"></script> | |
</body> | |
</html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function createElement(parent) { | |
var elem = document.createElement("div") | |
if (parent) { | |
parent.appendChild(elem) | |
} | |
return elem | |
} | |
var root = createElement() // . | |
var elem1 = createElement(root) // ├── elem1 | |
var elem2 = createElement(elem1) // | ├── elem2 | |
var elem3 = createElement(elem1) // | └── elem3 | |
var elem4 = createElement(elem3) // | └── elem4 | |
var elem5 = createElement(root) // └── elem5 | |
test("same parent", function() { | |
ok(commonAncestor(elem1, elem5) === root) | |
}) | |
test("same parent but deeper", function() { | |
ok(commonAncestor(elem4, elem5) === root) | |
}) | |
test("direct child of the other", function() { | |
ok(commonAncestor(elem1, elem2) === elem1) | |
}) | |
test("grandchild of the other", function() { | |
ok(commonAncestor(elem1, elem4) === elem1) | |
}) | |
test("when there's no common ancestor", function() { | |
var separate = createElement() | |
var thrown = false | |
try { | |
commonAncestor(elem3, separate) | |
} catch(e) { | |
thrown = true | |
} | |
ok(thrown) | |
}) |
Version that accepts more than two nodes
function getParents (node) {
// Place the first node into an array
const nodes = [node]
// As long as there is a parent node that we have yet to add
while (nodes[nodes.length - 1].parentNode) {
// Place that node at the end of the array
// This unravels the tree into an array with child/parents only.
nodes.push(node)
}
// Reverse the array so it starts from the highest ancestor, all the way down
// to our node.
nodes.reverse()
return nodes
}
function isArrayOfIdenticalItems (array) {
return array.every(item => item === array[0])
}
function getLastCommonAncestor (nodes) {
// Get an array whose items are arrays of parents
const arrayOfParents = nodes.map(node => getParents(node))
/* Although DOM can go many steps up to
** a common parent node, top down will be equal for a common ancestor, as
** the difference to the top is only after we break past the common ancestor.
** After that, the common node has the same parent as the other node, so it's
** the same all the way to the top. (If that doesn't make sense, thing about
** it, and maybe draw it out).
*/
// Ensure we have a common ancestor, it will be the first one if anything
const topMostAncestors = arrayOfParents.map(parents => parents[0])
if (!isArrayOfIdenticalItems(topMostAncestors)) {
// We do not have a common ancestor, let's throw
throw new Error('No common ancestor!')
}
// Let's move down the ancestor from the top to the bottom
for (let index = 1; index < arrayOfParents[0].length; index++) {
const parentsAtIndex = arrayOfParents.map(parents => parents[index])
if (isArrayOfIdenticalItems(parentsAtIndex)) {
// It's a common ancestor, let's continue the loop
} else {
// It's not a common ancestor, let's hence the common ancestor must be
// the one from the previous loop
return arrayOfParents[0][index - 1]
}
}
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Commenting is a wonderful feature of every language:
No, I don't over comment. I have no clue what you're talking about. ;)