multikeys

Multikeys data structures collection written in TypeScript: Map, Set, WeakMap and WeakSet. Based on trie data structure.

Benchmarks are located in ./benchmark directory. You can modify ./benchmark/index.js and run npm i && npm start to test your own use cases.

Results of calling set and get with random data (and random number of keys). You can find benchmark code in ./benchmark/index.js.

Maximum number of keys is 10

| package | set and get (ops/sec) | normalized on many-keys-map | |--------------------------------------------------------------|-----------------------|-------------------------------| | multikeymap | 1.37 ±19.20% | 0 | | many-keys-map | 27 795 ±0.84% | 1 | | multikey | 79 355 ±1.37% | 2.85 | | multikey-map | 153 616 ±1.32% | 5.52 | | multikeys | 185 565 ±1.70% | 6.67 |

Maximum number of keys is 100

| package | set and get (ops/sec) | normalized on many-keys-map | |--------------------------------------------------------------|-----------------------|-------------------------------| | multikeymap | fall with OOM | - | | many-keys-map | 7 120 ±0.92% | 1 | | multikey | 10 830 ±1.35% | 1.52 | | multikey-map | 29 635 ±1.26% | 4.16 | | multikeys | 43 394 ±1.52% | 6.09 |

Example of usage

const mkMap = new MKMap();

mkMap.set([1, 2, 3], 'foo');
mkMap.set([3, 2, 1], 'bar');

// order of keys matters
mkMap.get([1, 2, 3]); // => 'foo'
mkMap.get([3, 2, 1]); // => 'bar'

// an argument with empty keys is also valid
mkMap.set([], 'zero');
mkMap.get([]); // => 'zero'

const mkSet = new MKSet();
const obj = {};

mkSet.add([obj, 1]);
mkSet.has([{}, 1]); // => false, because {} is a new object, {} !== obj
mkSet.has([obj, 1]); // => true

Using MKMap we could simply add memoization to function with a variable number of arguments:

const {MKMap} = require("multikeys");

function memoize(func) {
    const mkMap = new MKMap();

    return (...args) => {
        if (mkMap.has(args)) {
            return mkMap.get(args);
        }

        const res = func(...args);

        mkMap.set(args, res);

        return res;
    };
}

Also, we could replace MKMap with MKWeakMap and get memoize with auto garbage collection. In such case only objects could be func arguments.

API

Table of contents

Classes

• MKMap
• MKSet
• MKWeakMap
• MKWeakSet

Class: MKMap<K, V>

Type parameters

Name | Default | :------ | :------ | K | any | V | any |

Table of contents

Constructors

• constructor

Accessors

• size

Methods

• [Symbol.iterator]
• clear
• delete
• entries
• forEach
• get
• has
• keys
• set
• values

Constructors

constructor

+ new MKMap<K, V>(iterable?: Iterable<readonly [readonly K[], V]>): MKMap<K, V>

Creates a new MKMap object.

Could be called with initial keys-values.

const empty = new MKMap();
const withValues = new MKMap([
    [['key_1', 'key_2'], 'value'],
    [['key'], 'val']
]);

Type parameters:

Name | Default | :------ | :------ | K | any | V | any |

Parameters:

Name | Type | :------ | :------ | iterable? | Iterable<readonly [readonly K[], V]> |

Returns: MKMap<K, V>

Accessors

size

• get size(): number

Returns the number of keys/value pairs in the MKMap object.

Returns: number

Methods

[Symbol.iterator]

▸ [Symbol.iterator](): IterableIterator<[K[], V]>

Returns a new Iterator object that contains an array of [keys, value] for each element in the MKMap object.

Returns: IterableIterator<[K[], V]>

clear

▸ clear(): void

Removes all keys-value pairs from the MKMap object.

Returns: void

delete

▸ delete(keys: readonly K[]): boolean

Returns true if an element in the MKMap object existed and has been removed, or false if the element does not exist.

const mkMap = new MKMap([['foo'], 'bar']);

mkMap.delete(['foo']); // => true
mkMap.delete(['foo']); // => false

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean

entries

