ordered-map-suren

1.0.0 • Public • Published

OrderedMap

Description

An implementation of an ordered map in JS.

How to use

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.

Methods / properties

  • constructor()

    Description

    The OrderedMap constructor.

    Signatures

     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

    Description

    The number of elements in this map.


  • has(key)

    Description

    Checks if a given key exists in the map. Returns true if present or false if not.


  • get(key)

    Description

    Searches for a given key. Returns the associated value if present or undefined if not.


  • set(key, value)

    Description

    Associates the given key with value. Returns the map object itself.


  • getNth(index)

    Description

    Searches for a value with its key ordering index. Returns the value if present or undefined if not. If index is negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.).


  • getNthKey(index)

    Description

    Searches for a key with an ordering index. Returns the key if present or undefined if not. If index is negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.).


  • getNthEntry(index)

    Description

    Searches for a [key, value] pair with an ordering index. Returns the pair if present or undefined if not. If index is negative the n-th from the end is taken (i.e. -1 means the last, -2 means the second last, etc.).


  • getIndex(key)

    Signatures

     getIndex(key)
     getIndex(key, isUpperBound)
    

    Description

    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 is false by default. If it is false 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. If count is negative the iteration order is reversed from the starting index.


  • getClosestKey(key)

    Signatures

     getClosestKey(key)
     getClosestKey(key, isUpperBound)
     getClosestKey(key, isUpperBound, canMatch)
    

    Description

    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 is false by default. If it is false the closest less or equal key is searched, otherwise the greater or equal closest key.

    canMatch is true by default. If it's false only strictly smaller or greater keys are searched.


  • getClosestValue(key)

    Signatures

     getClosestValue(key)
     getClosestValue(key, isUpperBound)
     getClosestValue(key, isUpperBound, canMatch)
    

    Description

    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 is false by default. If it is false the closest less or equal key is searched, otherwise the greater or equal closest key.

    canMatch is true by default. If it's false only strictly smaller or greater keys are searched.


  • getClosestEntry(key)

    Signatures

     getClosestEntry(key)
     getClosestEntry(key, isUpperBound)
     getClosestEntry(key, isUpperBound, canMatch)
    

    Description

    Searches for the closest key. Returns the associated entry ([key, value] pair) if the key exists or undefined if not.

    key is the key that the closest key is searched for.

    isUpperBound is false by default. If it is false the closest less or equal key is searched, otherwise the greater or equal closest key.

    canMatch is true by default. If it's false only strictly smaller or greater keys are searched.


  • delete(key)

    Description

    Deletes the key and the associated value from the map. Returns true if the key existed right before calling this method or false if not.


  • clear()

    Description

    Clears the map.


  • keys()

    Signatures

    keys()
    keys(startIndex)
    keys(startIndex, count)
    

    Description

    Returns an iterator for the keys.

    startIndex is the first key order index that the iteration should start from, by default it's 0. 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. If count is negative the iteration order is reversed from the starting index.


  • values()

    Signatures

     values()
     values(startIndex)
     values(startIndex, count)
    

    Description

    Returns an iterator for the values.

    startIndex is the first value associated key order index that the iteration should start from, by default it's 0. 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. If count is negative the iteration order is reversed from the starting index.


  • entries()

    Signatures

     entries()
     entries(startIndex)
     entries(startIndex, count)
    

    Description

    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's 0. 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. If count is negative the iteration order is reversed from the starting index.


  • forEach(callbackFn)

    Signatures

     forEach(callbackFn)
     forEach(callbackFn, thisArg)
     forEach(callbackFn, thisArg, startIndex)
     forEach(callbackFn, thisArg, startIndex, count)
    

    Description

    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's 0. 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. If count is negative the iteration order is reversed from the starting index.


Static methods / properties

  • groupBy()

    Signatures

     groupBy(iterable, callbackFn)
     groupBy(iterable, callbackFn, comparatorFn)
    

    Description

    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().

Algorithmic complexity (worst case)

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)

License

MIT license

Package Sidebar

Install

npm i ordered-map-suren

Weekly Downloads

0

Version

1.0.0

License

MIT

Unpacked Size

27.6 kB

Total Files

4

Last publish

Collaborators

  • senfiaj