iterator.md

下面是一段相对完整的 Iterator 相关源码（为了便于阅读，这里只摘取了关键部分），并进行详细解析：

// Iterator provides a mechanism to traverse nodes in key order within the tree.
type Iterator interface {
    // HasNext returns true if there are more nodes to visit during the iteration.
    HasNext() bool

    // Next returns the next node in the iteration and advances the iterator's position.
    Next() (Node, error)
}

//------------------------------------------------------------------------------
// iterator 及其配套数据结构
//------------------------------------------------------------------------------

// state 维护迭代过程的栈，每一层会存储一个 iteratorContext。
type state struct {
    items []*iteratorContext
}

// push 在栈顶压入新的 iteratorContext。
func (s *state) push(ctx *iteratorContext) {
    s.items = append(s.items, ctx)
}

// current 返回栈顶元素（即当前 iteratorContext）。
func (s *state) current() (*iteratorContext, bool) {
    if len(s.items) == 0 {
        return nil, false
    }
    return s.items[len(s.items)-1], true
}

// discard 弹出栈顶元素，表示这一层的遍历已完成。
func (s *state) discard() {
    if len(s.items) == 0 {
        return
    }
    s.items = s.items[:len(s.items)-1]
}

// iteratorContext 表示单个节点的遍历上下文。
// nextChildFn: 一个函数，用于获取“下一个子节点索引”。
// children:   保存该节点所有孩子的列表。
type iteratorContext struct {
    nextChildFn traverseFunc
    children    []*nodeRef
}

// newIteratorContext 根据节点创建一个 iteratorContext，设置好遍历函数(正序/逆序) 和孩子列表。
func newIteratorContext(nr *nodeRef, reverse bool) *iteratorContext {
    return &iteratorContext{
        nextChildFn: newTraverseFunc(nr, reverse),
        children:    toNode(nr).allChildren(),
    }
}

// next 从 iteratorContext 中获取下一个子节点。
// nextChildFn() 返回 (idx, hasMore)，idx 为下一个子节点索引，hasMore 表示是否还有更多索引可遍历。
// 如果对应子节点非空，则返回它，否则继续取下一个，直到没有更多。
func (ic *iteratorContext) next() (*nodeRef, bool) {
    for {
        idx, ok := ic.nextChildFn()
        if !ok {
            break
        }
        if child := ic.children[idx]; child != nil {
            return child, true
        }
    }
    return nil, false
}

//------------------------------------------------------------------------------
// iterator 结构体
//------------------------------------------------------------------------------

// iterator 负责按照深度优先的方式去遍历树（或者说所有节点），
// 它内部维护一个 state 栈来记录 "当前要遍历的节点列表"。
type iterator struct {
    version  int      // 迭代器生成时记录的树版本号，用来检测并发修改
    tree     *tree    // 所属的那颗树
    state    *state   // 当前迭代状态
    nextNode *nodeRef // 缓存下一个要返回的节点
    reverse  bool     // 是否逆序遍历
}

// 确保 iterator 实现了 Iterator 接口
var _ Iterator = (*iterator)(nil)

// newTreeIterator 用于从 tree 和遍历选项(opts) 创建一个迭代器。
// 如果 opts&TraverseAll==TraverseAll，就返回直接的 iterator；
// 否则包装成 bufferedIterator 做“叶子/节点”过滤。
func newTreeIterator(tr *tree, opts traverseOpts) Iterator {
    // 构造一个初始的 state，并把 root 节点压栈
    state := &state{}
    state.push(newIteratorContext(tr.root, opts.hasReverse()))

    it := &iterator{
        version:  tr.version,     // 记录当前树版本
        tree:     tr,
        nextNode: tr.root,        // 初始的 nextNode 先设成 root
        state:    state,
        reverse:  opts.hasReverse(),
    }

    // 如果遍历选项是 "TraverseAll" 就返回它自身
    if opts&TraverseAll == TraverseAll {
        return it
    }

    // 否则再包装一层 bufferedIterator，做“只要 leaf”/“只要 node”过滤
    bit := &bufferedIterator{
        opts: opts,
        it:   it,
    }
    // 预先获取下一个合法节点
    bit.peek()
    return bit
}

// HasNext 判断是否还有下一个节点可返回
func (it *iterator) HasNext() bool {
    return it.nextNode != nil
}

// Next 返回下一个节点，或者抛错
func (it *iterator) Next() (Node, error) {
    if !it.HasNext() {
        return nil, ErrNoMoreNodes
    }
    // 检测并发修改
    if it.hasConcurrentModification() {
        return nil, ErrConcurrentModification
    }
    current := it.nextNode
    it.next() // 移动到下一个
    return current, nil
}