▸ entries(): IterableIterator<[K[], V]>

Returns a new Iterator object that contains an array of [keys, value] for each element in the Map object.

Returns: IterableIterator<[K[], V]>

forEach

▸ forEach(callbackFn: (value: V, keys: K[], map: MKMap<K, V>) => void): void

Calls callbackFn once for each keys-value pair present in the MKMap object.

Parameters:

Name | Type | :------ | :------ | callbackFn | (value: V, keys: K[], map: MKMap<K, V>) => void |

Returns: void

get

▸ get(keys: readonly K[]): undefined | V

Returns the value associated to the keys, or undefined if there is none.

const mkMap = new MKMap([['foo'], 'bar']);

mkMap.get(['foo']); // => 'bar'

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: undefined | V

has

▸ has(keys: readonly K[]): boolean

Returns a boolean asserting whether a value has been associated to the keys in the MKMap object or not.

const mkMap = new MKMap([['foo'], 'bar']);

mkMap.has(['foo']); // => true

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean

keys

▸ keys(): IterableIterator<K[]>

Returns a new Iterator object that contains the keys for each element in the MKMap.

Returns: IterableIterator<K[]>

set

▸ set(keys: readonly K[], value: V): MKMap<K, V>

Sets the value for the keys in the MKMap object. Returns the MKMap object.

mkMap.set(['foo'], 'bar');

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] | value | V |

Returns: MKMap<K, V>

values

▸ values(): IterableIterator<V>

Returns a new Iterator object that contains the values for each element in the MKMap object.

Returns: IterableIterator<V>

Class: MKSet<K>

Type parameters

Name | Default | :------ | :------ | K | any |

Table of contents

Constructors

• constructor

Accessors

• size

Methods

• [Symbol.iterator]
• add
• clear
• delete
• entries
• forEach
• has
• keys
• values

Constructors

constructor

+ new MKSet<K>(iterable?: Iterable<readonly K[]>): MKSet<K>

Creates a new MKSet object.

Could be called with initial keys.

const empty = new MKSet();
const withKeys = new MKSet([
    ['key'],
    ['few', 'keys']
]);

Type parameters:

Name | Default | :------ | :------ | K | any |

Parameters:

Name | Type | :------ | :------ | iterable? | Iterable<readonly K[]> |

Returns: MKSet<K>

Accessors

size

• get size(): number

Returns the number of values in the MKSet object.

Returns: number

Methods

[Symbol.iterator]

▸ [Symbol.iterator](): IterableIterator<K[]>

Returns a new Iterator object that yields the keys for each element in the MKSet object.

Returns: IterableIterator<K[]>

add

▸ add(keys: readonly K[]): void

Appends keys to the MKSet object.

mkSet.add([1, 2, 3]);

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: void

clear

▸ clear(): void

Removes all elements from the MKSet object.

Returns: void

delete

▸ delete(keys: readonly K[]): boolean

Removes the element associated to the keys and returns the value that MKSet.has(keys) would have previously returned. MKSet.has(keys) will return false afterwards.

const mkSet = new MKSet([['foo']]);

mkSet.delete(['foo']); // => true
mkSet.delete(['foo']); // => false

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean

entries

▸ entries(): IterableIterator<[K[], K[]]>

Returns a new Iterator object that contains an array of [keys, keys] for each element in the MKSet object.

Returns: IterableIterator<[K[], K[]]>

forEach

▸ forEach(callbackFn: (value: K[], key: K[], map: MKSet<K>) => void): void

Calls callbackFn once for each value present in the MKSet object.

Parameters:

Name | Type | :------ | :------ | callbackFn | (value: K[], key: K[], map: MKSet<K>) => void |

Returns: void

has

▸ has(keys: readonly K[]): boolean

Returns a boolean asserting whether an element is present with the given keys in the MKSet object or not.

const mkSet = new MKSet([['foo']]);

mkSet.has(['foo']); // => true
mkSet.has(['bar']); // => false

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean

keys

▸ keys(): IterableIterator<K[]>

Returns a new Iterator object that yields the keys for each element in the MKSet object. (this is the same as the values() method.)

