Как в Java эффективно и элегантно передавать потомков узла дерева?

Для меня ваше решение уже настолько элегантно, насколько это возможно, и его ограниченная лень не по вашей вине. Самое простое решение — подождать, пока это не исправят разработчики JRE. Это было сделано с помощью Java 10.

Однако, если эта ограниченная лень сегодняшней реализации действительно вызывает беспокойство, возможно, пришло время решить эту проблему в общем виде. Что ж, речь идет о о реализации Spliterator, но не о конкретной задаче. Вместо этого это повторная реализация операции flatmap, обслуживающая все случаи, когда имеет значение ограниченная ленивость исходной реализации:

public class FlatMappingSpliterator<E,S> extends Spliterators.AbstractSpliterator<E>
implements Consumer<S> {

    static final boolean USE_ORIGINAL_IMPL
        = Boolean.getBoolean("stream.flatmap.usestandard");

    public static <T,R> Stream<R> flatMap(
        Stream<T> in, Function<? super T,? extends Stream<? extends R>> mapper) {

        if(USE_ORIGINAL_IMPL)
            return in.flatMap(mapper);

        Objects.requireNonNull(in);
        Objects.requireNonNull(mapper);
        return StreamSupport.stream(
            new FlatMappingSpliterator<>(sp(in), mapper), in.isParallel()
        ).onClose(in::close);
    }

    final Spliterator<S> src;
    final Function<? super S, ? extends Stream<? extends E>> f;
    Stream<? extends E> currStream;
    Spliterator<E> curr;

    private FlatMappingSpliterator(
        Spliterator<S> src, Function<? super S, ? extends Stream<? extends E>> f) {
        // actually, the mapping function can change the size to anything,
        // but it seems, with the current stream implementation, we are
        // better off with an estimate being wrong by magnitudes than with
        // reporting unknown size
        super(src.estimateSize()+100, src.characteristics()&ORDERED);
        this.src = src;
        this.f = f;
    }

    private void closeCurr() {
        try { currStream.close(); } finally { currStream=null; curr=null; }
    }

    public void accept(S s) {
        curr=sp(currStream=f.apply(s));
    }

    @Override
    public boolean tryAdvance(Consumer<? super E> action) {
        do {
            if(curr!=null) {
                if(curr.tryAdvance(action))
                    return true;
                closeCurr();
            }
        } while(src.tryAdvance(this));
        return false;
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        if(curr!=null) {
            curr.forEachRemaining(action);
            closeCurr();
        }
        src.forEachRemaining(s->{
            try(Stream<? extends E> str=f.apply(s)) {
                if(str!=null) str.spliterator().forEachRemaining(action);
            }
        });
    }

    @SuppressWarnings("unchecked")
    private static <X> Spliterator<X> sp(Stream<? extends X> str) {
        return str!=null? ((Stream<X>)str).spliterator(): null;
    }

    @Override
    public Spliterator<E> trySplit() {
        Spliterator<S> split = src.trySplit();
        if(split==null) {
            Spliterator<E> prefix = curr;
            while(prefix==null && src.tryAdvance(s->curr=sp(f.apply(s))))
                prefix=curr;
            curr=null;
            return prefix;
        }
        FlatMappingSpliterator<E,S> prefix=new FlatMappingSpliterator<>(split, f);
        if(curr!=null) {
            prefix.curr=curr;
            curr=null;
        }
        return prefix;
    }
}

Все, что вам нужно для его использования, это добавить в код import static метода flatMap и изменить выражения вида stream.flatmap(function) на flatmap(stream, function).

т.е. в вашем коде

public Stream<String> descendants(String node) {
    return Stream.concat(
        Stream.of(node),
        flatMap(children(node), this::descendants)
    );
}

то у вас полное ленивое поведение. Я тестировал это даже с бесконечными потоками…

Обратите внимание, что я добавил переключатель, позволяющий вернуться к исходной реализации, например. при указании    -Dstream.flatmap.usestandard=true в командной строке.

Вы немного ошибаетесь, говоря, что поток flatMap не ленив. Он несколько ленив, хотя его лень действительно ограничена. Давайте используем некоторые пользовательские Collection для отслеживания запрошенных элементов внутри вашего класса Tree:

private final Set<String> requested = new LinkedHashSet<>();

private class MyList extends AbstractList<String> implements RandomAccess
{
    private final String[] data;

    public MyList(String... data) {
        this.data = data;
    }

    @Override
    public String get(int index) {
        requested.add(data[index]);
        return data[index];
    }

    @Override
    public int size() {
        return data.length;
    }
}

Теперь давайте предварительно инициализируем ваш класс некоторыми данными дерева:

public Tree() {
    // "1" is the root note, contains three immediate descendants
    edges.put("1", new MyList("2", "3", "4"));
    edges.put("2", new MyList("5", "6", "7"));
    edges.put("3", new MyList("8", "9", "10"));
    edges.put("8", new MyList("11", "12"));
    edges.put("5", new MyList("13", "14", "15"));
    edges.put("7", new MyList("16", "17", "18"));
    edges.put("6", new MyList("19", "20"));
}

Наконец, давайте проверим, сколько элементов на самом деле запрашивается из вашего списка при разных предельных значениях:

public static void main(String[] args) {
    for(int i=1; i<=20; i++) {
        Tree tree = new Tree();
        tree.descendants("1").limit(i).toArray();
        System.out.println("Limit = " + i + "; requested = (" + tree.requested.size()
                + ") " + tree.requested);
    }
}

