Nanyx
PlaygroundPackages

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.