Source Edit

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:

  1. import std/critbits
  2. from std/sequtils import toSeq
  4. var critbitAsSet: CritBitTree[void] = ["kitten", "puppy"].toCritBitTree
  5. doAssert critbitAsSet.len == 2
  6. critbitAsSet.incl("")
  7. doAssert "" in critbitAsSet
  8. critbitAsSet.excl("")
  9. doAssert "" notin critbitAsSet
  10. doAssert toSeq(critbitAsSet.items) == @["kitten", "puppy"]
  11. let same = ["puppy", "kitten", "puppy"].toCritBitTree
  12. doAssert toSeq(same.keys) == toSeq(critbitAsSet.keys)
  14. var critbitAsDict: CritBitTree[int] = {"key1": 42}.toCritBitTree
  15. doAssert critbitAsDict.len == 1
  16. critbitAsDict["key2"] = 0
  17. doAssert "key2" in critbitAsDict
  18. doAssert critbitAsDict["key2"] == 0
  19. critbitAsDict.excl("key1")
  20. doAssert "key1" notin critbitAsDict
  21. doAssert toSeq(critbitAsDict.pairs) == @[("key2", 0)]

Imports

since

Types

  1. CritBitTree[T] = object

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

  1. func `$`[T](c: CritBitTree[T]): string

Turns c into a string representation.

Example:

  1. doAssert $CritBitTree[int].default == "{:}"
  2. doAssert $toCritBitTree({"key1": 1, "key2": 2}) == """{"key1": 1, "key2": 2}"""
  3. doAssert $CritBitTree[void].default == "{}"
  4. doAssert $toCritBitTree(["key1", "key2"]) == """{"key1", "key2"}"""

Source Edit 

  1. func `[]`[T](c: CritBitTree[T]; key: string): lent 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:

Source Edit 

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

Source Edit 

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

Alias for incl.

See also:

Source Edit 

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

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

Example:

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

Source Edit 

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

Returns true if c contains the given key.

Example:

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

Source Edit 

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

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

See also:

Example:

  1. block:
  2.   var c: CritBitTree[void]
  3.   doAssert not c.containsOrIncl("key")
  4.   doAssert c.contains("key")
  5. block:
  6.   var c: CritBitTree[void]
  7.   incl(c, "key")
  8.   doAssert c.containsOrIncl("key")

Source Edit 

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

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

See also:

Example:

  1. block:
  2.   var c: CritBitTree[int]
  3.   doAssert not c.containsOrIncl("key", 42)
  4.   doAssert c.contains("key")
  5. block:
  6.   var c: CritBitTree[int]
  7.   incl(c, "key", 21)
  8.   doAssert c.containsOrIncl("key", 42)
  9.   doAssert c["key"] == 21

Source Edit 

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

Example:

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

Source Edit 

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

Alias for contains. Source Edit 

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

Increments c[key] by val.

Example:

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

Source Edit 

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

Includes key in c.

See also:

Example:

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

Source Edit 

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

Inserts key with value val into c.

See also:

Example:

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

Source Edit 

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

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

Example:

  1. let c = ["key1", "key2"].toCritBitTree
  2. doAssert c.len == 2

Source Edit 

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

Example:

  1. block:
  2.   var c: CritBitTree[void]
  3.   doAssert c.missingOrExcl("key")
  4. block:
  5.   var c: CritBitTree[void]
  6.   incl(c, "key")
  7.   doAssert not c.missingOrExcl("key")
  8.   doAssert not c.contains("key")

Source Edit 

  1. proc toCritBitTree(items: sink openArray[string]): CritBitTree[void] {.
  2.     ...raises: [], tags: [], forbids: [].}

Creates a new CritBitTree that contains the given items.

Example:

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

Source Edit 

  1. proc toCritBitTree[T](pairs: sink openArray[(string, T)]): CritBitTree[T]

Creates a new CritBitTree that contains the given pairs.

Example:

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

Source Edit

Iterators

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

Alias for keys. Source Edit 

  1. iterator itemsWithPrefix[T](c: CritBitTree[T]; prefix: string): string

Alias for keysWithPrefix. Source Edit 

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

Yields all keys in lexicographical order.

Example:

  1. from std/sequtils import toSeq
  3. let c = {"key1": 1, "key2": 2}.toCritBitTree
  4. doAssert toSeq(c.keys) == @["key1", "key2"]

Source Edit 

  1. iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string): string

Yields all keys starting with prefix.

Example:

  1. from std/sequtils import toSeq
  3. let c = {"key1": 42, "key2": 43}.toCritBitTree
  4. doAssert toSeq(c.keysWithPrefix("key")) == @["key1", "key2"]

Source Edit 

  1. iterator mpairs[T](c: var CritBitTree[T]): tuple[key: string, val: var T]

Yields all (key, value)-pairs of c in the lexicographical order of the corresponding keys. The yielded values can be modified.

See also:

Source Edit 

  1. iterator mpairsWithPrefix[T](c: var CritBitTree[T]; prefix: string): tuple[
  2.     key: string, val: var T]

Yields all (key, value)-pairs of c starting with prefix. The yielded values can be modified.

See also:

Source Edit 

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

Source Edit 

  1. iterator mvaluesWithPrefix[T](c: var CritBitTree[T]; prefix: string): var T

Yields all values of c starting with prefix of the corresponding keys. The values can be modified.

See also:

Source Edit 

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

Yields all (key, value)-pairs of c in the lexicographical order of the corresponding keys.

See also:

Example:

  1. from std/sequtils import toSeq
  3. let c = {"key1": 1, "key2": 2}.toCritBitTree
  4. doAssert toSeq(c.pairs) == @[(key: "key1", val: 1), (key: "key2", val: 2)]

Source Edit 

  1. iterator pairsWithPrefix[T](c: CritBitTree[T]; prefix: string): tuple[
  2.     key: string, val: T]

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

See also:

Example:

  1. from std/sequtils import toSeq
  3. let c = {"key1": 42, "key2": 43}.toCritBitTree
  4. doAssert toSeq(c.pairsWithPrefix("key")) == @[(key: "key1", val: 42), (key: "key2", val: 43)]

Source Edit 

  1. iterator values[T](c: CritBitTree[T]): lent T

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

See also:

Example:

  1. from std/sequtils import toSeq
  3. let c = {"key1": 1, "key2": 2}.toCritBitTree
  4. doAssert toSeq(c.values) == @[1, 2]

Source Edit 

  1. iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string): lent T

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

See also:

Example:

  1. from std/sequtils import toSeq
  3. let c = {"key1": 42, "key2": 43}.toCritBitTree
  4. doAssert toSeq(c.valuesWithPrefix("key")) == @[42, 43]

Source Edit