Java сортировка Список объектов с иерархией по алфавиту

Question

У меня есть сущность с именем Item. Item могут иметь родителей и детей.

Каждый Item имеет следующие методы:

• getParent() -> возвращает Item
• getChildren() -> возвращает List<Item>
• isLeaf() -> возвращает Boolean
• getName() -> возвращает String

Каждый уровень в иерархии - это уровень на строительной площадке, например, уровень 1 - это Дом 1, уровень 2 - Этаж 1, уровень 3 - Комната, а уровень 4 - Окно.

У меня есть List<Item, и мне нужно отсортировать их так:

• Элемент 1 (Дом 1> Этаж 1> Комната 1> Ванна)
• Пункт 2 (Дом 1> Этаж 1> Комната 2> Подвал)
• Позиция 3 (Дом 1> Этаж 1> Комната 2> Дверь)
• Пункт 4 (Дом 1> Этаж 1> Комната 2> Окно)
• Пункт 5 (Дом 1> Этаж 2> Комната 1> Дверь)

Я думаю, что мне нужна какая-то рекурсивная функция, но я не представляю, как это должно быть.

Я уже исследовал сортировку объектов с иерархией в Java, но я не нахожу ничего похожего на мой случай.

Буду признателен за любую помощь и извините, если вопрос не ясен на 100%, но его довольно сложно описать.

Спасибо.

Answer 1

Это действительно было бы рекурсивно. Проблема в том, что простое рекурсивное сравнение будет работать только в том случае, если два узла находятся на одном уровне.

// Same level compare
int compareSameLevel(Item item) {
    int c = 0;
    if (this.getParent != null) {
        c = compare(this.getParent(), item.getParent());
    }
    return (c != 0) ? c : getName().compare(item.getName());
}

Но вы можете настроить уровни, чтобы найти общий уровень и предположить, что дети идут за родителем:

// Compare on any level
int compare(Item item) {
    Item thisItem = this;
    int thisLevel = thisItem.level();
    int itemLevel = item.level();

    for (int i = thisLevel; i > itemLevel; i--) {
        thisItem = thisItem.getParent();
    }

    for (int j = itemLevel; j > thisLevel; j--) {
        item = item.getParent();
    }

    int c = compareSameLevel(thisItem, item);

    return c != 0 ? c : (thisLevel > itemLevel ? -1 : 1);
}

Это просто чтобы дать вам идею. Он не проверен и не скомпилирован.

Answer 2

Псевдокод: Попробуйте вот так

    private static void printChildElements(List<Object> childNodes) {
    for(Object childNode : childNodes) {

        List<Object > childElements = childNode .....;
        if(childElements.size() > 0) {
            printChildElements( childElements);
        }
    }