Class SortedMap<K, V, C>

SortedMap is a sorted mutable mapping.

SortedMap keys are maintained in sorted order. The design of SortedMap is simple: SortedMap maintains a sorted array of keys and an array of values in parallel. It does not use the native Map type at all.

SortedMap is compatible with Map. A SortedMap can be used wherever a Map is expected, as long as the code relies on duck typing. SortedMap does not actually inherit Map, however.

SortedMap keys must have a total ordering. They are compared using the provided comparator function only; they do not have to be the same object to be considered equal. The total ordering of keys must not change while they are stored in the SortedMap.

Map methods and properties:

SortedMap#get
SortedMap#has
SortedMap#set
SortedMap#delete
SortedMap#clear
SortedMap#forEach
SortedMap#[Symbol.iterator]
SortedMap#keys
SortedMap#values
SortedMap#entries
SortedMap#size

Additional methods for adding items:

SortedMap#upsert
SortedMap#update

Additional methods for removing items:

SortedMap#popKey
SortedMap#popEntry

Additional methods for looking up items:

SortedMap#entryAt

Miscellaneous methods:

SortedMap#clone

SortedArray methods available (applies to keys):

SortedMap#at
SortedMap#bisectLeft
SortedMap#bisectRight
SortedMap#deleteAt
SortedMap#deleteSlice
SortedMap#indexOf
SortedMap#irange
SortedMap#islice

Type Parameters

K extends C
The type of keys.
V
The type of values.
C = K
Part of the key that the comparator function sees.

Hierarchy

AbstractSortedArray<K, C>
- SortedMap

Index

Constructors

constructor

new SortedMap<K, V, C = K>(
iterable?: Iterable<[K, V], any, any>,
options?: SortedArrayConstructorOptions<C>,
): SortedMap<K, V, C>
Initialize a SortedMap instance, optionally with the given key-value pairs.
Type Parameters
- K
- V
- C = K
Parameters
- Optionaliterable: Iterable<[K, V], any, any>
  Optional iterable argument provides an initial sequence of pairs to initialize the SortedMap. Each pair in the sequence defines the key and corresponding value. If a key is seen more than once, the first key and the last value is stored in the SortedMap.
- Optionaloptions: SortedArrayConstructorOptions<C>
  An object that specifies characteristics about the sorted container.
Returns SortedMap<K, V, C>
Example
```
// All of these construct a SortedMap {'alpha' => 1, 'beta' => 2}
new SortedMap([['alpha', 1], ['beta', 2]])
new SortedMap(Object.entries({alpha: 1, beta: 2}))

const m = new Map();
m.set('alpha', 1);
m.set('beta', 2);
new SortedMap(m)
```
Overrides AbstractSortedArray<K, C>.constructor
- Defined in sorted-map.ts:91

Properties

`Static`DEFAULT_LOAD_FACTOR

DEFAULT_LOAD_FACTOR: number = 1000

The default load factor. Override it with option loadFactor at construction time.

Accessors

size

get size(): number
Returns number
The number of entries in the SortedMap.
- Defined in sorted-map.ts:101

Methods

_iter

_iter(): IteratorObject<K, undefined, unknown>
Return an iterator over the sorted container.

Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.

Returns IteratorObject<K, undefined, unknown>
Inherited from AbstractSortedArray._iter
- Defined in abstract-sorted-array.ts:582

[iterator]

"[iterator]"(): MapIterator<[K, V]>
An alias for entries.

Returns MapIterator<[K, V]>
- Defined in sorted-map.ts:235

at

at(index: number): undefined | K
Lookup value at index in sorted container.

If index is out of range, returns undefined.
Parameters
- index: number
  The zero-based index of the desired code unit. A negative index will count back from the last item.
Returns undefined | K
The item located at the specified index, or undefined if index out of range.
Example
```
const sl = new SortedList('abcde');
sl.at(1) // 'b'
sl.at(-1) // 'e'
sl.at(7) // undefined
```
Inherited from AbstractSortedArray.at
- Defined in abstract-sorted-array.ts:552

