Skip to content

Instantly share code, notes, and snippets.

@ugultopu
Last active April 29, 2022 12:17
Show Gist options
  • Save ugultopu/518df0a01d069c626d8765509d4235ee to your computer and use it in GitHub Desktop.
Save ugultopu/518df0a01d069c626d8765509d4235ee to your computer and use it in GitHub Desktop.
An array based sorted list implementation in JavaScript. Compatible with array methods such as splice and slice.
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment