查找类集合的最近公共超类（或超接口）

给定一组类，找到最近的公共超类的最佳方法是什么？

例如，给出以下内容：

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 {} 

我希望以下（不详尽）：

 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 

我想我最终可以解决这个问题，但是有些人必须已经解决了它，比如Arrays.asList(...)的类型推断。 有人能指出我的算法，或者更好的是，现有的一些实用程序代码？

---

ETA：我知道reflectionAPI。 这是我正在寻找的算法（或这种算法的实现）。

ETA：我知道这是DAG。 谢谢。 你很聪明。

---

ETA：关于拓扑排序（在EJP的回答中 ）：我熟悉的拓扑排序算法要求您：

1. 从没有传入边的“根”节点n开始（即，在这种情况下，可能是Object和没有超接口的所有接口 – 必须检查整个集合，加上所有超类/超接口，以收集）并处理所有边缘(n, m) （即，所有m extends/implements n ，再次必须检查要收集的整个集合的信息），或者
2. 从没有传出边缘的“叶子”节点m开始（即，在这种情况下，没有类k extends/implements m所有类/接口k extends/implements m存在，再次需要检查要收集的整个集合）并处理所有edges (n, m) （即所有类/接口m扩展/实现 – 我们拥有哪些信息）。

可能这些多遍算法中的一个或另一个（好的，可能是＃2）是最有效的方法，但它肯定不是显而易见的。 它也完全有可能是我不熟悉的单程拓扑排序算法，或者我只是简单地将这些算法弄错了，但在这种情况下，再次，“它基本上是一种拓扑排序”并不会立即导致一个答案。

Answer 1

据我所知，完整的工作解决方案

• 每个类层次结构的BFS“向上” – 导致LinkedHashSet（保留顺序+没有重复）
• 将每个集合与下一个相交以查找任何共同点，再次使用LinkedHashSet来保留顺序
• 剩下的“有序”集合是共同的祖先，列表中的第一个是“最近的”，最后是最远的。
• 空列表意味着没有祖先（除了对象）

码

 private static Set> getClassesBfs(Class clazz) { Set> classes = new LinkedHashSet>(); Set> nextLevel = new LinkedHashSet>(); nextLevel.add(clazz); do { classes.addAll(nextLevel); Set> thisLevel = new LinkedHashSet>(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> commonSuperClass(Class... classes) { // start off with set from first hierarchy Set> rollingIntersect = new LinkedHashSet>( getClassesBfs(classes[0])); // intersect with next for (int i = 1; i < classes.length; i++) { rollingIntersect.retainAll(getClassesBfs(classes[i])); } return new LinkedList>(rollingIntersect); } 

支持方法和测试

 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> 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); } 

产量

 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, 

Answer 2

这是基于亚当的答案。

首先，我优化了getClasses以便创建更少的临时对象，即每个级别只有一个ArrayDeque而不是LinkedHashSet 。

 public static Set> getSuperclasses(Class clazz) { final Set> result = new LinkedHashSet<>(); final Queue> queue = new ArrayDeque<>(); queue.add(clazz); if (clazz.isInterface()) { queue.add(Object.class); // optional } while (!queue.isEmpty()) { Class c = queue.remove(); if (result.add(c)) { Class sup = c.getSuperclass(); if (sup != null) queue.add(sup); queue.addAll(Arrays.asList(c.getInterfaces())); } } return result; } 

要查找公共超类，可以使用if (!isAssignableFrom()) remove()替换对retainAll(getClasses())调用，以便只调用相当昂贵的getClasses一次。 由于嵌套循环，这种方法看起来比原始解决方案的复杂性更差，但这只是因为在原始解决方案中，内部循环隐藏在retainAll 。

 public static Set> commonSuperclasses(Iterable> classes) { Iterator> it = classes.iterator(); if (!it.hasNext()) { return Collections.emptySet(); } // begin with set from first hierarchy Set> result = getSuperclasses(it.next()); // remove non-superclasses of remaining while (it.hasNext()) { Class c = it.next(); Iterator> resultIt = result.iterator(); while (resultIt.hasNext()) { Class sup = resultIt.next(); if (!sup.isAssignableFrom(c)) { resultIt.remove(); } } } return result; } 

最后，在你的问题中，似乎你只对最低的超类感兴趣，这就是我们使用有序集的原因。 但我们也可以轻松删除非叶类。 这里的复杂性是O（n）最佳情况（如果只有一个结果）和O（n ^ 2）最坏情况。

 public static List> lowestCommonSuperclasses(Iterable> classes) { Collection> commonSupers = commonSuperclasses(classes); return lowestClasses(commonSupers); } public static List> lowestClasses(Collection> classes) { final LinkedList> source = new LinkedList<>(classes); final ArrayList> result = new ArrayList<>(classes.size()); while (!source.isEmpty()) { Iterator> srcIt = source.iterator(); Class c = srcIt.next(); srcIt.remove(); while (srcIt.hasNext()) { Class c2 = srcIt.next(); if (c2.isAssignableFrom(c)) { srcIt.remove(); } else if (c.isAssignableFrom(c2)) { c = c2; srcIt.remove(); } } result.add(c); } result.trimToSize(); return result; } 

Answer 3

尝试这个。

 static  Class commonSuperClass(Class c1, Class c2, T... args) { return (Class)args.getClass().getComponentType(); } static  Class commonSuperClass(Class c1, Class c2, Class c3, T... args) { return (Class)args.getClass().getComponentType(); } static  Class commonSuperClass(Class c1, Class c2, Class c3, Class c4, T... args) { return (Class)args.getClass().getComponentType(); } 

结果是

 System.out.println(commonSuperClass(A.class, AImpl.class)); // -> A System.out.println(commonSuperClass(A.class, B.class, C.class)); // -> Object System.out.println(commonSuperClass(A.class, AB.class)); // -> A System.out.println(commonSuperClass(AImpl.class, ABImpl.class)); // -> A System.out.println(commonSuperClass(ABImpl.class, ABImpl2.class)); // -> A System.out.println(commonSuperClass(AImpl.class, ABImpl.class, ABImpl2.class)); // -> A System.out.println(commonSuperClass(ABImpl.class, ABImpl2.class, BCImpl.class)); // -> B System.out.println(commonSuperClass(AImpl.class, ABImpl.class, ABImpl2.class, BCImpl.class)); // -> Object 

Answer 4

对于Spring Framework用户，有org.springframework.util.ClassUtils#determineCommonAncestor 。

例如：

 ClassUtils.determineCommonAncestor(Integer.class, LongAdder.class); 

Answer 5

reflection可以为您提供编写自己的代码所需的信息：

 Class c = SomeType.class; // or someObject.getClass() Class superClass = s.getSuperClass(); Class[] interfaces = s.getInterfaces(); 

Answer 6

我现在也面临这个问题。 我只需要超类级别的答案。 基本上我发现最好只做O（n）步行。

您必须定义一个操作Cmin（A，B），为您提供最近的A类和B类超类。

由于Cmin会导致类本身，因此您可以使用此算法：

结果= Cmin Ai | （ai elementIn类）。

给你O（n）。

但请记住，Java在接口或类的类型上有所区别。