This module implements a Trie, a container for a set|mapping of strings in the digital search tree family. It is drop-in compatible-ish with CritBitTree itself compatible with both HashSet[string] & Table[string,*]. It was easier for me to extend this with match&nearLev than CritBitTree.

Imports

sysUt

Types

Node[T] = ref NodeOb[T]
Trie[T] = object root*: Node[T] depth*: int

Procs

proc `$`[T](t: Trie[T]): string: Return string form of t; {A,B,..} if T is void or else {A: valA, B: valB}.
proc `[]`[T](t: Trie[T]; key: string): T {.inline.}: Retrieves value at t[key] or raises KeyError if missing.
proc `[]`[T](t: var Trie[T]; key: string): var T {.inline.}: Retrieves modifiable value at t[key] or raises KeyError if missing.
proc `[]=`[T](t: var Trie[T]; key: string; val: T) {.inline.}: Inserts key, val-pair into t, overwriting if present.
proc contains[T](t: Trie[T]; key: string): bool {.inline.}
proc containsOrIncl[T](t: var Trie[T]; key: string): bool {.discardable, inline.}: Returns true iff t contains key or inserts into t if missing.
proc containsOrIncl[T](t: var Trie[T]; key: string; val: T): bool {.inline.}: Returns true iff t contains key or does t[key]=val if missing.
proc excl[T](t: var Trie[T]; key: string) {.inline.}: Remove key (and any associated value) from t or do nothing.
proc inc[T](t: var Trie[T]; key: string; val: int = 1) {.inline.}: Increments t[key] by val (starting from 0 if missing).
proc incl(t: var Trie[void]; key: string) {.inline, ...raises: [], tags: [], forbids: [].}: Includes key in t.
proc incl[T](t: var Trie[T]; key: string; val: T) {.inline.}: Inserts key with value val into t, overwriting if present
proc len[T](t: Trie[T]): int {.inline.}
proc match[T](t: Trie[T]; pat = ""; limit = 0; a1 = '?'; aN = '*'): seq[string]: Return up to limit matches of shell [?*] glob pattern pat in t.
proc mgetOrPut[T](t: var Trie[T]; key: string; val: T): var T {.inline.}: Retrieves modifiable value at t[key] or inserts if missing.
proc missingOrExcl[T](t: var Trie[T]; key: string): bool {.inline.}: t.excl(key) if present in t and return true else just return false.
proc nearLev[T](t: Trie[T]; key: string; dmax = 1; limit = 6): seq[ tuple[d: int, k: string]]: Return seq[(dist, key)] for all trie keys with Levenshtein dist from key <= dmax.
proc simplifyPattern(pat: string; a1 = '?'; aN = '*'): string {....raises: [], tags: [], forbids: [].}: Map "(>1 of ?)" --> "?" or "(>1 '?')" --> just "?".
proc toTrie(x: openArray[string]): Trie[void] {....raises: [], tags: [], forbids: [].}: Compute & return a Trie[void] based on input parameter.
proc uniquePfxPat(x: openArray[string]; sep = "*"): seq[string] {....raises: [], tags: [], forbids: [].}: Return unique prefixes in x assuming non-empty-string&unique x[i].
proc uniquePfxPat[T](t: Trie[T]; key: string; sep = "*"): string: Return shortest unique prefix pattern for key known to be in t. Unlike a shortest unique prefix string, this is well-defined for all sets. sep is only used if it can shrink total rendered space.
proc uniqueSfxPat(x: openArray[string]; sep = "*"): seq[string] {....raises: [], tags: [], forbids: [].}: Return unique suffixes in x assuming non-empty-string&unique x[i].

Iterators

iterator items[T](t: Trie[T]): string: yields all keys in lexicographical order.
iterator keys[T](t: Trie[T]): string: yields all keys in lexicographical order.
iterator keysWithPrefix[T](t: Trie[T]; prefix: string; longest = false): string: Yields all keys starting with prefix.
iterator mpairs[T](t: var Trie[T]): tuple[key: string, val: var T]: yields all (key, value)-pairs of t. The yielded values can be modified.
iterator mpairsWithPrefix[T](t: var Trie[T]; prefix: string; longest = false): tuple[ key: string, val: var T]: Yields all (key, value)-pairs of t starting with prefix. The yielded values can be modified.
iterator mvalues[T](t: var Trie[T]): var T: yields all values of t in the lexicographical order of the corresponding keys. The values can be modified.
iterator mvaluesWithPrefix[T](t: var Trie[T]; prefix: string; longest = false): var T: Yields all values of t for keys starting with prefix. The values can be modified.
iterator pairs[T](t: Trie[T]): tuple[key: string, val: T]: yields all (key, value)-pairs of t.
iterator pairsWithPrefix[T](t: Trie[T]; prefix: string; longest = false): tuple[ key: string, val: T]: Yields all (key, value)-pairs of t starting with prefix.
iterator values[T](t: Trie[T]): T: yields all values of t in the lexicographical order of the corresponding keys.
iterator valuesWithPrefix[T](t: Trie[T]; prefix: string; longest = false): T: Yields all values of t for keys starting with prefix.

cligen/trie

Imports

Types

Procs

Iterators