#迭代器模式

// 数组遍历
String[] arr = {"a", "b", "c"};
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

// 链表遍历
LinkedList<String> list = new LinkedList<>();
for (String s : list) {
    System.out.println(s);
}

// 树遍历
class TreeNode {
    TreeNode left, right;
    Object value;
}

void printTree(TreeNode root) {
    if (root == null) return;
    printTree(root.left);
    System.out.println(root.value);
    printTree(root.right);
}

// 迭代器接口
interface Iterator<T> {
    boolean hasNext();
    T next();
    void remove(); // 可选
}

// 集合接口
interface Collection<T> {
    Iterator<T> createIterator();
}

// 具体集合：二叉树
class BinaryTree<T> {
    private TreeNode<T> root;

    public Iterator<T> createIterator() {
        return new InorderIterator<>(root);
    }

    // 中序遍历迭代器
    private static class InorderIterator<T> implements Iterator<T> {
        private final Stack<TreeNode<T>> stack = new Stack<>();
        private TreeNode<T> current;

        public InorderIterator(TreeNode<T> root) {
            current = root;
        }

        @Override
        public boolean hasNext() {
            return current != null || !stack.isEmpty();
        }

        @Override
        public T next() {
            // 先左子树
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // 处理节点
            current = stack.pop();
            T value = current.value;
            // 右子树
            current = current.right;
            return value;
        }
    }
}

List<String> list = Arrays.asList("a", "b", "c");
Iterator<String> it = list.iterator();

while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

// for-each 语法糖
for (String s : list) {
    System.out.println(s);
}

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
ListIterator<String> it = list.listIterator();

// 双向遍历
while (it.hasNext()) {
    System.out.println(it.next());
}
while (it.hasPrevious()) {
    System.out.println(it.previous());
}

// 修改元素
while (it.hasNext()) {
    String s = it.next();
    if ("b".equals(s)) {
        it.set("B"); // 修改当前元素
    }
}

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
Iterator<String> it = list.iterator();

while (it.hasNext()) {
    String s = it.next();
    if ("b".equals(s)) {
        list.remove(s); // ConcurrentModificationException!
    }
}

// ArrayList 中的 modCount 字段
protected transient int modCount = 0; // 修改计数器

// Iterator 中的 expectedModCount
private int expectedModCount = modCount;

// next() 方法检查
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

// 方式一：使用迭代器删除
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if ("b".equals(it.next())) {
        it.remove(); // 安全删除
    }
}

// 方式二：CopyOnWriteArrayList
List<String> safeList = new CopyOnWriteArrayList<>();
Iterator<String> it2 = safeList.iterator();
// 迭代器遍历的是快照，修改不会影响迭代器

// 前序遍历：根 → 左 → 右
class PreorderIterator<T> implements Iterator<T> {
    private final Stack<TreeNode<T>> stack = new Stack<>();

    public PreorderIterator(TreeNode<T> root) {
        if (root != null) {
            stack.push(root);
        }
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public T next() {
        TreeNode<T> node = stack.pop();
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
        return node.value;
    }
}

// 层序遍历：使用队列
class LevelOrderIterator<T> implements Iterator<T> {
    private final Queue<TreeNode<T>> queue = new LinkedList<>();

    public LevelOrderIterator(TreeNode<T> root) {
        if (root != null) queue.offer(root);
    }

    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }

    @Override
    public T next() {
        TreeNode<T> node = queue.poll();
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
        return node.value;
    }
}

class BSTRangeIterator<T> implements Iterator<T> {
    private final Stack<TreeNode<T>> stack = new Stack<>();
    private final T min;
    private final T max;
    private TreeNode<T> current;

    public BSTRangeIterator(TreeNode<T> root, T min, T max) {
        this.min = min;
        this.max = max;
        current = root;
    }

    @Override
    public boolean hasNext() {
        while (current != null && compare(current.value, min) < 0) {
            current = current.right;
        }
        if (current != null && compare(current.value, max) > 0) {
            return false;
        }
        return !stack.isEmpty() || current != null;
    }

    @Override
    public T next() {
        while (current != null) {
            if (compare(current.value, min) >= 0) {
                stack.push(current);
                current = current.left;
            } else {
                current = current.right;
            }
        }
        TreeNode<T> node = stack.pop();
        current = node.right;
        return node.value;
    }
}

// ❌ 错误：在迭代过程中修改集合
for (String s : list) {
    if (s.startsWith("a")) {
        list.remove(s); // 抛异常
    }
}

// ✅ 正确：用迭代器删除
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("a")) {
        it.remove();
    }
}

// ✅ 或者：用 removeIf
list.removeIf(s -> s.startsWith("a"));

// ❌ 错误：迭代器持有对集合的引用，导致内存泄漏
class LeakExample {
    private List<Iterator> allIterators = new ArrayList<>();

    void createIterator(Collection c) {
        Iterator it = c.iterator();
        allIterators.add(it); // 迭代器不会被 GC
    }
}