Class: SortedList<T>

Defined in: sorted-list.ts:29

A list that keeps its elements in sorted order as they're inserted.

A thin public wrapper around the internal BucketEngine — see there for the actual "list of lists" (sqrt-decomposition) implementation and its complexity notes.

Example

const scores = new SortedList<number>([42, 7, 99]);
scores.add(15);
[...scores]; // [7, 15, 42, 99]

Extended by

• SortedSet

Type Parameters

T

T

Implements

• Iterable<T>

Constructors

Constructor

new SortedList<T>(iterable?, ...options): SortedList<T>

Defined in: sorted-list.ts:40

Parameters

iterable?

Iterable<T, any, any>

options

...ComparatorArg<T>

Returns

SortedList<T>

Example

new SortedList<number>(); // empty
new SortedList<number>([3, 1, 2]); // [1, 2, 3]
new SortedList<Person>([...], { comparator: (a, b) => a.age - b.age });

Accessors

length

Get Signature

get length(): number

Defined in: sorted-list.ts:246

Example

new SortedList<number>([1, 2, 3]).length; // 3

Returns

number

Methods

[iterator]()

[iterator](): IterableIterator<T>

Defined in: sorted-list.ts:285

Returns

IterableIterator<T>

Example

const scores = new SortedList<number>([3, 1, 2]);
for (const value of scores) console.log(value); // 1, 2, 3

Implementation of

Iterable.[iterator]

---

add()

add(value): void

Defined in: sorted-list.ts:85

O(√n) amortized.

Parameters

value

T

Returns

void

Example

const scores = new SortedList<number>();
scores.add(42);
scores.add(7);
[...scores]; // [7, 42]

---

at()

at(index): T | undefined

Defined in: sorted-list.ts:158

O(√n): walks bucket lengths to find the element at index (negative indices count from the end).

Parameters

index

number

Returns

T | undefined

Example

const scores = new SortedList<number>([10, 20, 30]);
scores.at(0); // 10
scores.at(-1); // 30 — same as Array.prototype.at
scores.at(99); // undefined — out of range

---

bisectLeft()

bisectLeft(value): number

Defined in: sorted-list.ts:197

The leftmost index where value could be inserted while keeping the list sorted.

Parameters

value

T

Returns

number

Example

new SortedList<number>([1, 2, 2, 2, 3]).bisectLeft(2); // 1

---

bisectRight()

bisectRight(value): number

Defined in: sorted-list.ts:209

The rightmost index where value could be inserted while keeping the list sorted.

Parameters

value

T

Returns

number

Example

new SortedList<number>([1, 2, 2, 2, 3]).bisectRight(2); // 4

---

clear()

clear(): void

Defined in: sorted-list.ts:258

Returns

void

Example

const scores = new SortedList<number>([1, 2, 3]);
scores.clear();
scores.length; // 0

---

clone()

clone(): SortedList<T>

Defined in: sorted-list.ts:274

An independent copy — mutating the clone never affects the original.

Returns

SortedList<T>

Example

const original = new SortedList<number>([1, 2, 3]);
const copy = original.clone();
copy.add(4);
original.length; // 3
copy.length; // 4

---

comparatorArg()

protected comparatorArg(): ComparatorArg<T>

Defined in: sorted-list.ts:70

Safe to call from subclasses/clone: both ComparatorArg<T> branches accept { comparator }.

Returns

ComparatorArg<T>

---

discard()

discard(value): void

Defined in: sorted-list.ts:128

Like remove, but never throws (or returns anything) if value isn't present.

Parameters

value

T

Returns

void

Example

const scores = new SortedList<number>([1, 2, 3]);
scores.discard(99); // no-op, no error

---

has()

has(value): boolean

Defined in: sorted-list.ts:185

O(log n): binary search for the bucket, then binary search within it.

Parameters

value

T

Returns

boolean

Example

const scores = new SortedList<number>([1, 2, 3]);
scores.has(2); // true
scores.has(99); // false

---

indexOf()

indexOf(value): number

Defined in: sorted-list.ts:171

The index of the first occurrence of value, or -1 if absent.

Parameters

value

T

Returns

number

Example

new SortedList<number>([1, 2, 2, 3]).indexOf(2); // 1
new SortedList<number>([1, 2, 3]).indexOf(99); // -1

---

irange()

irange(min?, max?, options?): IterableIterator<T>

Defined in: sorted-list.ts:223

O(log n) to locate both bounds by value + O(k) to iterate the k results.

Parameters

min?

T

max?

T

options?

inclusive?

[boolean, boolean]

Returns

IterableIterator<T>

Example

const scores = new SortedList<number>([1, 2, 3, 4, 5]);
[...scores.irange(2, 4)]; // [2, 3, 4] — inclusive by default
[...scores.irange(2, 4, { inclusive: [false, true] })]; // [3, 4]

---

islice()

islice(start?, end?): IterableIterator<T>

Defined in: sorted-list.ts:236

O(√n) to locate both positional bounds + O(k) to iterate the k results.

Parameters

start?

number

end?

number

Returns

IterableIterator<T>

Example

const scores = new SortedList<number>([10, 20, 30, 40, 50]);
[...scores.islice(1, 4)]; // [20, 30, 40] — like Array.prototype.slice

---

pop()

pop(index?): T

Defined in: sorted-list.ts:143

Removes and returns the element at index (default: the last element). Negative indices count from the end, same as at.

Parameters

index?

number

Returns

T

Example

const scores = new SortedList<number>([10, 20, 30]);
scores.pop(); // 30 — last element
scores.pop(0); // 10 — first element

---

prepareSorted()

protected prepareSorted(iterable, comparator): T[]

Defined in: sorted-list.ts:53

Materializes and sorts iterable for the constructor to cut into buckets in one O(n) pass. A hook (not a field/engine access — engine isn't assigned yet when this runs) so SortedSet can additionally dedupe adjacent equal elements while still reusing this sort step.

Parameters

iterable

Iterable<T>

comparator

Comparator<T>

Returns

T[]

---

remove()

remove(value): boolean

Defined in: sorted-list.ts:115

Removes the first occurrence of value. Returns false if it wasn't present.

Parameters

value

T

Returns

boolean

Example

const scores = new SortedList<number>([1, 2, 2, 3]);
scores.remove(2); // true — removes one occurrence
scores.remove(99); // false — not present

---

update()

update(iterable): void

Defined in: sorted-list.ts:99

Bulk-inserts every value from iterable, one add at a time.

Parameters

iterable

Iterable<T>

Returns

void

Example

const scores = new SortedList<number>([3, 1]);
scores.update([2, 5, 4]);
[...scores]; // [1, 2, 3, 4, 5]

---

from()

static from<T>(iterable, ...options): SortedList<T>

Defined in: sorted-list.ts:65

A read-only iterable/array factory, paralleling Array.from.

Type Parameters

T

T

Parameters

iterable

Iterable<T>

options

...ComparatorArg<T>

Returns

SortedList<T>

Example

SortedList.from([3, 1, 2]); // same as new SortedList([3, 1, 2])