In Java, how to efficiently optimize the descendants of streaming tree nodes?

Suppose we have a collection of objects identified by a unique string and a class tree that defines the hierarchy on them This class is implemented using a mapping from a node (represented by its ID) to a collection of its respective child IDs

class Tree {
  private Map<String,Collection<String>> edges;

  // ...

  public Stream<String> descendants(String node) {
    // To be defined.
  }
}

I want to enable descendants of flow nodes This is a simple solution:

private Stream<String> children(String node) {
    return edges.getOrDefault(node,Collections.emptyList()).stream();
}

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

Before proceeding, I would like to make the following assertions about this solution (am I right about these?)

>The stream flow returned from descendants consumes resources (time and memory) relative to the size of the tree, and the complexity is the same as that of handwriting coding In particular, intermediate objects (streams, splitters,...) representing the iterative state form a stack, so the memory requirements at any given time have the same complexity as the depth of the tree. > It is understood that after this terminates the stream returned from descendants, the root level call to flatmap will lead to the immediate implementation of all contained streams (descendants of each (recursive) call) Therefore, the generated stream is only lazy in the first level recursion, but it cannot surpass (edited according to tagir valeevs answer.)

If I understand these points correctly, my question is: how do I define descendants so that the generated flow is lazy?

I want the solution to be as elegant as possible. In a sense, I prefer a solution that makes the iterative state implicit (to clarify what I mean: I know I can write a splitter, keep an explicit splitter stack at each level, and we can move around the tree. I want to avoid this.)

(there may be a way in Java to use it as a producer consumer workflow, which can be used in languages such as Julia and go)

Solution

For me, your solution has been as elegant as possible, and its limited laziness is not your fault The simplest solution is to wait for JRE developers to fix it

However, if the limited laziness implemented today is really a problem, it may also be the general time to solve this problem So this is about implementing a splitter, but not your task Instead, this is a re implementation of the plan operation, which applies to all cases where the original implementation was limited laziness:

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(),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;
    }
}

All you need to use is to add the import static of the flatmap method to your code and add the form stream The expression of flatmap (function) is changed to flatmap (stream, function)

That is, in your code

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

Then you have completely lazy behavior I tested, even with infinite flow

Note that I added a switch to allow you to go back to the original implementation, such as specifying - dstream. On the command line flatmap. When usestandard = true