Skip to main content

Immutable Balanced OrderedMap in TypeScript

class OrderedMap<K extends OrderedMapKey, V>

Immutable Ordered Map

The OrderedMap<K, V> class stores key-value pairs where the keys have type K and the values type V. Keys can be numbers, strings, booleans, dates, or custom objects which implement the ComparableObj interface. The entries are stored in a balanced binary tree, and various methods can iterate over the entries in either ascending or descending order of keys. OrderedMap implements the typescript-builtin ReadonlyMap interface (which consists of the read-only methods of the JS builtin Map).

The OrderedMap is immutable, which means that no changes or mutations are allowed directly to the OrderedMap. Instead, modification operations such as OrderedMap.alter return a new OrderedMap which contains the result of the modification. The original OrderedMap is unchanged and can continue to be accessed and used. The OrderedMap implements this efficiently using structural sharing and does not require a full copy; indeed, the alter method will copy at most O(log n) entries.

Creating Ordered Maps​

static empty<K extends OrderedMapKey, V extends NotUndefined>(): OrderedMap<
    K,
    V
  >
#Source

Static method to create a new empty OrderedMap

The key type must extend OrderedMapKey, which consists of strings, numbers, dates, booleans, or a custom user-defined object which implements the ComparableObj interface. The ComparableObj interface allows you to create complex keys which are made up of multiple properties. Values can have any type but can not contain undefined. The value type can include null if you wish to represent missing or empty values.

While you can start with an empty OrderedMap and then use OrderedMap.set to add entries, it is more efficient to create the OrderedMap in bulk using either the static OrderedMap.from or OrderedMap.build or using various methods on LazySeq to convert a LazySeq to an OrderedMap.

static from<K extends OrderedMapKey, V extends NotUndefined>(
    items: Iterable<readonly [K, V]>,
    merge?: (v1: V, v2: V) => V
): OrderedMap<K, V>
#Source

Efficiently create a new OrderedMap from key-value pairs

from efficiently creates an OrderedMap from a sequence of key-value pairs. An optional merge function can be provided. When from detects a duplicate key, the merge function is called to determine the value associated to the key. The first parameter v1 to the merge function is the existing value and the second parameter v2 is the new value just recieved from the sequence. The return value from the merge function is the value associated to the key. If no merge function is provided, the second value v2 is used, overwriting the first value v1. If you have a LazySeq, the LazySeq.LazySeq.toOrderedMap method is an easy way to call from.

Runs in time O(n log n)

static build<K extends OrderedMapKey, V extends NotUndefined>(
    items: Iterable<V>,
    key: (v: V) => K
): OrderedMap<K, V>
#Source

Efficently create a new OrderedMap

build efficiently creates an OrderedMap from a sequence of values and a key extraction function. If a duplicate key is found, the later value is used and the earlier value is overwritten. If this is not desired, use the more generalized version of build which also provides a value extraction function.

Runs in time O(n log n)

static build<T, K extends OrderedMapKey, V extends NotUndefined>(
    items: Iterable<T>,
    key: (v: T) => K,
    val: (old: V | undefined, t: T) => V
): OrderedMap<K, V>
#Source

Efficently create a new OrderedMap

build efficiently creates an OrderedMap from a sequence of items, a key extraction function, and a value extraction function. The sequence of items can have any type T, and for each item the key is extracted. If the key does not yet exist, the val extraction function is called with undefined to retrieve the value associated to the key. If the key already exists in the OrderedMap, the val extraction function is called with the old value to merge the new item t into the existing value old.

Runs in time O(n log n)

IReadOnlyMap interface​

𝑜𝑏𝑗.size(): number
#Source

size is a readonly property containing the number of entries in the OrderedMap.

𝑜𝑏𝑗.get(k: K): V | undefined
#Source

Looks up the value associated to the given key. Returns undefined if the key is not found.

Runs in time O(log n)

𝑜𝑏𝑗.has(k: K): boolean
#Source

