@sec-ant/trie-map NPM

@sec-ant/trie-map

GitHub top language

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

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

See #private and Symbol()

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"