51 lines
1.2 KiB
TypeScript
51 lines
1.2 KiB
TypeScript
export type Comparator<T> = (a: T, b: T) => number;
|
|
|
|
/** ordered contiguous set of items (backing array exposed) */
|
|
export class OrderedSet<T> {
|
|
items: T[] = [];
|
|
|
|
constructor(readonly comparator: Comparator<T> = (a, b) => (a < b ? -1 : a > b ? 1 : 0)) {}
|
|
|
|
add(item: T, fromEnd: boolean = false): number {
|
|
// TODO: binary search ?
|
|
|
|
let idx = 0;
|
|
if (!fromEnd) {
|
|
while (idx < this.items.length) {
|
|
const compareVal = this.comparator(this.items[idx], item);
|
|
if (compareVal === 0) return -1;
|
|
if (compareVal > 0) break;
|
|
idx++;
|
|
}
|
|
} else {
|
|
idx = this.items.length - 1;
|
|
while (idx > 0) {
|
|
const compareVal = this.comparator(this.items[idx], item);
|
|
if (compareVal === 0) return -1;
|
|
if (compareVal < 0) break;
|
|
idx--;
|
|
}
|
|
}
|
|
this.items.splice(idx, 0, item);
|
|
return idx;
|
|
}
|
|
|
|
remove(item: T): number {
|
|
const idx = this.items.findIndex(it => this.comparator(item, it) === 0);
|
|
if (idx === -1) return idx;
|
|
this.items.splice(idx, 1);
|
|
return idx;
|
|
}
|
|
|
|
at(n: number) {
|
|
return this.items.at(n);
|
|
}
|
|
|
|
get length(): number {
|
|
return this.items.length;
|
|
}
|
|
|
|
[Symbol.iterator]() {
|
|
return this.items[Symbol.iterator]();
|
|
}
|
|
}
|