查找类集合的最近公共超类（或超接口） [英] 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?

例如，给定以下内容：

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

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

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

ETA: I know about the reflection APIs. It's the algorithm (or an implementation of such an algorithm) I'm looking for.

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

ETA: And I know it's a DAG. Thank you. You're very clever.

ETA：关于拓扑排序（重新 EJP的答案）：我熟悉的拓扑排序算法要求您：

ETA: On topological sorting (in re EJP's answer): the topological sort algorithms I'm familiar with require you to either:

1. 从root节点 n 开始，没有传入边缘（即，在这种情况下，可能是对象和所有没有超接口的接口 - 必须检查整个集合，加上所有超类/超接口，以便收集）并处理所有边（n，m）（即，所有 m扩展/实现n ，再一次必须检查要收集的整个集合的信息），或


2. 从leaf节点 m 开始，没有传出边缘（即，在这种情况下，所有类/接口 m 没有类 k扩展/实现m 存在，再次需要检查整个集合以收集）并处理所有e dges （n，m）（即所有类/接口 m 扩展/实现 - 我们拥有哪些信息）。

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

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

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.

推荐答案

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

Full working solution to best of my knowledge

• 每个类层次结构的BFS向上 - 结果为LinkedHashSet（保留顺序+无重复）


• 将每个集合与下一个集合相交以查找任何内容通常，LinkedHashSet再次保留顺序


• 剩下的有序集是常见的祖先，列表中的第一个是最近，最后是最远的。


• 空列表表示没有祖先（除了对象）

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

代码

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,

这篇关于查找类集合的最近公共超类（或超接口）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！