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

Question

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

例如，鉴于以下情况：

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： 我了解反射API。我正在寻找的算法（或这种算法的实现）。

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

ETA：
关于拓扑排序（有关EJP的回答）：我熟悉的拓扑排序算法要求您执行以下任一操作：

1. 从n没有传入边缘的“根”节点开始（即，在这种情况下，大概是Object所有没有超接口的接口-必须检查整个集合以及所有超类/超接口以进行收集）并处理所有边缘(n, m)（即，全部m extends/implements n，必须再次检查整个集合以收集的信息），或
2. 从m没有传出边缘的“叶”节点开始（即，在这种情况下，m不k extends/implements m存在任何类的所有类/接口，这又将不得不检查要收集的整个集合）并处理所有边缘(n, m)（即，所有类/接口m扩展/实现-我们拥有哪些信息）。

这些多遍算法中的一种或另一种（可能是＃2）可能是实现此目的的最有效方法，但肯定并不明显。还有一种完全不熟悉的单遍拓扑排序算法，或者我只是弄错了这些算法是完全有可能的，但是在那种情况下，“这基本上是一种拓扑排序”并不会立即导致一个答案。

Answer 1

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

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

码

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

配套方法及试验

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

输出量

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,