trie
Maps whose keys are sequences, with prefix queries
Import it as nanyx/trie. A Trie maps keys that are lists to values, and also finds the keys that start with a prefix, and the longest key that is a prefix of another: what autocompletion and routing tables need. A StringTrie does the same with string keys.
import nanyx/trie
def routes = StringTrie["/" => "home", "/users" => "users", "/users/admin" => "admin"]
println("{StringTrie.longestPrefixOf(routes, "/users/42")}") -- #some(/users, users)
println("{StringTrie.withPrefix(routes, "/users")}") -- [(/users, users), (/users/admin, admin)]
Reference
Tries: maps whose keys are sequences, which also answer questions about prefixes.
A Trie(k, v) maps keys that are lists, list(k), to values, as a map does, and also finds every
key that starts with a prefix (Trie.withPrefix), whether any does (Trie.hasPrefix), and the
longest key that is a prefix of a given one (Trie.longestPrefixOf), as autocompletion and
routing tables need. Each node is an optional value and a map from the next element of a key to
the node below it, so finding a key takes time in proportion to its length, however many keys
there are. The elements need an == and a hash, as a map’s keys do.
A StringTrie(v) is the common case: its keys are strings, each read as its
characters.
Nothing about a trie changes once it is made: Trie.insert and Trie.remove give back a new
trie, which shares the nodes it didn’t change with the one it was made from. Removing a key
removes the nodes left with no value and nothing below them, so two tries holding the same keys
and values are ==, whatever order the keys were added in. A trie has no hash, as a map has
none. Trie.toString writes one as its pairs, Trie[[1, 2] => a].
A Trie’s keys come out in the order they were added in, those below one element before those
below the next, and each key before the keys it is a prefix of: its elements need no order. A
StringTrie’s come out sorted.
Each function is attached to Trie or StringTrie, so with import nanyx/trie it is called as
Trie.insert(t, [1, 2], "a"), or as t \insert([1, 2], "a"). A literal of key => value
entries makes one: Trie[[1] => "a", [1, 2] => "b"], or StringTrie["a" => 1, "ab" => 2].
Trie
type Trie(k, v) = protected Node(k, v)
Trie.empty
def Trie.empty: Trie(k, v)
The trie with no keys.
Trie.insert
def Trie.insert: [Eq(k), Hash(k)] Trie(k, v), list(k), v -> Trie(k, v)
trie with key mapped to value, in place of any value it had.
Trie.remove
def Trie.remove: [Eq(k), Hash(k)] Trie(k, v), list(k) -> Trie(k, v)
trie without key, and without the nodes that leaves with no value and nothing below them.
The same trie when it has no key.
Trie.get
def Trie.get: [Eq(k), Hash(k)] Trie(k, v), list(k) -> #some(v) | #none
The value trie maps key to, or #none when it has no key.
Trie.containsKey
def Trie.containsKey: [Eq(k), Hash(k)] Trie(k, v), list(k) -> bool
Whether trie maps key to a value.
Trie.length
def Trie.length: Trie(k, v) -> int
How many keys trie holds.
Trie.isEmpty
def Trie.isEmpty: Trie(k, v) -> bool
Whether trie holds no keys.
Trie.toList
def Trie.toList: Trie(k, v) -> list((list(k), v))
Each key in trie and its value, in the order the keys were added in, as the module’s
description says.
Trie.keys
def Trie.keys: Trie(k, v) -> list(list(k))
The keys in trie, in the order of Trie.toList.
Trie.fromList
def Trie.fromList: [Eq(k), Hash(k)] list((list(k), v)) -> Trie(k, v)
A trie of the keys and values in pairs; a key that comes twice maps to its last value.
Trie.fromArray
def Trie.fromArray: [Eq(k), Hash(k)] array((list(k), v)) -> Trie(k, v)
A trie of the keys and values in pairs. What a literal builds a trie with,
Trie[[1] => "a", [1, 2] => "b"].
Trie.withPrefix
def Trie.withPrefix: [Eq(k), Hash(k)] Trie(k, v), list(k) -> list((list(k), v))
Each key in trie that starts with prefix, prefix itself included, and its value, in the
order of Trie.toList.
Trie.hasPrefix
def Trie.hasPrefix: [Eq(k), Hash(k)] Trie(k, v), list(k) -> bool
Whether any key in trie starts with prefix, or is prefix.
Trie.longestPrefixOf
def Trie.longestPrefixOf: [Eq(k), Hash(k)] Trie(k, v), list(k) -> #some(list(k), v) | #none
The longest key in trie that key starts with, key itself included, and its value, or
#none when no key in trie is a prefix of key. A router finds the most specific route for a
path with it.
Trie.toString
def Trie.toString: [ToString(k), ToString(v)] Trie(k, v) -> string
trie as its literal is written, its keys in the order of Trie.toList:
Trie[[1] => a, [1, 2] => b], and Trie[=>] when it is empty.
StringTrie
type StringTrie(v) = protected Trie(string, v)
A trie whose keys are strings, each read as its characters, as string.chars gives them. Its
functions take and give strings, and give its keys sorted.
StringTrie.empty
def StringTrie.empty: StringTrie(v)
The string trie with no keys.
StringTrie.insert
def StringTrie.insert: StringTrie(v), string, v -> StringTrie(v)
trie with key mapped to value, in place of any value it had.
StringTrie.remove
def StringTrie.remove: StringTrie(v), string -> StringTrie(v)
trie without key, and without the nodes that leaves with no value and nothing below them.
StringTrie.get
def StringTrie.get: StringTrie(v), string -> #some(v) | #none
The value trie maps key to, or #none when it has no key.
StringTrie.containsKey
def StringTrie.containsKey: StringTrie(v), string -> bool
Whether trie maps key to a value.
StringTrie.length
def StringTrie.length: StringTrie(v) -> int
How many keys trie holds.
StringTrie.isEmpty
def StringTrie.isEmpty: StringTrie(v) -> bool
Whether trie holds no keys.
StringTrie.toList
def StringTrie.toList: StringTrie(v) -> list((string, v))
Each key in trie and its value, sorted by key.
StringTrie.keys
def StringTrie.keys: StringTrie(v) -> list(string)
The keys in trie, sorted.
StringTrie.fromList
def StringTrie.fromList: list((string, v)) -> StringTrie(v)
A string trie of the keys and values in pairs; a key that comes twice maps to its last value.
StringTrie.fromArray
def StringTrie.fromArray: array((string, v)) -> StringTrie(v)
A string trie of the keys and values in pairs. What a literal builds one with,
StringTrie["a" => 1, "ab" => 2].
StringTrie.withPrefix
def StringTrie.withPrefix: StringTrie(v), string -> list((string, v))
Each key in trie that starts with prefix, prefix itself included, and its value, sorted
by key: withPrefix(t, "ab") gives "ab", "abc" and "abd", but not "a".
StringTrie.hasPrefix
def StringTrie.hasPrefix: StringTrie(v), string -> bool
Whether any key in trie starts with prefix, or is prefix.
StringTrie.longestPrefixOf
def StringTrie.longestPrefixOf: StringTrie(v), string -> #some(string, v) | #none
The longest key in trie that key starts with, key itself included, and its value, or
#none when no key in trie is a prefix of key.
StringTrie.toString
def StringTrie.toString: [ToString(v)] StringTrie(v) -> string
trie as its literal is written, its keys sorted: StringTrie[a => 1, ab => 2], and
StringTrie[=>] when it is empty.