Как найти ближайший общий суперкласс двух классов без интерфейса

Чтобы найти ближайший общий суперкласс, учитывая два неинтерфейсных класса a и b, я делаю следующее:

static Class<?> findClosestCommonSuper(final Class<?> a, final Class<?> b) {
    Iterator<Class<?>> pathA = pathFromObject(a).iterator();
    Iterator<Class<?>> pathB = pathFromObject(b).iterator();
    Class<?> res = Object.class;
    Class<?> c;
    while (pathA.hasNext() && pathB.hasNext()) {
        if ((c = pathA.next()) == pathB.next())
            res = c;
    }
    return res;
}

pathFromObject() возвращает a List<Class<?>>, представляющую цепочку наследования, начиная с Object.class:

static List<Class<?>> pathFromObject(Class<?> cl) {
    List<Class<?>> res = new ArrayList<>();
    while (cl != null) {
        res.add(cl);
        cl = cl.getSuperclass();
    }
    Collections.reverse(res);
    return res;
}

Мой вопрос: существует ли какое-то готовое решение JDK для этого? Возможно, с помощью classloader или какой-то определенной функциональности. Или лучший алгоритм, который не требует двух итераций.

Ответы

Ответ 1

Я думаю, что самая простая реализация - это

static Class<?> findClosestCommonSuper(Class<?> a, Class<?> b) {
    while (!a.isAssignableFrom(b))
        a = a.getSuperclass();
    return a;
}

Ответ 2

Для этого не существует утилиты JDK.

Это интересный вопрос интервью. Это в основном проблема нахождения самого низкого общего предка между двумя узлами в дереве, учитывая только узлы. Типичным решением для этого является очередь. Вы поочередно проверяете, а затем добавляете родительский элемент для каждого node.

Что-то вроде:

static Class<?> findClosestCommonSuper(final Class<?> a, final Class<?> b) {
    // Validation on the type of Class (interface, primitive, etc.) and != null

    Set<Class<?>> visited = new HashSet<>();
    Queue<Class<?>> queue = new LinkedList<>();
    queue.add(a);
    queue.add(b);

    do {
        // first iteration not empty
        Class<?> current = queue.poll();
        if (!visited.add(current)) {
            // already seen it, must be lowest in tree
            return current;
        }
        if (current.getSuperclass() != null) {
            queue.add(current.getSuperclass());
        }
    } while (!queue.isEmpty());

    throw new IllegalStateException("should never happen if the validation above is correct");
}

Я считаю, что это самый эффективный способ, который вы можете получить, поскольку вам не нужно излишне проходить полные пути до Object.class.