Checks if the key exists in the OrderedMap. Returns true if found, otherwise false

Runs in time O(log n)

𝑜𝑏𝑗.[Symbol.iterator](): IterableIterator<[K, V]>
#Source

Iterates the keys and values in the OrderedMap in ascending order of keys

This is the default iteration when using for .. of directly on the OrderedMap. It iterates all keys and values in ascinding order of keys.

𝑜𝑏𝑗.entries(): IterableIterator<[K, V]>
#Source

Iterates the keys and values in the OrderedMap in ascending order of keys

This provides an iterator for all the entries in the map in ascending order of keys. Similar to the builtin Map.entries, it can only be iterated once. Use OrderedMap.toAscLazySeq or OrderedMap.toDescLazySeq to create an iterable that can be iterated more than once.

𝑜𝑏𝑗.keys(): IterableIterator<K>
#Source

Iterates the keys in the OrderedMap in ascending order

This provides an iterator for all the keys in the map in ascending order of keys. Similar to the builtin Map.keys, it can only be iterated once. Use OrderedMap.keysToAscLazySeq or OrderedMap.keysToDescLazySeq to create an iterable that can be iterated more than once.

𝑜𝑏𝑗.values(): IterableIterator<V>
#Source

Iterates the values in the OrderedMap

This provides an iterator for all the values in the map. Despite only yielding values, the order of iteration is in ascending order of keys. Similar to the builtin Map.values, it can only be iterated once. Use OrderedMap.valuesToAscLazySeq or OrderedMap.valuesToDescLazySeq to create an iterable that can be iterated more than once.

𝑜𝑏𝑗.forEach(f: (val: V, k: K, map: OrderedMap<K, V>) => void): void
#Source

Applys a function to each entry in the OrderedMap

This applies the function f to each value and key in the hashmap. The order of iteration is by ascending order of key.

Iteration​

𝑜𝑏𝑗.foldl<T>(f: (acc: T, key: K, val: V) => T, zero: T): T
#Source

Reduce all the entries in the OrderedMap to a single value

The letter-l in foldl stands for left. Thinking of all the entries as an ascending list, foldl starts combining entries from the left side. Thus, the entry with the smallest key is combined with the zero value, which is then combined with the next smallest key, and so on.

𝑜𝑏𝑗.foldr<T>(f: (key: K, val: V, acc: T) => T, zero: T): T
#Source

Reduce all the entries in the OrderedMap to a single value

The letter-r in foldr stands for right. Thinking of all the entries as an ascending list, foldr starts combining entries from the right side. Thus, the entry with the largest key is combined with the zero value, which is then combined with the second-to-largest key, and so on.

𝑜𝑏𝑗.toAscLazySeq(): LazySeq<readonly [K, V]>
#Source

Creates a LazySeq which iterates all the entries in the OrderedMap in ascending order of keys

𝑜𝑏𝑗.keysToAscLazySeq(): LazySeq<K>
#Source

Creates a LazySeq which iterates all the keys in the OrderedMap in ascending order of keys

𝑜𝑏𝑗.valuesToAscLazySeq(): LazySeq<V>
#Source

Creates a LazySeq which iterates all the values in the OrderedMap in ascending order of keys

𝑜𝑏𝑗.toDescLazySeq(): LazySeq<readonly [K, V]>
#Source

Creates a LazySeq which iterates all the entries in the OrderedMap in descending order of keys

𝑜𝑏𝑗.keysToDescLazySeq(): LazySeq<K>
#Source

Creates a LazySeq which iterates all the keys in the OrderedMap in descending order of keys

𝑜𝑏𝑗.valuesToDescLazySeq(): LazySeq<V>
#Source

Creates a LazySeq which iterates all the values in the OrderedMap in descending order of keys

𝑜𝑏𝑗.keySet(): OrderedSet<K>
#Source

Creates an OrderedSet which contains all the keys in the OrderedMap

