# std/critbits

Dark Mode

- Manual
- Standard library
- Index
- Compiler docs
- Fusion docs
- devel, stable

Search:
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:

    import std/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)]

# 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

    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

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

  Alias for incl.

  See also:

  - [] proc
  - [] proc
  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 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:

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

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

  Alias for contains. 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

    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:

  - 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 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 items[T](c: CritBitTree[T]): string

  Alias for keys. Source Edit

    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:

  - pairs iterator
  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:

  - pairsWithPrefix iterator
  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 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:

  - valuesWithPrefix iterator
  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:

  - mpairs iterator

  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:

  - mpairsWithPrefix iterator

  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:

  - mvalues iterator

  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:

  - mvaluesWithPrefix iterator

  Example:

      from std/sequtils import toSeq

      let c = {"key1": 42, "key2": 43}.toCritBitTree
      doAssert toSeq(c.valuesWithPrefix("key")) == @[42, 43]

  Source Edit