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.
TCritBitTree[T] = object {.pure, final.}
root: PNode[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.
proc len[T](c: TCritBitTree[T]): int
-
returns the number of elements in c in O(1).
proc contains[T](c: TCritBitTree[T]; key: string): bool {.inline.}-
returns true iff c contains the given key.
proc hasKey[T](c: TCritBitTree[T]; key: string): bool {.inline.}-
alias for contains.
proc containsOrIncl[T](c: var TCritBitTree[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.
proc containsOrIncl(c: var TCritBitTree[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.
proc incl(c: var TCritBitTree[void]; key: string) {.raises: [], tags: [].}-
includes key in c.
proc `[]=`[T](c: var TCritBitTree[T]; key: string; val: T)
-
puts a (key, value)-pair into t.
proc `[]`[T](c: var TCritBitTree[T]; key: string): T {.inline.}-
retrieves the value at c[key]. If key is not in t, default empty value for the type B is returned and no exception is raised. One can check with hasKey whether the key exists.
proc mget[T](c: var TCritBitTree[T]; key: string): var T {.inline.}-
retrieves the value at c[key]. The value can be modified. If key is not in t, the EInvalidKey exception is raised.
proc excl[T](c: var TCritBitTree[T]; key: string)
-
removes key (and its associated value) from the set c. If the key does not exist, nothing happens.
proc `$`[T](c: TCritBitTree[T]): string
-
turns c into a string representation. Example outputs: {keyA: value, keyB: value}, {:} If T is void the outputs look like: {keyA, keyB}, {}.
iterator keys[T](c: TCritBitTree[T]): string
-
yields all keys in lexicographical order.
iterator values[T](c: TCritBitTree[T]): T
-
yields all values of c in the lexicographical order of the corresponding keys.
iterator mvalues[T](c: var TCritBitTree[T]): var T
-
yields all values of c in the lexicographical order of the corresponding keys. The values can be modified.
iterator items[T](c: TCritBitTree[T]): string
-
yields all keys in lexicographical order.
iterator pairs[T](c: TCritBitTree[T]): tuple[key: string, val: T]
-
yields all (key, value)-pairs of c.
iterator mpairs[T](c: var TCritBitTree[T]): tuple[key: string, val: var T]
-
yields all (key, value)-pairs of c. The yielded values can be modified.
iterator itemsWithPrefix[T](c: TCritBitTree[T]; prefix: string): string
-
yields all keys starting with prefix.
iterator keysWithPrefix[T](c: TCritBitTree[T]; prefix: string): string
-
yields all keys starting with prefix.
iterator valuesWithPrefix[T](c: TCritBitTree[T]; prefix: string): T
-
yields all values of c starting with prefix of the corresponding keys.
iterator mvaluesWithPrefix[T](c: var TCritBitTree[T]; prefix: string): var T
-
yields all values of c starting with prefix of the corresponding keys. The values can be modified.
iterator pairsWithPrefix[T](c: TCritBitTree[T]; prefix: string): tuple[
key: string, val: T]-
yields all (key, value)-pairs of c starting with prefix.
iterator mpairsWithPrefix[T](c: var TCritBitTree[T]; prefix: string): tuple[
key: string, val: var T]-
yields all (key, value)-pairs of c starting with prefix. The yielded values can be modified.