1. 背景介绍

Reduce Functions 一文从实际业务出发，围绕 Stream#reduce() 展开，介绍了整套的代码设计与实现。Java8 引入的 Stream 不仅可以完成集合的 filter、map 等基本操作，将其融入到代码设计中还能够进一步抽象业务代码。

在 Java8 以前，方法（或函数）并不是一等公民，而在 Java8 引入 Lambda 表达式后，以另一种思路解决了这个问题。在实际开发过程中，使用 Lambda 表达式进行代码重构是我乐此不疲的事，它能够很好地实现千变万化的需求，将实际处理逻辑交给上游实现，而无需变更下游的接口定义。

本文将从一个简单的 DFS 出发，利用 Lambda 表达式对其进行重构，并完成回溯、剪枝等操作。

为保证阅读的流畅性，阅读前需要掌握的前置知识：

熟悉常见的函数式接口
对回溯有一定的理解，如果从未接触过回溯，可以参考回溯算法理论基础速通一波

2. 现状分析

在第一版需求中，需要基于 DFS 完成多个节点的遍历。假设节点有以下类型：

public enum NodeType {
    /**
     * 单个节点 A
     */
    SINGLE_A,

    /**
     * 单个节点 B
     */
    SINGLE_B,

    /**
     * 单个节点 C
     */
    SINGLE_C,

    /**
     * 容器
     */
    CONTAINER,

    /**
     * 虚拟容器
     */
    VIRTUAL_CONTAINER
}

SINGLE_A、SINGLE_B 和 SINGLE_C 代表不同的 SINGLE 节点，这些节点内部不会嵌套其他节点。

如果想要将多个 SINGLE 节点进行组合，则需要使用容器节点。

VIRTUAL_CONTAINER 节点内部只能包含若干个 SINGLE 节点，CONTAINER 节点内部只能包含多个 VIRTUAL_CONTAINER 节点。

CONTAINER 节点内部不会直接嵌套 SINGLE 节点，但借由嵌套的 VIRTUAL_CONTAINER 节点，就好像嵌套了 SINGLE 节点一样。

进行节点遍历时，忽略 VIRTUAL_CONTAINER 类型的节点！

基于以上节点类型，可以新建出具有以下依赖关系的多个类：

NodeInfo-Class-Diagram

3. 第一需求

给出一个节点列表，列表内存在各种的节点，要求实现遍历每个节点（不包括 VIRTUAL_CONTAINER 类型的节点，就像它的名称一样，它是虚拟的），但对每个节点的处理由调用方决定。

实现这个需求不难，无非两点：

挨个遍历节点，遇到容器节点时挨个遍历内部嵌套节点
要想对节点的处理由调用方决定，使用函数式接口 Consumer 即可

public class NodeFindSimpleSupport {

    protected final List<? extends NodeInfo> nodes;

    protected NodeFindSimpleSupport(List<? extends NodeInfo> nodes) {
        this.nodes = nodes;
    }

    public static NodeFindSimpleSupport from(List<? extends NodeInfo> nodes) {
        return new NodeFindSimpleSupport(nodes);
    }

    public void findNodes(Consumer<NodeInfo> consumer) {
        for (NodeInfo nodeInfo : CollectionUtils.emptyIfNull(this.nodes)) {
            findNode(nodeInfo, consumer);
        }
    }

    private void findNode(NodeInfo nodeInfo, Consumer<NodeInfo> consumer) {
        if (nodeInfo == null) {
            return;
        }
        // 处理每个节点，不包含虚拟容器节点
        if (!NodeType.VIRTUAL_CONTAINER.equals(nodeInfo.getNodeType())) {
            consumer.accept(nodeInfo);
        }
        // 处理容器节点
        if (nodeInfo instanceof BaseContainerNode container) {
            from(container.getNodes()).findNodes(consumer);
        }
    }
}

编写单元测试验证一下：