This function is O(1) and very fast because the backing data structure is reused. Essentially, the OrderedMap and OrderedSet classes are just two different APIs against the same underlying balanced tree. Since both OrderedSet and OrderedMap are immutable, they can both share the same underlying tree without problems.

Modification​

𝑜𝑏𝑗.set(k: K, v: V): OrderedMap<K, V>
#Source

Return a new OrderedMap with the given key set to the given value

If the key already exists and the value is === to the existing value, then the OrderedMap object instance is returned unchanged.

Runs in time O(log n)

𝑜𝑏𝑗.alter(k: K, f: (existing: V | undefined) => V | undefined): OrderedMap<K, V>
#Source

Return a new OrderedMap by inserting, modifying, or deleting the value at a given key

alter is a generalization of get, set, and delete. It can be used to insert a new entry, modify an existing entry, or delete an existing entry. alter first looks for the key in the map. The function f is then applied to the existing value if the key was found and undefined if the key does not exist. If the function f returns undefined, the entry is deleted and if f returns a value, the entry is updated to use the new value.

If the key is not found and f returns undefined or the key exists and the function f returns a value === to the existing value, then the OrderedMap object instance is returned unchanged.

Runs in time O(log n)

𝑜𝑏𝑗.delete(k: K): OrderedMap<K, V>
#Source

Return a new OrderedMap with the given key removed (if it exists)

If the key does not exist, then the OrderedMap object instance is returned unchanged.

Runs in time O(log n)

Transformation​

𝑜𝑏𝑗.partition(f: (k: K, v: V) => boolean): readonly [OrderedMap<K, V>, OrderedMap<K, V>]
#Source

Split an OrderedMap into two OrderedMaps based on a function

The function f is applied to each key and value. The entries for which f returns true are placed in one OrderedMap and entries for which f returns false are placed in the other. The two OrderedMaps are returned as a tuple, with the true ordered map returned as the first element of the tuple.

If the function f returns true for all entries, then the first OrderedMap object instance is guaranteed to be === to the this object instance. Similar for if f returns false for all entries.

This runs in O(n) time.

𝑜𝑏𝑗.mapValues<V2>(f: (v: V, k: K) => V2): OrderedMap<K, V2>
#Source

Transform the values in the OrderedMap using a function

mapValues applies the function f to each value and key in the OrderedMap and returns a new OrderedMap with the same keys but the values adjusted to the result of the function f. This can be done efficiently because the keys are unchanged the arrangement of the tree is unchanged. If you wish to transform both the keys and the values, either use OrderedMap.toAscLazySeq, map the lazy sequence, and then convert the lazy sequence back to an OrderedMap or use OrderedMap.adjust to bulk-adjust keys.

mapValues guarantees that if no values are changed, then the OrderedMap object instance is returned unchanged.

This runs in O(n) time.

𝑜𝑏𝑗.collectValues<V2>(f: (v: V, k: K) => V2 | null | undefined): OrderedMap<K, V2>
#Source

Transform or delete the values in the OrderedMap using a function

collectValues applies the function f to each value and key in the OrderedMap. If f returns null or undefined, the key and value is removed. Otherwise, the returned value from f is used as the new value associated to the key k. This can be done efficiently because the keys are unchanged the arrangement of the tree is unchanged. If you wish to transform both the keys and the values, either use OrderedMap.toAscLazySeq, map the lazy sequence, and then convert the lazy sequence back to an OrderedMap or use OrderedMap.adjust to change many keys in bulk.

collectValues guarantees that if no values are changed, then the OrderedMap object instance is returned unchanged.

This runs in O(n) time.

𝑜𝑏𝑗.filter(f: (v: V, k: K) => boolean): OrderedMap<K, V>
#Source

Remove entries from the OrderedMap that return false from a predicate

filter applies the function f to each value and key in the OrderedMap. If f returns false, the key is removed. filter guarantees that if no values are removed, then the OrderedMap object instance is returned unchanged.

