Class TreeMultiDict<K, V>

A tree-based dictionary that can store multile items with the same key, but only if the values differ.

import { TreeMultiDict } from "scl"

The following table summarises the worst-case time complexity of the most commonly used properies of this class. For more information, see the documentation of the respective property.

Property name Worst case
add() O(log(n))
clear() O(1)
equalKeys() O(n)
delete() O(log(n))
deleteAll() O(n)
deleteAt() O(log(n))
size O(1)

When a new entry is added with a key and value that is already taken, the dictionary will replace the corresponding entry with the new one.

const d = new TreeMultiDict<number, string>()
d.emplace(1, 'foo') // ok
assert.strictEqual(d.getValues(1), 'foo')
d.emplace(1, 'bar') // ok
d.emplace(1, 'foo') // ok
const values = [...d.getValues(1)]
assert.lengthOf(values, 3)
assert.deepInclude(value, [1, 'foo']) // appears two times
assert.deepInclude(value, [1, 'bar'])

If you need to throw an error when a key is already taken, simply use has().

The items in a tree-based dictionary are guaranteed to be sorted on their keys. This is not true for values with the same, which generally appear in the order by which they were inserted.

const d = new TreeMultiDict<number, string>()
d.emplace(2, 'two')
d.emplace(1, 'one')
d.emplace(3, 'three')
assert.deepEqual([...d], [[1, 'one'], [2, 'two'], [3, 'three']])

See

  • HashMultiDict for a fast, unordered version of this collection.
  • TreeDict when you need your keys to be unique.

Type Parameters

  • K

    The type of key of a given entry.

  • V

    The type of value associated with the given key.

Hierarchy

  • RBTreeMultiDict<K, V>
    • TreeMultiDict

Constructors

constructor

Accessors

size

Methods

[iterator] add clear clone delete deleteAll deleteAt deleteKey emplace equalKeys findKey getValues has hasKey toRange

Constructors

constructor

  • new TreeMultiDict<K, V>(
        opts?:
            | Iterable<[K, V], any, any>
            | RBTreeIndex<[K, V], K>
            | TreeDictOptions<K, V>,
    ): TreeMultiDict<K, V>

  • Construct a new tree-based dictionary.

    const d = new TreeMultiDict<number, string>()

    Similar to JavaScript's built-in map type, the constructor accepts a list of key-value pairs that will immediately be added to the resulting dictionary.

    const d = new TreeMultiDict<number, string>([
      [1, 'one'],
      [2, 'two']
    ])

    The dictionary can be tweaked by providing a TreeDictOptions-object, which allows to configure things like the default compare function and value equality.

    const d = new TreeMultiDict<number, string>({
      compare: (a, b) => a < b,
      valuesEqual: (a, b) => a === b,
      elements: [[1, 'one'], [2, 'two']]
    })

    Type Parameters

    • K
    • V

    Parameters

    Returns TreeMultiDict<K, V>

Accessors

size

  • get size(): number

  • Count the amount of elements in the collection.

    ⚠️ In most cases, this should be an O(1) operation. However, there are cases where this can be an O(n) operation. Therefore, it is recommended to always cache the result in a local variable.

    Returns number

Methods

[iterator]

  • "[iterator]"(): IterableIterator<[K, V], any, any>

  • Returns IterableIterator<[K, V], any, any>

add

  • add(element: [K, V], hint?: unknown): AddResult<[K, V]>

  • Add an element to the collection. If the element already exists, update its value.

    The location where the element is placed depends on the collection type, and in the generic case there is no guarantee on the location where it is inserted.

    This method returns a pair with the first element indicating whether the element was added, while the second element refers to the actual location of the element.

    Parameters

    • element: [K, V]
    • Optionalhint: unknown

      A transparent object obtained by getAddHint.

    Returns AddResult<[K, V]>

clear

  • clear(): void

  • Remove all elements from this collection, effectively setting the collection to the empty collection.

    Returns void

clone

delete

  • delete(element: [K, V]): boolean

  • Remove an element from the collection. If multiple elements are matched, the collection picks one of them.

    Parameters

    • element: [K, V]

    Returns boolean

    true if the element was found, false otherwise.

deleteAll

  • deleteAll(element: [K, V]): number

  • Remove an element from the collection. If multiple elements are matched, the collection removes all of them.

    Parameters

    • element: [K, V]

    Returns number

    The amount of elements that was removed.

deleteAt

  • deleteAt(position: Cursor<[K, V]>): void

  • Remove the element pointed to by the iterator result from this collection.

    Parameters

    Returns void

deleteKey

  • deleteKey(key: K): number

  • Delete a pair from the underlying collection that has the given key as key.

    Returns the amount of items that have been deleted.

    Parameters

    • key: K

    Returns number

emplace

  • emplace(key: K, value: V): [boolean, Cursor<[K, V]>]

  • Creates a new pair and inserts it in the underlying collection.

    Parameters

    • key: K
    • value: V

    Returns [boolean, Cursor<[K, V]>]

equalKeys

findKey

  • findKey(key: K): undefined | Cursor<[K, V]>

  • Similar to Dict.getValue, except that it returns the pair that was inserted in the collection.

    Parameters

    • key: K

    Returns undefined | Cursor<[K, V]>

getValues

  • getValues(key: K): IterableIterator<V, any, any>

  • Get all values that are associated with the given key.

    Parameters

    • key: K

    Returns IterableIterator<V, any, any>

has

  • has(element: [K, V]): boolean

  • Checks if the collection holds the given element.

    Parameters

    • element: [K, V]

      The element to check membership of.

    Returns boolean

    True if the collections holds the given element, false otherwise.

hasKey

  • hasKey(key: K): boolean

  • Checks whether there a pair in this collection that has the given key.

    Parameters

    • key: K

    Returns boolean

toRange

Settings

Member Visibility

On This Page

Constructors
Accessors
Methods