SortedMap on JavaScript

index.ts

async function main() {
  const myMap = createSortedMap<number, string>([], ([leftKey], [rightKey]) => {
    return leftKey - rightKey;
  });

  myMap.set(2, 'b');
  myMap.set(1, 'a');
  myMap.set(3, 'c');

  const assert = require('assert');
  for (const [key, value] of myMap) {
    console.log(key, value)
  }

  assert.deepEqual(Array.from(myMap.values()), ['a', 'b', 'c']);
  myMap.delete(2);

  assert.deepEqual(Array.from(myMap.values()), ['a', 'c']);

  myMap.delete(1);
  assert.deepEqual(Array.from(myMap.values()), ['c']);

  myMap.delete(3);
  assert.deepEqual(Array.from(myMap.values()), []);

  myMap.set(1, "a");
  myMap.set(1, "a");
  assert.deepEqual(Array.from(myMap.values()), ["a"]);
}

main();

function createSortedMap<K, V>(entries: [K, V][] | null, comparator: (a: [K, V], b: [K, V]) => number) {
  class SortedMap<K, V> extends Map<K, V> {
    private comparator: (a: [K, V], b: [K, V]) => number;
    private sortedEntries: [K, V][];

    constructor(entries: [K, V][] | null, comparator: (a: [K, V], b: [K, V]) => number) {
      super();
      this.sortedEntries = entries ?? [];
      this.comparator = comparator;
    }

    private getEntryIndex(entry: [K, V]) {
      return binarySearch(this.sortedEntries, (thatEntry) => {
        return this.comparator(entry, thatEntry);
      });
    }

    set(key: K, value: V) {
      if (!this.has(key)) {
        const entry: [K, V] = [key, value];
        const idx = ~this.getEntryIndex(entry);
        this.sortedEntries.splice(idx, 0, entry);
      }

      return super.set(key, value);
    }

    delete(key: K) {
      if (this.has(key)) {
        const value = this.get(key)!
        const idx = this.getEntryIndex([key, value]);
        if (idx >= 0) this.sortedEntries.splice(idx, 1);
      }

      return super.delete(key);
    }

    keys() {
      return this.sortedEntries.map((entry) => entry[0])[Symbol.iterator]();
    }

    values() {
      return this.sortedEntries.map((entry) => entry[1])[Symbol.iterator]();
    }

    entries() {
      return this.sortedEntries[Symbol.iterator]();
    }

    [Symbol.iterator]() {
      return this.sortedEntries[Symbol.iterator]();
    }
  }

  return new SortedMap(entries, comparator);

  function binarySearch<T>(arr: T[], compareFn: (value: T, idx: number) => number) {
    let min = 0;
    let max = arr.length;
    let found = false;
    while (min < max) {
      const middle = min + ((max - min) >>> 1);
      const compareResult = compareFn(arr[middle], middle);
      if (compareResult > 0) {
        min = middle + 1;
      } else {
        max = middle;
        found = !compareResult;
      }
    }
    return found ? min : -min - 1;
  }
}