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

Example:

static:
  block:
    var critbitAsSet: CritBitTree[void]
    doAssert critbitAsSet.len == 0
    incl critbitAsSet, "kitten"
    doAssert critbitAsSet.len == 1
    incl critbitAsSet, "puppy"
    doAssert critbitAsSet.len == 2
    incl critbitAsSet, "kitten"
    doAssert critbitAsSet.len == 2
    incl critbitAsSet, ""
    doAssert critbitAsSet.len == 3
block:
  var critbitAsDict: CritBitTree[int]
  critbitAsDict["key"] = 42
  doAssert critbitAsDict["key"] == 42
  critbitAsDict["key"] = 0
  doAssert critbitAsDict["key"] == 0
  critbitAsDict["key"] = -int.high
  doAssert critbitAsDict["key"] == -int.high
  critbitAsDict["key"] = int.high
  doAssert critbitAsDict["key"] == int.high

Imports

since

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

See also:

• incl proc
• incl proc

Example:

var c: CritBitTree[void]
incl(c, "key")
excl(c, "key")
doAssert not c.contains("key")

Source Edit

proc missingOrExcl[T](c: var CritBitTree[T]; key: string): bool

Returns true if c does not contain the given key. If the key does exist, c.excl(key) is performed.

See also:

• excl proc
• containsOrIncl proc
• containsOrIncl proc

Example:

block:
  var c: CritBitTree[void]
  doAssert c.missingOrExcl("key")
block:
  var c: CritBitTree[void]
  incl(c, "key")
  doAssert not c.missingOrExcl("key")
  doAssert not c.contains("key")

Source Edit

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

Returns true if c contains the given key. If the key does not exist c[key] = val is performed.

See also:

• incl proc
• incl proc
• containsOrIncl proc
• missingOrExcl proc

Example:

block:
  var c: CritBitTree[int]
  doAssert not c.containsOrIncl("key", 42)
  doAssert c.contains("key")
block:
  var c: CritBitTree[int]
  incl(c, "key", 21)
  doAssert c.containsOrIncl("key", 42)
  doAssert c["key"] == 21

Source Edit

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

Returns true if c contains the given key. If the key does not exist it is inserted into c.

See also:

• incl proc
• incl proc
• containsOrIncl proc
• missingOrExcl proc

Example:

block:
  var c: CritBitTree[void]
  doAssert not c.containsOrIncl("key")
  doAssert c.contains("key")
block:
  var c: CritBitTree[void]
  incl(c, "key")
  doAssert c.containsOrIncl("key")

Source Edit

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

Increments c[key] by val.

Example:

var c: CritBitTree[int]
c["key"] = 1
inc(c, "key")
doAssert c["key"] == 2

Source Edit

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

Includes key in c.

See also:

• excl proc
• incl proc

Example:

var c: CritBitTree[void]
incl(c, "key")
doAssert c.hasKey("key")

Source Edit

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

Inserts key with value val into c.

See also:

• excl proc
• incl proc

Example:

var c: CritBitTree[int]
incl(c, "key", 42)
doAssert c["key"] == 42

Source Edit

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

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

See also:

• [] proc
• [] proc

Example:

var c: CritBitTree[int]
c["key"] = 42
doAssert c["key"] == 42

Source Edit

Funcs

func len[T](c: CritBitTree[T]): int {...}{.inline.}

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

Example:

var c: CritBitTree[void]
incl(c, "key1")
incl(c, "key2")
doAssert c.len == 2

Source Edit

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

Returns true if c contains the given key.

Example:

var c: CritBitTree[void]
incl(c, "key")
doAssert c.contains("key")

Source Edit

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

Alias for contains. Source Edit

func `[]`[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.

See also:

• [] proc
• []= proc

Source Edit

func `[]`[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.

See also:

• [] proc
• []= proc

Source Edit

func `$`[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

func commonPrefixLen[T](c: CritBitTree[T]): int {...}{.inline.}

Returns longest common prefix length of all keys of c. If c is empty, returns 0.

Example:

var c: CritBitTree[void]
doAssert c.commonPrefixLen == 0
incl(c, "key1")
doAssert c.commonPrefixLen == 4
incl(c, "key2")
doAssert c.commonPrefixLen == 3

Source Edit

func toCritBitTree[A, B](pairs: openArray[(A, B)]): CritBitTree[A]

Creates a new CritBitTree that contains the given pairs.

Example:

doAssert {"a": "0", "b": "1", "c": "2"}.toCritBitTree is CritBitTree[string]

Source Edit

func toCritBitTree[T](items: openArray[T]): CritBitTree[void]

Creates a new CritBitTree that contains the given items.

Example:

doAssert ["a", "b", "c"].toCritBitTree is CritBitTree[void]

Source Edit

Iterators

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

Yields all keys in lexicographical order.

Example:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var keys: seq[string]
for key in c.keys:
  keys.add(key)
doAssert keys == @["key1", "key2"]

Source Edit

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

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

Example:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var vals: seq[int]
for val in c.values:
  vals.add(val)
doAssert vals == @[1, 2]

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.

See also:

• values iterator

Source Edit

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

Yields all keys in lexicographical order.

Example:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var keys: seq[string]
for key in c.items:
  keys.add(key)
doAssert keys == @["key1", "key2"]

Source Edit

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

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

Example:

var c: CritBitTree[int]
c["key1"] = 1
c["key2"] = 2
var ps: seq[tuple[key: string, val: int]]
for p in c.pairs:
  ps.add(p)
doAssert ps == @[(key: "key1", val: 1), (key: "key2", val: 2)]

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.

See also:

• pairs iterator

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.

Example:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var keys: seq[string]
for key in c.itemsWithPrefix("key"):
  keys.add(key)
doAssert keys == @["key1", "key2"]

Source Edit

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

Yields all keys starting with prefix.

Example:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var keys: seq[string]
for key in c.keysWithPrefix("key"):
  keys.add(key)
doAssert keys == @["key1", "key2"]

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.

Example:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var vals: seq[int]
for val in c.valuesWithPrefix("key"):
  vals.add(val)
doAssert vals == @[42, 43]

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.

See also:

• valuesWithPrefix iterator

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.

Example:

var c: CritBitTree[int]
c["key1"] = 42
c["key2"] = 43
var ps: seq[tuple[key: string, val: int]]
for p in c.pairsWithPrefix("key"):
  ps.add(p)
doAssert ps == @[(key: "key1", val: 42), (key: "key2", val: 43)]

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.

See also:

• pairsWithPrefix iterator

Source Edit