查找类集合的最近公共超类(或超级接口)

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,

Answer 2

这是基于亚当的答案.

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

public static Set<Class<?>> getSuperclasses(Class<?> clazz) {
    final Set<Class<?>> result = new LinkedHashSet<>();
    final Queue<Class<?>> 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;
}

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

public static Set<Class<?>> commonSuperclasses(Iterable<Class<?>> classes) {
    Iterator<Class<?>> it = classes.iterator();
    if (!it.hasNext()) {
        return Collections.emptySet();
    }
    // begin with set from first hierarchy
    Set<Class<?>> result = getSuperclasses(it.next());
    // remove non-superclasses of remaining
    while (it.hasNext()) {
        Class<?> c = it.next();
        Iterator<Class<?>> 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<Class<?>> lowestCommonSuperclasses(Iterable<Class<?>> classes) {
    Collection<Class<?>> commonSupers = commonSuperclasses(classes);
    return lowestClasses(commonSupers);
}

public static List<Class<?>> lowestClasses(Collection<Class<?>> classes) {
    final LinkedList<Class<?>> source = new LinkedList<>(classes);
    final ArrayList<Class<?>> result = new ArrayList<>(classes.size());
    while (!source.isEmpty()) {
        Iterator<Class<?>> 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;
}