@sec-ant/trie-map
v1.1.6
Published
TS/JS Map-like data structure backed by trie
Downloads
16
Maintainers
Readme
@sec-ant/trie-map
This package impelements a Map-like data structure backed by trie.
Why?
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:
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:
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.
Install
npm i @sec-ant/trie-map
or
yarn add @sec-ant/trie-map
Basic Usage
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"
Features
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:
Typescript Support
This packages is fully written in Typescript
import { TrieMap } from "@sec-ant/trie-map";
const tmap = new TrieMap<string[], string>();
tmap.set(["hello", "world"], "foo");
// value type will be inferred as string | undefined
const value = tmap.get(["hello", "world"]); // => "foo"
Pure ECMAScript Module
ECMAScript modules (ESM) is the now and future of javascript module system.
Fully Mimics All Native Map APIs
import { TrieMap } from "@sec-ant/trie-map";
// construct, use [key, value] entries to init a TrieMap instance
const tmap = new TrieMap<string[], string>([
[["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
Iterations in Insertion Order
All iterations (entries
, keys
, values
, forEach
and Symbol.iterator
) are in insertion order.
Mixing of Primitives and Iterable References as Keys
import { TrieMap } from "@sec-ant/trie-map";
const tmap = new TrieMap<string | number | string[], string>();
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"]]
Value Comparison of Deeply Nested Iterable Keys
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"
Shallow Comparison of Keys
This package also provides an option to opt out from value comparison of deeply nested iterable keys, and only compares the keys shallowly:
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
Class Private Fields and Unique Symbols for Encapsulation
No Dependencies
This package has no dependencies and the js code is only 1.37 kiB after minification.
Runtime Coverage
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.
Notes
Any two iterable reference type keys are considered equal, value-comparison-wise, as long as their iteration results are same:
import { TrieMap } from "@sec-ant/trie-map";
const tmap = new TrieMap<number[] | Uint8Array, string>();
tmap.set([1, 2], "foo");
tmap.get(new Uint8Array([1, 2])); // => "foo"
Todos
- [ ] Type issues.
- [ ] Unit tests.
LICENSE
MIT