How To Find Nearest Common Ancestor Class Of Two Objects?

This question is basically the JavaScript equivalent of How do I find the nearest common superclass of two non-interface classes TL;DR: Given two objects and an extensive inheritan

Solution 1:

This is a tree problem (Lowest common ancestor), where edges are determined by Object.getPrototypeOf.

The idea is to get the paths from the root for the two given nodes, and then compare the entries in those two paths starting at the root. The last node that is the same is the common node. Finally get the constructor of that prototype object, which is the "class":

functiongetPath(o) {
    const path = [];

    while (o) {
        path.push(o);
        o = Object.getPrototypeOf(o);
    }

    return path.reverse();
}

functiongetClosestCommonAncestorClass(x, y) {
    const xPath = getPath(x);
    const yPath = getPath(y);
    const steps = Math.min(xPath.length, yPath.length);

    let i = 0;

    for (; i < steps; i++) {
        if (xPath[i] !== yPath[i]) break;
    }

    return xPath[i - 1]?.constructor;
}

classA {}
classBextendsA {}
classCextendsB {}
classDextendsB {}
classEextendsD {}

console.log(getClosestCommonAncestorClass(newC(), newE())); // class B

Solution 2:

1. Walk each of the prototypes of left and right up the chain and keep track of all visited prototypes.
2. At each step see if you have already visited this prototype.
3. At some point there would be a crossover hit upon a prototype that is common to both. Return it.
4. (edge case) Where there truly are no common prototypes in the chain (most likely because at least one object is created via Object.create(null)) then return null as the common ancestor;

functiongetClosestCommonAncestorClass(left, right) {
  let protoLeft = Object.getPrototypeOf(left);
  let protoRight = Object.getPrototypeOf(right);
  
  const visited = newSet();
  while (protoLeft !== null || protoRight !== null) {
    if (protoLeft === protoRight)
      return protoLeft?.constructor;

    visited
      .add(protoLeft)
      .add(protoRight);
      
    protoLeft = protoLeft && Object.getPrototypeOf(protoLeft);
    protoRight = protoRight && Object.getPrototypeOf(protoRight);
    
    if (protoLeft !== null && visited.has(protoLeft))
      return protoLeft.constructor;
      
    if (protoRight !== null && visited.has(protoRight))
      return protoRight.constructor;
  }
  
  returnnull;
}

classA {}
classBextendsA {}
classCextendsB {}
classDextendsC {}
classEextendsB {}

const c = newC();
const e = newE();

const closestCommonAncestor = getClosestCommonAncestorClass(c, e);
console.log(closestCommonAncestor.name);
console.assert(closestCommonAncestor.name === "B");

const d = newD();

const closestCommonAncestor2 = getClosestCommonAncestorClass(d, e);
console.log(closestCommonAncestor2.name);
console.assert(closestCommonAncestor2.name === "B");

const closestCommonAncestor3 = getClosestCommonAncestorClass(d, c);
console.log(closestCommonAncestor3.name);
console.assert(closestCommonAncestor3.name === "C");

classZ {};
const z = newZ();

const closestCommonAncestor4 = getClosestCommonAncestorClass(z, d);
console.log(closestCommonAncestor4.name);
console.assert(closestCommonAncestor4 === Object);

const nullObj = Object.create(null);
const closestCommonAncestor5 = getClosestCommonAncestorClass(nullObj, d);
console.log(closestCommonAncestor5);
console.assert(closestCommonAncestor5 === null);

Solution 3:

Both @trincot's and @VLAZ's answers have their pros and cons, but I think I have achieved to amalgamate them together.

The approach here would be: for each parent class (closest to furthest) of one object (doesn't matter which one), check if another object is an instance of that class; if that's true, return the class; otherwise if the list is exhausted, return null.

Note, that getParentClassesOf is defined as a generator to avoid creating unused values (further common classes are not needed), but it should be easy enough to implement it as a plain array-returning function if needed.

function * getParentClassesOf(object) {
    let current = object;
    let prototype;

    while (prototype = Object.getPrototypeOf(current)) {
        yield prototype.constructor; // or classes.push(prototype.constructor)

        current = prototype;
    }
}

functiongetClosestCommonAncestorClass(left, right) {
    for (const parentClass ofgetParentClassesOf(left))
        if (right instanceof parentClass)
            return parentClass;

    returnnull;
}

function * getParentClassesOf(object) {
    let current = object;
    let prototype;

    while (prototype = Object.getPrototypeOf(current)) {
        yield prototype.constructor; // or classes.push(prototype.constructor)

        current = prototype;
    }
}

functiongetClosestCommonAncestorClass(left, right) {
    for (const parentClass ofgetParentClassesOf(left))
        if (right instanceof parentClass)
            return parentClass;

    returnnull;
}

// *** classA {}
classBextendsA {}
classCextendsB {}
classDextendsB {}
classEextendsD {}

const closestCommonAncestor = getClosestCommonAncestorClass(newC(), newE());
console.log(closestCommonAncestor.name);
console.assert(closestCommonAncestor.name === "B");

See more examples