{"version":3,"file":"trie.cjs","sources":["../../../src/core/trie.ts"],"sourcesContent":["/**\n * Trie (Prefix Tree) for fast prefix matching\n * Provides O(k) lookup where k is the query length, instead of O(n) where n is the number of terms\n */\n\nexport interface TrieNode {\n  children: Map<string, TrieNode>;\n  isEndOfWord: boolean;\n  docIds: Set<number>;\n  term?: string; // Store the full term at leaf nodes\n}\n\nexport class Trie {\n  private root: TrieNode;\n  private size: number;\n\n  constructor() {\n    this.root = this.createNode();\n    this.size = 0;\n  }\n\n  private createNode(): TrieNode {\n    return {\n      children: new Map(),\n      isEndOfWord: false,\n      docIds: new Set(),\n    };\n  }\n\n  /**\n   * Insert a term with associated document IDs\n   */\n  insert(term: string, docIds: number[]): void {\n    if (!term) return;\n\n    let node = this.root;\n\n    for (const char of term) {\n      if (!node.children.has(char)) {\n        node.children.set(char, this.createNode());\n      }\n      node = node.children.get(char)!;\n    }\n\n    node.isEndOfWord = true;\n    node.term = term;\n    docIds.forEach(id => node.docIds.add(id));\n    this.size++;\n  }\n\n  /**\n   * Find all terms that start with the given prefix\n   * Returns array of [term, docIds[]] tuples\n   */\n  findWithPrefix(prefix: string): Array<[string, number[]]> {\n    if (!prefix) return [];\n\n    // Navigate to the prefix node\n    let node = this.root;\n    for (const char of prefix) {\n      if (!node.children.has(char)) {\n        return []; // Prefix not found\n      }\n      node = node.children.get(char)!;\n    }\n\n    // Collect all terms from this node downwards\n    const results: Array<[string, number[]]> = [];\n    this.collectTerms(node, results);\n    return results;\n  }\n\n  /**\n   * Check if exact term exists\n   */\n  has(term: string): boolean {\n    let node = this.root;\n    for (const char of term) {\n      if (!node.children.has(char)) {\n        return false;\n      }\n      node = node.children.get(char)!;\n    }\n    return node.isEndOfWord;\n  }\n\n  /**\n   * Get document IDs for exact term\n   */\n  get(term: string): number[] | null {\n    let node = this.root;\n    for (const char of term) {\n      if (!node.children.has(char)) {\n        return null;\n      }\n      node = node.children.get(char)!;\n    }\n    return node.isEndOfWord ? Array.from(node.docIds) : null;\n  }\n\n  /**\n   * Recursively collect all terms from a node\n   */\n  private collectTerms(node: TrieNode, results: Array<[string, number[]]>): void {\n    if (node.isEndOfWord && node.term) {\n      results.push([node.term, Array.from(node.docIds)]);\n    }\n\n    for (const child of node.children.values()) {\n      this.collectTerms(child, results);\n    }\n  }\n\n  /**\n   * Get the number of terms in the trie\n   */\n  getSize(): number {\n    return this.size;\n  }\n\n  /**\n   * Clear the trie\n   */\n  clear(): void {\n    this.root = this.createNode();\n    this.size = 0;\n  }\n\n  /**\n   * Serialize trie to JSON-compatible format\n   */\n  toJSON(): any {\n    return {\n      root: this.serializeNode(this.root),\n      size: this.size,\n    };\n  }\n\n  /**\n   * Deserialize trie from JSON\n   */\n  static fromJSON(data: any): Trie {\n    const trie = new Trie();\n    trie.root = Trie.deserializeNode(data.root);\n    trie.size = data.size;\n    return trie;\n  }\n\n  private serializeNode(node: TrieNode): any {\n    return {\n      children: Array.from(node.children.entries()).map(([char, child]) => [\n        char,\n        this.serializeNode(child),\n      ]),\n      isEndOfWord: node.isEndOfWord,\n      docIds: Array.from(node.docIds),\n      term: node.term,\n    };\n  }\n\n  private static deserializeNode(data: any): TrieNode {\n    const node: TrieNode = {\n      children: new Map(),\n      isEndOfWord: data.isEndOfWord,\n      docIds: new Set(data.docIds),\n      term: data.term,\n    };\n\n    for (const [char, childData] of data.children) {\n      node.children.set(char, Trie.deserializeNode(childData));\n    }\n\n    return node;\n  }\n}\n"],"names":[],"mappings":";;AAYO,MAAM,KAAK;AAAA,EACR;AAAA,EACA;AAAA,EAER,cAAc;AACZ,SAAK,OAAO,KAAK,WAAA;AACjB,SAAK,OAAO;AAAA,EACd;AAAA,EAEQ,aAAuB;AAC7B,WAAO;AAAA,MACL,8BAAc,IAAA;AAAA,MACd,aAAa;AAAA,MACb,4BAAY,IAAA;AAAA,IAAI;AAAA,EAEpB;AAAA;AAAA;AAAA;AAAA,EAKA,OAAO,MAAc,QAAwB;AAC3C,QAAI,CAAC,KAAM;AAEX,QAAI,OAAO,KAAK;AAEhB,eAAW,QAAQ,MAAM;AACvB,UAAI,CAAC,KAAK,SAAS,IAAI,IAAI,GAAG;AAC5B,aAAK,SAAS,IAAI,MAAM,KAAK,YAAY;AAAA,MAC3C;AACA,aAAO,KAAK,SAAS,IAAI,IAAI;AAAA,IAC/B;AAEA,SAAK,cAAc;AACnB,SAAK,OAAO;AACZ,WAAO,QAAQ,CAAA,OAAM,KAAK,OAAO,IAAI,EAAE,CAAC;AACxC,SAAK;AAAA,EACP;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,eAAe,QAA2C;AACxD,QAAI,CAAC,OAAQ,QAAO,CAAA;AAGpB,QAAI,OAAO,KAAK;AAChB,eAAW,QAAQ,QAAQ;AACzB,UAAI,CAAC,KAAK,SAAS,IAAI,IAAI,GAAG;AAC5B,eAAO,CAAA;AAAA,MACT;AACA,aAAO,KAAK,SAAS,IAAI,IAAI;AAAA,IAC/B;AAGA,UAAM,UAAqC,CAAA;AAC3C,SAAK,aAAa,MAAM,OAAO;AAC/B,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA,EAKA,IAAI,MAAuB;AACzB,QAAI,OAAO,KAAK;AAChB,eAAW,QAAQ,MAAM;AACvB,UAAI,CAAC,KAAK,SAAS,IAAI,IAAI,GAAG;AAC5B,eAAO;AAAA,MACT;AACA,aAAO,KAAK,SAAS,IAAI,IAAI;AAAA,IAC/B;AACA,WAAO,KAAK;AAAA,EACd;AAAA;AAAA;AAAA;AAAA,EAKA,IAAI,MAA+B;AACjC,QAAI,OAAO,KAAK;AAChB,eAAW,QAAQ,MAAM;AACvB,UAAI,CAAC,KAAK,SAAS,IAAI,IAAI,GAAG;AAC5B,eAAO;AAAA,MACT;AACA,aAAO,KAAK,SAAS,IAAI,IAAI;AAAA,IAC/B;AACA,WAAO,KAAK,cAAc,MAAM,KAAK,KAAK,MAAM,IAAI;AAAA,EACtD;AAAA;AAAA;AAAA;AAAA,EAKQ,aAAa,MAAgB,SAA0C;AAC7E,QAAI,KAAK,eAAe,KAAK,MAAM;AACjC,cAAQ,KAAK,CAAC,KAAK,MAAM,MAAM,KAAK,KAAK,MAAM,CAAC,CAAC;AAAA,IACnD;AAEA,eAAW,SAAS,KAAK,SAAS,OAAA,GAAU;AAC1C,WAAK,aAAa,OAAO,OAAO;AAAA,IAClC;AAAA,EACF;AAAA;AAAA;AAAA;AAAA,EAKA,UAAkB;AAChB,WAAO,KAAK;AAAA,EACd;AAAA;AAAA;AAAA;AAAA,EAKA,QAAc;AACZ,SAAK,OAAO,KAAK,WAAA;AACjB,SAAK,OAAO;AAAA,EACd;AAAA;AAAA;AAAA;AAAA,EAKA,SAAc;AACZ,WAAO;AAAA,MACL,MAAM,KAAK,cAAc,KAAK,IAAI;AAAA,MAClC,MAAM,KAAK;AAAA,IAAA;AAAA,EAEf;AAAA;AAAA;AAAA;AAAA,EAKA,OAAO,SAAS,MAAiB;AAC/B,UAAM,OAAO,IAAI,KAAA;AACjB,SAAK,OAAO,KAAK,gBAAgB,KAAK,IAAI;AAC1C,SAAK,OAAO,KAAK;AACjB,WAAO;AAAA,EACT;AAAA,EAEQ,cAAc,MAAqB;AACzC,WAAO;AAAA,MACL,UAAU,MAAM,KAAK,KAAK,SAAS,SAAS,EAAE,IAAI,CAAC,CAAC,MAAM,KAAK,MAAM;AAAA,QACnE;AAAA,QACA,KAAK,cAAc,KAAK;AAAA,MAAA,CACzB;AAAA,MACD,aAAa,KAAK;AAAA,MAClB,QAAQ,MAAM,KAAK,KAAK,MAAM;AAAA,MAC9B,MAAM,KAAK;AAAA,IAAA;AAAA,EAEf;AAAA,EAEA,OAAe,gBAAgB,MAAqB;AAClD,UAAM,OAAiB;AAAA,MACrB,8BAAc,IAAA;AAAA,MACd,aAAa,KAAK;AAAA,MAClB,QAAQ,IAAI,IAAI,KAAK,MAAM;AAAA,MAC3B,MAAM,KAAK;AAAA,IAAA;AAGb,eAAW,CAAC,MAAM,SAAS,KAAK,KAAK,UAAU;AAC7C,WAAK,SAAS,IAAI,MAAM,KAAK,gBAAgB,SAAS,CAAC;AAAA,IACzD;AAEA,WAAO;AAAA,EACT;AACF;;"}