This module implements a crit bit tree which is an efficient container for a set or a mapping of strings. Based on the excellent paper by Adam Langley.
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
Procs
proc len[T](c: CritBitTree[T]): int
- returns the number of elements in c in O(1). Source
proc contains[T](c: CritBitTree[T]; key: string): bool {.inline.}
- returns true iff c contains the given key. Source
proc hasKey[T](c: CritBitTree[T]; key: string): bool {.inline.}
- alias for contains. Source
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
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
proc inc(c: var CritBitTree[int]; key: string) {.raises: [], tags: [].}
- counts the 'key'. Source
proc incl(c: var CritBitTree[void]; key: string) {.raises: [], tags: [].}
- includes key in c. Source
proc `[]=`[T](c: var CritBitTree[T]; key: string; val: T)
- puts a (key, value)-pair into t. Source
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
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
proc mget[T](c: var CritBitTree[T]; key: string): var T {.inline, deprecated.}
- retrieves the value at c[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Use ```[]``` instead. Source
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
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
Iterators
iterator keys[T](c: CritBitTree[T]): string
- yields all keys in lexicographical order. Source
iterator values[T](c: CritBitTree[T]): T
- yields all values of c in the lexicographical order of the corresponding keys. Source
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
iterator items[T](c: CritBitTree[T]): string
- yields all keys in lexicographical order. Source
iterator pairs[T](c: CritBitTree[T]): tuple[key: string, val: T]
- yields all (key, value)-pairs of c. Source
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
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
iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): string
- yields all keys starting with prefix. Source
iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): T
- yields all values of c starting with prefix of the corresponding keys. Source
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
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
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