{
  "version": 3,
  "sources": ["../../src/diff/trie.ts"],
  "sourcesContent": ["/**\n * Trie data structure\n *\n * Read more: https://en.wikipedia.org/wiki/Trie\n */\n\n/**\n * Represents a node in the trie data structure.\n * Each node can store a value and has a map of child nodes.\n *\n * @template Value - The type of value that can be stored in the node\n */\nexport class TrieNode<Value> {\n  constructor(\n    public value: Value | null,\n    public children: Record<string, TrieNode<Value>>,\n  ) {}\n}\n\n/**\n * A trie (prefix tree) data structure implementation.\n * This class provides efficient storage and retrieval of values associated with string paths.\n *\n * @template Value - The type of value to store at each node\n *\n * @example\n * const trie = new Trie<number>()\n * trie.addPath(['a', 'b', 'c'], 1)\n * trie.addPath(['a', 'b', 'd'], 2)\n * trie.findMatch(['a', 'b'], (value) => console.log(value)) // Logs: 1, 2\n */\nexport class Trie<Value> {\n  private root: TrieNode<Value>\n  constructor() {\n    this.root = new TrieNode<Value>(null, {})\n  }\n\n  /**\n   * Adds a value to the trie at the specified path.\n   * Creates new nodes as needed to build the path.\n   *\n   * @param path - Array of strings representing the path to store the value\n   * @param value - The value to store at the end of the path\n   *\n   * @example\n   * const trie = new Trie<number>()\n   * trie.addPath(['users', 'john', 'age'], 30)\n   */\n  addPath(path: string[], value: Value) {\n    let current = this.root\n    for (const dir of path) {\n      if (current.children[dir]) {\n        current = current.children[dir]\n      } else {\n        current.children[dir] = new TrieNode<Value>(null, {})\n        current = current.children[dir]\n      }\n    }\n\n    current.value = value\n  }\n\n  /**\n   * Finds all matches along a given path in the trie.\n   * This method traverses both the exact path and all deeper paths,\n   * executing a callback for each matching value found.\n   *\n   * The search is performed in two phases:\n   * 1. Traverse the exact path, checking for matches at each node\n   * 2. Perform a depth-first search from the end of the path to find all deeper matches\n   *\n   * @param path - Array of strings representing the path to search\n   * @param callback - Function to execute for each matching value found\n   *\n   * @example\n   * const trie = new Trie<number>()\n   * trie.addPath(['a', 'b', 'c'], 1)\n   * trie.addPath(['a', 'b', 'd'], 2)\n   * trie.findMatch(['a', 'b'], (value) => console.log(value)) // Logs: 1, 2\n   */\n  findMatch(path: string[], callback: (value: Value) => void) {\n    let current = this.root\n\n    for (const dir of path) {\n      // Note: the last callback wont fire here because it will fire on the dfs\n      if (current.value !== null) {\n        callback(current.value)\n      }\n\n      const next = current.children[dir]\n      if (!next) {\n        return\n      }\n\n      current = next\n    }\n\n    const dfs = (current: TrieNode<Value> | undefined) => {\n      for (const child of Object.keys(current?.children ?? {})) {\n        if (current && Object.hasOwn(current.children, child)) {\n          dfs(current?.children[child])\n        }\n      }\n\n      if (current?.value) {\n        callback(current.value)\n      }\n    }\n\n    // Dfs for the rest of the path\n    dfs(current)\n  }\n}\n"],
  "mappings": "AAYO,MAAM,SAAgB;AAAA,EAC3B,YACS,OACA,UACP;AAFO;AACA;AAAA,EACN;AACL;AAcO,MAAM,KAAY;AAAA,EACf;AAAA,EACR,cAAc;AACZ,SAAK,OAAO,IAAI,SAAgB,MAAM,CAAC,CAAC;AAAA,EAC1C;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,QAAQ,MAAgB,OAAc;AACpC,QAAI,UAAU,KAAK;AACnB,eAAW,OAAO,MAAM;AACtB,UAAI,QAAQ,SAAS,GAAG,GAAG;AACzB,kBAAU,QAAQ,SAAS,GAAG;AAAA,MAChC,OAAO;AACL,gBAAQ,SAAS,GAAG,IAAI,IAAI,SAAgB,MAAM,CAAC,CAAC;AACpD,kBAAU,QAAQ,SAAS,GAAG;AAAA,MAChC;AAAA,IACF;AAEA,YAAQ,QAAQ;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAoBA,UAAU,MAAgB,UAAkC;AAC1D,QAAI,UAAU,KAAK;AAEnB,eAAW,OAAO,MAAM;AAEtB,UAAI,QAAQ,UAAU,MAAM;AAC1B,iBAAS,QAAQ,KAAK;AAAA,MACxB;AAEA,YAAM,OAAO,QAAQ,SAAS,GAAG;AACjC,UAAI,CAAC,MAAM;AACT;AAAA,MACF;AAEA,gBAAU;AAAA,IACZ;AAEA,UAAM,MAAM,CAACA,aAAyC;AACpD,iBAAW,SAAS,OAAO,KAAKA,UAAS,YAAY,CAAC,CAAC,GAAG;AACxD,YAAIA,YAAW,OAAO,OAAOA,SAAQ,UAAU,KAAK,GAAG;AACrD,cAAIA,UAAS,SAAS,KAAK,CAAC;AAAA,QAC9B;AAAA,MACF;AAEA,UAAIA,UAAS,OAAO;AAClB,iBAASA,SAAQ,KAAK;AAAA,MACxB;AAAA,IACF;AAGA,QAAI,OAAO;AAAA,EACb;AACF;",
  "names": ["current"]
}