TS/JS Map-like data structure backed by trie
npm install @sec-ant/trie-map!GitHub top language    !GitHub search hit counter 
This package impelements a Map-like data structure backed by trie.
In the native Map data structure provided by Javascript, key equality is based on the SameValueZero algorithm. So, two different arrays with same contents are considered as two different keys:
``js
const a = ["hello", "world"];
const b = ["hello", "world"];
const map = new Map();
map.set(a, "foo").set(b, "bar");
map.get(a); // => "foo"
map.get(b); // => "bar"
map.get(["hello", "world"]); // => undefined
`
However, in some use cases, we don't always preserve the references of the keys (and in some cases we just don't have them, e.g., when the map is imported from a third-party module) and we want arrays with same contents always point to the same value, e.g., in a file system:
`js
const fs = new Map();
fs.set(["c", "program files"], "hello world.txt");
fs.get(["c", "program files"]); // => undefined, oops!
`
This package treats iterable-reference-type (array or array-like object that implements the iterable protocol) keys as values and uses value-equality to check key equality. The underlying structure is a trie.
`bash`
npm i @sec-ant/trie-map
or
`bash`
yarn add @sec-ant/trie-map
`js
import { TrieMap } from "@sec-ant/trie-map";
const a = ["hello", "world"];
const b = ["hello", "world"];
const tmap = new TrieMap();
tmap.set(a, "foo");
tmap.get(a); // => "foo"
tmap.get(b); // => "foo"
tmap.get(["hello", "world"]); // => "foo"
`
This package is greatly inspired by and plays a similar role as anko/array-keyed-map. Other similar packages include immutable.js Map, bemoje/trie-map, isogon/tuple-map, etc.
However, the following features make this package stand out:
This packages is fully written in Typescript
`ts
import { TrieMap } from "@sec-ant/trie-map";
const tmap = new TrieMap
tmap.set(["hello", "world"], "foo");
// value type will be inferred as string | undefined
const value = tmap.get(["hello", "world"]); // => "foo"
`
ECMAScript modules (ESM) is the now and future of javascript module system.
Mimic all methods and properties in
`ts
import { TrieMap } from "@sec-ant/trie-map";
// construct, use [key, value] entries to init a TrieMap instance
const tmap = new TrieMap
[["hello", "world"], "foo"],
[["hello", "TrieMap"], "bar"],
]);
// set
tmap.set([], "empty"); // => tmap
tmap.set([""], "empty string"); // => tmap
// has
tmap.has(["hello", "world"]); // => true
tmap.has(["hello"]); // => false
// get
tmap.get([]); // => "empty"
tmap.get(["hello"]); // => undefined
// delete
tmap.delete([]); // => true
tmap.delete(["hello"]); // => false
// size
tmap.size; // => 3
// entries
[...tmap.entries()]; // => [[["hello", "world"], "foo"], [["hello", "TrieMap"], "bar"], [[""], "empty string"]]
// keys
[...tmap.keys()]; // => [["hello", "world"], ["hello", "TrieMap"], [""]]
// values
[...tmap.values()]; // => ["foo", "bar", "empty string"]
// forEach
tmap.forEach((value, key) => console.log([key[0], value])); // => [["hello", "foo"], ["hello", "bar"], ["", "empty string"]]
// Symbol.iterator
[...tmap]; // => same result as [...tmap.entries()]
// Symbol.toStringTag
tmap.toString(); // => [object TrieMap]
// clear
tmap.clear(); // => undefined, remove all key-value pairs
`
All iterations (entries, keys, values, forEach and Symbol.iterator) are in insertion order.
`ts
import { TrieMap } from "@sec-ant/trie-map";
const tmap = new TrieMap
tmap.set("key", "string").get("key"); // => "string"
tmap.set(2, "number").get(2); // => "number"
tmap.set(["string"], "array").get(["string"]); // => "array"
[...tmap]; // => [["key", "string"], [2, "number"], [["string"], "array"]]
`
`ts
import { TrieMap } from "@sec-ant/trie-map";
const tmap = new TrieMap<(string | string[])[], string>();
tmap.set([], "foo").get([]); // => "foo"
tmap.set([[]], "bar").get([[]]); // => "bar"
tmap.set([[], []], "baz").get([[], []]); // => "baz"
tmap.set([["1"], [], "2", ["3"]], "123").get([["1"], [], "2", ["3"]]); // => "123"
`
This package also provides an option to opt out from value comparison of deeply nested iterable keys, and only compares the keys shallowly:
`ts
import { TrieMap, TrieMapOptions } from "@sec-ant/trie-map";
const options: TrieMapOptions = { deep: false }; // the default value of deep is true
const tmap = new TrieMap<(string | string[])[], string>(undefined, options);
const two = ["2"];
tmap.set([], "foo").get([]); // => "foo"
tmap.set(["1"], "bar").get(["1"]); // => "bar"
tmap.set(["1", two, "3"], "baz").get(["1", two, "3"]); // => "baz"
tmap.get(["1", ["2"], "3"]); // => undefined
`
This package has no dependencies and the js code is only 1.37 kiB after minification.
The runtime should support ES modules, Classes, Generators and yield and Symbol. Although you should be able to transpile this package when using other front-end build or bundle tools.
Check the configured browserslist coverage here.
Any two iterable reference type keys are considered equal, value-comparison-wise, as long as their iteration results are same:
`ts
import { TrieMap } from "@sec-ant/trie-map";
const tmap = new TrieMap
tmap.set([1, 2], "foo");
tmap.get(new Uint8Array([1, 2])); // => "foo"
``
- [ ] Type issues.
- [ ] Unit tests.
MIT