An implementation of an ordered map in JS.
Modern JS supports Map object, which is useful in a lot of cases as a fast associative key - value storage. However, it doesn't support ordering by keys. OrderedMap adds this functionality, it supports all the methods that a normal Map has and is compatible with it, with the only limitation that the iteration is not guaranteed to be correct when the map is modified during iteration (this is a performance and memory usage tradeoff, I might work on this in the future).
It adds additional functionality that keeps the keys ordered.
-
constructor()
The OrderedMap constructor.
constructor() constructor(iterable) constructor(comparatorFn) constructor(iterable, comparatorFn)
iterable
is an Array or other iterable object whose elements are key-value pairs. (For example, arrays with two elements, such as[[ 1, 'one' ],[ 2, 'two' ]]
).comparatorFn
is a custom function that determines the order of the elements, it works exactly like the passed callback in Array.prototype.sort().If the only argument is a function (
typeof arg === 'function'
) it will be recognized as comparator, otherwise as an iterator.
-
size
The number of elements in this map.
-
has(key)
Checks if a given key exists in the map. Returns
true
if present orfalse
if not.
-
get(key)
Searches for a given key. Returns the associated value if present or
undefined
if not.
-
set(key, value)
Associates the given key with value. Returns the map object itself.
-
getNth(index)
Searches for a value with its key ordering index. Returns the value if present or
undefined
if not. Ifindex
is negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.).
-
getNthKey(index)
Searches for a key with an ordering index. Returns the key if present or
undefined
if not. Ifindex
is negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.).
-
getNthEntry(index)
Searches for a
[key, value]
pair with an ordering index. Returns the pair if present orundefined
if not. Ifindex
is negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.).
-
getIndex(key)
getIndex(key) getIndex(key, isUpperBound)
Returns the index of the closest less or equal key or the greater or equal key. If no such key is found
-1
is returned.key
is the searched key.isUpperBound
isfalse
by default. If it isfalse
the closest less or equal key index is searched, otherwise the greater or equal key index.
count
is the maximum number of keys that should be taken, if omitted all the available keys are taken. Ifcount
is negative the iteration order is reversed from the starting index.
-
getClosestKey(key)
getClosestKey(key) getClosestKey(key, isUpperBound) getClosestKey(key, isUpperBound, canMatch)
Searches for the closest key. Returns the closest key if it exists or
undefined
if not.key
is the key that the closest key is searched for.isUpperBound
isfalse
by default. If it isfalse
the closest less or equal key is searched, otherwise the greater or equal closest key.canMatch
istrue
by default. If it'sfalse
only strictly smaller or greater keys are searched.
-
getClosestValue(key)
getClosestValue(key) getClosestValue(key, isUpperBound) getClosestValue(key, isUpperBound, canMatch)
Searches for the closest key. Returns the associated value if the key exists or
undefined
if not.key
is the key that the closest key is searched for.isUpperBound
isfalse
by default. If it isfalse
the closest less or equal key is searched, otherwise the greater or equal closest key.canMatch
istrue
by default. If it'sfalse
only strictly smaller or greater keys are searched.
-
getClosestEntry(key)
getClosestEntry(key) getClosestEntry(key, isUpperBound) getClosestEntry(key, isUpperBound, canMatch)
Searches for the closest key. Returns the associated entry (
[key, value]
pair) if the key exists orundefined
if not.key
is the key that the closest key is searched for.isUpperBound
isfalse
by default. If it isfalse
the closest less or equal key is searched, otherwise the greater or equal closest key.canMatch
istrue
by default. If it'sfalse
only strictly smaller or greater keys are searched.
-
delete(key)
Deletes the key and the associated value from the map. Returns
true
if the key existed right before calling this method orfalse
if not.
-
clear()
Clears the map.
-
keys()
keys() keys(startIndex) keys(startIndex, count)
Returns an iterator for the keys.
startIndex
is the first key order index that the iteration should start from, by default it's0
. If it's negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.). Note that this still doesn't reverse the iteration order.count
is the maximum number of keys that should be taken, if omitted all the available keys are taken. Ifcount
is negative the iteration order is reversed from the starting index.
-
values()
values() values(startIndex) values(startIndex, count)
Returns an iterator for the values.
startIndex
is the first value associated key order index that the iteration should start from, by default it's0
. If it's negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.). Note that this still doesn't reverse the iteration order.count
is the maximum number of values that should be taken, if omitted all the available values are taken. Ifcount
is negative the iteration order is reversed from the starting index.
-
entries()
entries() entries(startIndex) entries(startIndex, count)
Returns an iterator for the entries (
[key, value]
pairs).startIndex
is the first entry associated key order index that the iteration should start from, by default it's0
. If it's negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.). Note that this still doesn't reverse the iteration order.count
is the maximum number of entries that should be taken, if omitted all the available entries are taken. Ifcount
is negative the iteration order is reversed from the starting index.
-
forEach(callbackFn)
forEach(callbackFn) forEach(callbackFn, thisArg) forEach(callbackFn, thisArg, startIndex) forEach(callbackFn, thisArg, startIndex, count)
Executes a provided function once per each key/value pair in this map.
callbackFn(value, key, map)
is a function to execute for each entry in the map.value
is the value of each iteration.key
is the key of each iteration.map
is the map being iterated.startIndex
is the first entry associated key order index that the iteration should start from, by default it's0
. If it's negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.). Note that this still doesn't reverse the iteration order.count
is the maximum number of entries that should be taken, if omitted all the available entries are taken. Ifcount
is negative the iteration order is reversed from the starting index.
-
groupBy()
groupBy(iterable, callbackFn) groupBy(iterable, callbackFn, comparatorFn)
Groups the elements of a given iterable using the values returned by a provided callback function. The final returned OrderedMap uses the unique values from the test function as keys, which can be used to get the array of elements in each group.
iterable
is an iterable (such as an Array) whose elements will be grouped.callbackFn(element, index)
is a function to execute for each element in the iterable. It should return a value (object or primitive) indicating the group of the current element.element
is current element being processed.index
is the index of the current element being processed.comparatorFn
is a custom function that determines the order of the elements, it works exactly like the passed callback in Array.prototype.sort().
Operation | Complexity |
---|---|
Search | log(n) |
Insertion | log(n) |
Deletion | log(n) |
Construction from generic iterable / groupBy() | n * log(n) |
Construction from another OrderedMap (with the same comparator) | n |
Searching n-th key / value / entry | log(n) |
Searching closest key / value / entry | log(n) |
Finding the key index | log(n) |
Iteration from k-th entry | count + log(n) |