private List<NodeInfo> buildNodes() {
    SingleA a1 = new SingleA("A1");
    SingleA a2 = new SingleA("A2");
    SingleA a3 = new SingleA("A3");
    SingleA a4 = new SingleA("A4");

    SingleB b1 = new SingleB("B1");
    SingleB b2 = new SingleB("B2");

    SingleC c1 = new SingleC("C1");
    SingleC c2 = new SingleC("C2");

    VirtualContainerNode containerA = new VirtualContainerNode("ContainerA", List.of(a1, b1));
    VirtualContainerNode containerB = new VirtualContainerNode("ContainerB", List.of(a2, b2, c1));

    ContainerNode parentContainer = new ContainerNode("parentContainer", List.of(containerA, containerB));

    return List.of(a3, a4, parentContainer, c2);
}

@Test
public void testNodeFindSimpleSupport() {
    NodeFindSimpleSupport support = NodeFindSimpleSupport.from(buildNodes());
    AtomicInteger count = new AtomicInteger(0);
    // 统计节点数量
    support.findNodes(node -> count.incrementAndGet());
    assertThat(count).hasValue(9);
}

4. 第二需求

4.1 作用域内的节点

现在新增了一个需求：返回某一节点所在【作用域】内所有节点。

对于【作用域】，则有：

同一容器节点内的所有节点属于同一作用域，不同容器节点内的节点属于不同作用域
嵌套在容器节点内的另一个容器节点下的作用域与外层作用域不同
最初的节点列表下的节点属于同一个作用域

节点的作用域

以上图为例：

A3、A4、ContainerA、ContainerB 和 C2 属于同一作用域
A1 和 B1 属于同一作用域
A1 与 A2、A1 和 A3 并 不属于 同一作用域

4.2 需求剖析

新增需求的要点

新增的需求一共有两个要点：

先找到目标节点
然后返回目标节点所在作用域内的所有节点

找目标节点很简单，利用 DFS 遍历每个节点，如果当前节点 ID 等于目标节点 ID，那么就找到目标节点了。

为了能够更方便地获取目标作用域内的所有节点，在遍历节点时需要额外维护一个栈，栈内每个位置存放的元素类型是 List<? extends NodeInfo>。

每当遍历到一个新的作用域时，先将包含该作用域内所有节点的集合入栈。如果目标节点存在于该作用域内，那么栈顶元素即为所求；如果遍历完该作用域内的所有节点都没有找到目标节点，那么弹出栈顶元素，继续遍历剩余节点，直到找到目标节点或遍历完所有节点。

当找到目标节点时，应当立即终止遍历， 后续的遍历没有意义。

新增需求带来的变化

与原始需求相比，新增需求后的代码实现也会存在变化：

需要额外维护一个栈
存在遍历终止条件

如果了解回溯算法，不难发现就是要将原先的简单遍历改写成回溯，但是 不能影响原来的功能。

5. 实现重构

回溯相比于普通 DFS 遍历，就是增加了遍历终止条件。如果又要实现回溯，由不能影响原来的功能，那么可以将是否终止遍历交由上层调用方决定。

对于每个节点来说，原先使用函数式接口 Consumer 进行处理，重构成回溯后，为了能够判断是否需要终止遍历，需要选用函数式接口 Predicate 进行处理。如果需要遍历完所有节点，那么 Predicate 始终返回 false 即可。

容器节点共有两种：

CONTAINER 类型：依次遍历内部的虚拟容器节点即可，该类型节点嵌套的节点并不构成一个作用域
VIRTUAL_CONTAINER 类型：该类型节点嵌套的节点构成一个作用域，因此遍历时需要先将内部节点组成的集合入栈，然后再依次遍历内部的节点

重构后的代码如下：

public class NodeFindSupport extends NodeFindSimpleSupport {

    private NodeFindSupport(List<? extends NodeInfo> nodes) {
        super(nodes);
    }

    public static NodeFindSupport from(List<? extends NodeInfo> nodes) {
        return new NodeFindSupport(nodes);
    }

    /**
     * 获取每个节点并对它们进行处理
     *
     * @param consumer 对每个节点的处理方式
     */
    @Override
    public void findNodes(Consumer<NodeInfo> consumer) {
        findNodes(objectNode -> {
            consumer.accept(objectNode);
            // 始终返回 false，遍历完所有节点
            return false;
        });
    }