Returns: IterableIterator<K[]>

values

▸ values(): IterableIterator<K[]>

Returns a new Iterator object that yields the keys for each element in the MKSet object. (this is the same as the keys() method.)

Returns: IterableIterator<K[]>

Class: MKWeakMap<K, V>

Type parameters

Name | Type | Default | :------ | :------ | :------ | K | object | object | V | - | any |

Table of contents

Constructors

• constructor

Methods

• delete
• get
• has
• set

Constructors

constructor

+ new MKWeakMap<K, V>(iterable?: Iterable<readonly [readonly K[], V]>): MKWeakMap<K, V>

Creates a new MKWeakMap object.

Could be called with initial keys-values

const empty = new MKWeakMap();
const withValues = new MKWeakMap([
    [[{foo: 'bar'}], 'val']
]);

Type parameters:

Name | Type | Default | :------ | :------ | :------ | K | object | object | V | - | any |

Parameters:

Name | Type | :------ | :------ | iterable? | Iterable<readonly [readonly K[], V]> |

Returns: MKWeakMap<K, V>

Methods

delete

▸ delete(keys: readonly K[]): boolean

Removes any value associated to the keys. Returns true if an element in the MKWeakMap object has been removed successfully.

const obj = {};
const mkWeakMap = new MKWeakMap([[obj, 'foo']]);

mkWeakMap.delete([obj]); // => true
mkWeakMap.delete([obj]); // => false

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean

get

▸ get(keys: readonly K[]): undefined | V

Returns the value associated to the keys, or undefined if there is none.

const obj = {};
const mkWeakMap = new MKWeakMap([[obj, 'foo']]);

mkWeakMap.get([obj]); // => 'foo'

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: undefined | V

has

▸ has(keys: readonly K[]): boolean

Returns a Boolean asserting whether a value has been associated to the keys in the MKWeakMap object or not.

const obj = {};
const mkWeakMap = new MKWeakMap([[obj, 'foo']]);

mkWeakMap.has([obj]); // => 'true'

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean

set

▸ set(keys: readonly K[], value: V): MKWeakMap<K, V>

Sets the value for the keys in the MKWeakMap object. Returns the MKWeakMap object.

const mkWeakMap = new MKWeakMap();
const obj = {};

mkWeakMap.set([obj], 'foo');
mkWeakMap.get([obj]); // => 'foo'

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] | value | V |

Returns: MKWeakMap<K, V>

Class: MKWeakSet<K>

Type parameters

Name | Type | :------ | :------ | K | object |

Table of contents

Constructors

• constructor

Methods

• add
• delete
• has

Constructors

constructor

+ new MKWeakSet<K>(iterable?: Iterable<readonly K[]>): MKWeakSet<K>

Creates a new MKWeakSet object.

Could be called with initial keys

const empty = new MKWeakSet();
const withValues = new MKWeakSet([
    [{foo: 'bar'}]
]);

Type parameters:

Name | Type | :------ | :------ | K | object |

Parameters:

Name | Type | :------ | :------ | iterable? | Iterable<readonly K[]> |

Returns: MKWeakSet<K>

Methods

add

▸ add(keys: readonly K[]): void

Add keys to the MKWeakSet object.

const mkWeakSet = new MKWeakSet();
const obj = {};

mkWeakSet.add([obj]);
mkWeakSet.has([obj]); // => 'true'

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: void

delete

▸ delete(keys: readonly K[]): boolean

Removes keys from the MKWeakSet. Returns true if keys has been removed successfully.

const obj = {};
const mkWeakSet = new MKWeakSet([[obj]]);

mkWeakSet.delete([obj]); // => true
mkWeakSet.delete([obj]); // => false

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean

has

▸ has(keys: readonly K[]): boolean

Returns true if an element with the specified keys exists in the MKWeakSet object.

const obj = {};
const mkWeakSet = new MKWeakSet([[obj]]);

mkWeakSet.has([obj]); // => 'true'

Parameters:

Name | Type | :------ | :------ | keys | readonly K[] |

Returns: boolean