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

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

• 每个类层次结构的BFS“向上” - 结果进入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,

这是基于亚当的回答。

首先，我进行了优化，以便它将创建更少的临时对象，即每个级别只有一个而不是一个。getClassesArrayDequeLinkedHashSet

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()getClassesretainAll

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