{"version":3,"sources":["../src/heap.ts"],"sourcesContent":["// ─────────────────────────────────────────────────────────────────────────────\n// Heap — a generic binary heap usable as a min-heap or max-heap.\n//\n// Comparator conventions (same as Array.prototype.sort):\n//   compare(a, b) < 0  →  a has higher priority than b  (a closer to top)\n//   compare(a, b) > 0  →  b has higher priority than a  (b closer to top)\n//   compare(a, b) = 0  →  equal priority\n//\n// Min-heap: (a, b) => a - b          top = smallest number\n// Max-heap: (a, b) => b - a          top = largest number\n// By field:  (a, b) => a.ts - b.ts   top = smallest .ts\n//\n// All core operations are O(log n) except peek and size which are O(1).\n// ─────────────────────────────────────────────────────────────────────────────\n\nexport type Comparator<T> = (a: T, b: T) => number;\n\nexport class Heap<T> {\n  private readonly data: T[];\n  private readonly compare: Comparator<T>;\n\n  /**\n   * @param compare - Comparator function. Return negative to place `a` above\n   *   `b` in the heap (i.e. closer to the top / higher priority).\n   * @param initial - Optional array of items to heapify in O(n) time.\n   *   The array is copied; the original is not modified.\n   */\n  public constructor(compare: Comparator<T>, initial: T[] = []) {\n    this.compare = compare;\n    this.data = [...initial];\n\n    // Floyd's algorithm: heapify in O(n) by sifting down from last parent.\n    for (let i = parent(this.data.length - 1); i >= 0; i--) {\n      this.siftDown(i);\n    }\n  }\n\n  // ── Accessors ──────────────────────────────────────────────────────────────\n\n  /** Number of items currently in the heap. */\n  public get size(): number {\n    return this.data.length;\n  }\n\n  /** True when the heap contains no items. */\n  public get isEmpty(): boolean {\n    return this.data.length === 0;\n  }\n\n  /** Return the top item without removing it. O(1). */\n  public peek(): T | undefined {\n    return this.data[0];\n  }\n\n  // ── Mutators ───────────────────────────────────────────────────────────────\n\n  /** Add an item. O(log n). */\n  public push(item: T): void {\n    this.data.push(item);\n    this.siftUp(this.data.length - 1);\n  }\n\n  /** Remove and return the top item. O(log n). */\n  public pop(): T | undefined {\n    if (this.data.length === 0) return undefined;\n\n    const top = this.data[0];\n    const last = this.data.pop()!;\n\n    if (this.data.length > 0) {\n      this.data[0] = last;\n      this.siftDown(0);\n    }\n\n    return top;\n  }\n\n  /**\n   * Push a new item and pop the top in one pass — more efficient than calling\n   * push() then pop() separately because it avoids an extra sift. O(log n).\n   */\n  public pushPop(item: T): T {\n    if (this.data.length === 0 || this.compare(item, this.data[0]) <= 0) {\n      // The new item would immediately be popped anyway.\n      return item;\n    }\n\n    const top = this.data[0];\n    this.data[0] = item;\n    this.siftDown(0);\n    return top;\n  }\n\n  /**\n   * Pop the top item and push a replacement in one pass — more efficient than\n   * pop() then push() separately. Throws if the heap is empty. O(log n).\n   */\n  public replace(item: T): T {\n    if (this.data.length === 0) {\n      throw new Error(\"Heap is empty\");\n    }\n\n    const top = this.data[0];\n    this.data[0] = item;\n    this.siftDown(0);\n    return top;\n  }\n\n  /**\n   * Remove the first item that satisfies the predicate.\n   * Returns the removed item, or undefined if not found.\n   *\n   * Finding the item is O(n). The removal itself is O(log n).\n   */\n  public remove(predicate: (item: T) => boolean): T | undefined {\n    const i = this.data.findIndex(predicate);\n    if (i === -1) return undefined;\n    return this.removeAt(i);\n  }\n\n  /**\n   * Remove all items that satisfy the predicate. Returns the removed items in\n   * the order they were found (not priority order).\n   *\n   * O(n) to scan + O(k log n) for k removals.\n   */\n  public removeAll(predicate: (item: T) => boolean): T[] {\n    const removed: T[] = [];\n\n    // Iterate backwards so that removeAt's swap of the last element\n    // doesn't cause us to skip or re-visit items.\n    for (let i = this.data.length - 1; i >= 0; i--) {\n      if (predicate(this.data[i])) {\n        removed.push(this.removeAt(i));\n      }\n    }\n\n    return removed;\n  }\n\n  /** Remove all items. */\n  public clear(): void {\n    this.data.length = 0;\n  }\n\n  // ── Bulk operations ────────────────────────────────────────────────────────\n\n  /**\n   * Add multiple items at once. More efficient than repeated push() calls\n   * when adding many items: uses heapify (O(n)) rather than O(n log n). */\n  public pushAll(items: Iterable<T>): void {\n    for (const item of items) {\n      this.data.push(item);\n    }\n\n    // Re-heapify from scratch.\n    for (let i = parent(this.data.length - 1); i >= 0; i--) {\n      this.siftDown(i);\n    }\n  }\n\n  /**\n   * Drain all items in priority order. The heap is empty afterward.\n   * Equivalent to calling pop() until empty, but expressed as a generator\n   * so callers can break early without popping everything. O(n log n) total.\n   */\n  public *drain(): Generator<T> {\n    while (this.data.length > 0) {\n      yield this.pop()!;\n    }\n  }\n\n  /**\n   * Return a sorted array of all items in priority order without mutating\n   * the heap. O(n log n).\n   */\n  public toSortedArray(): T[] {\n    // Clone into a temporary heap and drain it.\n    const tmp = new Heap<T>(this.compare, this.data);\n    return [...tmp.drain()];\n  }\n\n  // ── Private helpers ────────────────────────────────────────────────────────\n\n  private siftUp(i: number): void {\n    while (i > 0) {\n      const p = parent(i);\n      if (this.compare(this.data[i], this.data[p]) >= 0) break;\n      swap(this.data, i, p);\n      i = p;\n    }\n  }\n\n  private siftDown(i: number): void {\n    const n = this.data.length;\n\n    while (true) {\n      let top = i;\n      const l = leftChild(i);\n      const r = rightChild(i);\n\n      if (l < n && this.compare(this.data[l], this.data[top]) < 0) top = l;\n      if (r < n && this.compare(this.data[r], this.data[top]) < 0) top = r;\n      if (top === i) break;\n\n      swap(this.data, i, top);\n      i = top;\n    }\n  }\n\n  private removeAt(i: number): T {\n    const last = this.data.pop()!;\n\n    // If we just removed the last element, no fixup needed.\n    if (i === this.data.length) return last;\n\n    // Overwrite the target slot with the last element, then restore the\n    // heap invariant. We need to try both directions because the last\n    // element could be either larger or smaller than the removed item's\n    // neighbours.\n    const removed = this.data[i];\n    this.data[i] = last;\n    this.siftUp(i);\n    this.siftDown(i);\n    return removed;\n  }\n}\n\n// ── Index arithmetic (plain functions keep the class body clean) ─────────────\n\nfunction parent(i: number): number {\n  return (i - 1) >> 1;\n}\n\nfunction leftChild(i: number): number {\n  return 2 * i + 1;\n}\n\nfunction rightChild(i: number): number {\n  return 2 * i + 2;\n}\n\nfunction swap<T>(data: T[], i: number, j: number): void {\n  const tmp = data[i];\n  data[i] = data[j];\n  data[j] = tmp;\n}\n"],"mappings":"yaAAA,IAAAA,EAAA,GAAAC,EAAAD,EAAA,UAAAE,IAAA,eAAAC,EAAAH,GAiBO,IAAME,EAAN,MAAME,CAAQ,CACF,KACA,QAQV,YAAYC,EAAwBC,EAAe,CAAC,EAAG,CAC5D,KAAK,QAAUD,EACf,KAAK,KAAO,CAAC,GAAGC,CAAO,EAGvB,QAAS,EAAIC,EAAO,KAAK,KAAK,OAAS,CAAC,EAAG,GAAK,EAAG,IACjD,KAAK,SAAS,CAAC,CAEnB,CAKA,IAAW,MAAe,CACxB,OAAO,KAAK,KAAK,MACnB,CAGA,IAAW,SAAmB,CAC5B,OAAO,KAAK,KAAK,SAAW,CAC9B,CAGO,MAAsB,CAC3B,OAAO,KAAK,KAAK,CAAC,CACpB,CAKO,KAAKC,EAAe,CACzB,KAAK,KAAK,KAAKA,CAAI,EACnB,KAAK,OAAO,KAAK,KAAK,OAAS,CAAC,CAClC,CAGO,KAAqB,CAC1B,GAAI,KAAK,KAAK,SAAW,EAAG,OAE5B,IAAMC,EAAM,KAAK,KAAK,CAAC,EACjBC,EAAO,KAAK,KAAK,IAAI,EAE3B,OAAI,KAAK,KAAK,OAAS,IACrB,KAAK,KAAK,CAAC,EAAIA,EACf,KAAK,SAAS,CAAC,GAGVD,CACT,CAMO,QAAQD,EAAY,CACzB,GAAI,KAAK,KAAK,SAAW,GAAK,KAAK,QAAQA,EAAM,KAAK,KAAK,CAAC,CAAC,GAAK,EAEhE,OAAOA,EAGT,IAAMC,EAAM,KAAK,KAAK,CAAC,EACvB,YAAK,KAAK,CAAC,EAAID,EACf,KAAK,SAAS,CAAC,EACRC,CACT,CAMO,QAAQD,EAAY,CACzB,GAAI,KAAK,KAAK,SAAW,EACvB,MAAM,IAAI,MAAM,eAAe,EAGjC,IAAMC,EAAM,KAAK,KAAK,CAAC,EACvB,YAAK,KAAK,CAAC,EAAID,EACf,KAAK,SAAS,CAAC,EACRC,CACT,CAQO,OAAOE,EAAgD,CAC5D,IAAMC,EAAI,KAAK,KAAK,UAAUD,CAAS,EACvC,GAAIC,IAAM,GACV,OAAO,KAAK,SAASA,CAAC,CACxB,CAQO,UAAUD,EAAsC,CACrD,IAAME,EAAe,CAAC,EAItB,QAAS,EAAI,KAAK,KAAK,OAAS,EAAG,GAAK,EAAG,IACrCF,EAAU,KAAK,KAAK,CAAC,CAAC,GACxBE,EAAQ,KAAK,KAAK,SAAS,CAAC,CAAC,EAIjC,OAAOA,CACT,CAGO,OAAc,CACnB,KAAK,KAAK,OAAS,CACrB,CAOO,QAAQC,EAA0B,CACvC,QAAWN,KAAQM,EACjB,KAAK,KAAK,KAAKN,CAAI,EAIrB,QAASI,EAAIL,EAAO,KAAK,KAAK,OAAS,CAAC,EAAGK,GAAK,EAAGA,IACjD,KAAK,SAASA,CAAC,CAEnB,CAOA,CAAQ,OAAsB,CAC5B,KAAO,KAAK,KAAK,OAAS,GACxB,MAAM,KAAK,IAAI,CAEnB,CAMO,eAAqB,CAG1B,MAAO,CAAC,GADI,IAAIR,EAAQ,KAAK,QAAS,KAAK,IAAI,EAChC,MAAM,CAAC,CACxB,CAIQ,OAAOQ,EAAiB,CAC9B,KAAOA,EAAI,GAAG,CACZ,IAAMG,EAAIR,EAAOK,CAAC,EAClB,GAAI,KAAK,QAAQ,KAAK,KAAKA,CAAC,EAAG,KAAK,KAAKG,CAAC,CAAC,GAAK,EAAG,MACnDC,EAAK,KAAK,KAAMJ,EAAGG,CAAC,EACpBH,EAAIG,CACN,CACF,CAEQ,SAASH,EAAiB,CAChC,IAAMK,EAAI,KAAK,KAAK,OAEpB,OAAa,CACX,IAAIR,EAAMG,EACJM,EAAIC,EAAUP,CAAC,EACfQ,EAAIC,EAAWT,CAAC,EAItB,GAFIM,EAAID,GAAK,KAAK,QAAQ,KAAK,KAAKC,CAAC,EAAG,KAAK,KAAKT,CAAG,CAAC,EAAI,IAAGA,EAAMS,GAC/DE,EAAIH,GAAK,KAAK,QAAQ,KAAK,KAAKG,CAAC,EAAG,KAAK,KAAKX,CAAG,CAAC,EAAI,IAAGA,EAAMW,GAC/DX,IAAQG,EAAG,MAEfI,EAAK,KAAK,KAAMJ,EAAGH,CAAG,EACtBG,EAAIH,CACN,CACF,CAEQ,SAASG,EAAc,CAC7B,IAAMF,EAAO,KAAK,KAAK,IAAI,EAG3B,GAAIE,IAAM,KAAK,KAAK,OAAQ,OAAOF,EAMnC,IAAMG,EAAU,KAAK,KAAKD,CAAC,EAC3B,YAAK,KAAKA,CAAC,EAAIF,EACf,KAAK,OAAOE,CAAC,EACb,KAAK,SAASA,CAAC,EACRC,CACT,CACF,EAIA,SAASN,EAAOK,EAAmB,CACjC,OAAQA,EAAI,GAAM,CACpB,CAEA,SAASO,EAAUP,EAAmB,CACpC,MAAO,GAAIA,EAAI,CACjB,CAEA,SAASS,EAAWT,EAAmB,CACrC,MAAO,GAAIA,EAAI,CACjB,CAEA,SAASI,EAAQM,EAAWV,EAAWW,EAAiB,CACtD,IAAMC,EAAMF,EAAKV,CAAC,EAClBU,EAAKV,CAAC,EAAIU,EAAKC,CAAC,EAChBD,EAAKC,CAAC,EAAIC,CACZ","names":["heap_exports","__export","Heap","__toCommonJS","_Heap","compare","initial","parent","item","top","last","predicate","i","removed","items","p","swap","n","l","leftChild","r","rightChild","data","j","tmp"]}