critbits

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