{"version":3,"file":"btree-index.cjs","sources":["../../../src/indexes/btree-index.ts"],"sourcesContent":["import { compareKeys } from '@tanstack/db-ivm'\nimport { compareKeysReversed } from '../utils/array-utils.js'\nimport { BTree } from '../utils/btree.js'\nimport { areSameValueZeroEqual, normalizeValue } from '../utils/comparison.js'\nimport { codedMessage, devBuild } from '../error-message.js'\nimport {\n  BaseIndex,\n  builtInIndexResolverNames,\n  warnRemovalFailure,\n} from './base-index.js'\nimport type { IndexComparisonOptions, IndexOperation } from './base-index.js'\n\nexport type BTreeIndexOptions = IndexComparisonOptions\nexport interface RangeQueryOptions {\n  from?: any\n  to?: any\n  fromInclusive?: boolean\n  toInclusive?: boolean\n}\n\ntype SortKey = { value: any }\ntype Group<TKey> = SortKey & {\n  keys: Map<TKey, any>\n  buckets?: Map<unknown, Set<TKey>>\n  representativeKey: TKey\n  nextRepresentative?: IterableIterator<[TKey, any]>\n}\nexport class BTreeIndex<\n  TKey extends string | number = string | number,\n> extends BaseIndex<TKey> {\n  private orderedEntries = new BTree<SortKey, Group<TKey>>((a, b) =>\n    this.compareFn(a.value, b.value),\n  )\n  private valueMap = new Map<any, Group<TKey>>()\n  private indexedKeys = new Set<TKey>()\n\n  add(key: TKey, item: any): void {\n    const value = this.evaluateAddedValue(key, item)\n    const exact = normalizeValue(value)\n    this.addToBucket(key, value, exact)\n    this.addRangeValue(value)\n    this.indexedKeys.add(key)\n  }\n\n  private addToBucket(key: TKey, value: any, exact: unknown): void {\n    const group = this.valueMap.get(exact)\n    if (group) {\n      group.keys.set(key, value)\n      group.buckets?.get(exact)!.add(key)\n      return\n    }\n    const ordered = this.orderedEntries.get({ value })\n    if (ordered) {\n      ordered.buckets ??= new Map([\n        [normalizeValue(ordered.value), new Set(ordered.keys.keys())],\n      ])\n      ordered.buckets.set(exact, new Set([key]))\n      ordered.keys.set(key, value)\n      this.valueMap.set(exact, ordered)\n    } else {\n      const created = {\n        value,\n        keys: new Map([[key, value]]),\n        representativeKey: key,\n      }\n      // The tree compares before the exact lookup map changes.\n      this.orderedEntries.set(created, created)\n      this.valueMap.set(exact, created)\n    }\n  }\n\n  remove(key: TKey, item: any): void {\n    let value: any\n    try {\n      value = this.evaluateIndexExpression(item)\n    } catch (error) {\n      warnRemovalFailure(key, error)\n      return\n    }\n    const exact = normalizeValue(value)\n    this.removeFromBucket(key, exact)\n    this.removeRangeValue(value)\n    this.indexedKeys.delete(key)\n  }\n\n  private removeFromBucket(key: TKey, exact: unknown): void {\n    const group = this.valueMap.get(exact)\n    if (!group?.keys.has(key)) return\n    const bucket = group.buckets?.get(exact)\n    if (group.buckets && !bucket?.has(key)) return\n    if (group.keys.size === 1) {\n      this.orderedEntries.delete(group)\n    }\n    bucket?.delete(key)\n    group.keys.delete(key)\n    if (bucket?.size === 0 || group.keys.size === 0) {\n      this.valueMap.delete(exact)\n      group.buckets?.delete(exact)\n    }\n    if (group.keys.size && group.representativeKey === key) {\n      // Advancing one iterator skips each removed Map slot at most once.\n      const [nextKey, nextValue] = (group.nextRepresentative ??=\n        group.keys.entries()).next().value as [TKey, any]\n      group.representativeKey = nextKey\n      group.value = nextValue\n    }\n  }\n\n  update(key: TKey, oldItem: any, newItem: any): void {\n    let oldValue: any\n    let newValue: any\n    try {\n      oldValue = this.evaluateIndexExpression(oldItem)\n      newValue = this.evaluateIndexExpression(newItem)\n    } catch {\n      this.remove(key, oldItem)\n      this.add(key, newItem)\n      return\n    }\n    const oldExact = normalizeValue(oldValue)\n    const newExact = normalizeValue(newValue)\n    const group = this.valueMap.get(newExact)\n    const containsKey = group?.buckets\n      ? group.buckets.get(newExact)?.has(key)\n      : group?.keys.has(key)\n    if (areSameValueZeroEqual(oldExact, newExact) && containsKey) {\n      group!.keys.set(key, newValue)\n      if (group!.representativeKey === key) group!.value = newValue\n      this.removeRangeValue(oldValue)\n      this.addRangeValue(newValue)\n      return\n    }\n    this.removeFromBucket(key, oldExact)\n    this.removeRangeValue(oldValue)\n    this.addToBucket(key, newValue, newExact)\n    this.addRangeValue(newValue)\n    this.indexedKeys.add(key)\n  }\n\n  build(entries: Iterable<[TKey, any]>): void {\n    this.clear()\n    for (const [key, item] of entries) this.add(key, item)\n  }\n\n  clear(): void {\n    this.orderedEntries.clear()\n    this.valueMap.clear()\n    this.indexedKeys.clear()\n    this.clearRangeValues()\n  }\n\n  lookup(operation: IndexOperation, value: any): Set<TKey> {\n    const result = this.lookupSupportedOperation(operation, value)\n    if (result !== undefined) return result\n    throw new Error(\n      devBuild() && process.env.NODE_ENV !== `production`\n        ? `Operation ${operation} not supported by BTreeIndex`\n        : codedMessage(101, { operation }),\n    )\n  }\n\n  get keyCount(): number {\n    return this.indexedKeys.size\n  }\n\n  equalityLookup(value: any): Set<TKey> {\n    return new Set(this.exactBucketKeys(value))\n  }\n\n  protected exactBucketKeys(value: any): Iterable<TKey> | undefined {\n    const exact = normalizeValue(value)\n    const group = this.valueMap.get(exact)\n    return group?.buckets ? group.buckets.get(exact) : group?.keys.keys()\n  }\n\n  rangeQuery(options: RangeQueryOptions = {}): Set<TKey> {\n    const result = new Set<TKey>()\n    if (this.orderedEntries.size === 0) return result\n    const { from, to, fromInclusive = true, toInclusive = true } = options\n    const low =\n      'from' in options ? { value: from } : this.orderedEntries.minKey()!\n    const high = 'to' in options ? { value: to } : this.orderedEntries.maxKey()!\n    this.orderedEntries.forRange(\n      low,\n      high,\n      !('to' in options) || toInclusive,\n      (sortKey, group) => {\n        if (\n          'from' in options &&\n          !fromInclusive &&\n          this.compareFn(sortKey.value, from) === 0\n        )\n          return\n        for (const key of group.keys.keys()) result.add(key)\n      },\n    )\n    return result\n  }\n\n  private takeInternal(\n    n: number,\n    from: SortKey | undefined,\n    filterFn: ((key: TKey) => boolean) | undefined,\n    reversed: boolean,\n  ): Array<TKey> {\n    const result: Array<TKey> = []\n    let pair = reversed\n      ? this.orderedEntries.nextLowerPair(from)\n      : this.orderedEntries.nextHigherPair(from)\n    while (pair && result.length < n) {\n      for (const key of [...pair[1].keys.keys()].sort(\n        reversed ? compareKeysReversed : compareKeys,\n      )) {\n        if (filterFn?.(key) ?? true) result.push(key)\n        if (result.length >= n) break\n      }\n      if (result.length >= n) break\n      pair = reversed\n        ? this.orderedEntries.nextLowerPair(pair[0])\n        : this.orderedEntries.nextHigherPair(pair[0])\n    }\n    return result\n  }\n\n  take(n: number, from: any, filterFn?: (key: TKey) => boolean): Array<TKey> {\n    return this.takeInternal(n, { value: from }, filterFn, false)\n  }\n\n  takeFromStart(n: number, filterFn?: (key: TKey) => boolean): Array<TKey> {\n    return this.takeInternal(n, undefined, filterFn, false)\n  }\n\n  takeReversed(\n    n: number,\n    from: any,\n    filterFn?: (key: TKey) => boolean,\n  ): Array<TKey> {\n    return this.takeInternal(n, { value: from }, filterFn, true)\n  }\n\n  takeReversedFromEnd(\n    n: number,\n    filterFn?: (key: TKey) => boolean,\n  ): Array<TKey> {\n    return this.takeInternal(n, undefined, filterFn, true)\n  }\n}\n\nbuiltInIndexResolverNames.set(BTreeIndex, 'BTreeIndex')\n"],"names":["BaseIndex","orderedEntries","BTree","valueMap","indexedKeys","normalizeValue","addToBucket","warnRemovalFailure","removeFromBucket","areSameValueZeroEqual","devBuild","codedMessage","takeInternal","compareKeysReversed","compareKeys","builtInIndexResolverNames"],"mappings":";;;;;;;;AA2BO,MAAM,mBAEHA,UAAAA,UAAgB;AAAA,EAFnB,cAAA;AAAA,UAAA,GAAA,SAAA;AAGL,SAAQC,KAAiB,IAAIC,MAAAA;AAAAA,MAA4B,CAAC,GAAG,MAC3D,KAAK,UAAU,EAAE,OAAO,EAAE,KAAK;AAAA,IAAA;AAEjC,SAAQC,yBAAe,IAAA;AACvB,SAAQC,yBAAkB,IAAA;AAAA,EAAU;AAAA,EAEpC,IAAI,KAAW,MAAiB;AAC9B,UAAM,QAAQ,KAAK,mBAAmB,KAAK,IAAI;AAC/C,UAAM,QAAQC,WAAAA,eAAe,KAAK;AAClC,SAAKC,GAAY,KAAK,OAAO,KAAK;AAClC,SAAK,cAAc,KAAK;AACxB,SAAKF,GAAY,IAAI,GAAG;AAAA,EAC1B;AAAA,EAEQE,GAAY,KAAW,OAAY,OAAsB;AAC/D,UAAM,QAAQ,KAAKH,GAAS,IAAI,KAAK;AACrC,QAAI,OAAO;AACT,YAAM,KAAK,IAAI,KAAK,KAAK;AACzB,YAAM,SAAS,IAAI,KAAK,EAAG,IAAI,GAAG;AAClC;AAAA,IACF;AACA,UAAM,UAAU,KAAKF,GAAe,IAAI,EAAE,OAAO;AACjD,QAAI,SAAS;AACX,cAAQ,gCAAgB,IAAI;AAAA,QAC1B,CAACI,WAAAA,eAAe,QAAQ,KAAK,GAAG,IAAI,IAAI,QAAQ,KAAK,MAAM,CAAC;AAAA,MAAA,CAC7D;AACD,cAAQ,QAAQ,IAAI,OAAO,oBAAI,IAAI,CAAC,GAAG,CAAC,CAAC;AACzC,cAAQ,KAAK,IAAI,KAAK,KAAK;AAC3B,WAAKF,GAAS,IAAI,OAAO,OAAO;AAAA,IAClC,OAAO;AACL,YAAM,UAAU;AAAA,QACd;AAAA,QACA,0BAAU,IAAI,CAAC,CAAC,KAAK,KAAK,CAAC,CAAC;AAAA,QAC5B,mBAAmB;AAAA,MAAA;AAGrB,WAAKF,GAAe,IAAI,SAAS,OAAO;AACxC,WAAKE,GAAS,IAAI,OAAO,OAAO;AAAA,IAClC;AAAA,EACF;AAAA,EAEA,OAAO,KAAW,MAAiB;AACjC,QAAI;AACJ,QAAI;AACF,cAAQ,KAAK,wBAAwB,IAAI;AAAA,IAC3C,SAAS,OAAO;AACdI,gBAAAA,mBAAmB,KAAK,KAAK;AAC7B;AAAA,IACF;AACA,UAAM,QAAQF,WAAAA,eAAe,KAAK;AAClC,SAAKG,GAAiB,KAAK,KAAK;AAChC,SAAK,iBAAiB,KAAK;AAC3B,SAAKJ,GAAY,OAAO,GAAG;AAAA,EAC7B;AAAA,EAEQI,GAAiB,KAAW,OAAsB;AACxD,UAAM,QAAQ,KAAKL,GAAS,IAAI,KAAK;AACrC,QAAI,CAAC,OAAO,KAAK,IAAI,GAAG,EAAG;AAC3B,UAAM,SAAS,MAAM,SAAS,IAAI,KAAK;AACvC,QAAI,MAAM,WAAW,CAAC,QAAQ,IAAI,GAAG,EAAG;AACxC,QAAI,MAAM,KAAK,SAAS,GAAG;AACzB,WAAKF,GAAe,OAAO,KAAK;AAAA,IAClC;AACA,YAAQ,OAAO,GAAG;AAClB,UAAM,KAAK,OAAO,GAAG;AACrB,QAAI,QAAQ,SAAS,KAAK,MAAM,KAAK,SAAS,GAAG;AAC/C,WAAKE,GAAS,OAAO,KAAK;AAC1B,YAAM,SAAS,OAAO,KAAK;AAAA,IAC7B;AACA,QAAI,MAAM,KAAK,QAAQ,MAAM,sBAAsB,KAAK;AAEtD,YAAM,CAAC,SAAS,SAAS,KAAK,MAAM,uBAClC,MAAM,KAAK,WAAW,KAAA,EAAO;AAC/B,YAAM,oBAAoB;AAC1B,YAAM,QAAQ;AAAA,IAChB;AAAA,EACF;AAAA,EAEA,OAAO,KAAW,SAAc,SAAoB;AAClD,QAAI;AACJ,QAAI;AACJ,QAAI;AACF,iBAAW,KAAK,wBAAwB,OAAO;AAC/C,iBAAW,KAAK,wBAAwB,OAAO;AAAA,IACjD,QAAQ;AACN,WAAK,OAAO,KAAK,OAAO;AACxB,WAAK,IAAI,KAAK,OAAO;AACrB;AAAA,IACF;AACA,UAAM,WAAWE,WAAAA,eAAe,QAAQ;AACxC,UAAM,WAAWA,WAAAA,eAAe,QAAQ;AACxC,UAAM,QAAQ,KAAKF,GAAS,IAAI,QAAQ;AACxC,UAAM,cAAc,OAAO,UACvB,MAAM,QAAQ,IAAI,QAAQ,GAAG,IAAI,GAAG,IACpC,OAAO,KAAK,IAAI,GAAG;AACvB,QAAIM,iCAAsB,UAAU,QAAQ,KAAK,aAAa;AAC5D,YAAO,KAAK,IAAI,KAAK,QAAQ;AAC7B,UAAI,MAAO,sBAAsB,IAAK,OAAO,QAAQ;AACrD,WAAK,iBAAiB,QAAQ;AAC9B,WAAK,cAAc,QAAQ;AAC3B;AAAA,IACF;AACA,SAAKD,GAAiB,KAAK,QAAQ;AACnC,SAAK,iBAAiB,QAAQ;AAC9B,SAAKF,GAAY,KAAK,UAAU,QAAQ;AACxC,SAAK,cAAc,QAAQ;AAC3B,SAAKF,GAAY,IAAI,GAAG;AAAA,EAC1B;AAAA,EAEA,MAAM,SAAsC;AAC1C,SAAK,MAAA;AACL,eAAW,CAAC,KAAK,IAAI,KAAK,QAAS,MAAK,IAAI,KAAK,IAAI;AAAA,EACvD;AAAA,EAEA,QAAc;AACZ,SAAKH,GAAe,MAAA;AACpB,SAAKE,GAAS,MAAA;AACd,SAAKC,GAAY,MAAA;AACjB,SAAK,iBAAA;AAAA,EACP;AAAA,EAEA,OAAO,WAA2B,OAAuB;AACvD,UAAM,SAAS,KAAK,yBAAyB,WAAW,KAAK;AAC7D,QAAI,WAAW,OAAW,QAAO;AACjC,UAAM,IAAI;AAAA,MACRM,aAAAA,SAAA,KAAc,QAAQ,IAAI,aAAa,eACnC,aAAa,SAAS,iCACtBC,aAAAA,aAAa,KAAK,EAAE,WAAW;AAAA,IAAA;AAAA,EAEvC;AAAA,EAEA,IAAI,WAAmB;AACrB,WAAO,KAAKP,GAAY;AAAA,EAC1B;AAAA,EAEA,eAAe,OAAuB;AACpC,WAAO,IAAI,IAAI,KAAK,gBAAgB,KAAK,CAAC;AAAA,EAC5C;AAAA,EAEU,gBAAgB,OAAwC;AAChE,UAAM,QAAQC,WAAAA,eAAe,KAAK;AAClC,UAAM,QAAQ,KAAKF,GAAS,IAAI,KAAK;AACrC,WAAO,OAAO,UAAU,MAAM,QAAQ,IAAI,KAAK,IAAI,OAAO,KAAK,KAAA;AAAA,EACjE;AAAA,EAEA,WAAW,UAA6B,IAAe;AACrD,UAAM,6BAAa,IAAA;AACnB,QAAI,KAAKF,GAAe,SAAS,EAAG,QAAO;AAC3C,UAAM,EAAE,MAAM,IAAI,gBAAgB,MAAM,cAAc,SAAS;AAC/D,UAAM,MACJ,UAAU,UAAU,EAAE,OAAO,SAAS,KAAKA,GAAe,OAAA;AAC5D,UAAM,OAAO,QAAQ,UAAU,EAAE,OAAO,OAAO,KAAKA,GAAe,OAAA;AACnE,SAAKA,GAAe;AAAA,MAClB;AAAA,MACA;AAAA,MACA,EAAE,QAAQ,YAAY;AAAA,MACtB,CAAC,SAAS,UAAU;AAClB,YACE,UAAU,WACV,CAAC,iBACD,KAAK,UAAU,QAAQ,OAAO,IAAI,MAAM;AAExC;AACF,mBAAW,OAAO,MAAM,KAAK,OAAQ,QAAO,IAAI,GAAG;AAAA,MACrD;AAAA,IAAA;AAEF,WAAO;AAAA,EACT;AAAA,EAEQW,GACN,GACA,MACA,UACA,UACa;AACb,UAAM,SAAsB,CAAA;AAC5B,QAAI,OAAO,WACP,KAAKX,GAAe,cAAc,IAAI,IACtC,KAAKA,GAAe,eAAe,IAAI;AAC3C,WAAO,QAAQ,OAAO,SAAS,GAAG;AAChC,iBAAW,OAAO,CAAC,GAAG,KAAK,CAAC,EAAE,KAAK,KAAA,CAAM,EAAE;AAAA,QACzC,WAAWY,WAAAA,sBAAsBC,MAAAA;AAAAA,MAAA,GAChC;AACD,YAAI,WAAW,GAAG,KAAK,KAAM,QAAO,KAAK,GAAG;AAC5C,YAAI,OAAO,UAAU,EAAG;AAAA,MAC1B;AACA,UAAI,OAAO,UAAU,EAAG;AACxB,aAAO,WACH,KAAKb,GAAe,cAAc,KAAK,CAAC,CAAC,IACzC,KAAKA,GAAe,eAAe,KAAK,CAAC,CAAC;AAAA,IAChD;AACA,WAAO;AAAA,EACT;AAAA,EAEA,KAAK,GAAW,MAAW,UAAgD;AACzE,WAAO,KAAKW,GAAa,GAAG,EAAE,OAAO,KAAA,GAAQ,UAAU,KAAK;AAAA,EAC9D;AAAA,EAEA,cAAc,GAAW,UAAgD;AACvE,WAAO,KAAKA,GAAa,GAAG,QAAW,UAAU,KAAK;AAAA,EACxD;AAAA,EAEA,aACE,GACA,MACA,UACa;AACb,WAAO,KAAKA,GAAa,GAAG,EAAE,OAAO,KAAA,GAAQ,UAAU,IAAI;AAAA,EAC7D;AAAA,EAEA,oBACE,GACA,UACa;AACb,WAAO,KAAKA,GAAa,GAAG,QAAW,UAAU,IAAI;AAAA,EACvD;AACF;AAEAG,UAAAA,0BAA0B,IAAI,YAAY,YAAY;;"}