bisectLeft

bisectLeft(key: C): number
Return an index to insert key in the SortedMap.

If the key is already present, the insertion point will be the index of that entry.
Parameters
- key: C
  Key to find the insertion point of.
Returns number
Insertion index of key in the SortedMap.
Example
```
const sd = new SortedMap([[10, 4], [11, 2], [12, 6], [13, 2], [14, 4]]);
sd.bisectLeft(12) // 2
```
Inherited from AbstractSortedArray.bisectLeft
- Defined in sorted-map.ts:480

bisectRight

bisectRight(key: C): number
Return an index to insert key in the SortedMap.

Similar to bisectLeft, but if value is already present, the insertion point will be after (to the right of) the existing entry.
Parameters
- key: C
  Key to find the insertion point of.
Returns number
Insertion index of key in the SortedMap.
Example
```
const sd = new SortedMap([[10, 4], [11, 2], [12, 6], [13, 2], [14, 4]]);
sl.bisectRight(12) // 3
```
Inherited from AbstractSortedArray.bisectRight
- Defined in sorted-map.ts:494

clear

clear(): void
Remove all items from the SortedMap.

Returns void
Overrides AbstractSortedArray.clear
- Defined in sorted-map.ts:194

clone

clone(): this
Return a shallow copy of the SortedMap.

Returns this
A new SortedMap instance.
Overrides AbstractSortedArray.clone
- Defined in sorted-map.ts:244

delete

delete(value: C): boolean
Remove one value from sorted container if it is a member.

If value is not a member, do nothing.
Parameters
- value: C
  Value to discard from SortedArray.
Returns boolean
Returns true if an element in the SortedArray existed and has been removed, or false if the element does not exist.
Example
```
const sl = new SortedArray([1, 2, 3, 4, 5])
sl.delete(5)
sl.delete(0)
Array.from(sl) // [1, 2, 3, 4]
```
Inherited from AbstractSortedArray.delete
- Defined in abstract-sorted-array.ts:178

deleteAt

deleteAt(index: number): undefined | K
Remove and return value at index in sorted container.

If the sorted container is empty or index is out of range, undefined is returned and the sorted container is not modified.

Negative indices count back from the last item.
Parameters
- index: number
  Index of value. Negative integers count back from the last item in the array.
Returns undefined | K
The removed value or undefined.
Example
```
const sl = new SortedArray('abcde');
sl.deleteAt(-1) // 'e'
sl.deleteAt(2) // 'c'
sl // SortedArray ['a', 'b', 'd']
```
Inherited from AbstractSortedArray.deleteAt
- Defined in abstract-sorted-array.ts:413

deleteSlice

deleteSlice(start?: number, end?: number): void
Removes elements from sorted container by index.
Parameters
- start: number = 0
  The zero-based location in the array from which to start removing elements. Negative integers count back from the last item in the array.
- end: number = ...
  The zero-based location in the array at which to stop removing elements. Negative integers count back from the last item in the array. Elements up to but not including end are removed.
Returns void
Example
```
const sl = new SortedArray('abcde');
sl.deleteSlice(0, 2);
sl // SortedArray ['c', 'd', 'e']
```
Overrides AbstractSortedArray.deleteSlice
- Defined in sorted-map.ts:215

entries

entries(): MapIterator<[K, V]>
Return an iterator of key-value pairs over the SortedMap.

The returned iterator yields the same object on every iteration to save allocations, so you must unpack the pair before calling .next().

Iterating a SortedMap while adding or deleting elements may throw an error or silently fail to iterate over all entries. This is different from the native Map.

Returns MapIterator<[K, V]>
- Defined in sorted-map.ts:286

entryAt

entryAt(index?: number): undefined | [K, V]
Return [key, value] pair at index from the SortedMap.

Optional argument index defaults to -1, the last item in the SortedMap. Specify index to be 0 for the first item in the sorted dict.

If the index is out of range, returns undefined.
Parameters
- index: number = -1
  Index of item (default -1).
