Поиск ближайшего общего суперкласса (или суперинтерфейса) набора классов

Ответ 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,

Ответ 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;
} 

Ответ 3

Попробуйте это.

static <T> Class<T> commonSuperClass(Class<? extends T> c1, Class<? extends T> c2, T... args) {
    return (Class<T>)args.getClass().getComponentType();
}

static <T> Class<T> commonSuperClass(Class<? extends T> c1, Class<? extends T> c2, Class<? extends T> c3, T... args) {
    return (Class<T>)args.getClass().getComponentType();
}

static <T> Class<T> commonSuperClass(Class<? extends T> c1, Class<? extends T> c2, Class<? extends T> c3, Class<? extends T> c4, T... args) {
    return (Class<T>)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

Ответ 4

Для пользователей Spring Framework существует org.springframework.util.ClassUtils#determineCommonAncestor.

например:

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

Ответ 5

Отражение может предоставить вам информацию, необходимую для написания собственного кода:

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

Ответ 6

Я также сталкиваюсь с этой проблемой прямо сейчас. Мне нужен только ответ на уровне суперкласса. В основном я нашел, что лучше всего пройти O (n).

Вы должны определить операцию Cmin (A, B), дающую вам ближайший суперкласс класса A и класса B.

Так как Cmin приводит к самому классу, вы можете использовать этот алгоритм:

Результат = Cmin Ai | (классы ai elementIn).

дает вам O (n).

Но помните, что Java делает различия в типах, являющихся интерфейсами или классами.