diff options
author | konsumlamm <44230978+konsumlamm@users.noreply.github.com> | 2021-01-04 07:25:05 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-01-03 22:25:05 -0800 |
commit | 763fef59fa9bf618f9b546dcb199872b5d8ee890 (patch) | |
tree | 0e37d078c87f2ba293aece8ccecb2868e6ca4132 | |
parent | a0134671eeed3cfac1e9035568cbdec41825da8d (diff) | |
download | Nim-763fef59fa9bf618f9b546dcb199872b5d8ee890.tar.gz |
Improve documentation for critbits (#16568)
-rw-r--r-- | lib/pure/collections/critbits.nim | 242 |
1 files changed, 107 insertions, 135 deletions
diff --git a/lib/pure/collections/critbits.nim b/lib/pure/collections/critbits.nim index a4e727909..113939567 100644 --- a/lib/pure/collections/critbits.nim +++ b/lib/pure/collections/critbits.nim @@ -8,10 +8,32 @@ # ## This module implements a `crit bit tree`:idx: 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. +## 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 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 type @@ -28,17 +50,15 @@ type 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. + ## some type `T` or as a set of + ## strings if `T` is `void`. root: Node[T] count: int func len*[T](c: CritBitTree[T]): int {.inline.} = ## Returns the number of elements in `c` in O(1). runnableExamples: - var c: CritBitTree[void] - incl(c, "key1") - incl(c, "key2") + let c = ["key1", "key2"].toCritBitTree doAssert c.len == 2 result = c.count @@ -144,7 +164,7 @@ 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: + ## **See also:** ## * `incl proc <#incl,CritBitTree[void],string>`_ ## * `incl proc <#incl,CritBitTree[T],string,T>`_ runnableExamples: @@ -157,9 +177,9 @@ proc excl*[T](c: var CritBitTree[T], key: string) = 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. + ## does exist, `c.excl(key)` is performed. ## - ## See also: + ## **See also:** ## * `excl proc <#excl,CritBitTree[T],string>`_ ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[T],string,T>`_ ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[void],string>`_ @@ -178,10 +198,10 @@ proc missingOrExcl*[T](c: var CritBitTree[T], key: string): bool = result = c.count == oldCount 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. + ## Returns true if `c` contains the given `key`. If the key does not exist, + ## `c[key] = val` is performed. ## - ## See also: + ## **See also:** ## * `incl proc <#incl,CritBitTree[void],string>`_ ## * `incl proc <#incl,CritBitTree[T],string,T>`_ ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[void],string>`_ @@ -204,10 +224,10 @@ proc containsOrIncl*[T](c: var CritBitTree[T], key: string, val: T): bool = if not result: n.val = val proc containsOrIncl*(c: var CritBitTree[void], key: string): bool = - ## Returns true if `c` contains the given `key`. If the key does not exist + ## Returns true if `c` contains the given `key`. If the key does not exist, ## it is inserted into `c`. ## - ## See also: + ## **See also:** ## * `incl proc <#incl,CritBitTree[void],string>`_ ## * `incl proc <#incl,CritBitTree[T],string,T>`_ ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[T],string,T>`_ @@ -240,7 +260,7 @@ proc inc*(c: var CritBitTree[int]; key: string, val: int = 1) = proc incl*(c: var CritBitTree[void], key: string) = ## Includes `key` in `c`. ## - ## See also: + ## **See also:** ## * `excl proc <#excl,CritBitTree[T],string>`_ ## * `incl proc <#incl,CritBitTree[T],string,T>`_ runnableExamples: @@ -253,7 +273,7 @@ proc incl*(c: var CritBitTree[void], key: string) = proc incl*[T](c: var CritBitTree[T], key: string, val: T) = ## Inserts `key` with value `val` into `c`. ## - ## See also: + ## **See also:** ## * `excl proc <#excl,CritBitTree[T],string>`_ ## * `incl proc <#incl,CritBitTree[void],string>`_ runnableExamples: @@ -265,16 +285,11 @@ proc incl*[T](c: var CritBitTree[T], key: string, val: T) = n.val = val proc `[]=`*[T](c: var CritBitTree[T], key: string, val: T) = - ## Puts a (key, value)-pair into `t`. + ## Alias for `incl <#incl,CritBitTree[T],string,T>`_. ## - ## See also: + ## **See also:** ## * `[] proc <#[],CritBitTree[T],string>`_ ## * `[] proc <#[],CritBitTree[T],string_2>`_ - runnableExamples: - var c: CritBitTree[int] - c["key"] = 42 - doAssert c["key"] == 42 - var n = rawInsert(c, key) n.val = val @@ -286,20 +301,20 @@ template get[T](c: CritBitTree[T], key: string): T = n.val 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 + ## 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: + ## **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. + ## Retrieves the value at `c[key]`. The value can be modified. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## - ## See also: + ## **See also:** ## * `[] proc <#[],CritBitTree[T],string>`_ ## * `[]= proc <#[]=,CritBitTree[T],string,T>`_ get(c, key) @@ -320,27 +335,24 @@ iterator leaves[T](n: Node[T]): Node[T] = iterator keys*[T](c: CritBitTree[T]): string = ## Yields all keys in lexicographical order. runnableExamples: - 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"] + from 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: CritBitTree[T]): T = ## Yields all values of `c` in the lexicographical order of the ## corresponding keys. + ## + ## **See also:** + ## * `mvalues iterator <#mvalues.i,CritBitTree[T]>`_ runnableExamples: - 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] + from 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 @@ -348,40 +360,33 @@ 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: + ## **See also:** ## * `values iterator <#values.i,CritBitTree[T]>`_ for x in leaves(c.root): yield x.val iterator items*[T](c: CritBitTree[T]): string = - ## Yields all keys in lexicographical order. - runnableExamples: - 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"] - + ## Alias for `keys <#keys.i,CritBitTree[T]>`_. for x in leaves(c.root): yield x.key iterator pairs*[T](c: CritBitTree[T]): tuple[key: string, val: T] = - ## Yields all (key, value)-pairs of `c`. + ## Yields all `(key, value)`-pairs of `c` in the lexicographical order of the + ## corresponding keys. + ## + ## **See also:** + ## * `mpairs iterator <#mpairs.i,CritBitTree[T]>`_ runnableExamples: - 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)] + from 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 CritBitTree[T]): tuple[key: string, val: var T] = - ## Yields all (key, value)-pairs of `c`. The yielded values can be modified. + ## Yields all `(key, value)`-pairs of `c` in the lexicographical order of the + ## corresponding keys. The yielded values can be modified. ## - ## See also: + ## **See also:** ## * `pairs iterator <#pairs.i,CritBitTree[T]>`_ for x in leaves(c.root): yield (x.key, x.val) @@ -401,33 +406,14 @@ proc allprefixedAux[T](c: CritBitTree[T], key: string; if i >= p.key.len or p.key[i] != key[i]: return result = top -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. - runnableExamples: - 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"] - - let top = allprefixedAux(c, prefix, longestMatch) - for x in leaves(top): yield x.key - iterator keysWithPrefix*[T](c: CritBitTree[T], prefix: string; longestMatch = false): string = ## Yields all keys starting with `prefix`. runnableExamples: - 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"] + from sequtils import toSeq + + let c = {"key1": 42, "key2": 43}.toCritBitTree + doAssert toSeq(c.keysWithPrefix("key")) == @["key1", "key2"] let top = allprefixedAux(c, prefix, longestMatch) for x in leaves(top): yield x.key @@ -436,14 +422,14 @@ iterator valuesWithPrefix*[T](c: CritBitTree[T], prefix: string; longestMatch = false): T = ## Yields all values of `c` starting with `prefix` of the ## corresponding keys. + ## + ## **See also:** + ## * `mvaluesWithPrefix iterator <#mvaluesWithPrefix.i,CritBitTree[T],string>`_ runnableExamples: - 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] + from sequtils import toSeq + + let c = {"key1": 42, "key2": 43}.toCritBitTree + doAssert toSeq(c.valuesWithPrefix("key")) == @[42, 43] let top = allprefixedAux(c, prefix, longestMatch) for x in leaves(top): yield x.val @@ -453,43 +439,52 @@ iterator mvaluesWithPrefix*[T](c: var CritBitTree[T], prefix: string; ## Yields all values of `c` starting with `prefix` of the ## corresponding keys. The values can be modified. ## - ## See also: + ## **See also:** ## * `valuesWithPrefix iterator <#valuesWithPrefix.i,CritBitTree[T],string>`_ let top = allprefixedAux(c, prefix, longestMatch) for x in leaves(top): yield x.val +iterator itemsWithPrefix*[T](c: CritBitTree[T], prefix: string; + longestMatch = false): string = + ## Alias for `keysWithPrefix <#keysWithPrefix.i,CritBitTree[T],string>`_. + let top = allprefixedAux(c, prefix, longestMatch) + for x in leaves(top): yield x.key + 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`. + ## + ## **See also:** + ## * `mpairsWithPrefix iterator <#mpairsWithPrefix.i,CritBitTree[T],string>`_ runnableExamples: - 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)] + from 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, longestMatch) for x in leaves(top): yield (x.key, x.val) iterator mpairsWithPrefix*[T](c: var CritBitTree[T], prefix: string; - longestMatch = false): tuple[key: string, val: var T] = + 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: + ## **See also:** ## * `pairsWithPrefix iterator <#pairsWithPrefix.i,CritBitTree[T],string>`_ let top = allprefixedAux(c, prefix, longestMatch) for x in leaves(top): yield (x.key, x.val) 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}``, ``{}``. + ## 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 = "{}" @@ -516,7 +511,7 @@ func `$`*[T](c: CritBitTree[T]): string = result.add("}") func commonPrefixLen*[T](c: CritBitTree[T]): int {.inline, since((1, 3)).} = - ## Returns longest common prefix length of all keys of `c`. + ## Returns the length of the longest common prefix of all keys in `c`. ## If `c` is empty, returns 0. runnableExamples: var c: CritBitTree[void] @@ -536,35 +531,12 @@ func toCritBitTree*[T](pairs: openArray[(string, T)]): CritBitTree[T] {.since: ( 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] func toCritBitTree*(items: 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 - -runnableExamples: - 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 + for item in items: result.incl item |