containers

Here are some useful container datastructures written in Typescript.

HAMT (Hash Array Mapped Trie)

A persistent map datastructure with string keys. The main reason to use this over JavaScript's default Map type is if you need a datastructure which is immutable. That is, updating the map produces a new map. However, this datastructure implements some structural sharing so that only a portion of the map needs to be copied on each update.

Method	Description
new HAMT()	Construct a new HAMT.
size: number	Get the number of elements in the map.
get(key: string): V | undefined	Retrieve a value from the map (or undefined if no such key exists).
set(key: string, value: V): HAMT<V>	Associate a key-value pair in the map, returning a new map, containing the given key. If the key already exists in the map, its value is replaced in the resulting map.

Red-Black Tree

A mutable key-value map datastructure. The main reason to use this over JavaScript's default Map type is that you can define your own key ordering, enabling structural comparisons of the key.

Method	Description
new RBTree(compareFn?: CompareFn<K>)	Construct a new RBTree, optionally providing a comparison function on keys.
has(key: K): boolean	Check if the map contains a value with the given key.
get(key: K): V | undefined	Retrieve a value by its key, returning undefined if the value isn't in the map.
set(key: K, value: V): RBTree<K, V>	Associate a key with a value. If the key is already associated with a value, the value is updated.
delete(key: K): boolean	Delete a key and its associated value from the map. If the key does not exist in the map, this is a no-op.
size: number	Get the number of elements in the map.
*entries(): IterableIterator<[K, V]>	Iterate over the keys and values of the map from least to greatest key.

Interval Tree

A mutable interval tree which can associate a value for each interval. We can consider this another key-value map datastructure, where the keys are specialized to intervals. This affords us a search method which returns all of the values which intersect a given query interval.

Method	Description
new IntervalTree()	Construct a new IntervalTree
has(interval: Interval)	Check if the interval tree contains a value with the given interval.
get(interval: Interval): V | undefined	Retrieve a value by its interval, returning undefined if the value isn't in the map.
set(interval: Interval, value: V): IntervalTree<V>	Associate an interval with a value. If the interval already exists within the map, then the value at the interval is replaced.
delete(interval: Interval): boolean	Delete an interval and its associated value from the tree. If the interval does not exist in the map, this is a no-op.
*search(query: Interval): IterableIterator<V>	Find all of the values which intersect the given interval.
size: number	Get the number of elements in the map.
*entries(): IterableIterator<[K, V]>	Iterate over the keys and values of the map from least to greatest key.

Contributing

Feedback and pull requests are welcome!