How do I find the nearest common superclass of two non-interface classes

Question

To find the nearest common superclass, given two non-interface classes a and b, I do the following:

static Class<?> findClosestCommonSuper(final Class<?> a, final Class<?> b) {
    Iterator<Class<?>> pathA = pathFromObject(a).iterator();
    Iterator<Class<?>> pathB = pathFromObject(b).iterator();
    Class<?> res = Object.class;
    Class<?> c;
    while (pathA.hasNext() && pathB.hasNext()) {
        if ((c = pathA.next()) == pathB.next())
            res = c;
    }
    return res;
}

pathFromObject() returns a List<Class<?>> representing inheritance chain, starting from Object.class:

static List<Class<?>> pathFromObject(Class<?> cl) {
    List<Class<?>> res = new ArrayList<>();
    while (cl != null) {
        res.add(cl);
        cl = cl.getSuperclass();
    }
    Collections.reverse(res);
    return res;
}

My question is: does some out-of-the-box JDK solution exist for this? Maybe using classloader or some specific functionality. Or a better algorithm that doesn't require two iterations.

Take a look at this question which discusses a more general version of the problem: http://stackoverflow.com/questions/9797212/finding-the-nearest-common-superclass-or-superinterface-of-a-collection-of-cla — mikej, Apr 08 '16 at 21:32
@mikej thank you. There are no mistake: path is reversed, so 0th item of the list is always `Object.class`. Certainly, I did read that question--it provides a solution to a very common problem, where multiple inheritance (interfaces) is involved. My task is much more easy, so I hope that easy solution exists. — Alex Salauyou, Apr 08 '16 at 21:34
Cool. I think that I missed that is a sign it's time for me to step away from the keyboard for the night :) — mikej, Apr 08 '16 at 21:36
You could do one iteration to find the path of one of the classes, and then just walk back up the chain of superclasses of the other class until you find the first common class. It's no better in the worst case, though. — Andy Turner, Apr 08 '16 at 21:36

score 19 · Accepted Answer · answered Apr 08 '16 at 21:37

19

I think the simplest implementation is this

static Class<?> findClosestCommonSuper(Class<?> a, Class<?> b) {
    while (!a.isAssignableFrom(b))
        a = a.getSuperclass();
    return a;
}

answered Apr 08 '16 at 21:37

Paul Boddington

37,127
10
65
116

What if `a` is never assignable from `b`? Don't you need to check symmetrically? – Andy Turner Apr 08 '16 at 21:37
It will be because we must reach `Object.class`. Interface types are excluded. – Paul Boddington Apr 08 '16 at 21:38
Ah, I see. Carry on :) – Andy Turner Apr 08 '16 at 21:40
@PaulBoddington I checked, that's ingeniously great! Need some time to understand how it works... but, I vote 3 times if I could. – Alex Salauyou Apr 08 '16 at 21:48
1

@SashaSalauyou I've got a maths degree - a course in lattice theory helped! This is a common algorithm (and it is symmetric, despite appearances). – Paul Boddington Apr 08 '16 at 21:49
This can be inefficient if `a` is deep in some inheritance hierarchy and `b` directly extends from `Object`. (This will rarely happen in Java class hierarchies, at least as far as I've seen, but it's something to consider.) – Savior Apr 08 '16 at 21:52
1

@Pillar That's true. Sometimes a bottom-up approach is better, other times a top-down one. Most classes are at most 5 or 6 levels deep so I don't think it's critical. – Paul Boddington Apr 08 '16 at 21:53
Great answer for NON-INTERFACE classes. – GlenPeterson May 07 '17 at 17:19
If you include interfaces as input values this yields different results depending on the input order. e.g. `(Serializable, String) = Serializable`, but `(String, Serializable) = Object`. This little check beforehand can avoid this: `if (a.isInterface() != b.isInterface()) { return Object.class; }`, but it does not add full support for interfaces. – Frederic Leitenberger Jul 31 '17 at 15:08
And these checks can speed up things and/or avoid some other corner-cases: `if (a == b) { return a; } if (a == null || b == null || a.isPrimitive() || b.isPrimitive()) { return null; }` For primitives maybe you want to return Object.class as well (since when boxed they are objects). Or convert primitive types to boxed types before doing the rest of the routine: [ClassUtils.primitiveToWrapper()](https://commons.apache.org/proper/commons-lang/javadocs/api-3.1/org/apache/commons/lang3/ClassUtils.html#primitiveToWrapper(java.lang.Class)) – Frederic Leitenberger Jul 31 '17 at 15:09

Savior · Answer 2 · 2016-04-18T15:12:41.830

There is no JDK utility to do this.

This is an interesting interview question. It's basically the problem of finding the lowest common ancestor between two nodes in a tree, given only the nodes. The typical solution for that is a queue. You alternate verifying and then adding the parent of each node.

Something like:

static Class<?> findClosestCommonSuper(final Class<?> a, final Class<?> b) {
    // Validation on the type of Class (interface, primitive, etc.) and != null

    Set<Class<?>> visited = new HashSet<>();
    Queue<Class<?>> queue = new LinkedList<>();
    queue.add(a);
    queue.add(b);

    do {
        // first iteration not empty
        Class<?> current = queue.poll();
        if (!visited.add(current)) {
            // already seen it, must be lowest in tree
            return current;
        }
        if (current.getSuperclass() != null) {
            queue.add(current.getSuperclass());
        }
    } while (!queue.isEmpty());

    throw new IllegalStateException("should never happen if the validation above is correct");
}

I believe this is the most efficient you can get since you don't have to unnecessarily traverse full paths up to Object.class.

no idea why they downvoted... I find this answer useful and informative — Alex Salauyou, May 04 '16 at 11:33
I added this code at the beginning: `if (a == null || b == null || a.isPrimitive() || b.isPrimitive()) { return null; } if (a == b) { return a; /* optimization */ }` And instead of throwing the exception i `return Object.class;`. This way it can also be used for interfaces. But when mixing interfaces with classes you get `Object.class` as result. For my purpose (array construction) this works just fine. — Frederic Leitenberger, Jul 31 '17 at 14:37

How do I find the nearest common superclass of two non-interface classes

2 Answers2

Linked