{"version":3,"sources":["../src/binary-search.ts"],"sourcesContent":["import { RingBuffer } from './ring-buffer.js';\n\nexport interface Comparator<T> {\n  (a: T, b: T): number;\n}\n\nexport class BinarySearchArray<T> implements Iterable<T, void, unknown> {\n  #buffer: RingBuffer<T>;\n  #comparator: Comparator<T>;\n\n  constructor(comparator: Comparator<T>) {\n    this.#buffer = new RingBuffer();\n    this.#comparator = comparator;\n  }\n\n  readonly [Symbol.toStringTag] = 'BinarySearchArray';\n\n  get length(): number {\n    return this.#buffer.length;\n  }\n\n  at(index: number) {\n    return this.#buffer.peekAt(index);\n  }\n\n  lowerBound(value: T): number {\n    const length = this.#buffer.length;\n    if (length === 0) return 0;\n\n    const buffer = this.#buffer;\n    const comparator = this.#comparator;\n    let left = 0;\n    let right = length;\n\n    while (left < right) {\n      const mid = (left + right) >>> 1;\n      const midValue = buffer.peekAt(mid)!;\n      if (comparator(midValue, value) < 0) {\n        left = mid + 1;\n      } else {\n        right = mid;\n      }\n    }\n\n    return left;\n  }\n\n  upperBound(value: T): number {\n    const length = this.#buffer.length;\n    if (length === 0) return 0;\n\n    const buffer = this.#buffer;\n    const comparator = this.#comparator;\n    let left = 0;\n    let right = length;\n\n    while (left < right) {\n      const mid = (left + right) >>> 1;\n      const midValue = buffer.peekAt(mid)!;\n      if (comparator(midValue, value) <= 0) {\n        left = mid + 1;\n      } else {\n        right = mid;\n      }\n    }\n\n    return left;\n  }\n\n  indexOf(value: T, index = 0) {\n    const length = this.#buffer.length;\n    if (length === 0 || index >= length) return -1;\n\n    const buffer = this.#buffer;\n    const comparator = this.#comparator;\n    let left = index;\n    let right = length - 1;\n\n    while (left <= right) {\n      const mid = (left + right) >>> 1;\n      const midValue = buffer.peekAt(mid)!;\n      const cmp = comparator(midValue, value);\n\n      if (cmp === 0) {\n        return mid;\n      } else if (cmp < 0) {\n        left = mid + 1;\n      } else {\n        right = mid - 1;\n      }\n    }\n\n    return -1;\n  }\n\n  has(value: T): boolean {\n    return this.indexOf(value) !== -1;\n  }\n\n  insert(value: T) {\n    const index = this.lowerBound(value);\n    this.#buffer.setOne(index, value, true);\n\n    return index;\n  }\n\n  removeOne(index: number) {\n    return this.#buffer.removeOne(index);\n  }\n\n  removeFirst(value: T) {\n    const index = this.indexOf(value);\n    return this.#buffer.removeOne(index);\n  }\n\n  remove(index: number, count: number): this {\n    this.#buffer.deallocate(index, count);\n\n    return this;\n  }\n\n  iter() {\n    return this.#buffer.iter();\n  }\n\n  [Symbol.iterator](): Iterator<T> {\n    return this.#buffer[Symbol.iterator]();\n  }\n}\n"],"names":["BinarySearchArray","comparator","RingBuffer","Symbol","toStringTag","length","at","index","peekAt","lowerBound","value","buffer","left","right","mid","midValue","upperBound","indexOf","cmp","has","insert","setOne","removeOne","removeFirst","remove","count","deallocate","iter","iterator"],"mappings":";;;;+BAMaA;;;eAAAA;;;+BANc;AAMpB,MAAMA;IACX,CAAA,MAAO,CAAgB;IACvB,CAAA,UAAW,CAAgB;IAE3B,YAAYC,UAAyB,CAAE;QACrC,IAAI,CAAC,CAAA,MAAO,GAAG,IAAIC,yBAAU;QAC7B,IAAI,CAAC,CAAA,UAAW,GAAGD;IACrB;IAES,CAACE,OAAOC,WAAW,CAAC,GAAG,oBAAoB;IAEpD,IAAIC,SAAiB;QACnB,OAAO,IAAI,CAAC,CAAA,MAAO,CAACA,MAAM;IAC5B;IAEAC,GAAGC,KAAa,EAAE;QAChB,OAAO,IAAI,CAAC,CAAA,MAAO,CAACC,MAAM,CAACD;IAC7B;IAEAE,WAAWC,KAAQ,EAAU;QAC3B,MAAML,SAAS,IAAI,CAAC,CAAA,MAAO,CAACA,MAAM;QAClC,IAAIA,WAAW,GAAG,OAAO;QAEzB,MAAMM,SAAS,IAAI,CAAC,CAAA,MAAO;QAC3B,MAAMV,aAAa,IAAI,CAAC,CAAA,UAAW;QACnC,IAAIW,OAAO;QACX,IAAIC,QAAQR;QAEZ,MAAOO,OAAOC,MAAO;YACnB,MAAMC,MAAM,AAACF,OAAOC,UAAW;YAC/B,MAAME,WAAWJ,OAAOH,MAAM,CAACM;YAC/B,IAAIb,WAAWc,UAAUL,SAAS,GAAG;gBACnCE,OAAOE,MAAM;YACf,OAAO;gBACLD,QAAQC;YACV;QACF;QAEA,OAAOF;IACT;IAEAI,WAAWN,KAAQ,EAAU;QAC3B,MAAML,SAAS,IAAI,CAAC,CAAA,MAAO,CAACA,MAAM;QAClC,IAAIA,WAAW,GAAG,OAAO;QAEzB,MAAMM,SAAS,IAAI,CAAC,CAAA,MAAO;QAC3B,MAAMV,aAAa,IAAI,CAAC,CAAA,UAAW;QACnC,IAAIW,OAAO;QACX,IAAIC,QAAQR;QAEZ,MAAOO,OAAOC,MAAO;YACnB,MAAMC,MAAM,AAACF,OAAOC,UAAW;YAC/B,MAAME,WAAWJ,OAAOH,MAAM,CAACM;YAC/B,IAAIb,WAAWc,UAAUL,UAAU,GAAG;gBACpCE,OAAOE,MAAM;YACf,OAAO;gBACLD,QAAQC;YACV;QACF;QAEA,OAAOF;IACT;IAEAK,QAAQP,KAAQ,EAAEH,QAAQ,CAAC,EAAE;QAC3B,MAAMF,SAAS,IAAI,CAAC,CAAA,MAAO,CAACA,MAAM;QAClC,IAAIA,WAAW,KAAKE,SAASF,QAAQ,OAAO,CAAC;QAE7C,MAAMM,SAAS,IAAI,CAAC,CAAA,MAAO;QAC3B,MAAMV,aAAa,IAAI,CAAC,CAAA,UAAW;QACnC,IAAIW,OAAOL;QACX,IAAIM,QAAQR,SAAS;QAErB,MAAOO,QAAQC,MAAO;YACpB,MAAMC,MAAM,AAACF,OAAOC,UAAW;YAC/B,MAAME,WAAWJ,OAAOH,MAAM,CAACM;YAC/B,MAAMI,MAAMjB,WAAWc,UAAUL;YAEjC,IAAIQ,QAAQ,GAAG;gBACb,OAAOJ;YACT,OAAO,IAAII,MAAM,GAAG;gBAClBN,OAAOE,MAAM;YACf,OAAO;gBACLD,QAAQC,MAAM;YAChB;QACF;QAEA,OAAO,CAAC;IACV;IAEAK,IAAIT,KAAQ,EAAW;QACrB,OAAO,IAAI,CAACO,OAAO,CAACP,WAAW,CAAC;IAClC;IAEAU,OAAOV,KAAQ,EAAE;QACf,MAAMH,QAAQ,IAAI,CAACE,UAAU,CAACC;QAC9B,IAAI,CAAC,CAAA,MAAO,CAACW,MAAM,CAACd,OAAOG,OAAO;QAElC,OAAOH;IACT;IAEAe,UAAUf,KAAa,EAAE;QACvB,OAAO,IAAI,CAAC,CAAA,MAAO,CAACe,SAAS,CAACf;IAChC;IAEAgB,YAAYb,KAAQ,EAAE;QACpB,MAAMH,QAAQ,IAAI,CAACU,OAAO,CAACP;QAC3B,OAAO,IAAI,CAAC,CAAA,MAAO,CAACY,SAAS,CAACf;IAChC;IAEAiB,OAAOjB,KAAa,EAAEkB,KAAa,EAAQ;QACzC,IAAI,CAAC,CAAA,MAAO,CAACC,UAAU,CAACnB,OAAOkB;QAE/B,OAAO,IAAI;IACb;IAEAE,OAAO;QACL,OAAO,IAAI,CAAC,CAAA,MAAO,CAACA,IAAI;IAC1B;IAEA,CAACxB,OAAOyB,QAAQ,CAAC,GAAgB;QAC/B,OAAO,IAAI,CAAC,CAAA,MAAO,CAACzB,OAAOyB,QAAQ,CAAC;IACtC;AACF"}