Returns undefined | [K, V]
Key and value pair.
Example
```
const sd = new SortedMap([['a', 1], ['b', 2], ['c', 3]]);
sd.entryAt() // ['c', 3]
sd.entryAt(0) // ['a', 1]
sd.entryAt(100) // undefined
```
- Defined in sorted-map.ts:419

find

find(value: C): undefined | K
Return the first element in the sorted container that is equal to the provided value. If it is not found, undefined is returned.

With the default comparator and primitive elements, this method does not tell anything beyond whether the value exists in the sorted container. However, it can turn out to be useful with a custom comparator.
Parameters
- value: C
  The value to find.
Returns undefined | K
Example
```
const sl = new SortedArray(
  [
    { id: 1, value: 'one' },
    { id: 2, value: 'two' },
    { id: 3, value: 'three' },
  ],
  { comparator: (a, b) => a.id - b.id }
);
sl.find({ id: 2 }) // { id: 2, value: 'two' }
```
Inherited from AbstractSortedArray.find
- Defined in abstract-sorted-array.ts:935

forEach

forEach(
fn: (value: V, key: K, map: SortedMap<K, V>) => void,
thisArg?: any,
): void
Executes a callback function once for each key-value pair in a SortedMap.
Parameters
- fn: (value: V, key: K, map: SortedMap<K, V>) => void
  The function to execute.
- OptionalthisArg: any
  An object to which the this keyword can refer in the callback function. If thisArg is omitted, undefined is used.
Returns void
- Defined in sorted-map.ts:257

get

get(key: C): undefined | V
Get the value associated with the key, returning undefined if key is not found.
Parameters
- key: C
  The key to look up.
Returns undefined | V
- Defined in sorted-map.ts:117
get<R>(key: C, defaultValue: R): V | R
Get the value associated with the key, with defaultValue as a fallback.
Type Parameters
- R
Parameters
- key: C
  The key to look up.
- defaultValue: R
  The value to return if no value is associated with the key.
Returns V | R
- Defined in sorted-map.ts:124

has

has(key: C): boolean
Parameters
- key: C
Returns boolean
A boolean value indicating whether an entry with the specified key exists or not.
- Defined in sorted-map.ts:108

indexOf

indexOf(key: C, start?: number, end?: number): number
Return the index of key in the SortedMap, or -1 if key is not present.

Index must be between start and end for the key to be considered present. Negative indices count back from the last item.
Parameters
- key: C
  Key in SortedMap.
- Optionalstart: number
  The index at which to start the search (default 0).
- Optionalend: number
  The index at which to end the search (default length).
Returns number
The index of the occurrence of key in the sorted container, or -1 if it is not present.
Example
```
const sl = new SortedMap([['a', 1], ['b', 2], ['c', 4]]);
sl.indexOf('c') // 2
sl.indexOf('z') // -1
```
Inherited from AbstractSortedArray.indexOf
- Defined in sorted-map.ts:512

irange

irange(
    minimum?: C,
    maximum?: C,
    includeMinimum?: boolean,
    includeMaximum?: boolean,
    reverse?: boolean,
): IteratorObject<K, undefined, unknown>
Create an iterator of values between minimum and maximum.

Both minimum and maximum default to undefined which is automatically inclusive of the beginning and end of the sorted container.

The argument includeMinimum and includeMaximum is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. Both arguments default to true such that the range is inclusive of both minimum and maximum.

When reverse is true the values are yielded from the iterator in reverse order; reverse defaults to false.

Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.
Parameters
- Optionalminimum: C
  Minimum value to start iterating.
- Optionalmaximum: C
  Maximum value to stop iterating.
- includeMinimum: boolean = true
  Whether the minimum ought to be included in the range.
- includeMaximum: boolean = true
  Whether the maximum ought to be included in the range.
- reverse: boolean = false
  Whether to yield values in reverse order.
