This module implements a crit bit tree which is an efficient container for a sorted set of strings, or for a sorted mapping of strings. Based on the excellent paper by Adam Langley. (A crit bit tree is a form of radix tree or patricia trie.)
Types
CritBitTree[T] = object root: Node[T] count: int
- The crit bit tree can either be used as a mapping from strings to some type T or as a set of strings if T is void. Source Edit
Procs
proc len[T](c: CritBitTree[T]): int
- returns the number of elements in c in O(1). Source Edit
proc contains[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}
- returns true iff c contains the given key. Source Edit
proc hasKey[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}
- alias for contains. Source Edit
proc excl[T](c: var CritBitTree[T]; key: string)
- removes key (and its associated value) from the set c. If the key does not exist, nothing happens. Source Edit
proc missingOrExcl[T](c: var CritBitTree[T]; key: string): bool
- Returns true iff c does not contain the given key. If the key does exist, c.excl(key) is performed. Source Edit
proc containsOrIncl[T](c: var CritBitTree[T]; key: string; val: T): bool
- returns true iff c contains the given key. If the key does not exist c[key] = val is performed. Source Edit
proc containsOrIncl(c: var CritBitTree[void]; key: string): bool {...}{.raises: [], tags: [].}
- returns true iff c contains the given key. If the key does not exist it is inserted into c. Source Edit
proc inc(c: var CritBitTree[int]; key: string; val: int = 1) {...}{.raises: [], tags: [].}
- increments c[key] by val. Source Edit
proc incl(c: var CritBitTree[void]; key: string) {...}{.raises: [], tags: [].}
- includes key in c. Source Edit
proc incl[T](c: var CritBitTree[T]; key: string; val: T)
- inserts key with value val into c. Source Edit
proc `[]=`[T](c: var CritBitTree[T]; key: string; val: T)
- puts a (key, value)-pair into t. Source Edit
proc `[]`[T](c: CritBitTree[T]; key: string): T {...}{.inline.}
- retrieves the value at c[key]. If key is not in t, the KeyError exception is raised. One can check with hasKey whether the key exists. Source Edit
proc `[]`[T](c: var CritBitTree[T]; key: string): var T {...}{.inline.}
- retrieves the value at c[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Source Edit
proc `$`[T](c: CritBitTree[T]): string
- turns c into a string representation. Example outputs: {keyA: value, keyB: value}, {:} If T is void the outputs look like: {keyA, keyB}, {}. Source Edit
Iterators
iterator keys[T](c: CritBitTree[T]): string
- yields all keys in lexicographical order. Source Edit
iterator values[T](c: CritBitTree[T]): T
- yields all values of c in the lexicographical order of the corresponding keys. Source Edit
iterator mvalues[T](c: var CritBitTree[T]): var T
- yields all values of c in the lexicographical order of the corresponding keys. The values can be modified. Source Edit
iterator items[T](c: CritBitTree[T]): string
- yields all keys in lexicographical order. Source Edit
iterator pairs[T](c: CritBitTree[T]): tuple[key: string, val: T]
- yields all (key, value)-pairs of c. Source Edit
iterator mpairs[T](c: var CritBitTree[T]): tuple[key: string, val: var T]
- yields all (key, value)-pairs of c. The yielded values can be modified. Source Edit
iterator itemsWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): string
- yields all keys starting with prefix. If longestMatch is true, the longest match is returned, it doesn't have to be a complete match then. Source Edit
iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): string
- yields all keys starting with prefix. Source Edit
iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): T
- yields all values of c starting with prefix of the corresponding keys. Source Edit
iterator mvaluesWithPrefix[T](c: var CritBitTree[T]; prefix: string; longestMatch = false): var T
- yields all values of c starting with prefix of the corresponding keys. The values can be modified. Source Edit
iterator pairsWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): tuple[ key: string, val: T]
- yields all (key, value)-pairs of c starting with prefix. Source Edit
iterator mpairsWithPrefix[T](c: var CritBitTree[T]; prefix: string; longestMatch = false): tuple[key: string, val: var T]
- yields all (key, value)-pairs of c starting with prefix. The yielded values can be modified. Source Edit