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
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:
- It exports a factory function (
trieMapping()
) which may be initialized from a trie'sroot
object - It exposes the trie's internal representation through the
root
getter to enable advanced use cases - The
key
argument ofget()
,delete()
,has()
, andset()
must be a string - The iteration order of
entries()
,forEach()
,keys()
,values()
, and[@@iterator]()
is alphabetical
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.