Given a collection of classes, what's the best way to find the nearest common superclass?
E.g., given the following:
interface A {} interface B {} interface AB extends A, B {} interface C {} class AImpl implements A {} class ABImpl implements AB {} class ABImpl2 implements A, B {} class BCImpl implements B, C {}
I would expect the following (not exhaustive):
commonSuperclass(A, AImpl) == A commonSuperclass(A, B, C) == Object or null, I'm not picky commonSuperclass(A, AB) == A commonSuperclass(AImpl, ABImpl) == A commonSuperclass(ABImpl, ABImpl2) == either A or B or both, I'm not picky commonSuperclass(AImpl, ABImpl, ABImpl2) == A commonSuperclass(ABImpl, ABImpl2, BCImpl) == B commonSuperclass(AImpl, ABImpl, ABImpl2, BCImpl) == Object
I imagine I could eventually work this out, but someone must have solved it already for things like the type inference in Arrays.asList(...)
. Can anyone point me to an algorithm, or better yet, some existing utility code?
ETA: I know about the reflection APIs. It's the algorithm (or an implementation of such an algorithm) I'm looking for.
ETA: And I know it's a DAG. Thank you. You're very clever.
ETA: On topological sorting (in re EJP's answer): the topological sort algorithms I'm familiar with require you to either:
n
with no incoming edges (i.e., in this scenario, presumably Object
and all interfaces without superinterfaces -- which one would have to examine the whole set, plus all superclasses/superinterfaces, to collect) and process all edges (n, m)
(i.e., all m extends/implements n
, information which again one would have to examine the whole set to collect), orm
with no outgoing edges (i.e., in this scenario, all classes/interfaces m
for which no class k extends/implements m
exists, which again one would have to examine the whole set to collect) and process all edges (n, m)
(i.e., all class/interfaces m
extends/implements -- which information we do have).It's possible one or the other of these multi-pass algorithms (okay, presumably #2) is the most efficient way to do this, but it's certainly not trivially obvious. It's also entirely possible there's a one-pass topological sort algorithm I'm not familiar with, or that I've simply got these algorithms wrong, but in that case, again, "it's basically a kind of topological sort" does not immediately lead one to the answer.
To determine the superclass of a class, you invoke the getSuperclass method. This method returns a Class object representing the superclass, or returns null if the class has no superclass. To identify all ancestors of a class, call getSuperclass iteratively until it returns null.
A superclass is the class from which many subclasses can be created. The subclasses inherit the characteristics of a superclass. The superclass is also known as the parent class or base class. In the above example, Vehicle is the Superclass and its subclasses are Car, Truck and Motorcycle.
The superclass method is used to access the parent class inside a child class. This method has a variety of uses when inheriting parent members.
Definitions: A class that is derived from another class is called a subclass (also a derived class, extended class, or child class). The class from which the subclass is derived is called a superclass (also a base class or a parent class).
Full working solution to best of my knowledge
Code
private static Set<Class<?>> getClassesBfs(Class<?> clazz) { Set<Class<?>> classes = new LinkedHashSet<Class<?>>(); Set<Class<?>> nextLevel = new LinkedHashSet<Class<?>>(); nextLevel.add(clazz); do { classes.addAll(nextLevel); Set<Class<?>> thisLevel = new LinkedHashSet<Class<?>>(nextLevel); nextLevel.clear(); for (Class<?> each : thisLevel) { Class<?> superClass = each.getSuperclass(); if (superClass != null && superClass != Object.class) { nextLevel.add(superClass); } for (Class<?> eachInt : each.getInterfaces()) { nextLevel.add(eachInt); } } } while (!nextLevel.isEmpty()); return classes; } private static List<Class<?>> commonSuperClass(Class<?>... classes) { // start off with set from first hierarchy Set<Class<?>> rollingIntersect = new LinkedHashSet<Class<?>>( getClassesBfs(classes[0])); // intersect with next for (int i = 1; i < classes.length; i++) { rollingIntersect.retainAll(getClassesBfs(classes[i])); } return new LinkedList<Class<?>>(rollingIntersect); }
Supporting methods and test
private static void test(Class<?>... classes) { System.out.println("Common ancestor for " + simpleClassList(Arrays.asList(classes)) + ", Result => " + simpleClassList(commonSuperClass(classes))); } private static String simpleClassList(Collection<Class<?>> classes) { StringBuilder builder = new StringBuilder(); for (Class<?> clazz : classes) { builder.append(clazz.getSimpleName()); builder.append(","); } return builder.toString(); } public static void main(String[] args) { test(A.class, AImpl.class); test(A.class, B.class, C.class); test(A.class, AB.class); test(AImpl.class, ABImpl.class); test(ABImpl.class, ABImpl2.class); test(AImpl.class, ABImpl.class, ABImpl2.class); test(ABImpl.class, ABImpl2.class, BCImpl.class); test(AImpl.class, ABImpl.class, ABImpl2.class, BCImpl.class); test(AB.class, ABImpl.class); }
Output
Common ancestor for A,AImpl,, Result => A, Common ancestor for A,B,C,, Result => Common ancestor for A,AB,, Result => A, Common ancestor for AImpl,ABImpl,, Result => A, Common ancestor for ABImpl,ABImpl2,, Result => A,B, Common ancestor for AImpl,ABImpl,ABImpl2,, Result => A, Common ancestor for ABImpl,ABImpl2,BCImpl,, Result => B, Common ancestor for AImpl,ABImpl,ABImpl2,BCImpl,, Result => Common ancestor for AB,ABImpl,, Result => AB,A,B,
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With