В 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, който съдържа стек от итератори (сочещи към съответната колекция от стойности), но предполагам, че винаги ще има състояние на "указател" на всяко ниво на дълбочина, дори ако е скрито в flatMap на 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