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:
import pure/collections/critbits from std/sequtils import toSeq var critbitAsSet: CritBitTree[void] = ["kitten", "puppy"].toCritBitTree doAssert critbitAsSet.len == 2 critbitAsSet.incl("") doAssert "" in critbitAsSet critbitAsSet.excl("") doAssert "" notin critbitAsSet doAssert toSeq(critbitAsSet.items) == @["kitten", "puppy"] let same = ["puppy", "kitten", "puppy"].toCritBitTree doAssert toSeq(same.keys) == toSeq(critbitAsSet.keys) var critbitAsDict: CritBitTree[int] = {"key1": 42}.toCritBitTree doAssert critbitAsDict.len == 1 critbitAsDict["key2"] = 0 doAssert "key2" in critbitAsDict doAssert critbitAsDict["key2"] == 0 critbitAsDict.excl("key1") doAssert "key1" notin critbitAsDict doAssert toSeq(critbitAsDict.pairs) == @[("key2", 0)]
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
func `$`[T](c: CritBitTree[T]): string
-
Turns c into a string representation.
Example:
doAssert $CritBitTree[int].default == "{:}" doAssert $toCritBitTree({"key1": 1, "key2": 2}) == """{"key1": 1, "key2": 2}""" doAssert $CritBitTree[void].default == "{}" doAssert $toCritBitTree(["key1", "key2"]) == """{"key1", "key2"}"""
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:
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:
Source Edit 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:
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 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 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:
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 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:
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 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:
var c: CritBitTree[void] incl(c, "key") excl(c, "key") doAssert not c.contains("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:
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:
Example:
var c: CritBitTree[int] incl(c, "key", 42) doAssert c["key"] == 42
Source Edit func len[T](c: CritBitTree[T]): int {.inline.}
-
Returns the number of elements in c in O(1).
Example:
let c = ["key1", "key2"].toCritBitTree doAssert c.len == 2
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:
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 toCritBitTree(items: openArray[string]): CritBitTree[void] {....raises: [], tags: [].}
-
Creates a new CritBitTree that contains the given items.
Example:
doAssert ["a", "b", "c"].toCritBitTree is CritBitTree[void]
Source Edit proc toCritBitTree[T](pairs: openArray[(string, T)]): CritBitTree[T] {..}
-
Creates a new CritBitTree that contains the given pairs.
Example:
doAssert {"a": "0", "b": "1", "c": "2"}.toCritBitTree is CritBitTree[string] doAssert {"a": 0, "b": 1, "c": 2}.toCritBitTree is CritBitTree[int]
Source Edit
Iterators
iterator itemsWithPrefix[T](c: CritBitTree[T]; prefix: string): string
- Alias for keysWithPrefix. Source Edit
iterator keys[T](c: CritBitTree[T]): string
-
Yields all keys in lexicographical order.
Example:
from std/sequtils import toSeq let c = {"key1": 1, "key2": 2}.toCritBitTree doAssert toSeq(c.keys) == @["key1", "key2"]
Source Edit iterator keysWithPrefix[T](c: CritBitTree[T]; prefix: string): string
-
Yields all keys starting with prefix.
Example:
from std/sequtils import toSeq let c = {"key1": 42, "key2": 43}.toCritBitTree doAssert toSeq(c.keysWithPrefix("key")) == @["key1", "key2"]
Source Edit 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 iterator mpairsWithPrefix[T](c: var CritBitTree[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.
See also:
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:
Source Edit 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 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:
from std/sequtils import toSeq let c = {"key1": 1, "key2": 2}.toCritBitTree doAssert toSeq(c.pairs) == @[(key: "key1", val: 1), (key: "key2", val: 2)]
Source Edit iterator pairsWithPrefix[T](c: CritBitTree[T]; prefix: string): tuple[ key: string, val: T]
-
Yields all (key, value)-pairs of c starting with prefix.
See also:
Example:
from std/sequtils import toSeq let c = {"key1": 42, "key2": 43}.toCritBitTree doAssert toSeq(c.pairsWithPrefix("key")) == @[(key: "key1", val: 42), (key: "key2", val: 43)]
Source Edit iterator values[T](c: CritBitTree[T]): T
-
Yields all values of c in the lexicographical order of the corresponding keys.
See also:
Example:
from std/sequtils import toSeq let c = {"key1": 1, "key2": 2}.toCritBitTree doAssert toSeq(c.values) == @[1, 2]
Source Edit iterator valuesWithPrefix[T](c: CritBitTree[T]; prefix: string): T
-
Yields all values of c starting with prefix of the corresponding keys.
See also:
Example:
from std/sequtils import toSeq let c = {"key1": 42, "key2": 43}.toCritBitTree doAssert toSeq(c.valuesWithPrefix("key")) == @[42, 43]
Source Edit