An array based sorted list implementation in JavaScript. Compatible with array methods such as splice and slice.

SortedList.js

class SortedList {
  #items;
  #comparator;
  #locator;

  constructor(items, comparator, locator, itemsAreSorted = false) {
    items = [...items];

    if (!itemsAreSorted) items.sort(comparator);

    this.#items = items;
    this.#comparator = comparator;
    this.#locator = locator;
  }

  #indexOf(item) {
    return this.#items.findIndex(listItem => this.#locator(listItem, item));
  }

  #indexOfOrFail(item) {
    const index = this.#indexOf(item);

    if (index === -1) throw new Error('Item not found.');

    return index;
  }

  clone() {
    return new SortedList(this.#items, this.#comparator, this.#locator, true);
  }

  // TODO: Use binary search instead of linear.
  firstIndexOf(item) {
    for (let i = 0; i < this.#items.length; i++) {
      const listItem = this.#items[i];

      if (this.#comparator(listItem, item) >= 0) return i;
    }

    return this.#items.length;
  }

  // TODO: Use binary search instead of linear.
  lastIndexOf(item) {
    for (let i = this.#items.length - 1; i >= 0; i--) {
      const listItem = this.#items[i];

      if (this.#comparator(listItem, item) <= 0) return i;
    }

    return -1;
  }

  add(item) {
    if (this.#indexOf(item) !== -1) throw new Error('An equivalent item already exists.');

    this.#items.splice(this.firstIndexOf(item), 0, item);

    return this;
  }

  get(item) {
    return item === undefined ? this.#items : this.#items[this.#indexOfOrFail(item)];
  }

  modify(item, orderMightChange = true) {
    const index = this.#indexOfOrFail(item);

    if (orderMightChange) {
      this.remove(item);
      this.add(item);
    } else {
      this.#items[index] = item;
    }

    return this;
  }

  remove(item) {
    this.#items.splice(this.#indexOfOrFail(item), 1);

    return this;
  }
}