This runs in O(n) time.

𝑜𝑏𝑗.split(k: K): {
    readonly below: OrderedMap<K, V>;
    readonly val: V | undefined;
    readonly above: OrderedMap<K, V>;
  }
#Source

Split an OrderedMap into the entries below a key, the value for a key, and the entries above a key

split returns an object with three properties. below is an OrderedMap with all the entries which have key less than the provided key k. If the provided key k exists in the OrderedMap, the returned val property contains the value associated with the key k. Otherwise, val is undefined. Finally, the above property consists of all the entries in the OrderedMap with keys greater than k.

This runs in time O(log n) so is efficient.

𝑜𝑏𝑗.transform<U>(f: (s: OrderedMap<K, V>) => U): U
#Source

Apply a function to the OrderedMap

Applies the provided function f to this and returns the result. This is a convenience function which allows you to continue to chain operations without having to create a new temporary variable.

Min/Max Keys​

𝑜𝑏𝑗.lookupMin(): readonly [K, V] | undefined
#Source

Find the minimum key and associated value in the OrderedMap

In O(log n) time, find the minimum key. Returns undefined if the OrderedMap is empty.

𝑜𝑏𝑗.lookupMax(): readonly [K, V] | undefined
#Source

Find the maximum key and associated value in the OrderedMap

In O(log n) time, find the maximum key. Returns undefined if the OrderedMap is empty.

𝑜𝑏𝑗.deleteMin(): OrderedMap<K, V>
#Source

Remove the minimum key and return the resulting OrderedMap

In O(log n) time, find and remove the minimum key.

𝑜𝑏𝑗.deleteMax(): OrderedMap<K, V>
#Source

Remove the maximum key and return the resulting OrderedMap

In O(log n) time, find and remove the maximum key.

𝑜𝑏𝑗.minView():
    | { readonly minKey: K; readonly minVal: V; readonly rest: OrderedMap<K, V> }
    | undefined
#Source

Lookup and remove the minimum key

In O(log n) time, find and remove the minimum key. The minimum key, the asscoiated value, and the result of removing the minimum key are returned. If the original OrderedMap is empty, undefined is returned.

𝑜𝑏𝑗.maxView():
    | { readonly maxKey: K; readonly maxVal: V; readonly rest: OrderedMap<K, V> }
    | undefined
#Source

Lookup and remove the maximum key

In O(log n) time, find and remove the maximum key. The maximum key, the asscoiated value, and the result of removing the maximum key are returned. If the original OrderedMap is empty, undefined is returned.

Bulk Modification​

𝑜𝑏𝑗.union(
    other: OrderedMap<K, V>,
    merge?: (vThis: V, vOther: V, k: K) => V
): OrderedMap<K, V>
#Source

Returns a new OrderedMap which combines all entries in two OrderedMaps

union produces a new OrderedMap which contains all the entries in both OrderedMaps. If a key appears in only one of the two maps, the value from the map is used. If a key appears in both maps, the provided merge function is used to determine the value. If the merge function is not specified, the value from other is used.

union guarantees that if the resulting OrderedMap is equal to this, then the OrderedMap object instance is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller map and n is the size of the larger map.

static union<K extends OrderedMapKey, V extends NotUndefined>(
    merge: (v1: V, v2: V, k: K) => V,
    ...maps: readonly OrderedMap<K, V>[]
): OrderedMap<K, V>
#Source

Create a new OrderedMap which combines all entries in a sequence of OrderedMaps

OrderedMap.union is the static version of OrderedMap.union and allows unioning more than two OrderedMaps at once. It produces a new OrderedMap which contains all the entries in all the OrderedMaps. If a key appears in only one of the maps, the value from that map is used. If a key appears in multiple maps, the provided merge function is used to determine the value. The order of merging is equivalent to the order of maps in the sequence.

