JSPM

  • ESM via JSPM
  • ES Module Entrypoint
  • Export Map
  • Keywords
  • License
  • Repository URL
  • TypeScript Types
  • README
  • Created
  • Published
  • Downloads 210
  • Score
    100M100P100Q72145F
  • License MIT

A compact trie for mapping keys to values that allows efficient prefix-based retrievals

Package Exports

  • trie-mapping

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (trie-mapping) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

trie-mapping

build status npm version bundle size

A compact trie for mapping keys to values that allows efficient prefix-based retrievals

Installing

npm install trie-mapping

API

The API mimics the native Map (so it may be used as a drop in replacement), with the following differences:

The size getter and the clear() method are identical to those of the native Map.

trieMapping(elements)

Returns a trie object.

It may be initialized from the given elements, which is an array or other iterable whose elements are key-value pairs, or a root object. If elements is a root object, it may be deeply mutated by the trie's methods.

import trieMapping from "trie-mapping";

// Create an empty trie
trieMapping();

// Initialize from an array
trieMapping([
  ["hey", 0],
  ["hi", 1]
]);

// Initialize from a trie's root object, e.g., what the `root` getter returns
trieMapping({
  h: {
    ey: { "": 0 },
    i: { "": 1 }
  }
});

root

Returns the root node, whose "" key is the label of its value, and the rest of its keys are the labels of its child nodes.

import trieMapping from "trie-mapping";

trieMapping([
  ["he", 1],
  ["hey", 5],
  ["hells", 4],
  ["hello", 3],
  ["hell", 2],
  ["bye", 0]
]).root;
// =>
// {
//   he: {
//     "": 1,
//     y: { "": 5 },
//     ll: {
//       s: { "": 4 },
//       o: { "": 3 },
//       "": 2
//     }
//   },
//   bye: { "": 0 }
// }

It exposes the inner state of the trie for use cases such as:

  • Finding all entries prefixed with a given prefix (see example)
  • Implementing fuzzy string searching, e.g., with Levenshtein distance
  • Serializing a trie as JSON more compactly and quickly than with entries()
  • Efficiently initializing a new trie by passing a trie node to the trieMapping() factory function

size

Returns the number of key-value pairs.

Note that if the trie was initialized from a root object, getting the size for the first time requires traversing the trie to count the number of elements. Afterwards, the size is memoized, even if you delete() or set() elements.

clear()

Removes all key-value pairs.

delete(key)

Returns true if an element with the given key existed and has been removed, or false if the element does not exist.

entries()

Returns a new Iterator object that contains an array of [key, value] for each element in alphabetical order.

forEach(callbackfn, thisArg)

Calls the given callbackfn once for each key-value pair, in alphabetical order, passing to the callbackfn the value of the item, the key of the item, and the trie object being traversed. If thisArg is given, it will be used as the this value for each callback.

get(key)

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

has(key)

Returns true if a value has been associated to the given key, or false otherwise.

keys()

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

set(key, value)

Returns the trie, associating the given value to the given key.

values()

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

[@@iterator]()

Returns a new Iterator object that contains an array of [key, value] for each element in alphabetical order.

License

MIT