Returns IteratorObject<K, undefined, unknown>
Iterator.
Example
```
const sl = new SortedArray('abcdefghij');
const it = sl.irange('c', 'f');
Array.from(it) // ['c', 'd', 'e', 'f']
```
Inherited from AbstractSortedArray.irange
- Defined in abstract-sorted-array.ts:729

islice

islice(
    start?: number,
    end?: number,
    reverse?: boolean,
): IteratorObject<K, undefined, unknown>
Return an iterator that slices sorted container from start to end.

The start and end index are treated inclusive and exclusive, respectively.

A negative index will count back from the last item.

Both start and end default to undefined which is automatically inclusive of the beginning and end of the sorted container.

When reverse is true the values are yielded from the iterator in reverse order; reverse defaults to false.

Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.
Parameters
- start: number = 0
  Start index (inclusive).
- end: number = ...
  Stop index (exclusive).
- reverse: boolean = false
  Whether to yield values in reverse order.
Returns IteratorObject<K, undefined, unknown>
Iterator.
Example
```
const sl = new SortedArray('abcdefghij');
const it = sl.islice(2, 6);
Array.from(it) // ['c', 'd', 'e', 'f']
```
Inherited from AbstractSortedArray.islice
- Defined in abstract-sorted-array.ts:622

keys

keys(): MapIterator<K>
Return an iterator of the SortedMap's keys.

Iterating a SortedMap while adding or deleting elements may throw an error or silently fail to iterate over all entries. This is different from the native Map.

Returns MapIterator<K>
- Defined in sorted-map.ts:273

pop

pop(): undefined | K
Remove the last element from the sorted container and return it. If the sorted container is empty, undefined is returned and the sorted container is not modified.

Returns undefined | K
Popped value or undefined.
Example
```
const sl = new SortedArray('abcde');
sl.pop() // 'e'
sl.pop() // 'd'
sl // SortedArray ['a', 'b', 'c']
```
Inherited from AbstractSortedArray.pop
- Defined in abstract-sorted-array.ts:862

popEntry

popEntry(index?: number): undefined | [K, V]
Remove and return [key, value] pair at index from the SortedMap.

Optional argument index defaults to -1, the last item in the SortedMap. Specify index to be 0 for the first item in the sorted dict.

If the index is out of range, returns undefined.
Parameters
- index: number = -1
  Index of item (default -1).
Returns undefined | [K, V]
Key and value pair.
Example
```
const sd = new SortedMap([['a', 1], ['b', 2], ['c', 3]]);
sd.popEntry() // ['c', 3]
sd.popEntry(0) // ['a', 1]
sd.popEntry(100) // undefined
```
- Defined in sorted-map.ts:396

popKey

popKey(key: C): undefined | V
Remove and return value for the item identified by key.

If the key is not found then return undefined.
Parameters
- key: C
  Key for item.
Returns undefined | V
Value for item or undefined.
Example
```
const sd = new SortedMap([['a', 1], ['b', 2], ['c', 3]]);
sd.popKey('c') // 3
sd.popKey('y') // undefined
```
- Defined in sorted-map.ts:357
popKey<R>(key: C, defaultValue: R): V | R
Remove and return value for the item identified by key.

If the key is not found then return defaultValue.
Type Parameters
- R
Parameters
- key: C
  Key for item.
- defaultValue: R
  Default value if key not found.
Returns V | R
Value for item.
Example
```
const sd = new SortedMap([['a', 1], ['b', 2], ['c', 3]]);
sd.popKey('c', 26) // 3
sd.popKey('z', 26) // 26
```
- Defined in sorted-map.ts:372

reversed

reversed(): IteratorObject<K, undefined, unknown>
Return a reverse iterator over the sorted container.

Iterating a sorted container while adding or deleting elements may throw an error or silently fail to iterate over all elements.

Returns IteratorObject<K, undefined, unknown>
Inherited from AbstractSortedArray.reversed
- Defined in abstract-sorted-array.ts:593

set

set(key: K, value: V): this
Store an entry in SortedMap with key and corresponding value. Keep the key but overwrite the value if the key already has an associated value.
Parameters
- key: K
  Key for entry.
