使用流API对树状结构的惰性BFS遍历

Question

考虑我想使用Stream API遍历树状结构的一些节点（类似的问题：[1]，[2]，[3]）。首先想到的是：

abstract class Node {
    abstract Collection<Node> getChildren();

    final Stream<Node> stream() {
        return Stream.concat(Stream.of(this), this.getChildren().stream().flatMap(Node::stream));
    }
}

上面的stream（）实现具有以下特性：

• 它几乎是懒惰的，在某种意义上，只有根节点的直接子节点将在流创建期间被检索（其他内部节点的子节点将在必要时被查询）。
• 它显示一个DFS遍历顺序。

现在考虑我有一个大的层次结构，<代码> GeHeaveNe（）/Cux>操作非常昂贵，我正在寻找任何<代码>节点< /C> >匹配一些谓词：

final Node tree = ...;
final Predicate<Node> p = ...;
tree.stream().filter(p).findAny();

1. 如何使我的stream（）实现“完全懒惰”？如果节点本身已经匹配谓词，我不希望查询节点的子节点。我正在寻找流的惰性版本。concat（），签名为（流




Answer 1

有点丑，但这应该适用于Java8：

public static <N> Stream<N> breadthFirst(N start, Function<? super N, Stream<N>> getChildren) {
    final LinkedList<Stream<N>> generations = new LinkedList<>();
    generations.add(Stream.of(start));
    final Iterator<Stream<N>> genIterator = createIterator(generations::remove, () -> !generations.isEmpty());
    return StreamSupport.stream(Spliterators.spliteratorUnknownSize(genIterator, Spliterator.ORDERED), false)
            .flatMap(Function.identity())
            .distinct() // avoids loops
            .peek(n -> generations.add(getChildren.apply(n)));
}

public static <E> Iterator<E> createIterator(Supplier<E> supplier, BooleanSupplier hasNext) {
    return new Iterator<E>() {
        @Override
        public boolean hasNext() {
            return hasNext.getAsBoolean();
        }
        @Override
        public E next() {
            return supplier.get();
        }
    };
}

这里的想法是，您需要保留对后续代的引用，因此我们创建一个列表以在处理时保存它们。使用Java9，您将能够用流替换自定义迭代器代码。生成（generations:：poll）。takeWhile（Objects:：nonNull）。

Answer 2

您可以使用拆分器库和低级流支持原语。然后，您可以在节点上提供一个迭代器，该迭代器只逐个使用节点。

return StreamSupport.stream( Spliterators.spliteratorUnknownSize( new Iterator<Node>()
{
    @Override
    public boolean hasNext()
    {
        // to implement
        return ...;
    }

    @Override
    public ContentVersion next()
    {
        // to implement
        return ...;
    }
}, 0 ), false );

Answer 3

不幸的是，我只能回答你的第一个问题。同样，flatMap是您在这里的朋友。它使我们能够创建一个稍微不同的concat方法，该方法接受stream-供应商s，而不仅仅是streams：

abstract class Node {
    abstract Collection<Node> getChildren();

    Stream<Node> lazyTraverse() {
        return Node.concat(() -> Stream.of(this),
                           () -> getChildren().stream().flatMap(Node::lazyTraverse));
    }

    static Stream<Node> concat(Supplier<Stream<Node>> a, Supplier<Stream<Node>> b) {
        return Stream.of(a, b).flatMap(Supplier::get);
    }
}

一个更好的解决方案是，如果您可以用某种返回惰性流的机制替换getChildren

关于你的第二个问题：

我不知道是否有BFS遍历算法以优雅的方式使用流API，但我倾向于说“不”，因为BFS通常需要额外的内存来存储所有已经访问但尚未遍历的节点。