// next 进行一次 “深度优先” 式的遍历推进。
func (it *iterator) next() {
    for {
        ctx, ok := it.state.current()
        if !ok {
            // 栈空了，没有更多节点
            it.nextNode = nil
            return
        }
        // 获取当前上下文 ctx 中的下一个子节点
        nextNode, hasMore := ctx.next()
        if hasMore {
            // 找到一个子节点，就设置为 nextNode 并压栈 => 下次再进一步
            it.nextNode = nextNode
            it.state.push(newIteratorContext(nextNode, it.reverse))
            return
        }
        // 当前上下文耗尽了，把这一层弹栈，回到上一层
        it.state.discard()
    }
}

// 检查树版本是否发生变更
func (it *iterator) hasConcurrentModification() bool {
    return it.version != it.tree.version
}

//------------------------------------------------------------------------------
// bufferedIterator 进一步对节点进行过滤
//------------------------------------------------------------------------------

// bufferedIterator 实际上对 iterator 做了一层包装：
//   - 如果只需要遍历叶子 (TraverseLeaf) 或只需要遍历内部节点 (TraverseNode)，
//     就在 next() 里过滤掉不符合条件的节点。
//   - 同时也要处理 ErrNoMoreNodes / ErrConcurrentModification。
type bufferedIterator struct {
    opts     traverseOpts
    it       Iterator  // 被包装的迭代器
    nextNode Node      // 缓存下一个符合过滤条件的节点
    nextErr  error     // 缓存错误
}

// 确保 bufferedIterator 也实现了 Iterator 接口
var _ Iterator = (*bufferedIterator)(nil)

func (bit *bufferedIterator) HasNext() bool {
    return bit.nextNode != nil
}

func (bit *bufferedIterator) Next() (Node, error) {
    current := bit.nextNode
    if !bit.HasNext() {
        return nil, bit.nextErr
    }
    // 先把当前要返回的节点记录，然后再找下一个符合条件的
    bit.peek()

    // 如果下一个出现并发修改，就立即返回错误
    if errors.Is(bit.nextErr, ErrConcurrentModification) {
        return nil, bit.nextErr
    }

    return current, nil
}

// peek 负责不断从底层 it.Next() 中拿到节点，如果符合过滤条件就存下并返回。
// 如果不符合，则继续拿下一个，直到拿到符合的或没有更多。
func (bit *bufferedIterator) peek() {
    for {
        bit.nextNode, bit.nextErr = bit.it.Next()
        if bit.nextErr != nil {
            // 出错（或迭代到底）就终止
            return
        }
        if bit.matchesFilter() {
            return
        }
    }
}

// matchesFilter 根据 bit.opts 里的 TraverseLeaf / TraverseNode 判断节点是否需要
func (bit *bufferedIterator) matchesFilter() bool {
    // 如果需要遍历叶子节点，且当前 nextNode 是 Leaf
    if (bit.opts & TraverseLeaf) == TraverseLeaf && bit.nextNode.Kind() == Leaf {
        return true
    }
    // 如果需要遍历内部节点，且当前 nextNode 不是 Leaf
    if (bit.opts & TraverseNode) == TraverseNode && bit.nextNode.Kind() != Leaf {
        return true
    }
    return false
}

下面分几个角度做更详细的说明：

---

1. 整体思路：深度优先 + 栈 stack

• iterator 使用了一个 state 对象，其本质是个栈。
• state 每个元素都是 *iteratorContext，里面保存了“当前节点的孩子列表”和一个 “取下一个孩子索引的函数 nextChildFn”。
• 当遍历一个节点时，我们就把它的孩子“上下文”压栈，下一次调用 Next() 时就会从栈顶元素开始继续取下一个孩子。
• 当这一层所有孩子都遍历完，iteratorContext 会被 discard() 出栈，然后回到上一层。

好处：这种实现结构相当于一个手动维护的深度优先搜索（DFS）。但不是用简单的递归，而是用迭代 + 栈的方式来控制遍历顺序，方便在 Next() 的调用间歇中保持遍历状态。

---

2. iteratorContext 结构：nextChildFn + children

type iteratorContext struct {
    nextChildFn traverseFunc
    children    []*nodeRef
}

1. children: 保存一个节点的所有子节点指针 []*nodeRef。
2. nextChildFn: 是一个函数类型 type traverseFunc func() (int, bool)，每次调用返回下一个要访问的下标 idx，以及是否还有更多子节点 bool。
   • 根据 TraverseReverse 设置不同的 traverseFunc，可以让遍历顺序是正序或倒序。