Вывод следующий:

Limit = 1; requested = (0) []
Limit = 2; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 3; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 4; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 5; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 6; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 7; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 8; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 9; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 10; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 11; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 12; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 13; requested = (12) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18]
Limit = 14; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 15; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 16; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 17; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 18; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 19; requested = (18) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10]
Limit = 20; requested = (19) [2, 5, 13, 14, 15, 6, 19, 20, 7, 16, 17, 18, 3, 8, 11, 12, 9, 10, 4]

Таким образом, когда запрашивается только корневая заметка, доступ к дочерним элементам не осуществляется (поскольку Stream.concat является умным). Когда запрашивается первый непосредственный дочерний элемент, обрабатывается все поддерево для этого дочернего элемента, даже если в нем нет необходимости. Тем не менее, второй непосредственный дочерний элемент не обрабатывается до тех пор, пока не завершится первый. Это может быть проблематично для сценариев короткого замыкания, но в большинстве случаев работа вашего терминала не является коротким замыканием, поэтому это все еще хороший подход.

Что касается ваших опасений по поводу потребления памяти: да, оно ест память в соответствии с глубиной дерева (и, что более важно, съедает стек). Если ваше дерево имеет тысячи уровней вложенности, у вас возникнут проблемы с вашим решением, поскольку вы можете нажать StackOverflowError для настройки по умолчанию -Xss. Для нескольких сотен уровней глубины это сработает нормально.

Мы используем аналогичный подход на уровне бизнес-логики нашего приложения, он отлично работает для нас, хотя наши деревья редко бывают глубже 10 уровней.

Не реальный ответ, а просто мысль:

Если вы заглянете в коллекцию значений и на следующем шаге «разрешите» это последнее увиденное значение в новую коллекцию значений, рекурсивно возвращающую следующие значения таким же образом, то, как бы это ни было реализовано, оно всегда будет заканчиваться каким-то « указатель» на текущий элемент в коллекции значений на текущем «уровне» глубины дерева, а также с каким-то стеком, содержащим все эти «указатели».

Это потому, что вам нужна как информация о более высоких уровнях в дереве (стеке), так и «указатель» на текущий элемент на текущем уровне. В этом случае одно вызывает другое.

Конечно, вы можете реализовать это как Spliterator, который содержит стек итераторов (указывающий на соответствующую коллекцию значений), но я полагаю, что на каждом уровне глубины всегда будет состояние «указатель», даже если оно скрыто в плоской карте Java ( или связанные) временные объекты.

В качестве альтернативы: как насчет использования «настоящего» дерева с узлами, которые содержат ссылку на его родительский узел? Кроме того, добавление карты в корень дерева, которая содержит ссылку на все отдельные узлы, чтобы упростить доступ к под-под-под-дочернему элементу. Я предполагаю, что реализация Spliterator тогда будет очень простой, потому что ей просто нужна ссылка на текущий узел для обхода и критерий остановки (начальное значение узла), чтобы перестать слишком «высоко» подниматься по дереву.

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

public class TreeIterator {
    private Tree tree;
    private List<String> topLevelNodes;

    public TreeIterator(Tree t, String node) {
        topLevelNodes = new List();
        topLevelNodes.add(node);
        tree = t;
    }

    public String next() {
        if (topLevelNodes.size() > 0) {
            int last = topLevelNodes.size() - 1;
            String result = topLevelNodes.get(last);
            topLevelNodes.remove(last);
            topLevelNodes.addAll(tree.get(result));
            return result;
        }
        return null;
    }
}

Извините за new List() и другие неправильные вещи, просто хотел поделиться идеей.

Давайте сначала ответим на вопрос, предоставив техническое обсуждение -

1. TreeNode может также содержать ссылку на пользовательский объект, использование которого остается за пользователем. Запрашивая TreeNode его строковое представление с помощью toString(), вы возвращаете строковое представление своего пользовательского объекта.
2. У узла дерева может быть не более одного родителя и 0 или более дочерних элементов. TreeNode предоставляет операции для проверки и изменения родительского и дочернего узлов узла, а также операции для проверки дерева, частью которого является узел. Дерево узлов — это набор всех узлов, до которых можно добраться, начав с узла и следуя всем возможным ссылкам на родителей и потомков. Узел без родителя является корнем своего дерева; узел без детей является листом. Дерево может состоять из множества поддеревьев, причем каждый узел выступает в качестве корня для своего собственного поддерева.
3. Существующий DefaultMutableTrrNode Java 8 изменен.
4. Этот класс предоставляет перечисления для эффективного обхода дерева или поддерева в различных порядках или для следования по пути между двумя узлами.
5. Это не потокобезопасный класс. Если вы собираетесь использовать TreeNode (или дерево TreeNodes) более чем в одном потоке, вам необходимо выполнить собственную синхронизацию. Хорошим соглашением является синхронизация на корневом узле дерева.
6. Сериализованные объекты этого класса не будут совместимы с будущими версиями Swing. Текущая поддержка сериализации подходит для краткосрочного хранения или RMI между приложениями, использующими одну и ту же версию Swing. Начиная с версии 1.4, в пакет java.beans добавлена ​​поддержка долговременного хранения всех JavaBeans™.

Проверьте эту модифицированную версию TreeNode, добавленную в Git — TreeNode