    private void findNodes(Predicate<NodeInfo> predicate) {
        findNodes(this.nodes, predicate, (supplier, nodes) -> supplier.getAsBoolean());
    }

    /**
     * 查找某个节点所在作用域中的所有节点
     *
     * @param nodeId 节点 ID，用于确定作用域
     * @return 目标作用域中的所有节点
     */
    @SuppressWarnings("unchecked")
    public List<NodeInfo> findScopeNodes(String nodeId) {
        // 遍历节点时，记录当前作用域中的节点。先进后出，使用栈。
        Deque<List<? extends NodeInfo>> stack = new ArrayDeque<>();
        // 最外层也是一个作用域
        stack.push(this.nodes);
        findNodes(this.nodes, node -> Objects.equals(nodeId, node.getNodeId()), (supplier, nodes) -> {
            // 到达一个新的作用域时，添加域中所有节点到栈中
            stack.push(nodes);
            // 如果在当前作用域中找到目标节点，立即返回
            if (supplier.getAsBoolean()) {
                return true;
            }
            // 否则弹出当前作用域中的节点
            stack.pop();
            // 返回 false，继续遍历节点
            return false;
        });
        // 如果找到目标节点 ID 所在的作用域，那么这个作用域中的所有节点就是栈顶元素
        return Optional.of(stack.pop()).map(i -> (List<NodeInfo>) i).orElse(Collections.emptyList());
    }

    /**
     * @see NodeFindSupport#findNode(NodeInfo, Predicate, BiPredicate)
     */
    private boolean findNodes(List<? extends NodeInfo> nodeList,
                              Predicate<NodeInfo> predicate,
                              BiPredicate<BooleanSupplier, List<NodeInfo>> biPredicate) {
        for (NodeInfo node : nodeList) {
            if (findNode(node, predicate, biPredicate)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 处理每个节点的底层实现
     *
     * @param node                          遍历的每个节点
     * @param eachNodePredicate             对每个节点的处理与判断，返回 true 时，结束遍历
     * @param virtualContainerNodePredicate 对虚拟容器节点的处理与判断。接收两个参数，第一个参数表示对容器内节点的处理结果，
     *                                      如果返回 true，结束对容器内节点的处理；第二个参数表示容器中的所有节点。整个
     *                                      谓词返回 true 时，结束遍历
     * @return 是否找到目标节点
     */
    private boolean findNode(NodeInfo node,
                             Predicate<NodeInfo> eachNodePredicate,
                             BiPredicate<BooleanSupplier, List<NodeInfo>> virtualContainerNodePredicate) {
        if (node == null) {
            return false;
        }
        // 忽略虚拟容器节点
        if (!NodeType.VIRTUAL_CONTAINER.equals(node.getNodeType()) && eachNodePredicate.test(node)) {
            return true;
        }
        switch (node) {
            case VirtualContainerNode virtual -> {
                List<NodeInfo> nodeList = virtual.getNodes();
                // 不仅要记录容器内的节点信息，如果容器中存在目标节点，还要立即返回
                if (virtualContainerNodePredicate.test(() -> findNodes(nodeList, eachNodePredicate, virtualContainerNodePredicate), nodeList)) {
                    return true;
                }
            }
            case ContainerNode container -> {
                if (findNodes(container.getNodes(), eachNodePredicate, virtualContainerNodePredicate)) {
                    return true;
                }
            }
            // 其他类型的节点，不做处理
            default -> {
            }
        }
        return false;
    }
}

编写单元测试验证一下：

@Test
public void testNodeFindSupport() {
    NodeFindSupport support = NodeFindSupport.from(buildNodes());
    AtomicInteger count = new AtomicInteger(0);
    // 统计所有节点数量
    support.findNodes(node -> count.incrementAndGet());
    assertThat(count).hasValue(9);

    // 统计某个范围的节点数量
    count.set(0);
    List<NodeInfo> nodes = support.findScopeNodes("B2");
    assertThat(nodes).hasSize(3)
            .extracting(NodeInfo::getNodeId)
            .containsExactly("A2", "B2", "C1");
}