diff options
Diffstat (limited to 'lib/pure/collections/critbits.nim')
| -rw-r--r-- | lib/pure/collections/critbits.nim | 525 |
1 files changed, 380 insertions, 145 deletions
diff --git a/lib/pure/collections/critbits.nim b/lib/pure/collections/critbits.nim index 40a02b651..24257dacb 100644 --- a/lib/pure/collections/critbits.nim +++ b/lib/pure/collections/critbits.nim @@ -1,6 +1,6 @@ # # -# Nimrod's Runtime Library +# Nim's Runtime Library # (c) Copyright 2012 Andreas Rumpf # # See the file "copying.txt", included in this @@ -8,34 +8,65 @@ # ## This module implements a `crit bit tree`:idx: which is an efficient -## container for a set or a mapping of strings. Based on the excellent paper -## by Adam Langley. +## container for a sorted set of strings, or for a sorted mapping of strings. Based on the +## [excellent paper by Adam Langley](https://www.imperialviolet.org/binary/critbit.pdf). +## (A crit bit tree is a form of `radix tree`:idx: or `patricia trie`:idx:.) + +runnableExamples: + 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)] + +import std/private/since + +when defined(nimPreviewSlimSystem): + import std/assertions type - TNode[T] = object {.pure, final, acyclic.} + NodeObj[T] {.acyclic.} = object byte: int ## byte index of the difference - otherbits: char + otherBits: char case isLeaf: bool - of false: child: array[0..1, ref TNode[T]] - of true: + of false: child: array[0..1, ref NodeObj[T]] + of true: key: string when T isnot void: val: T - - PNode[T] = ref TNode[T] - TCritBitTree*[T] = object {. - pure, final.} ## 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. - root: PNode[T] + + Node[T] = ref NodeObj[T] + 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`. + root: Node[T] count: int - -proc len*[T](c: TCritBitTree[T]): int = - ## returns the number of elements in `c` in O(1). + +func len*[T](c: CritBitTree[T]): int {.inline.} = + ## Returns the number of elements in `c` in O(1). + runnableExamples: + let c = ["key1", "key2"].toCritBitTree + doAssert c.len == 2 + result = c.count -proc rawGet[T](c: TCritBitTree[T], key: string): PNode[T] = +proc rawGet[T](c: CritBitTree[T], key: string): Node[T] = var it = c.root while it != nil: if not it.isLeaf: @@ -45,19 +76,22 @@ proc rawGet[T](c: TCritBitTree[T], key: string): PNode[T] = else: return if it.key == key: it else: nil -proc contains*[T](c: TCritBitTree[T], key: string): bool {.inline.} = - ## returns true iff `c` contains the given `key`. +func contains*[T](c: CritBitTree[T], key: string): bool {.inline.} = + ## Returns true if `c` contains the given `key`. + runnableExamples: + var c: CritBitTree[void] + incl(c, "key") + doAssert c.contains("key") + result = rawGet(c, key) != nil -proc hasKey*[T](c: TCritBitTree[T], key: string): bool {.inline.} = - ## alias for `contains`. +func hasKey*[T](c: CritBitTree[T], key: string): bool {.inline.} = + ## Alias for `contains <#contains,CritBitTree[T],string>`_. result = rawGet(c, key) != nil -proc rawInsert[T](c: var TCritBitTree[T], key: string): PNode[T] = +proc rawInsert[T](c: var CritBitTree[T], key: string): Node[T] = if c.root == nil: - new c.root - c.root.isleaf = true - c.root.key = key + c.root = Node[T](isleaf: true, key: key) result = c.root else: var it = c.root @@ -65,34 +99,33 @@ proc rawInsert[T](c: var TCritBitTree[T], key: string): PNode[T] = let ch = if it.byte < key.len: key[it.byte] else: '\0' let dir = (1 + (ch.ord or it.otherBits.ord)) shr 8 it = it.child[dir] - + var newOtherBits = 0 var newByte = 0 block blockX: - while newbyte < key.len: - if it.key[newbyte] != key[newbyte]: - newotherbits = it.key[newbyte].ord xor key[newbyte].ord + while newByte < key.len: + let ch = if newByte < it.key.len: it.key[newByte] else: '\0' + if ch != key[newByte]: + newOtherBits = ch.ord xor key[newByte].ord break blockX - inc newbyte - if it.key[newbyte] != '\0': - newotherbits = it.key[newbyte].ord + inc newByte + if newByte < it.key.len: + newOtherBits = it.key[newByte].ord else: return it while (newOtherBits and (newOtherBits-1)) != 0: newOtherBits = newOtherBits and (newOtherBits-1) newOtherBits = newOtherBits xor 255 - let ch = it.key[newByte] + let ch = if newByte < it.key.len: it.key[newByte] else: '\0' let dir = (1 + (ord(ch) or newOtherBits)) shr 8 - - var inner: PNode[T] + + var inner: Node[T] new inner - new result - result.isLeaf = true - result.key = key + result = Node[T](isLeaf: true, key: key) inner.otherBits = chr(newOtherBits) inner.byte = newByte inner.child[1 - dir] = result - + var wherep = addr(c.root) while true: var p = wherep[] @@ -106,76 +139,195 @@ proc rawInsert[T](c: var TCritBitTree[T], key: string): PNode[T] = wherep[] = inner inc c.count -proc containsOrIncl*[T](c: var TCritBitTree[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. +func exclImpl[T](c: var CritBitTree[T], key: string): int = + var p = c.root + var wherep = addr(c.root) + var whereq: ptr Node[T] = nil + if p == nil: return c.count + var dir = 0 + var q: Node[T] + while not p.isLeaf: + whereq = wherep + q = p + let ch = if p.byte < key.len: key[p.byte] else: '\0' + dir = (1 + (ch.ord or p.otherBits.ord)) shr 8 + wherep = addr(p.child[dir]) + p = wherep[] + if p.key == key: + # else: not in tree at all + if whereq == nil: + c.root = nil + else: + whereq[] = q.child[1 - dir] + dec c.count + + return c.count + +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,CritBitTree[void],string>`_ + ## * `incl proc <#incl,CritBitTree[T],string,T>`_ + runnableExamples: + var c: CritBitTree[void] + incl(c, "key") + excl(c, "key") + doAssert not c.contains("key") + + discard exclImpl(c, key) + +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 <#excl,CritBitTree[T],string>`_ + ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[T],string,T>`_ + ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[void],string>`_ + runnableExamples: + 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") + + let oldCount = c.count + discard exclImpl(c, key) + result = c.count == oldCount + +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:** + ## * `incl proc <#incl,CritBitTree[void],string>`_ + ## * `incl proc <#incl,CritBitTree[T],string,T>`_ + ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[void],string>`_ + ## * `missingOrExcl proc <#missingOrExcl,CritBitTree[T],string>`_ + runnableExamples: + 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 + let oldCount = c.count var n = rawInsert(c, key) result = c.count == oldCount when T isnot void: if not result: n.val = val -proc containsOrIncl*(c: var TCritBitTree[void], key: string): bool = - ## returns true iff `c` contains the given `key`. If the key does not exist +proc containsOrIncl*(c: var CritBitTree[void], key: string): bool = + ## Returns true if `c` contains the given `key`. If the key does not exist, ## it is inserted into `c`. + ## + ## **See also:** + ## * `incl proc <#incl,CritBitTree[void],string>`_ + ## * `incl proc <#incl,CritBitTree[T],string,T>`_ + ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[T],string,T>`_ + ## * `missingOrExcl proc <#missingOrExcl,CritBitTree[T],string>`_ + runnableExamples: + 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") + let oldCount = c.count - var n = rawInsert(c, key) + discard rawInsert(c, key) result = c.count == oldCount -proc incl*(c: var TCritBitTree[void], key: string) = - ## includes `key` in `c`. +proc inc*(c: var CritBitTree[int]; key: string, val: int = 1) = + ## Increments `c[key]` by `val`. + runnableExamples: + var c: CritBitTree[int] + c["key"] = 1 + inc(c, "key") + doAssert c["key"] == 2 + + var n = rawInsert(c, key) + inc n.val, val + +proc incl*(c: var CritBitTree[void], key: string) = + ## Includes `key` in `c`. + ## + ## **See also:** + ## * `excl proc <#excl,CritBitTree[T],string>`_ + ## * `incl proc <#incl,CritBitTree[T],string,T>`_ + runnableExamples: + var c: CritBitTree[void] + incl(c, "key") + doAssert c.hasKey("key") + discard rawInsert(c, key) -proc `[]=`*[T](c: var TCritBitTree[T], key: string, val: T) = - ## puts a (key, value)-pair into `t`. +proc incl*[T](c: var CritBitTree[T], key: string, val: sink T) = + ## Inserts `key` with value `val` into `c`. + ## + ## **See also:** + ## * `excl proc <#excl,CritBitTree[T],string>`_ + ## * `incl proc <#incl,CritBitTree[void],string>`_ + runnableExamples: + var c: CritBitTree[int] + incl(c, "key", 42) + doAssert c["key"] == 42 + var n = rawInsert(c, key) n.val = val -proc `[]`*[T](c: var TCritBitTree[T], key: string): T {.inline.} = - ## retrieves the value at ``c[key]``. If `key` is not in `t`, - ## default empty value for the type `B` is returned - ## and no exception is raised. One can check with ``hasKey`` whether the key - ## exists. - let n = rawGet(c, key) - if n != nil: result = n.val +proc `[]=`*[T](c: var CritBitTree[T], key: string, val: sink T) = + ## Alias for `incl <#incl,CritBitTree[T],string,T>`_. + ## + ## **See also:** + ## * `[] proc <#[],CritBitTree[T],string>`_ + ## * `[] proc <#[],CritBitTree[T],string_2>`_ + var n = rawInsert(c, key) + n.val = val -proc mget*[T](c: var TCritBitTree[T], key: string): var T {.inline.} = - ## retrieves the value at ``c[key]``. The value can be modified. - ## If `key` is not in `t`, the ``EInvalidKey`` exception is raised. +template get[T](c: CritBitTree[T], key: string): T = let n = rawGet(c, key) - if n != nil: result = n.val - else: raise newException(EInvalidKey, "key not found: " & $key) + if n == nil: + raise newException(KeyError, "key not found: " & key) -proc excl*[T](c: var TCritBitTree[T], key: string) = - ## removes `key` (and its associated value) from the set `c`. - ## If the `key` does not exist, nothing happens. - var p = c.root - var wherep = addr(c.root) - var whereq: ptr PNode = nil - if p == nil: return - var dir = 0 - var q: PNode - while not p.isLeaf: - whereq = wherep - q = p - let ch = if p.byte < key.len: key[p.byte] else: '\0' - dir = (1 + (ch.ord or p.otherBits.ord)) shr 8 - wherep = addr(p.child[dir]) - p = wherep[] - if p.key == key: - # else: not in tree at all - if whereq == nil: - c.root = nil - else: - whereq[] = q.child[1 - dir] - dec c.count + n.val + +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:** + ## * `[] proc <#[],CritBitTree[T],string_2>`_ + ## * `[]= proc <#[]=,CritBitTree[T],string,T>`_ + get(c, key) + +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 <#[],CritBitTree[T],string>`_ + ## * `[]= proc <#[]=,CritBitTree[T],string,T>`_ + get(c, key) -iterator leaves[T](n: PNode[T]): PNode[T] = +iterator leaves[T](n: Node[T]): Node[T] = if n != nil: # XXX actually we could compute the necessary stack size in advance: - # it's rougly log2(c.count). + # it's roughly log2(c.count). var stack = @[n] - while stack.len > 0: + while stack.len > 0: var it = stack.pop while not it.isLeaf: stack.add(it.child[1]) @@ -183,33 +335,65 @@ iterator leaves[T](n: PNode[T]): PNode[T] = assert(it != nil) yield it -iterator keys*[T](c: TCritBitTree[T]): string = - ## yields all keys in lexicographical order. +iterator keys*[T](c: CritBitTree[T]): string = + ## Yields all keys in lexicographical order. + runnableExamples: + from std/sequtils import toSeq + + let c = {"key1": 1, "key2": 2}.toCritBitTree + doAssert toSeq(c.keys) == @["key1", "key2"] + for x in leaves(c.root): yield x.key -iterator values*[T](c: TCritBitTree[T]): T = - ## yields all values of `c` in the lexicographical order of the +iterator values*[T](c: CritBitTree[T]): lent T = + ## Yields all values of `c` in the lexicographical order of the ## corresponding keys. + ## + ## **See also:** + ## * `mvalues iterator <#mvalues.i,CritBitTree[T]>`_ + runnableExamples: + from std/sequtils import toSeq + + let c = {"key1": 1, "key2": 2}.toCritBitTree + doAssert toSeq(c.values) == @[1, 2] + for x in leaves(c.root): yield x.val -iterator mvalues*[T](c: var TCritBitTree[T]): var T = - ## yields all values of `c` in the lexicographical order of the +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 <#values.i,CritBitTree[T]>`_ for x in leaves(c.root): yield x.val -iterator items*[T](c: TCritBitTree[T]): string = - ## yields all keys in lexicographical order. +iterator items*[T](c: CritBitTree[T]): string = + ## Alias for `keys <#keys.i,CritBitTree[T]>`_. for x in leaves(c.root): yield x.key -iterator pairs*[T](c: TCritBitTree[T]): tuple[key: string, val: T] = - ## yields all (key, value)-pairs of `c`. +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 <#mpairs.i,CritBitTree[T]>`_ + runnableExamples: + from std/sequtils import toSeq + + let c = {"key1": 1, "key2": 2}.toCritBitTree + doAssert toSeq(c.pairs) == @[(key: "key1", val: 1), (key: "key2", val: 2)] + for x in leaves(c.root): yield (x.key, x.val) - -iterator mpairs*[T](c: var TCritBitTree[T]): tuple[key: string, val: var T] = - ## yields all (key, value)-pairs of `c`. The yielded values can be modified. + +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 <#pairs.i,CritBitTree[T]>`_ for x in leaves(c.root): yield (x.key, x.val) -proc allprefixedAux[T](c: TCritBitTree[T], key: string): PNode[T] = +proc allprefixedAux[T](c: CritBitTree[T], key: string): Node[T] = var p = c.root var top = p if p != nil: @@ -219,50 +403,83 @@ proc allprefixedAux[T](c: TCritBitTree[T], key: string): PNode[T] = let dir = (1 + (ch.ord or p.otherBits.ord)) shr 8 p = p.child[dir] if q.byte < key.len: top = p - for i in 0 .. <key.len: - if p.key[i] != key[i]: return + for i in 0 ..< key.len: + if i >= p.key.len or p.key[i] != key[i]: return result = top -iterator itemsWithPrefix*[T](c: TCritBitTree[T], prefix: string): string = - ## yields all keys starting with `prefix`. - let top = allprefixedAux(c, prefix) - for x in leaves(top): yield x.key +iterator keysWithPrefix*[T](c: CritBitTree[T], prefix: string): string = + ## Yields all keys starting with `prefix`. + runnableExamples: + from std/sequtils import toSeq + + let c = {"key1": 42, "key2": 43}.toCritBitTree + doAssert toSeq(c.keysWithPrefix("key")) == @["key1", "key2"] -iterator keysWithPrefix*[T](c: TCritBitTree[T], prefix: string): string = - ## yields all keys starting with `prefix`. let top = allprefixedAux(c, prefix) for x in leaves(top): yield x.key -iterator valuesWithPrefix*[T](c: TCritBitTree[T], prefix: string): T = - ## yields all values of `c` starting with `prefix` of the +iterator valuesWithPrefix*[T](c: CritBitTree[T], prefix: string): lent T = + ## Yields all values of `c` starting with `prefix` of the ## corresponding keys. + ## + ## **See also:** + ## * `mvaluesWithPrefix iterator <#mvaluesWithPrefix.i,CritBitTree[T],string>`_ + runnableExamples: + from std/sequtils import toSeq + + let c = {"key1": 42, "key2": 43}.toCritBitTree + doAssert toSeq(c.valuesWithPrefix("key")) == @[42, 43] + let top = allprefixedAux(c, prefix) for x in leaves(top): yield x.val -iterator mvaluesWithPrefix*[T](c: var TCritBitTree[T], prefix: string): var T = - ## yields all values of `c` starting with `prefix` of the +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 <#valuesWithPrefix.i,CritBitTree[T],string>`_ let top = allprefixedAux(c, prefix) for x in leaves(top): yield x.val -iterator pairsWithPrefix*[T](c: TCritBitTree[T], +iterator itemsWithPrefix*[T](c: CritBitTree[T], prefix: string): string = + ## Alias for `keysWithPrefix <#keysWithPrefix.i,CritBitTree[T],string>`_. + let top = allprefixedAux(c, prefix) + for x in leaves(top): yield x.key + +iterator pairsWithPrefix*[T](c: CritBitTree[T], prefix: string): tuple[key: string, val: T] = - ## yields all (key, value)-pairs of `c` starting with `prefix`. + ## Yields all (key, value)-pairs of `c` starting with `prefix`. + ## + ## **See also:** + ## * `mpairsWithPrefix iterator <#mpairsWithPrefix.i,CritBitTree[T],string>`_ + runnableExamples: + 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)] + let top = allprefixedAux(c, prefix) for x in leaves(top): yield (x.key, x.val) - -iterator mpairsWithPrefix*[T](c: var TCritBitTree[T], + +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`. + ## Yields all (key, value)-pairs of `c` starting with `prefix`. ## The yielded values can be modified. + ## + ## **See also:** + ## * `pairsWithPrefix iterator <#pairsWithPrefix.i,CritBitTree[T],string>`_ let top = allprefixedAux(c, prefix) for x in leaves(top): yield (x.key, x.val) -proc `$`*[T](c: TCritBitTree[T]): string = - ## turns `c` into a string representation. Example outputs: - ## ``{keyA: value, keyB: value}``, ``{:}`` - ## If `T` is void the outputs look like: - ## ``{keyA, keyB}``, ``{}``. +func `$`*[T](c: CritBitTree[T]): string = + ## Turns `c` into a string representation. + runnableExamples: + doAssert $CritBitTree[int].default == "{:}" + doAssert $toCritBitTree({"key1": 1, "key2": 2}) == """{"key1": 1, "key2": 2}""" + doAssert $CritBitTree[void].default == "{}" + doAssert $toCritBitTree(["key1", "key2"]) == """{"key1", "key2"}""" + if c.len == 0: when T is void: result = "{}" @@ -276,27 +493,45 @@ proc `$`*[T](c: TCritBitTree[T]): string = const avgItemLen = 16 result = newStringOfCap(c.count * avgItemLen) result.add("{") - for key, val in pairs(c): - if result.len > 1: result.add(", ") - result.add($key) - when T isnot void: + when T is void: + for key in keys(c): + if result.len > 1: result.add(", ") + result.addQuoted(key) + else: + for key, val in pairs(c): + if result.len > 1: result.add(", ") + result.addQuoted(key) result.add(": ") - result.add($val) + result.addQuoted(val) result.add("}") -when isMainModule: - var r: TCritBitTree[void] - r.incl "abc" - r.incl "xyz" - r.incl "def" - r.incl "definition" - r.incl "prefix" - doAssert r.contains"def" - #r.del "def" - - for w in r.items: - echo w - - for w in r.itemsWithPrefix("de"): - echo w +func commonPrefixLen*[T](c: CritBitTree[T]): int {.inline, since((1, 3)).} = + ## Returns the length of the longest common prefix of all keys in `c`. + ## If `c` is empty, returns 0. + runnableExamples: + var c: CritBitTree[void] + doAssert c.commonPrefixLen == 0 + incl(c, "key1") + doAssert c.commonPrefixLen == 4 + incl(c, "key2") + doAssert c.commonPrefixLen == 3 + + if c.root != nil: + if c.root.isLeaf: len(c.root.key) + else: c.root.byte + else: 0 + +proc toCritBitTree*[T](pairs: sink openArray[(string, T)]): CritBitTree[T] {.since: (1, 3).} = + ## Creates a new `CritBitTree` that contains the given `pairs`. + runnableExamples: + doAssert {"a": "0", "b": "1", "c": "2"}.toCritBitTree is CritBitTree[string] + doAssert {"a": 0, "b": 1, "c": 2}.toCritBitTree is CritBitTree[int] + + for item in pairs: result.incl item[0], item[1] + +proc toCritBitTree*(items: sink openArray[string]): CritBitTree[void] {.since: (1, 3).} = + ## Creates a new `CritBitTree` that contains the given `items`. + runnableExamples: + doAssert ["a", "b", "c"].toCritBitTree is CritBitTree[void] + for item in items: result.incl item |