{"version":3,"file":"SortedMap.cjs","sources":["../../src/SortedMap.ts"],"sourcesContent":["import { compareKeys } from '@tanstack/db-ivm'\n\n/**\n * A Map implementation that keeps its entries sorted based on a comparator function\n * @template TKey - The type of keys in the map (must be string | number)\n * @template TValue - The type of values in the map\n */\nexport class SortedMap<TKey extends string | number, TValue> {\n  private map: Map<TKey, TValue>\n  private sortedKeys: Array<TKey>\n  private comparator: ((a: TValue, b: TValue) => number) | undefined\n  // Keys set or deleted with deferOrder since the last restoreOrder. A dirty\n  // key can still hold a slot in sortedKeys that its old value ordered.\n  private dirtyKeys = new Set<TKey>()\n\n  /**\n   * Creates a new SortedMap instance\n   *\n   * @param comparator - Optional function to compare values for sorting.\n   *                     If not provided, entries are sorted by key only.\n   */\n  constructor(comparator?: (a: TValue, b: TValue) => number) {\n    this.map = new Map<TKey, TValue>()\n    this.sortedKeys = []\n    this.comparator = comparator\n  }\n\n  /**\n   * Finds the index where a key-value pair should be inserted to maintain sort order.\n   * Uses binary search to find the correct position based on the value (if comparator provided),\n   * with key-based tie-breaking for deterministic ordering when values compare as equal.\n   * If no comparator is provided, sorts by key only.\n   * Runs in O(log n) time.\n   *\n   * @param key - The key to find position for (used as tie-breaker or primary sort when no comparator)\n   * @param value - The value to compare against (only used if comparator is provided)\n   * @param keys - The ordered keys to search\n   * @returns The index where the key should be inserted\n   */\n  private indexOf(\n    key: TKey,\n    value: TValue,\n    keys: Array<TKey> = this.sortedKeys,\n  ): number {\n    let left = 0\n    let right = keys.length\n\n    // Fast path: no comparator means sort by key only\n    if (!this.comparator) {\n      while (left < right) {\n        const mid = Math.floor((left + right) / 2)\n        const midKey = keys[mid]!\n        const keyComparison = compareKeys(key, midKey)\n        if (keyComparison < 0) {\n          right = mid\n        } else if (keyComparison > 0) {\n          left = mid + 1\n        } else {\n          return mid\n        }\n      }\n      return left\n    }\n\n    // With comparator: sort by value first, then key as tie-breaker\n    while (left < right) {\n      const mid = Math.floor((left + right) / 2)\n      const midKey = keys[mid]!\n      const midValue = this.map.get(midKey)!\n      const valueComparison = this.comparator(value, midValue)\n\n      if (valueComparison < 0) {\n        right = mid\n      } else if (valueComparison > 0) {\n        left = mid + 1\n      } else {\n        // Values are equal, use key as tie-breaker for deterministic ordering\n        const keyComparison = compareKeys(key, midKey)\n        if (keyComparison < 0) {\n          right = mid\n        } else if (keyComparison > 0) {\n          left = mid + 1\n        } else {\n          // Same key (shouldn't happen during insert, but handle for lookups)\n          return mid\n        }\n      }\n    }\n\n    return left\n  }\n\n  /**\n   * Restore the ordered view after a synchronous batch of deferred writes.\n   * Dirty keys leave their old slots by Set membership, so a deleted value or\n   * one a sync source mutated in place cannot strand a slot. The dirty keys\n   * still present are sorted and merged into the rest in one pass:\n   * O(n + k log n) for k dirty keys. The merge rewrites sortedKeys in place,\n   * so an open key iterator reads the restored order.\n   */\n  restoreOrder(): void {\n    if (this.dirtyKeys.size === 0) return\n    const keys = this.sortedKeys\n    const kept = keys.filter((key) => !this.dirtyKeys.has(key))\n    const placed = [...this.dirtyKeys]\n      .filter((key) => this.map.has(key))\n      .sort(\n        (left, right) =>\n          (this.comparator?.(this.map.get(left)!, this.map.get(right)!) ?? 0) ||\n          compareKeys(left, right),\n      )\n    keys.length = 0\n    let next = 0\n    for (const key of placed) {\n      const index = this.indexOf(key, this.map.get(key)!, kept)\n      while (next < index) keys.push(kept[next++]!)\n      keys.push(key)\n    }\n    while (next < kept.length) keys.push(kept[next++]!)\n    this.dirtyKeys.clear()\n  }\n\n  /** Removes a key's slot while its placed value is still mapped. */\n  private unplace(key: TKey): void {\n    // Binary search misses a value that a sync source mutated in place after\n    // it was placed, so fall back to a scan. Slots compare as Map keys do, so\n    // a NaN key matches its own slot.\n    const sameKey = (candidate: TKey) =>\n      candidate === key || (candidate !== candidate && key !== key)\n    let index = this.indexOf(key, this.map.get(key)!)\n    if (!sameKey(this.sortedKeys[index]!)) {\n      index = this.sortedKeys.findIndex(sameKey)\n    }\n    this.sortedKeys.splice(index, 1)\n  }\n\n  /**\n   * Sets a key-value pair in the map and maintains sort order\n   *\n   * @param key - The key to set\n   * @param value - The value to associate with the key\n   * @param deferOrder - Defer ordering until restoreOrder or the next ordered read\n   * @returns This SortedMap instance for chaining\n   */\n  set(key: TKey, value: TValue, deferOrder = false): this {\n    // Key order cannot change when an existing key gets a new value.\n    if (!this.comparator && this.map.has(key)) {\n      this.map.set(key, value)\n      return this\n    }\n    if (deferOrder) {\n      this.map.set(key, value)\n      this.dirtyKeys.add(key)\n      return this\n    }\n    this.restoreOrder()\n    // The old slot leaves before the search, since an in-place mutation can\n    // misorder it.\n    if (this.map.has(key)) this.unplace(key)\n    this.sortedKeys.splice(this.indexOf(key, value), 0, key)\n    this.map.set(key, value)\n    return this\n  }\n\n  /**\n   * Gets a value by its key\n   *\n   * @param key - The key to look up\n   * @returns The value associated with the key, or undefined if not found\n   */\n  get(key: TKey): TValue | undefined {\n    return this.map.get(key)\n  }\n\n  /**\n   * Removes a key-value pair from the map\n   *\n   * @param key - The key to remove\n   * @param deferOrder - Defer ordering until restoreOrder or the next ordered read\n   * @returns True if the key was found and removed, false otherwise\n   */\n  delete(key: TKey, deferOrder = false): boolean {\n    if (deferOrder) {\n      const deleted = this.map.delete(key)\n      if (deleted) this.dirtyKeys.add(key)\n      return deleted\n    }\n    this.restoreOrder()\n    if (this.map.has(key)) this.unplace(key)\n    return this.map.delete(key)\n  }\n\n  /**\n   * Checks if a key exists in the map\n   *\n   * @param key - The key to check\n   * @returns True if the key exists, false otherwise\n   */\n  has(key: TKey): boolean {\n    return this.map.has(key)\n  }\n\n  /**\n   * Removes all key-value pairs from the map\n   */\n  clear(): void {\n    this.map.clear()\n    this.sortedKeys = []\n    this.dirtyKeys.clear()\n  }\n\n  /**\n   * Gets the number of key-value pairs in the map\n   */\n  get size(): number {\n    return this.map.size\n  }\n\n  /**\n   * Default iterator that returns entries in sorted order\n   *\n   * @returns An iterator for the map's entries\n   */\n  *[Symbol.iterator](): IterableIterator<[TKey, TValue]> {\n    for (const key of this.keys()) yield [key, this.map.get(key)!]\n  }\n\n  /**\n   * Returns an iterator for the map's entries in sorted order\n   *\n   * @returns An iterator for the map's entries\n   */\n  entries(): IterableIterator<[TKey, TValue]> {\n    return this[Symbol.iterator]()\n  }\n\n  /**\n   * Returns an iterator for the map's keys in sorted order\n   *\n   * @returns An iterator for the map's keys\n   */\n  keys(): IterableIterator<TKey> {\n    this.restoreOrder()\n    return this.sortedKeys[Symbol.iterator]()\n  }\n\n  /**\n   * Returns an iterator for the map's values in sorted order\n   *\n   * @returns An iterator for the map's values\n   */\n  *values(): IterableIterator<TValue> {\n    for (const key of this.keys()) yield this.map.get(key)!\n  }\n}\n"],"names":["dirtyKeys","sortedKeys","compareKeys","unplace"],"mappings":";;;AAOO,MAAM,UAAgD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAc3D,YAAY,YAA+C;AAR3D,SAAQA,yBAAgB,IAAA;AAStB,SAAK,0BAAU,IAAA;AACf,SAAKC,KAAa,CAAA;AAClB,SAAK,aAAa;AAAA,EACpB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAcQ,QACN,KACA,OACA,OAAoB,KAAKA,IACjB;AACR,QAAI,OAAO;AACX,QAAI,QAAQ,KAAK;AAGjB,QAAI,CAAC,KAAK,YAAY;AACpB,aAAO,OAAO,OAAO;AACnB,cAAM,MAAM,KAAK,OAAO,OAAO,SAAS,CAAC;AACzC,cAAM,SAAS,KAAK,GAAG;AACvB,cAAM,gBAAgBC,MAAAA,YAAY,KAAK,MAAM;AAC7C,YAAI,gBAAgB,GAAG;AACrB,kBAAQ;AAAA,QACV,WAAW,gBAAgB,GAAG;AAC5B,iBAAO,MAAM;AAAA,QACf,OAAO;AACL,iBAAO;AAAA,QACT;AAAA,MACF;AACA,aAAO;AAAA,IACT;AAGA,WAAO,OAAO,OAAO;AACnB,YAAM,MAAM,KAAK,OAAO,OAAO,SAAS,CAAC;AACzC,YAAM,SAAS,KAAK,GAAG;AACvB,YAAM,WAAW,KAAK,IAAI,IAAI,MAAM;AACpC,YAAM,kBAAkB,KAAK,WAAW,OAAO,QAAQ;AAEvD,UAAI,kBAAkB,GAAG;AACvB,gBAAQ;AAAA,MACV,WAAW,kBAAkB,GAAG;AAC9B,eAAO,MAAM;AAAA,MACf,OAAO;AAEL,cAAM,gBAAgBA,MAAAA,YAAY,KAAK,MAAM;AAC7C,YAAI,gBAAgB,GAAG;AACrB,kBAAQ;AAAA,QACV,WAAW,gBAAgB,GAAG;AAC5B,iBAAO,MAAM;AAAA,QACf,OAAO;AAEL,iBAAO;AAAA,QACT;AAAA,MACF;AAAA,IACF;AAEA,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,eAAqB;AACnB,QAAI,KAAKF,GAAU,SAAS,EAAG;AAC/B,UAAM,OAAO,KAAKC;AAClB,UAAM,OAAO,KAAK,OAAO,CAAC,QAAQ,CAAC,KAAKD,GAAU,IAAI,GAAG,CAAC;AAC1D,UAAM,SAAS,CAAC,GAAG,KAAKA,EAAS,EAC9B,OAAO,CAAC,QAAQ,KAAK,IAAI,IAAI,GAAG,CAAC,EACjC;AAAA,MACC,CAAC,MAAM,WACJ,KAAK,aAAa,KAAK,IAAI,IAAI,IAAI,GAAI,KAAK,IAAI,IAAI,KAAK,CAAE,KAAK,MACjEE,MAAAA,YAAY,MAAM,KAAK;AAAA,IAAA;AAE7B,SAAK,SAAS;AACd,QAAI,OAAO;AACX,eAAW,OAAO,QAAQ;AACxB,YAAM,QAAQ,KAAK,QAAQ,KAAK,KAAK,IAAI,IAAI,GAAG,GAAI,IAAI;AACxD,aAAO,OAAO,MAAO,MAAK,KAAK,KAAK,MAAM,CAAE;AAC5C,WAAK,KAAK,GAAG;AAAA,IACf;AACA,WAAO,OAAO,KAAK,aAAa,KAAK,KAAK,MAAM,CAAE;AAClD,SAAKF,GAAU,MAAA;AAAA,EACjB;AAAA;AAAA,EAGQG,GAAQ,KAAiB;AAI/B,UAAM,UAAU,CAAC,cACf,cAAc,OAAQ,cAAc,aAAa,QAAQ;AAC3D,QAAI,QAAQ,KAAK,QAAQ,KAAK,KAAK,IAAI,IAAI,GAAG,CAAE;AAChD,QAAI,CAAC,QAAQ,KAAKF,GAAW,KAAK,CAAE,GAAG;AACrC,cAAQ,KAAKA,GAAW,UAAU,OAAO;AAAA,IAC3C;AACA,SAAKA,GAAW,OAAO,OAAO,CAAC;AAAA,EACjC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,IAAI,KAAW,OAAe,aAAa,OAAa;AAEtD,QAAI,CAAC,KAAK,cAAc,KAAK,IAAI,IAAI,GAAG,GAAG;AACzC,WAAK,IAAI,IAAI,KAAK,KAAK;AACvB,aAAO;AAAA,IACT;AACA,QAAI,YAAY;AACd,WAAK,IAAI,IAAI,KAAK,KAAK;AACvB,WAAKD,GAAU,IAAI,GAAG;AACtB,aAAO;AAAA,IACT;AACA,SAAK,aAAA;AAGL,QAAI,KAAK,IAAI,IAAI,GAAG,EAAG,MAAKG,GAAQ,GAAG;AACvC,SAAKF,GAAW,OAAO,KAAK,QAAQ,KAAK,KAAK,GAAG,GAAG,GAAG;AACvD,SAAK,IAAI,IAAI,KAAK,KAAK;AACvB,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,KAA+B;AACjC,WAAO,KAAK,IAAI,IAAI,GAAG;AAAA,EACzB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,OAAO,KAAW,aAAa,OAAgB;AAC7C,QAAI,YAAY;AACd,YAAM,UAAU,KAAK,IAAI,OAAO,GAAG;AACnC,UAAI,QAAS,MAAKD,GAAU,IAAI,GAAG;AACnC,aAAO;AAAA,IACT;AACA,SAAK,aAAA;AACL,QAAI,KAAK,IAAI,IAAI,GAAG,EAAG,MAAKG,GAAQ,GAAG;AACvC,WAAO,KAAK,IAAI,OAAO,GAAG;AAAA,EAC5B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,KAAoB;AACtB,WAAO,KAAK,IAAI,IAAI,GAAG;AAAA,EACzB;AAAA;AAAA;AAAA;AAAA,EAKA,QAAc;AACZ,SAAK,IAAI,MAAA;AACT,SAAKF,KAAa,CAAA;AAClB,SAAKD,GAAU,MAAA;AAAA,EACjB;AAAA;AAAA;AAAA;AAAA,EAKA,IAAI,OAAe;AACjB,WAAO,KAAK,IAAI;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,EAAE,OAAO,QAAQ,IAAsC;AACrD,eAAW,OAAO,KAAK,OAAQ,OAAM,CAAC,KAAK,KAAK,IAAI,IAAI,GAAG,CAAE;AAAA,EAC/D;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,UAA4C;AAC1C,WAAO,KAAK,OAAO,QAAQ,EAAA;AAAA,EAC7B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,OAA+B;AAC7B,SAAK,aAAA;AACL,WAAO,KAAKC,GAAW,OAAO,QAAQ,EAAA;AAAA,EACxC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,CAAC,SAAmC;AAClC,eAAW,OAAO,KAAK,KAAA,SAAc,KAAK,IAAI,IAAI,GAAG;AAAA,EACvD;AACF;;"}