- value: V
  Value for entry.
Returns this
Example
```
const sd = new SortedMap();
sd.set('c', 3);
sd.set('a', 1);
sd.set('b', 2);
sd // SortedMap {'a' => 1, 'b' => 2, 'c' => 3}
```
- Defined in sorted-map.ts:149

shift

shift(): undefined | K
Remove the first element from the sorted container and return it. If the sorted container is empty, undefined is returned and the sorted container is not modified.

Returns undefined | K
Shifted value or undefined.
Example
```
const sl = new SortedArray('abcde');
sl.shift() // 'a'
sl.shift() // 'b'
sl // SortedArray ['c', 'd', 'e']
```
Inherited from AbstractSortedArray.shift
- Defined in abstract-sorted-array.ts:846

slice

slice(start?: number, end?: number): K[]
Returns a copy of a section of sorted container as an ordinary Array.

For both start and end, a negative index can be used to indicate an offset from the end of the array.
Parameters
- start: number = 0
  The beginning index of the specified portion of the array. If start is undefined, then the slice begins at index 0.
- end: number = ...
  The end index of the specified portion of the array. This is exclusive of the element at the index end. If end is undefined, then the slice extends to the end of the array.
Returns K[]
Inherited from AbstractSortedArray.slice
- Defined in abstract-sorted-array.ts:502

toJSON

toJSON(): K[]
Return sorted container as an ordinary Array.

Returns K[]
Inherited from AbstractSortedArray.toJSON
- Defined in abstract-sorted-array.ts:950

toString

toString(): string
Return a string representation of sorted container.

Returns string
Inherited from AbstractSortedArray.toString
- Defined in abstract-sorted-array.ts:957

update

update(other: Iterable<[K, V]>): void
Update SortedMap with entries from other.

Overwrites existing items.

other argument may be a Map, a SortedMap, an iterable of pairs. See constructor for details.
Parameters
- other: Iterable<[K, V]>
  Iterable of pairs.
Returns void
Overrides AbstractSortedArray.update
- Defined in sorted-map.ts:459

upsert

upsert(key: K, defaultValue: V): V
Return the value for the entry identified by key in the SortedMap.

If key is in the SortedMap then return its value. If key is not in the SortedMap then insert key with value default and return default.
Parameters
- key: K
  Key of the entry.
- defaultValue: V
  Value of the entry if the entry does not exist.
Returns V
Value of the entry after potential insertion.
Example
```
const sd = new SortedMap();
sd.upsert('a', 1) // 1
sd.upsert('a', 10) // 1
sd // SortedMap {'a' => 1}
```
- Defined in sorted-map.ts:441

values

values(): MapIterator<V>
Return an iterator of the SortedMap's values.

Iterating a SortedMap while adding or deleting elements may throw an error or silently fail to iterate over all entries. This is different from the native Map.

Returns MapIterator<V>
- Defined in sorted-map.ts:319

Class SortedMap<K, V, C>

Type Parameters

Hierarchy

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns SortedMap<K, V, C>

Example

Properties

StaticDEFAULT_LOAD_FACTOR

Accessors

size

Returns number

Methods

_iter

Returns IteratorObject<K, undefined, unknown>

[iterator]

Returns MapIterator<[K, V]>

at

Parameters

Returns undefined | K

Example

bisectLeft

Parameters

Returns number

Example

bisectRight

Parameters

Returns number

Example

clear

Returns void

clone

Returns this

delete

Parameters

Returns boolean

Example

deleteAt

Parameters

Returns undefined | K

Example

deleteSlice

Parameters

Returns void

Example

entries

Returns MapIterator<[K, V]>

entryAt

Parameters

Returns undefined | [K, V]

Example

find

Parameters

Returns undefined | K

Example

forEach

Parameters

Returns void

get

Parameters

Returns undefined | V

Type Parameters

Parameters

Returns V | R

has

Parameters

Returns boolean

indexOf

Parameters

Returns number

Example

irange

Parameters

`Static`DEFAULT_LOAD_FACTOR