Module 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.)

Imports

sequtils

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.

Procs

proc len[T](c: CritBitTree[T]): int

returns the number of elements in c in O(1).

proc contains[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}

returns true iff c contains the given key.

proc hasKey[T](c: CritBitTree[T]; key: string): bool {...}{.inline.}

alias for contains.

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.

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.

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.

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.

proc inc(c: var CritBitTree[int]; key: string; val: int = 1) {...}{.raises: [], tags: [].}

increments c[key] by val.

proc incl(c: var CritBitTree[void]; key: string) {...}{.raises: [], tags: [].}

includes key in c.

proc incl[T](c: var CritBitTree[T]; key: string; val: T)

inserts key with value val into c.

proc `[]=`[T](c: var CritBitTree[T]; key: string; val: T)

puts a (key, value)-pair into t.

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.

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.

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.

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}, {}.

Iterators

iterator keys[T](c: CritBitTree[T]): string

yields all keys in lexicographical order.

iterator values[T](c: CritBitTree[T]): T

yields all values of c in the lexicographical order of the corresponding keys.

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.

iterator items[T](c: CritBitTree[T]): string

yields all keys in lexicographical order.

iterator pairs[T](c: CritBitTree[T]): tuple[key: string, val: T]

yields all (key, value)-pairs of c.

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.

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.

iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): string

yields all keys starting with prefix.

iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string; longestMatch = false): T

yields all values of c starting with prefix of the corresponding keys.

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.

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.

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.