在 newIteratorContext(nr *nodeRef, reverse bool) 里会调用 newTraverseFunc(nr, reverse) 做不同的遍历策略，比如:

• 正序：子节点从左到右索引依次返回 (0,1,2,...)。
• 逆序：子节点从右到左索引依次返回 (N-1, N-2, ...)。

这样就统一了获取子节点下标的逻辑，写在一个函数里，避免写两套循环。

---

3. iterator 的工作流程

1. 初始

   • newTreeIterator(...) 会创建一个 iterator，并把 root 节点包装成一个 iteratorContext 压入 state.items 栈顶。
   • iterator.nextNode 初始设为 root。

2. HasNext()

   • 判断 iterator.nextNode != nil，如果不为 nil 就说明还有节点可返回。
   • 如果已经遍历完，会把 nextNode 设成 nil，则 HasNext() == false。

3. Next()

   • 检查 HasNext()，若没有则抛 ErrNoMoreNodes。
   • 检查 hasConcurrentModification()，若版本不一致，则抛 ErrConcurrentModification。
   • 记下当前的 it.nextNode 作为要返回的 Node，然后调用 it.next() 来推进到下一个。
   • 返回记录下的 Node。

4. it.next()

   • 循环：
     1. ctx, ok := it.state.current() 取栈顶的遍历上下文。如果空了说明已经完全遍历结束，nextNode = nil。
     2. ctx.next() 会去调用 ctx.nextChildFn()，得到 (idx, true/false)。
        • 如果 true，说明拿到一个子节点索引 idx，并且 child := ctx.children[idx] != nil。
          • 找到后，就 it.nextNode = child，并把 newIteratorContext(child, it.reverse) 压栈，返回。
        • 如果 false，说明当前节点全部孩子都取完了，就把这个 ctx 出栈 (state.discard())，回到上一个层级，继续循环。
   • 这个过程正是深度优先遍历的“往下走 / 回溯”逻辑。

---

4. bufferedIterator 做节点过滤

有时我们只想遍历叶子节点(TraverseLeaf)，或只想遍历内部节点(TraverseNode)。为了不破坏底层 DFS 的逻辑，作者选择再包装一层迭代器：

type bufferedIterator struct {
    opts     traverseOpts
    it       Iterator  // 底层的迭代器
    nextNode Node      // 缓存下一个符合筛选条件的节点
    nextErr  error
}

• HasNext(): 判断自身的 nextNode != nil。
• Next(): 返回当前 nextNode，然后再去 peek() 下一个。
• peek(): 连续调用 it.Next() 获取下一个节点，对照 opts 判断是否为叶子或内部节点，若符合就停止，不符合就继续要下一个。

这样就只在最外层做一次过滤，大大简化了逻辑。底层 DFS 不需要关心“是不是要遍历叶子/节点”；它把所有节点都遍历出来即可，最后交给 bufferedIterator 决定保留还是跳过。

---

5. 版本检测：version != it.tree.version

func (it *iterator) hasConcurrentModification() bool {
    return it.version != it.tree.version
}

• 在 Next() 时若检测到不一致，就报 ErrConcurrentModification。
• 这样可快速失败(fail-fast)，防止在迭代树时有人又插入/删除导致数据结构不一致。

---

6. 顺序 vs. 逆序：TraverseReverse

• 在 newTraverseFunc(n *nodeRef, reverse bool) 里，会根据 reverse 来返回不同的遍历顺序函数。
• 例如正序函数会从 0 -> 1 -> 2 -> ... -> nChildren-1，逆序函数会从 nChildren-1 -> ... -> 0。
• 在 node4 / node16 / node48 / node256 内部，也要分别考虑它们的实现方式（有时还有 “zeroChild” 特殊的索引）来正确生成遍历顺序。

---

总结

iterator 在这段代码里采用了一个**“手动维护深度优先栈”**的思路，每次 Next() 就弹出一个节点并向下压栈其子节点，直到整棵树都被遍历完毕。关键要点有：

1. iteratorContext：把“当前节点如何按顺序返回子节点索引”的逻辑封装成 nextChildFn + children。
2. 栈 state：深度优先遍历不再用递归，而是每次 Next() 手动推进。
3. bufferedIterator：外层包装做过滤，避免在核心 DFS 代码里插大量 if-else。
4. 版本检测：出现结构修改后，迭代器快速失败。

这使得整个迭代实现既可控又可扩展：可以轻松支持正序/逆序、叶子/内部节点过滤、前缀过滤等多种场景，且不会把核心遍历代码写得又长又复杂。通过栈和函数回调的方式，把遍历逻辑“拆”得比较干净，是值得借鉴的Go 数据结构迭代器设计思路。