Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding the nearest common superclass (or superinterface) of a collection of classes

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:

  1. start from "root" nodes 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), or
  2. start from "leaf" nodes m 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.

like image 858
David Moles Avatar asked Mar 21 '12 00:03

David Moles


People also ask

How do you identify a superclass?

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.

What is a superclass example?

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.

What are superclass methods?

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.

What is subclass in superclass?

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).


1 Answers

Full working solution to best of my knowledge

  • BFS of each class hierarchy going "upwards" - result into LinkedHashSet (preserve order + no duplicates)
  • Intersect each set with the next to find anything in common, again LinkedHashSet to preserve order
  • The remaining "ordered" set is the common ancestors, first in list is "nearest", last is furthest.
  • Empty list implies no ancestors (apart from object)

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, 
like image 112
Adam Avatar answered Oct 08 '22 16:10

Adam