Java Stream API的陷阱：为何不应在中间操作中修改数据源

// 初始尝试：在filter中修改队列
State next = Stream.generate(q::poll).takeWhile(Objects::nonNull)
    .filter(s -> {
        if (atGoal(s)) return true;
        s.expand().forEach(q::add); // 问题所在：在中间操作中修改数据源q
        return false;
    }).findFirst().orElse(null);

// 尝试简化，但问题依旧
State goal = Stream.generate(fringe::poll).takeWhile(Objects::nonNull)
    .filter(s -> atGoal(s) || s.expand().map(fringe::add).anyMatch(b -> true)) // 问题依旧：在中间操作中修改数据源fringe
    .findFirst().orElse(null);

import java.util.*;
import java.util.function.Predicate;

/**
 * 模拟图中的一个状态或节点
 */
class State {
    String id;
    List<State> children; // 该状态的邻居或子节点

    public State(String id) {
        this.id = id;
        this.children = new ArrayList<>();
    }

    public State(String id, List<State> children) {
        this.id = id;
        this.children = children;
    }

    /**
     * 模拟扩展当前状态，获取其所有邻居或子状态
     * 在实际应用中，这可能涉及复杂的逻辑来生成新的状态
     */
    public List<State> expand() {
        System.out.println("Expanding state: " + this.id);
        return this.children;
    }

    @Override
    public String toString() {
        return "State{" + "id='" + id + '\'' + '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        State state = (State) o;
        return Objects.equals(id, state.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class BreadthFirstSearch {

    /**
     * 模拟目标状态的判断条件
     */
    public static boolean atGoal(State s) {
        return "Goal".equals(s.id);
    }

    /**
     * 使用广度优先搜索算法查找目标状态
     * @param startState 搜索的起始状态
     * @param goalPredicate 判断是否达到目标状态的谓词
     * @return 如果找到目标状态则返回该状态，否则返回null
     */
    public static State findGoalBFS(State startState, Predicate<State> goalPredicate) {
        Queue<State> fringe = new LinkedList<>(); // 待访问队列
        Set<State> visited = new HashSet<>();     // 已访问集合，防止循环和重复访问

        fringe.add(startState);
        visited.add(startState);

        while (!fringe.isEmpty()) {
            State current = fringe.poll(); // 取出队列头部元素

            if (goalPredicate.test(current)) {
                return current; // 找到目标状态
            }

            // 扩展当前状态，并将其未访问过的邻居加入队列
            for (State neighbor : current.expand()) {
                if (!visited.contains(neighbor)) {
                    fringe.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        return null; // 未找到目标状态
    }

    public static void main(String[] args) {
        // 构造一个简单的图结构进行演示
        State s0 = new State("S0");
        State s1 = new State("S1");
        State s2 = new State("S2");
        State s3 = new State("S3");
        State s4 = new State("S4");
        State goalState = new State("Goal"); // 目标状态

        s0.children.add(s1);
        s0.children.add(s2);
        s1.children.add(s3);
        s2.children.add(s4);
        s3.children.add(goalState);
        s4.children.add(s0); // 引入一个循环，测试visited集合的作用

        System.out.println("Starting BFS from S0...");
        State found = findGoalBFS(s0, BreadthFirstSearch::atGoal);

        if (found != null) {
            System.out.println("Goal state found: " + found);
        } else {
            System.out.println("Goal state not found.");
        }
    }
}