55 lines
2.3 KiB
JavaScript
55 lines
2.3 KiB
JavaScript
/**
|
|
* This is used to determine the start and end of a selection range so
|
|
* we can get the nodes between the two border nodes.
|
|
*
|
|
* It finds the nodes' common ancestor using
|
|
* a naive implementation of a lowest common ancestor algorithm
|
|
* (https://en.wikipedia.org/wiki/Lowest_common_ancestor).
|
|
* Then compares the ancestor's 2 children that are ancestors of nodeA and NodeB
|
|
* so we can compare their indexes to work out which node comes first in a depth first search.
|
|
* (https://en.wikipedia.org/wiki/Depth-first_search)
|
|
*
|
|
* Another way to put it is which node is shallower in a trémaux tree
|
|
* https://en.wikipedia.org/wiki/Tr%C3%A9maux_tree
|
|
*/
|
|
export const findOrderInTremauxTree = (instance, nodeAId, nodeBId) => {
|
|
if (nodeAId === nodeBId) {
|
|
return [nodeAId, nodeBId];
|
|
}
|
|
const nodeA = instance.getNode(nodeAId);
|
|
const nodeB = instance.getNode(nodeBId);
|
|
if (nodeA.parentId === nodeB.id || nodeB.parentId === nodeA.id) {
|
|
return nodeB.parentId === nodeA.id ? [nodeA.id, nodeB.id] : [nodeB.id, nodeA.id];
|
|
}
|
|
const aFamily = [nodeA.id];
|
|
const bFamily = [nodeB.id];
|
|
let aAncestor = nodeA.parentId;
|
|
let bAncestor = nodeB.parentId;
|
|
let aAncestorIsCommon = bFamily.indexOf(aAncestor) !== -1;
|
|
let bAncestorIsCommon = aFamily.indexOf(bAncestor) !== -1;
|
|
let continueA = true;
|
|
let continueB = true;
|
|
while (!bAncestorIsCommon && !aAncestorIsCommon) {
|
|
if (continueA) {
|
|
aFamily.push(aAncestor);
|
|
aAncestorIsCommon = bFamily.indexOf(aAncestor) !== -1;
|
|
continueA = aAncestor !== null;
|
|
if (!aAncestorIsCommon && continueA) {
|
|
aAncestor = instance.getNode(aAncestor).parentId;
|
|
}
|
|
}
|
|
if (continueB && !aAncestorIsCommon) {
|
|
bFamily.push(bAncestor);
|
|
bAncestorIsCommon = aFamily.indexOf(bAncestor) !== -1;
|
|
continueB = bAncestor !== null;
|
|
if (!bAncestorIsCommon && continueB) {
|
|
bAncestor = instance.getNode(bAncestor).parentId;
|
|
}
|
|
}
|
|
}
|
|
const commonAncestor = aAncestorIsCommon ? aAncestor : bAncestor;
|
|
const ancestorFamily = instance.getChildrenIds(commonAncestor);
|
|
const aSide = aFamily[aFamily.indexOf(commonAncestor) - 1];
|
|
const bSide = bFamily[bFamily.indexOf(commonAncestor) - 1];
|
|
return ancestorFamily.indexOf(aSide) < ancestorFamily.indexOf(bSide) ? [nodeAId, nodeBId] : [nodeBId, nodeAId];
|
|
}; |