Trie
Defined in: packages/data/src/trie/trie.ts:49
A prefix tree over sequences of a caller-chosen segment type.
Generic over the segment, not hard-coded to string/char: a key is a
readonly S[], so S can be a character, a path component, a token, an enum
member. Split the string yourself and the same structure indexes routes,
namespaces or n-grams without a second implementation.
What a trie buys over a Map is prefix access: withPrefix, hasPrefix and
longestPrefixOf are what a hash map cannot answer at all. A plain Map is
faster for exact lookup and should be preferred when that is all that is
needed.
Time complexity, for a key of k segments: O(k) for get, set, has and
delete — independent of how many keys are stored. withPrefix is O(k +
size of the subtree). Space is O(total segments), shared across common
prefixes.
Type Parameters
Section titled “Type Parameters”S
The segment type.
V extends DefinedValue
The value type.
Implements
Section titled “Implements”ITrie<S,V>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new Trie<
S,V>(iterable?):Trie<S,V>
Defined in: packages/data/src/trie/trie.ts:53
Parameters
Section titled “Parameters”iterable?
Section titled “iterable?”Iterable<readonly [readonly S[], V], any, any>
Returns
Section titled “Returns”Trie<S, V>
Methods
Section titled “Methods”[iterator]()
Section titled “[iterator]()”[iterator]():
Iterator<readonly [readonlyS[],V]>
Defined in: packages/data/src/trie/trie.ts:61
Returns
Section titled “Returns”Iterator<readonly [readonly S[], V]>
Implementation of
Section titled “Implementation of”clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/trie/trie.ts:70
Removes all elements from the collection.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”count()
Section titled “count()”count():
number
Defined in: packages/data/src/trie/trie.ts:66
The number of stored keys. O(1).
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”delete()
Section titled “delete()”delete(
key):boolean
Defined in: packages/data/src/trie/trie.ts:122
O(k). Prunes every node left holding neither a value nor a child.
Parameters
Section titled “Parameters”readonly S[]
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”entries()
Section titled “entries()”entries():
IterableIterator<readonly [readonlyS[],V]>
Defined in: packages/data/src/trie/trie.ts:163
Every stored entry, in depth-first order.
Returns
Section titled “Returns”IterableIterator<readonly [readonly S[], V]>
Implementation of
Section titled “Implementation of”get(
key):V|undefined
Defined in: packages/data/src/trie/trie.ts:78
O(k).
Parameters
Section titled “Parameters”readonly S[]
Returns
Section titled “Returns”V | undefined
Implementation of
Section titled “Implementation of”has(
key):boolean
Defined in: packages/data/src/trie/trie.ts:117
O(k). Whether this exact key is stored — see hasPrefix for the other
question.
Parameters
Section titled “Parameters”readonly S[]
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”hasPrefix()
Section titled “hasPrefix()”hasPrefix(
prefix):boolean
Defined in: packages/data/src/trie/trie.ts:188
Whether any stored key starts with prefix. O(k).
Distinct from has: a prefix can exist as a path without being a key.
Parameters
Section titled “Parameters”prefix
Section titled “prefix”readonly S[]
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”keys()
Section titled “keys()”keys():
IterableIterator<readonlyS[]>
Defined in: packages/data/src/trie/trie.ts:149
Every stored key, in depth-first order.
Returns
Section titled “Returns”IterableIterator<readonly S[]>
Implementation of
Section titled “Implementation of”longestPrefixOf()
Section titled “longestPrefixOf()”longestPrefixOf(
key): readonlyS[] |undefined
Defined in: packages/data/src/trie/trie.ts:199
The longest stored key that is a prefix of key, or undefined if none
is. O(k).
This is the lookup behind longest-prefix routing and dictionary matching:
the whole point of holding the keys in a trie rather than a Map.
Parameters
Section titled “Parameters”readonly S[]
Returns
Section titled “Returns”readonly S[] | undefined
Implementation of
Section titled “Implementation of”set(
key,value):void
Defined in: packages/data/src/trie/trie.ts:90
O(k). Overwrites a key already stored.
The empty key is legal and addresses the root, so a trie can carry a “default” value alongside its prefixed ones.
Parameters
Section titled “Parameters”readonly S[]
V
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”values()
Section titled “values()”values():
IterableIterator<V>
Defined in: packages/data/src/trie/trie.ts:156
Every stored value, in the same order as keys.
Returns
Section titled “Returns”IterableIterator<V>
Implementation of
Section titled “Implementation of”withPrefix()
Section titled “withPrefix()”withPrefix(
prefix):IterableIterator<readonly [readonlyS[],V]>
Defined in: packages/data/src/trie/trie.ts:171
Every entry whose key starts with prefix, including prefix itself when
it is stored. O(k + the size of the subtree).
Parameters
Section titled “Parameters”prefix
Section titled “prefix”readonly S[]
Returns
Section titled “Returns”IterableIterator<readonly [readonly S[], V]>