union guarantees that if the resulting OrderedMap is equal to the first non-empty OrderedMap in the sequence, then the OrderedMap object instance is returned unchanged.

𝑜𝑏𝑗.intersection(
    other: OrderedMap<K, V>,
    merge?: (vThis: V, vOther: V, k: K) => V
): OrderedMap<K, V>
#Source

Returns a new OrderedMap which contains only entries whose keys are in both OrderedMaps

intersection produces a new OrderedMap which contains all the entries which have keys in both OrderedMaps. For each such entry, the merge function is used to determine the resulting value. If the merge function is not specified, the value from the other is used.

intersection guarantees that if the resulting OrderedMap is equal to this, then the OrderedMap object instance is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller map and n is the size of the larger map.

static intersection<K extends OrderedMapKey, V extends NotUndefined>(
    merge: (v1: V, v2: V, k: K) => V,
    ...maps: readonly OrderedMap<K, V>[]
): OrderedMap<K, V>
#Source

Returns a new OrderedMap which contains only entries whose keys are in all OrderedMaps

OrderedMap.intersection is a static version of OrderedMap.intersection, and produces a new OrderedMap which contains the entries which have keys in all specified OrderedMaps. For each such entry, the merge function is used to determine the resulting value.

intersection guarantees that if the resulting OrderedMap is equal to the first non-empty OrderedMap, then the OrderedMap object instance is returned unchanged.

𝑜𝑏𝑗.difference<V2>(other: OrderedMap<K, V2>): OrderedMap<K, V>
#Source

Returns a new OrderedMap which contains only keys which do not appear in the provided OrderedMap

difference produces a new OrderedMap which contains all the entries in this where the key does not exist in the provided other OrderedMap. Can think of this as this - other where the subtraction is removing all the keys in other from this. The values of the other OrderedMap are ignored and can be any value V2.

difference guarantees that if no entries are removed from this, then the OrderedMap object instance is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller map and n is the size of the larger map.

𝑜𝑏𝑗.symmetricDifference(other: OrderedMap<K, V>): OrderedMap<K, V>
#Source

Returns an OrderedMap which contains only entries whose key appear in exactly one of the two maps

symmetricDifference produces a new OrderedMap which contains all the entries whose keys appear in exactly one of this and other. If other is empty, this is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller map and n is the size of the larger map.

𝑜𝑏𝑗.withoutKeys(other: OrderedSet<K>): OrderedMap<K, V>
#Source

Returns a new OrderedMap which contains only keys which do not appear in the provided OrderedSet

withoutKeys produces a new OrderedMap which contains all the entries in this where the key does not exist in the provided keys OrderedSet. withoutKeys guarantees that if no entries are removed from this, then the OrderedMap object instance is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller map and n is the size of the larger map.

𝑜𝑏𝑗.adjust<V2>(
    keysToAdjust: OrderedMap<K, V2>,
    adjustVal: (existingVal: V | undefined, helperVal: V2, k: K) => V | undefined
): OrderedMap<K, V>
#Source

Return a new OrderedMap which adjusts all the provided keys with a specified modification function.

adjust is passed an OrderedMap of keys to adjust associated to helper values of type V2 (the type V2 can be anything). For each key to modify, adjust then calls the adjustVal function with the current existing value in the OrderedMap (or undefined if the key does not exist) and the helper value associated with the key. The return value is set as the new value for the key, or removed if the return value is undefined.

adjust is equivalent to the following code, but is much more efficient since adjust can perform the operation in a single pass through the tree.

const m = this;
for (const [k, v2] of keysToAdjust) {
  const v = m.get(k);
  const newV = adjustVal(v, v2, k);
  if (newV === undefined) {
    m = m.delete(k);
  } else {
    m = m.set(k, newV);
  }
}
return m;

adjust guarantees that if no entries are changed from this, then the OrderedMap object instance is returned unchanged.

Runs in time O(n + m) where n and m are the sizes of this OrderedMap and the keysToAdjust OrderedMap.