Class TrieIterator

packages/effect/src/internal/trie.ts:78–134

}

class TrieIterator<in out V, out T> implements IterableIterator<T> {
  stack: Array<[Node<V>, string, boolean]> = []
  readonly trie: TrieImpl<V>
  readonly f: TraversalMap<string, V, T>
  readonly filter: TraversalFilter<string, V>

  constructor(
    trie: TrieImpl<V>,
    f: TraversalMap<string, V, T>,
    filter: TraversalFilter<string, V>
  ) {
    this.trie = trie
    this.f = f
    this.filter = filter
    const root = trie._root !== undefined ? trie._root : undefined
    if (root !== undefined) {
      this.stack.push([root, "", false])
    }
  }

  next(): IteratorResult<T> {
    while (this.stack.length > 0) {
      const [node, keyString, isAdded] = this.stack.pop()!

      if (isAdded) {
        const value = node.value
        if (value !== undefined) {
          const key = keyString + node.key
          if (this.filter(key, value.value)) {
            return { done: false, value: this.f(key, value.value) }
          }
        }
      } else {
        this.addToStack(node, keyString)
      }
    }

    return { done: true, value: undefined }
  }

  addToStack(node: Node<V>, keyString: string) {
    if (node.right !== undefined) {
      this.stack.push([node.right, keyString, false])
    }
    if (node.mid !== undefined) {
      this.stack.push([node.mid, keyString + node.key, false])
    }
    this.stack.push([node, keyString, true])
    if (node.left !== undefined) {
      this.stack.push([node.left, keyString, false])
    }
  }

  [Symbol.iterator](): IterableIterator<T> {
    return new TrieIterator(this.trie, this.f, this.filter)
  }
}