java - 是否可以有一个带有中间生产者的 Java Stream？

Question

我有一个递归遍历树的解析器。我想重写这个解析器的实现，这样我就可以使用 Java 的 Stream API，并且只能使用 Stream API，而无需任何递归。

树的每个节点都应由具有以下签名的处理器处理:Stream<Token> process(Token) 。恕我直言，我不能使用 flatMap()因为我不知道我处理的树的深度，并且我无法修改我处理的流。我知道如何使用普通循环、简单列表以及大量索引和偏移计算来做到这一点。

Answer 1

如果我理解清楚的话:

1. 您想要树中所有节点的流。这是正确的吗？
2. 您有一个 process 函数，可以返回节点的直接子节点

如果这是正确的，并且您确实想排除任何递归，Spliterator API是要走的路。您创建一个流风格的迭代器来接收流中的元素。任何标准 Java Stream 在底层都使用 Spliterator。

编辑:请参阅代码示例末尾提供的实现(深度优先浏览)。

但是，如果允许递归，则可以轻松生成深度优先流。下面的简单示例显示了这两种方法:

import java.util.Arrays;
import java.util.Spliterator;
import java.util.Stack;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.TimeUnit;
import java.util.function.Consumer;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class Main {

    /**
     * Sample in-memory node class
     */
    static class Node {
        Node[] children;
        final String name;

        Node(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return name;
        }
    }

    /**
     * Simple implementation of your process function, giving back direct children.
     * @param node Node to get children for.
     * @return A stream of available children, can be empty.
     */
    static Stream<Node> process(Node node) {
        return node.children == null? Stream.empty() : Arrays.stream(node.children);
    }

    /**
     * Recursion entrypoint. Allow to perform depth-first browsing.
     */
    static Stream<Node> recurse(Node input) {
        if (input.children == null || input.children.length < 1) return Stream.of(input);
        else return Stream.concat(
                Stream.of(input),
                Arrays.stream(input.children)
                        .flatMap(Main::recurse)
        );
    }

    public static void main(String[] args) throws InterruptedException {

        /* Simple tree :
         * ROOT
         * - A
         * -- AA
         * -- AB
         * --- ABA
         * -- AC
         * - B
         * -- BA
         * -- BB
         * - C
         */
        Node root = new Node("ROOT");
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        root.children = new Node[]{a, b, c};

        Node aa = new Node("AA");
        Node ab = new Node("AB");
        Node ac = new Node("AC");
        a.children = new Node[]{aa, ab, ac};

        Node ba = new Node("BA");
        Node bb = new Node("BB");
        b.children = new Node[]{ba, bb};

        Node aba = new Node("ABA");
        ab.children = new Node[]{aba};

        System.out.println("RECURSIVE BROWSING");
        Stream.of(root).flatMap(Main::recurse)
                .forEach(System.out::println);

        System.out.println("NON-RECURSIVE USING SINGLE-THREAD SPLITERATOR");
        final NodeSpliterator spliterator = new NodeSpliterator(root);
        StreamSupport.stream(spliterator, false)
                .forEach(System.out::println);
    }

    static class NodeSpliterator implements Spliterator<Node> {

        private final Stack<Node> nodeQueue = new Stack<>();

        NodeSpliterator(Node root) {
            nodeQueue.push(root);
        }

        @Override
        public boolean tryAdvance(Consumer<? super Node> action) {
            if (nodeQueue.empty()) return false; // No more nodes, end of this fork of the stream.
            final Node next = nodeQueue.pop();
            // Iterate on next available node
            action.accept(next);
            // Sink direct children for next iteration
            final int endOfQueue = nodeQueue.size();
            process(next).forEach(node -> nodeQueue.add(endOfQueue, node));
            // Notify Stream API that an element has successfully been processed.
            return true;
        }

        @Override
        public Spliterator<Node> trySplit() {
            // Little trick : Parallelism of ordered streams requires the fork to distribute a prefix of
            // Available elements. I'll keep things simple here, I let you work on that.
            return null;
        }

        @Override
        public long estimateSize() {
            return Long.MAX_VALUE; // Would require external metadata for estimation, or womplete browsing for exact count
        }

        @Override
        public int characteristics() {
            // Note : you can add Spliterator.CONCURRENT below once you've resolved how to implement trySplit.
            return ORDERED|NONNULL;
        }
    }
}

此代码产生以下输出:

RECURSIVE BROWSING
ROOT
A
AA
AB
ABA
AC
B
BA
BB
C
NON-RECURSIVE USING SINGLE-THREAD SPLITERATOR
ROOT
A
AA
AB
ABA
AC
B
BA
BB
C