diff options
Diffstat (limited to 'lib/pure/collections')
| -rw-r--r-- | lib/pure/collections/critbits.nim | 296 | ||||
| -rw-r--r-- | lib/pure/collections/deques.nim | 438 | ||||
| -rw-r--r-- | lib/pure/collections/hashcommon.nim | 29 | ||||
| -rw-r--r-- | lib/pure/collections/heapqueue.nim | 154 | ||||
| -rw-r--r-- | lib/pure/collections/intsets.nim | 5 | ||||
| -rw-r--r-- | lib/pure/collections/lists.nim | 757 | ||||
| -rw-r--r-- | lib/pure/collections/sequtils.nim | 331 | ||||
| -rw-r--r-- | lib/pure/collections/setimpl.nim | 7 | ||||
| -rw-r--r-- | lib/pure/collections/sets.nim | 119 | ||||
| -rw-r--r-- | lib/pure/collections/sharedlist.nim | 11 | ||||
| -rw-r--r-- | lib/pure/collections/sharedtables.nim | 121 | ||||
| -rw-r--r-- | lib/pure/collections/tableimpl.nim | 55 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 921 |
13 files changed, 1788 insertions, 1456 deletions
diff --git a/lib/pure/collections/critbits.nim b/lib/pure/collections/critbits.nim index 695f44646..24257dacb 100644 --- a/lib/pure/collections/critbits.nim +++ b/lib/pure/collections/critbits.nim @@ -8,12 +8,37 @@ # ## 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 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 NodeObj[T] {.acyclic.} = object byte: int ## byte index of the difference @@ -28,17 +53,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 +167,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 +180,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>`_ @@ -177,11 +200,11 @@ proc missingOrExcl*[T](c: var CritBitTree[T], key: string): bool = discard exclImpl(c, key) 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. +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: + ## **See also:** ## * `incl proc <#incl,CritBitTree[void],string>`_ ## * `incl proc <#incl,CritBitTree[T],string,T>`_ ## * `containsOrIncl proc <#containsOrIncl,CritBitTree[void],string>`_ @@ -204,10 +227,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 +263,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: @@ -250,10 +273,10 @@ proc incl*(c: var CritBitTree[void], key: string) = discard rawInsert(c, key) -proc incl*[T](c: var CritBitTree[T], key: string, val: T) = +proc incl*[T](c: var CritBitTree[T], key: string, val: sink 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: @@ -264,17 +287,12 @@ proc incl*[T](c: var CritBitTree[T], key: string, val: T) = var n = rawInsert(c, key) n.val = val -proc `[]=`*[T](c: var CritBitTree[T], key: string, val: T) = - ## Puts a (key, value)-pair into `t`. +proc `[]=`*[T](c: var CritBitTree[T], key: string, val: sink 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 @@ -285,21 +303,21 @@ 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 +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: + ## **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 +338,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 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: CritBitTree[T]): T = +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: - 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 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 @@ -348,45 +363,37 @@ 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 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 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) -proc allprefixedAux[T](c: CritBitTree[T], key: string; - longestMatch: bool): Node[T] = +proc allprefixedAux[T](c: CritBitTree[T], key: string): Node[T] = var p = c.root var top = p if p != nil: @@ -396,100 +403,83 @@ proc allprefixedAux[T](c: CritBitTree[T], key: string; let dir = (1 + (ch.ord or p.otherBits.ord)) shr 8 p = p.child[dir] if q.byte < key.len: top = p - if not longestMatch: - for i in 0 ..< key.len: - if i >= p.key.len or 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: 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 = +iterator keysWithPrefix*[T](c: CritBitTree[T], prefix: string): 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"] - - let top = allprefixedAux(c, prefix, longestMatch) + from std/sequtils import toSeq + + let c = {"key1": 42, "key2": 43}.toCritBitTree + doAssert toSeq(c.keysWithPrefix("key")) == @["key1", "key2"] + + let top = allprefixedAux(c, prefix) for x in leaves(top): yield x.key -iterator valuesWithPrefix*[T](c: CritBitTree[T], prefix: string; - longestMatch = false): T = +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: - 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] - - let top = allprefixedAux(c, prefix, longestMatch) + 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 CritBitTree[T], prefix: string; - longestMatch = false): var T = +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: + ## **See also:** ## * `valuesWithPrefix iterator <#valuesWithPrefix.i,CritBitTree[T],string>`_ - let top = allprefixedAux(c, prefix, longestMatch) + let top = allprefixedAux(c, prefix) for x in leaves(top): yield x.val +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; - longestMatch = false): tuple[key: string, val: T] = + prefix: string): 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)] - - let top = allprefixedAux(c, prefix, longestMatch) + 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 CritBitTree[T], - prefix: string; - longestMatch = false): tuple[key: string, val: var 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: + ## **See also:** ## * `pairsWithPrefix iterator <#pairsWithPrefix.i,CritBitTree[T],string>`_ - let top = allprefixedAux(c, prefix, longestMatch) + let top = allprefixedAux(c, prefix) 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 +506,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] @@ -531,39 +521,17 @@ func commonPrefixLen*[T](c: CritBitTree[T]): int {.inline, since((1, 3)).} = else: c.root.byte else: 0 -func toCritBitTree*[A, B](pairs: openArray[(A, B)]): CritBitTree[A] {.since: (1, 3).} = +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] -func toCritBitTree*[T](items: openArray[T]): CritBitTree[void] {.since: (1, 3).} = +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 - -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 diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim index f6d0f945e..d2b0099f2 100644 --- a/lib/pure/collections/deques.nim +++ b/lib/pure/collections/deques.nim @@ -7,25 +7,25 @@ # distribution, for details about the copyright. # -## Implementation of a `deque`:idx: (double-ended queue). -## The underlying implementation uses a ``seq``. +## An implementation of a `deque`:idx: (double-ended queue). +## The underlying implementation uses a `seq`. ## -## None of the procs that get an individual value from the deque can be used -## on an empty deque. -## If compiled with `boundChecks` option, those procs will raise an `IndexDefect` +## .. note:: None of the procs that get an individual value from the deque should be used +## on an empty deque. +## +## If compiled with the `boundChecks` option, those procs will raise an `IndexDefect` ## on such access. This should not be relied upon, as `-d:danger` or `--checks:off` will -## disable those checks and may return garbage or crash the program. +## disable those checks and then the procs may return garbage or crash the program. ## ## As such, a check to see if the deque is empty is needed before any ## access, unless your program logic guarantees it indirectly. runnableExamples: - var a = initDeque[int]() + var a = [10, 20, 30, 40].toDeque - doAssertRaises(IndexDefect, echo a[0]) + doAssertRaises(IndexDefect, echo a[4]) - for i in 1 .. 5: - a.addLast(10*i) + a.addLast(50) assert $a == "[10, 20, 30, 40, 50]" assert a.peekFirst == 10 @@ -44,130 +44,116 @@ runnableExamples: a.shrink(fromFirst = 1, fromLast = 2) assert $a == "[22, 11, 20]" -## **See also:** +## See also +## ======== ## * `lists module <lists.html>`_ for singly and doubly linked lists and rings -## * `channels module <channels.html>`_ for inter-thread communication import std/private/since -import math +import std/[assertions, hashes, math] type Deque*[T] = object - ## A double-ended queue backed with a ringed seq buffer. + ## A double-ended queue backed with a ringed `seq` buffer. ## - ## To initialize an empty deque use `initDeque proc <#initDeque,int>`_. + ## To initialize an empty deque, + ## use the `initDeque proc <#initDeque,int>`_. data: seq[T] - head, tail, count, mask: int + + # `head` and `tail` are masked only when accessing an element of `data` + # so that `tail - head == data.len` when the deque is full. + # They are uint so that incrementing/decrementing them doesn't cause + # over/underflow. You can get a number of items with `tail - head` + # even if `tail` or `head` is wraps around and `tail < head`, because + # `tail - head == (uint.high + 1 + tail) - head` when `tail < head`. + head, tail: uint const defaultInitialSize* = 4 template initImpl(result: typed, initialSize: int) = let correctSize = nextPowerOfTwo(initialSize) - result.mask = correctSize-1 newSeq(result.data, correctSize) template checkIfInitialized(deq: typed) = - when compiles(defaultInitialSize): - if deq.mask == 0: - initImpl(deq, defaultInitialSize) + if deq.data.len == 0: + initImpl(deq, defaultInitialSize) + +func mask[T](deq: Deque[T]): uint {.inline.} = + uint(deq.data.len) - 1 -proc initDeque*[T](initialSize: int = 4): Deque[T] = +proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] = ## Creates a new empty deque. ## ## Optionally, the initial capacity can be reserved via `initialSize` - ## as a performance optimization. + ## as a performance optimization + ## (default: `defaultInitialSize <#defaultInitialSize>`_). ## The length of a newly created deque will still be 0. ## - ## See also: + ## **See also:** ## * `toDeque proc <#toDeque,openArray[T]>`_ result.initImpl(initialSize) -proc toDeque*[T](x: openArray[T]): Deque[T] {.since: (1, 3).} = - ## Creates a new deque that contains the elements of `x` (in the same order). - ## - ## See also: - ## * `initDeque proc <#initDeque,int>`_ - runnableExamples: - var a = toDeque([7, 8, 9]) - assert len(a) == 3 - assert a.popFirst == 7 - assert len(a) == 2 - - result.initImpl(x.len) - for item in items(x): - result.addLast(item) - -proc len*[T](deq: Deque[T]): int {.inline.} = +func len*[T](deq: Deque[T]): int {.inline.} = ## Returns the number of elements of `deq`. - result = deq.count + int(deq.tail - deq.head) template emptyCheck(deq) = # Bounds check for the regular deque access. when compileOption("boundChecks"): - if unlikely(deq.count < 1): + if unlikely(deq.len < 1): raise newException(IndexDefect, "Empty deque.") template xBoundsCheck(deq, i) = # Bounds check for the array like accesses. when compileOption("boundChecks"): # `-d:danger` or `--checks:off` should disable this. - if unlikely(i >= deq.count): # x < deq.low is taken care by the Natural parameter + if unlikely(i >= deq.len): # x < deq.low is taken care by the Natural parameter raise newException(IndexDefect, - "Out of bounds: " & $i & " > " & $(deq.count - 1)) + "Out of bounds: " & $i & " > " & $(deq.len - 1)) if unlikely(i < 0): # when used with BackwardsIndex raise newException(IndexDefect, "Out of bounds: " & $i & " < 0") -proc `[]`*[T](deq: Deque[T], i: Natural): T {.inline.} = - ## Accesses the i-th element of `deq`. +proc `[]`*[T](deq: Deque[T], i: Natural): lent T {.inline.} = + ## Accesses the `i`-th element of `deq`. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert a[0] == 10 assert a[3] == 40 doAssertRaises(IndexDefect, echo a[8]) xBoundsCheck(deq, i) - return deq.data[(deq.head + i) and deq.mask] + return deq.data[(deq.head + i.uint) and deq.mask] proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} = - ## Accesses the i-th element of `deq` and return a mutable + ## Accesses the `i`-th element of `deq` and returns a mutable ## reference to it. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) - assert a[0] == 10 - assert a[3] == 40 - doAssertRaises(IndexDefect, echo a[8]) + var a = [10, 20, 30, 40, 50].toDeque + inc(a[0]) + assert a[0] == 11 xBoundsCheck(deq, i) - return deq.data[(deq.head + i) and deq.mask] + return deq.data[(deq.head + i.uint) and deq.mask] -proc `[]=`*[T](deq: var Deque[T], i: Natural, val: T) {.inline.} = - ## Changes the i-th element of `deq`. +proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} = + ## Sets the `i`-th element of `deq` to `val`. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque a[0] = 99 a[3] = 66 assert $a == "[99, 20, 30, 66, 50]" checkIfInitialized(deq) xBoundsCheck(deq, i) - deq.data[(deq.head + i) and deq.mask] = val + deq.data[(deq.head + i.uint) and deq.mask] = val -proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): T {.inline.} = - ## Accesses the backwards indexed i-th element. +proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): lent T {.inline.} = + ## Accesses the backwards indexed `i`-th element. ## ## `deq[^1]` is the last element. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert a[^1] == 50 assert a[^4] == 20 doAssertRaises(IndexDefect, echo a[^9]) @@ -176,28 +162,24 @@ proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): T {.inline.} = return deq[deq.len - int(i)] proc `[]`*[T](deq: var Deque[T], i: BackwardsIndex): var T {.inline.} = - ## Accesses the backwards indexed i-th element. + ## Accesses the backwards indexed `i`-th element and returns a mutable + ## reference to it. ## ## `deq[^1]` is the last element. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) - assert a[^1] == 50 - assert a[^4] == 20 - doAssertRaises(IndexDefect, echo a[^9]) + var a = [10, 20, 30, 40, 50].toDeque + inc(a[^1]) + assert a[^1] == 51 xBoundsCheck(deq, deq.len - int(i)) return deq[deq.len - int(i)] -proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: T) {.inline.} = - ## Changes the backwards indexed i-th element. +proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: sink T) {.inline.} = + ## Sets the backwards indexed `i`-th element of `deq` to `x`. ## ## `deq[^1]` is the last element. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque a[^1] = 99 a[^3] = 77 assert $a == "[10, 20, 77, 40, 99]" @@ -206,152 +188,143 @@ proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: T) {.inline.} = xBoundsCheck(deq, deq.len - int(i)) deq[deq.len - int(i)] = x -iterator items*[T](deq: Deque[T]): T = +iterator items*[T](deq: Deque[T]): lent T = ## Yields every element of `deq`. + ## + ## **See also:** + ## * `mitems iterator <#mitems.i,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 3: - a.addLast(10*i) - from sugar import collect - doAssert collect(for x in a: x) == [10, 20, 30] - # same as above: - doAssert collect(for x in items(a): x) == [10, 20, 30] - var i = deq.head - for c in 0 ..< deq.count: - yield deq.data[i] - i = (i + 1) and deq.mask + from std/sequtils import toSeq + + let a = [10, 20, 30, 40, 50].toDeque + assert toSeq(a.items) == @[10, 20, 30, 40, 50] + + for c in 0 ..< deq.len: + yield deq.data[(deq.head + c.uint) and deq.mask] iterator mitems*[T](deq: var Deque[T]): var T = ## Yields every element of `deq`, which can be modified. + ## + ## **See also:** + ## * `items iterator <#items.i,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): - x = 5*x - 1 + x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]" - var i = deq.head - for c in 0 ..< deq.count: - yield deq.data[i] - i = (i + 1) and deq.mask + for c in 0 ..< deq.len: + yield deq.data[(deq.head + c.uint) and deq.mask] iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] = - ## Yields every (position, value) of `deq`. + ## Yields every `(position, value)`-pair of `deq`. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 3: - a.addLast(10*i) - from sugar import collect - doAssert collect(for k, v in pairs(a): (k, v)) == @[(0, 10), (1, 20), (2, 30)] - var i = deq.head - for c in 0 ..< deq.count: - yield (c, deq.data[i]) - i = (i + 1) and deq.mask + from std/sequtils import toSeq + + let a = [10, 20, 30].toDeque + assert toSeq(a.pairs) == @[(0, 10), (1, 20), (2, 30)] + + for c in 0 ..< deq.len: + yield (c, deq.data[(deq.head + c.uint) and deq.mask]) proc contains*[T](deq: Deque[T], item: T): bool {.inline.} = ## Returns true if `item` is in `deq` or false if not found. ## - ## Usually used via the ``in`` operator. - ## It is the equivalent of ``deq.find(item) >= 0``. + ## Usually used via the `in` operator. + ## It is the equivalent of `deq.find(item) >= 0`. runnableExamples: - var q = [7, 9].toDeque + let q = [7, 9].toDeque assert 7 in q - assert q.contains 7 + assert q.contains(7) assert 8 notin q + for e in deq: if e == item: return true return false proc expandIfNeeded[T](deq: var Deque[T]) = checkIfInitialized(deq) - var cap = deq.mask + 1 - if unlikely(deq.count >= cap): + let cap = deq.data.len + assert deq.len <= cap + if unlikely(deq.len == cap): var n = newSeq[T](cap * 2) var i = 0 for x in mitems(deq): - when nimVM: n[i] = x # workaround for VM bug + when nimvm: n[i] = x # workaround for VM bug else: n[i] = move(x) inc i deq.data = move(n) - deq.mask = cap * 2 - 1 - deq.tail = deq.count + deq.tail = cap.uint deq.head = 0 -proc addFirst*[T](deq: var Deque[T], item: T) = - ## Adds an `item` to the beginning of the `deq`. +proc addFirst*[T](deq: var Deque[T], item: sink T) = + ## Adds an `item` to the beginning of `deq`. ## - ## See also: - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ + ## **See also:** + ## * `addLast proc <#addLast,Deque[T],sinkT>`_ runnableExamples: var a = initDeque[int]() for i in 1 .. 5: - a.addFirst(10*i) + a.addFirst(10 * i) assert $a == "[50, 40, 30, 20, 10]" expandIfNeeded(deq) - inc deq.count - deq.head = (deq.head - 1) and deq.mask - deq.data[deq.head] = item + dec deq.head + deq.data[deq.head and deq.mask] = item -proc addLast*[T](deq: var Deque[T], item: T) = - ## Adds an `item` to the end of the `deq`. +proc addLast*[T](deq: var Deque[T], item: sink T) = + ## Adds an `item` to the end of `deq`. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ + ## **See also:** + ## * `addFirst proc <#addFirst,Deque[T],sinkT>`_ runnableExamples: var a = initDeque[int]() for i in 1 .. 5: - a.addLast(10*i) + a.addLast(10 * i) assert $a == "[10, 20, 30, 40, 50]" expandIfNeeded(deq) - inc deq.count - deq.data[deq.tail] = item - deq.tail = (deq.tail + 1) and deq.mask + deq.data[deq.tail and deq.mask] = item + inc deq.tail + +proc toDeque*[T](x: openArray[T]): Deque[T] {.since: (1, 3).} = + ## Creates a new deque that contains the elements of `x` (in the same order). + ## + ## **See also:** + ## * `initDeque proc <#initDeque,int>`_ + runnableExamples: + let a = toDeque([7, 8, 9]) + assert len(a) == 3 + assert $a == "[7, 8, 9]" + + result.initImpl(x.len) + for item in items(x): + result.addLast(item) -proc peekFirst*[T](deq: Deque[T]): T {.inline.} = +proc peekFirst*[T](deq: Deque[T]): lent T {.inline.} = ## Returns the first element of `deq`, but does not remove it from the deque. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ + ## **See also:** + ## * `peekFirst proc <#peekFirst,Deque[T]_2>`_ which returns a mutable reference ## * `peekLast proc <#peekLast,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.peekFirst == 10 assert len(a) == 5 emptyCheck(deq) - result = deq.data[deq.head] + result = deq.data[deq.head and deq.mask] -proc peekLast*[T](deq: Deque[T]): T {.inline.} = +proc peekLast*[T](deq: Deque[T]): lent T {.inline.} = ## Returns the last element of `deq`, but does not remove it from the deque. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ + ## **See also:** + ## * `peekLast proc <#peekLast,Deque[T]_2>`_ which returns a mutable reference ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.peekLast == 50 assert len(a) == 5 @@ -360,41 +333,31 @@ proc peekLast*[T](deq: Deque[T]): T {.inline.} = result = deq.data[(deq.tail - 1) and deq.mask] proc peekFirst*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} = - ## Returns the first element of `deq`, but does not remove it from the deque. + ## Returns a mutable reference to the first element of `deq`, + ## but does not remove it from the deque. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ + ## **See also:** + ## * `peekFirst proc <#peekFirst,Deque[T]>`_ + ## * `peekLast proc <#peekLast,Deque[T]_2>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) - assert $a == "[10, 20, 30, 40, 50]" - assert a.peekFirst == 10 - assert len(a) == 5 + var a = [10, 20, 30, 40, 50].toDeque + a.peekFirst() = 99 + assert $a == "[99, 20, 30, 40, 50]" emptyCheck(deq) - result = deq.data[deq.head] + result = deq.data[deq.head and deq.mask] proc peekLast*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} = - ## Returns the last element of `deq`, but does not remove it from the deque. + ## Returns a mutable reference to the last element of `deq`, + ## but does not remove it from the deque. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ + ## **See also:** + ## * `peekFirst proc <#peekFirst,Deque[T]_2>`_ + ## * `peekLast proc <#peekLast,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) - assert $a == "[10, 20, 30, 40, 50]" - assert a.peekLast == 50 - assert len(a) == 5 + var a = [10, 20, 30, 40, 50].toDeque + a.peekLast() = 99 + assert $a == "[10, 20, 30, 40, 99]" emptyCheck(deq) result = deq.data[(deq.tail - 1) and deq.mask] @@ -406,68 +369,46 @@ proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} = ## Removes and returns the first element of the `deq`. ## ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ ## * `popLast proc <#popLast,Deque[T]>`_ - ## * `clear proc <#clear,Deque[T]>`_ ## * `shrink proc <#shrink,Deque[T],int,int>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.popFirst == 10 assert $a == "[20, 30, 40, 50]" emptyCheck(deq) - dec deq.count - result = deq.data[deq.head] - destroy(deq.data[deq.head]) - deq.head = (deq.head + 1) and deq.mask + result = move deq.data[deq.head and deq.mask] + inc deq.head proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} = ## Removes and returns the last element of the `deq`. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ + ## **See also:** ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `clear proc <#clear,Deque[T]>`_ ## * `shrink proc <#shrink,Deque[T],int,int>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.popLast == 50 assert $a == "[10, 20, 30, 40]" emptyCheck(deq) - dec deq.count - deq.tail = (deq.tail - 1) and deq.mask - result = deq.data[deq.tail] - destroy(deq.data[deq.tail]) + dec deq.tail + result = move deq.data[deq.tail and deq.mask] proc clear*[T](deq: var Deque[T]) {.inline.} = ## Resets the deque so that it is empty. ## - ## See also: - ## * `clear proc <#clear,Deque[T]>`_ + ## **See also:** ## * `shrink proc <#shrink,Deque[T],int,int>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addFirst(10*i) - assert $a == "[50, 40, 30, 20, 10]" + var a = [10, 20, 30, 40, 50].toDeque + assert $a == "[10, 20, 30, 40, 50]" clear(a) assert len(a) == 0 for el in mitems(deq): destroy(el) - deq.count = 0 deq.tail = deq.head proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) = @@ -477,34 +418,63 @@ proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) = ## If the supplied number of elements exceeds the total number of elements ## in the deque, the deque will remain empty. ## - ## See also: + ## **See also:** ## * `clear proc <#clear,Deque[T]>`_ + ## * `popFirst proc <#popFirst,Deque[T]>`_ + ## * `popLast proc <#popLast,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addFirst(10*i) - assert $a == "[50, 40, 30, 20, 10]" + var a = [10, 20, 30, 40, 50].toDeque + assert $a == "[10, 20, 30, 40, 50]" a.shrink(fromFirst = 2, fromLast = 1) - assert $a == "[30, 20]" + assert $a == "[30, 40]" - if fromFirst + fromLast > deq.count: + if fromFirst + fromLast > deq.len: clear(deq) return for i in 0 ..< fromFirst: - destroy(deq.data[deq.head]) - deq.head = (deq.head + 1) and deq.mask + destroy(deq.data[deq.head and deq.mask]) + inc deq.head for i in 0 ..< fromLast: - destroy(deq.data[deq.tail]) - deq.tail = (deq.tail - 1) and deq.mask - - dec deq.count, fromFirst + fromLast + destroy(deq.data[(deq.tail - 1) and deq.mask]) + dec deq.tail proc `$`*[T](deq: Deque[T]): string = ## Turns a deque into its string representation. + runnableExamples: + let a = [10, 20, 30].toDeque + assert $a == "[10, 20, 30]" + result = "[" for x in deq: if result.len > 1: result.add(", ") result.addQuoted(x) result.add("]") + +func `==`*[T](deq1, deq2: Deque[T]): bool = + ## The `==` operator for Deque. + ## Returns `true` if both deques contains the same values in the same order. + runnableExamples: + var a, b = initDeque[int]() + a.addFirst(2) + a.addFirst(1) + b.addLast(1) + b.addLast(2) + doAssert a == b + + if deq1.len != deq2.len: + return false + + for i in 0 ..< deq1.len: + if deq1.data[(deq1.head + i.uint) and deq1.mask] != deq2.data[(deq2.head + i.uint) and deq2.mask]: + return false + + true + +func hash*[T](deq: Deque[T]): Hash = + ## Hashing of Deque. + var h: Hash = 0 + for x in deq: + h = h !& hash(x) + !$h diff --git a/lib/pure/collections/hashcommon.nim b/lib/pure/collections/hashcommon.nim index 336dbc07d..17785c8c7 100644 --- a/lib/pure/collections/hashcommon.nim +++ b/lib/pure/collections/hashcommon.nim @@ -7,17 +7,17 @@ # distribution, for details about the copyright. # -# An ``include`` file which contains common code for +# An `include` file which contains common code for # hash sets and tables. +when defined(nimPreviewSlimSystem): + import std/assertions + +import std / outparams + const growthFactor = 2 -when not defined(nimHasDefault): - template default[T](t: typedesc[T]): T = - var v: T - v - # hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These # two procs retain clarity of that encoding without the space cost of an enum. proc isEmpty(hcode: Hash): bool {.inline.} = @@ -38,16 +38,6 @@ proc slotsNeeded(count: Natural): int {.inline.} = # Make sure to synchronize with `mustRehash` above result = nextPowerOfTwo(count * 3 div 2 + 4) -proc rightSize*(count: Natural): int {.inline, deprecated: "Deprecated since 1.4.0".} = - ## **Deprecated since Nim v1.4.0**, it is not needed anymore - ## because picking the correct size is done internally. - ## - ## Return the value of ``initialSize`` to support ``count`` items. - ## - ## If more items are expected to be added, simply add that - ## expected extra amount to the parameter before calling this. - result = count - template rawGetKnownHCImpl() {.dirty.} = if t.dataLen == 0: return -1 @@ -68,7 +58,10 @@ proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} = template genHashImpl(key, hc: typed) = hc = hash(key) if hc == 0: # This almost never taken branch should be very predictable. - hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. + when sizeof(int) < 4: + hc = 31415 # Value doesn't matter; Any non-zero favorite is fine <= 16-bit. + else: + hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. template genHash(key: typed): Hash = var res: Hash @@ -79,5 +72,5 @@ template rawGetImpl() {.dirty.} = genHashImpl(key, hc) rawGetKnownHCImpl() -proc rawGet[X, A](t: X, key: A, hc: var Hash): int {.inline.} = +proc rawGet[X, A](t: X, key: A, hc: var Hash): int {.inline, outParamsAt: [3].} = rawGetImpl() diff --git a/lib/pure/collections/heapqueue.nim b/lib/pure/collections/heapqueue.nim index 30fa5dae8..96f9b4430 100644 --- a/lib/pure/collections/heapqueue.nim +++ b/lib/pure/collections/heapqueue.nim @@ -8,31 +8,27 @@ ## The `heapqueue` module implements a -## `heap data structure<https://en.wikipedia.org/wiki/Heap_(data_structure)>`_ -## that can be used as a -## `priority queue<https://en.wikipedia.org/wiki/Priority_queue>`_. -## Heaps are arrays for which `a[k] <= a[2*k+1]` and `a[k] <= a[2*k+2]` for -## all `k`, counting elements from 0. The interesting property of a heap is that +## `binary heap data structure<https://en.wikipedia.org/wiki/Binary_heap>`_ +## that can be used as a `priority queue<https://en.wikipedia.org/wiki/Priority_queue>`_. +## They are represented as arrays for which `a[k] <= a[2*k+1]` and `a[k] <= a[2*k+2]` +## for all indices `k` (counting elements from 0). The interesting property of a heap is that ## `a[0]` is always its smallest element. ## ## Basic usage ## ----------- ## - runnableExamples: - var heap = initHeapQueue[int]() - heap.push(8) - heap.push(2) + var heap = [8, 2].toHeapQueue heap.push(5) - # The first element is the lowest element + # the first element is the lowest element assert heap[0] == 2 - # Remove and return the lowest element + # remove and return the lowest element assert heap.pop() == 2 - # The lowest element remaining is 5 + # the lowest element remaining is 5 assert heap[0] == 5 -## Usage with custom object -## ------------------------ +## Usage with custom objects +## ------------------------- ## To use a `HeapQueue` with a custom object, the `<` operator must be ## implemented. @@ -48,8 +44,12 @@ runnableExamples: assert jobs[0].priority == 1 + import std/private/since +when defined(nimPreviewSlimSystem): + import std/assertions + type HeapQueue*[T] = object ## A heap queue, commonly known as a priority queue. data: seq[T] @@ -57,27 +57,40 @@ type HeapQueue*[T] = object proc initHeapQueue*[T](): HeapQueue[T] = ## Creates a new empty heap. ## - ## See also: + ## Heaps are initialized by default, so it is not necessary to call + ## this function explicitly. + ## + ## **See also:** ## * `toHeapQueue proc <#toHeapQueue,openArray[T]>`_ - discard + result = default(HeapQueue[T]) proc len*[T](heap: HeapQueue[T]): int {.inline.} = ## Returns the number of elements of `heap`. + runnableExamples: + let heap = [9, 5, 8].toHeapQueue + assert heap.len == 3 + heap.data.len proc `[]`*[T](heap: HeapQueue[T], i: Natural): lent T {.inline.} = ## Accesses the i-th element of `heap`. heap.data[i] -proc heapCmp[T](x, y: T): bool {.inline.} = - return (x < y) +iterator items*[T](heap: HeapQueue[T]): lent T {.inline, since: (2, 1, 1).} = + ## Iterates over each item of `heap`. + let L = len(heap) + for i in 0 .. high(heap.data): + yield heap.data[i] + assert(len(heap) == L, "the length of the HeapQueue changed while iterating over it") -proc siftdown[T](heap: var HeapQueue[T], startpos, p: int) = - ## 'heap' is a heap at all indices >= startpos, except possibly for `pos`. `pos` +proc heapCmp[T](x, y: T): bool {.inline.} = x < y + +proc siftup[T](heap: var HeapQueue[T], startpos, p: int) = + ## `heap` is a heap at all indices >= `startpos`, except possibly for `p`. `p` ## is the index of a leaf with a possibly out-of-order value. Restores the ## heap invariant. var pos = p - var newitem = heap[pos] + let newitem = heap[pos] # Follow the path to the root, moving parents down until finding a place # newitem fits. while pos > startpos: @@ -90,13 +103,14 @@ proc siftdown[T](heap: var HeapQueue[T], startpos, p: int) = break heap.data[pos] = newitem -proc siftup[T](heap: var HeapQueue[T], p: int) = +proc siftdownToBottom[T](heap: var HeapQueue[T], p: int) = + # This is faster when the element should be close to the bottom. let endpos = len(heap) var pos = p let startpos = pos let newitem = heap[pos] # Bubble up the smaller child until hitting a leaf. - var childpos = 2*pos + 1 # leftmost child position + var childpos = 2 * pos + 1 # leftmost child position while childpos < endpos: # Set childpos to index of smaller child. let rightpos = childpos + 1 @@ -105,118 +119,146 @@ proc siftup[T](heap: var HeapQueue[T], p: int) = # Move the smaller child up. heap.data[pos] = heap[childpos] pos = childpos - childpos = 2*pos + 1 - # The leaf at pos is empty now. Put newitem there, and bubble it up + childpos = 2 * pos + 1 + # The leaf at pos is empty now. Put newitem there, and bubble it up # to its final resting place (by sifting its parents down). heap.data[pos] = newitem - siftdown(heap, startpos, pos) + siftup(heap, startpos, pos) + +proc siftdown[T](heap: var HeapQueue[T], p: int) = + let endpos = len(heap) + var pos = p + let newitem = heap[pos] + var childpos = 2 * pos + 1 + while childpos < endpos: + let rightpos = childpos + 1 + if rightpos < endpos and not heapCmp(heap[childpos], heap[rightpos]): + childpos = rightpos + if not heapCmp(heap[childpos], newitem): + break + heap.data[pos] = heap[childpos] + pos = childpos + childpos = 2 * pos + 1 + heap.data[pos] = newitem proc push*[T](heap: var HeapQueue[T], item: sink T) = - ## Pushes `item` onto heap, maintaining the heap invariant. + ## Pushes `item` onto `heap`, maintaining the heap invariant. heap.data.add(item) - siftdown(heap, 0, len(heap)-1) + siftup(heap, 0, len(heap) - 1) proc toHeapQueue*[T](x: openArray[T]): HeapQueue[T] {.since: (1, 3).} = ## Creates a new HeapQueue that contains the elements of `x`. ## - ## See also: + ## **See also:** ## * `initHeapQueue proc <#initHeapQueue>`_ runnableExamples: - var heap = toHeapQueue([9, 5, 8]) + var heap = [9, 5, 8].toHeapQueue assert heap.pop() == 5 assert heap[0] == 8 - result = initHeapQueue[T]() - for item in items(x): - result.push(item) + # see https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap + result.data = @x + for i in countdown(x.len div 2 - 1, 0): + siftdown(result, i) proc pop*[T](heap: var HeapQueue[T]): T = ## Pops and returns the smallest item from `heap`, ## maintaining the heap invariant. runnableExamples: - var heap = toHeapQueue([9, 5, 8]) + var heap = [9, 5, 8].toHeapQueue assert heap.pop() == 5 + let lastelt = heap.data.pop() if heap.len > 0: result = heap[0] heap.data[0] = lastelt - siftup(heap, 0) + siftdownToBottom(heap, 0) else: result = lastelt proc find*[T](heap: HeapQueue[T], x: T): int {.since: (1, 3).} = - ## Linear scan to find index of item ``x`` or -1 if not found. + ## Linear scan to find the index of the item `x` or -1 if not found. runnableExamples: - var heap = toHeapQueue([9, 5, 8]) + let heap = [9, 5, 8].toHeapQueue assert heap.find(5) == 0 assert heap.find(9) == 1 assert heap.find(777) == -1 + result = -1 for i in 0 ..< heap.len: if heap[i] == x: return i +proc contains*[T](heap: HeapQueue[T], x: T): bool {.since: (2, 1, 1).} = + ## Returns true if `x` is in `heap` or false if not found. This is a shortcut + ## for `find(heap, x) >= 0`. + result = find(heap, x) >= 0 + proc del*[T](heap: var HeapQueue[T], index: Natural) = ## Removes the element at `index` from `heap`, maintaining the heap invariant. runnableExamples: - var heap = toHeapQueue([9, 5, 8]) + var heap = [9, 5, 8].toHeapQueue heap.del(1) assert heap[0] == 5 assert heap[1] == 8 + swap(heap.data[^1], heap.data[index]) let newLen = heap.len - 1 heap.data.setLen(newLen) if index < newLen: - heap.siftup(index) + siftdownToBottom(heap, index) proc replace*[T](heap: var HeapQueue[T], item: sink T): T = ## Pops and returns the current smallest value, and add the new item. - ## This is more efficient than pop() followed by push(), and can be + ## This is more efficient than `pop()` followed by `push()`, and can be ## more appropriate when using a fixed-size heap. Note that the value - ## returned may be larger than item! That constrains reasonable uses of - ## this routine unless written as part of a conditional replacement: + ## returned may be larger than `item`! That constrains reasonable uses of + ## this routine unless written as part of a conditional replacement. + ## + ## **See also:** + ## * `pushpop proc <#pushpop,HeapQueue[T],sinkT>`_ runnableExamples: - var heap = initHeapQueue[int]() - heap.push(5) - heap.push(12) + var heap = [5, 12].toHeapQueue assert heap.replace(6) == 5 assert heap.len == 2 assert heap[0] == 6 assert heap.replace(4) == 6 + result = heap[0] heap.data[0] = item - siftup(heap, 0) + siftdown(heap, 0) proc pushpop*[T](heap: var HeapQueue[T], item: sink T): T = - ## Fast version of a push followed by a pop. + ## Fast version of a `push()` followed by a `pop()`. + ## + ## **See also:** + ## * `replace proc <#replace,HeapQueue[T],sinkT>`_ runnableExamples: - var heap = initHeapQueue[int]() - heap.push(5) - heap.push(12) + var heap = [5, 12].toHeapQueue assert heap.pushpop(6) == 5 assert heap.len == 2 assert heap[0] == 6 assert heap.pushpop(4) == 4 + result = item if heap.len > 0 and heapCmp(heap.data[0], result): swap(result, heap.data[0]) - siftup(heap, 0) + siftdown(heap, 0) proc clear*[T](heap: var HeapQueue[T]) = ## Removes all elements from `heap`, making it empty. runnableExamples: - var heap = initHeapQueue[int]() - heap.push(1) + var heap = [9, 5, 8].toHeapQueue heap.clear() assert heap.len == 0 + heap.data.setLen(0) proc `$`*[T](heap: HeapQueue[T]): string = ## Turns a heap into its string representation. runnableExamples: - var heap = initHeapQueue[int]() - heap.push(1) - heap.push(2) + let heap = [1, 2].toHeapQueue assert $heap == "[1, 2]" + result = "[" for x in heap.data: if result.len > 1: result.add(", ") diff --git a/lib/pure/collections/intsets.nim b/lib/pure/collections/intsets.nim index e4c216d08..765a23e97 100644 --- a/lib/pure/collections/intsets.nim +++ b/lib/pure/collections/intsets.nim @@ -7,9 +7,8 @@ # distribution, for details about the copyright. # -## Deprecated by the generic `PackedSet` for ordinal sparse sets. -## **See also:** -## * `Ordinal packed sets module <packedsets.html>`_ for more general packed sets +## Specialization of the generic `packedsets module <packedsets.html>`_ +## (see its documentation for more examples) for ordinal sparse sets. import std/private/since import std/packedsets diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index 8af0ed826..6b88747ef 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -13,120 +13,90 @@ ## * `singly linked rings <#SinglyLinkedRing>`_ (circular lists) ## * `doubly linked rings <#DoublyLinkedRing>`_ (circular lists) ## -## -## Basic Usage -## =========== -## +## # Basic Usage ## Because it makes no sense to do otherwise, the `next` and `prev` pointers ## are not hidden from you and can be manipulated directly for efficiency. ## -## Lists -## ----- -## -## .. code-block:: -## import lists -## -## var -## l = initDoublyLinkedList[int]() -## a = newDoublyLinkedNode[int](3) -## b = newDoublyLinkedNode[int](7) -## c = newDoublyLinkedNode[int](9) -## -## l.append(a) -## l.append(b) -## l.prepend(c) -## -## assert a.next == b -## assert a.prev == c -## assert c.next == a -## assert c.next.next == b -## assert c.prev == nil -## assert b.next == nil -## -## -## Rings -## ----- -## -## .. code-block:: -## import lists -## -## var -## l = initSinglyLinkedRing[int]() -## a = newSinglyLinkedNode[int](3) -## b = newSinglyLinkedNode[int](7) -## c = newSinglyLinkedNode[int](9) -## -## l.append(a) -## l.append(b) -## l.prepend(c) -## -## assert c.next == a -## assert a.next == b -## assert c.next.next == b -## assert b.next == c -## assert c.next.next.next == c -## -## See also -## ======== -## +## ## Lists +runnableExamples: + var list = initDoublyLinkedList[int]() + let + a = newDoublyLinkedNode[int](3) + b = newDoublyLinkedNode[int](7) + c = newDoublyLinkedNode[int](9) + + list.add(a) + list.add(b) + list.prepend(c) + + assert a.next == b + assert a.prev == c + assert c.next == a + assert c.next.next == b + assert c.prev == nil + assert b.next == nil + +## ## Rings +runnableExamples: + var ring = initSinglyLinkedRing[int]() + let + a = newSinglyLinkedNode[int](3) + b = newSinglyLinkedNode[int](7) + c = newSinglyLinkedNode[int](9) + + ring.add(a) + ring.add(b) + ring.prepend(c) + + assert c.next == a + assert a.next == b + assert c.next.next == b + assert b.next == c + assert c.next.next.next == c + +## # See also ## * `deques module <deques.html>`_ for double-ended queues -## * `sharedlist module <sharedlist.html>`_ for shared singly-linked lists import std/private/since -when not defined(nimhygiene): - {.pragma: dirty.} - -when not defined(nimHasCursor): - {.pragma: cursor.} +when defined(nimPreviewSlimSystem): + import std/assertions type - DoublyLinkedNodeObj*[T] = object ## \ - ## A node a doubly linked list consists of. + DoublyLinkedNodeObj*[T] = object + ## A node of a doubly linked list. ## ## It consists of a `value` field, and pointers to `next` and `prev`. - next*: <//>(ref DoublyLinkedNodeObj[T]) - prev* {.cursor.}: ref DoublyLinkedNodeObj[T] + next*: DoublyLinkedNode[T] + prev* {.cursor.}: DoublyLinkedNode[T] value*: T DoublyLinkedNode*[T] = ref DoublyLinkedNodeObj[T] - SinglyLinkedNodeObj*[T] = object ## \ - ## A node a singly linked list consists of. + SinglyLinkedNodeObj*[T] = object + ## A node of a singly linked list. ## ## It consists of a `value` field, and a pointer to `next`. - next*: <//>(ref SinglyLinkedNodeObj[T]) + next*: SinglyLinkedNode[T] value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] - SinglyLinkedList*[T] = object ## \ + SinglyLinkedList*[T] = object ## A singly linked list. - ## - ## Use `initSinglyLinkedList proc <#initSinglyLinkedList>`_ to create - ## a new empty list. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] - DoublyLinkedList*[T] = object ## \ + DoublyLinkedList*[T] = object ## A doubly linked list. - ## - ## Use `initDoublyLinkedList proc <#initDoublyLinkedList>`_ to create - ## a new empty list. - head*: <//>(DoublyLinkedNode[T]) + head*: DoublyLinkedNode[T] tail* {.cursor.}: DoublyLinkedNode[T] - SinglyLinkedRing*[T] = object ## \ + SinglyLinkedRing*[T] = object ## A singly linked ring. - ## - ## Use `initSinglyLinkedRing proc <#initSinglyLinkedRing>`_ to create - ## a new empty ring. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] - DoublyLinkedRing*[T] = object ## \ + DoublyLinkedRing*[T] = object ## A doubly linked ring. - ## - ## Use `initDoublyLinkedRing proc <#initDoublyLinkedRing>`_ to create - ## a new empty ring. head*: DoublyLinkedNode[T] SomeLinkedList*[T] = SinglyLinkedList[T] | DoublyLinkedList[T] @@ -139,74 +109,70 @@ type proc initSinglyLinkedList*[T](): SinglyLinkedList[T] = ## Creates a new singly linked list that is empty. + ## + ## Singly linked lists are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initSinglyLinkedList[int]() + let a = initSinglyLinkedList[int]() + discard proc initDoublyLinkedList*[T](): DoublyLinkedList[T] = ## Creates a new doubly linked list that is empty. + ## + ## Doubly linked lists are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initDoublyLinkedList[int]() + let a = initDoublyLinkedList[int]() + discard proc initSinglyLinkedRing*[T](): SinglyLinkedRing[T] = ## Creates a new singly linked ring that is empty. + ## + ## Singly linked rings are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initSinglyLinkedRing[int]() + let a = initSinglyLinkedRing[int]() + discard proc initDoublyLinkedRing*[T](): DoublyLinkedRing[T] = ## Creates a new doubly linked ring that is empty. + ## + ## Doubly linked rings are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initDoublyLinkedRing[int]() + let a = initDoublyLinkedRing[int]() + discard -proc newDoublyLinkedNode*[T](value: T): <//>(DoublyLinkedNode[T]) = +proc newDoublyLinkedNode*[T](value: T): DoublyLinkedNode[T] = ## Creates a new doubly linked node with the given `value`. runnableExamples: - var n = newDoublyLinkedNode[int](5) + let n = newDoublyLinkedNode[int](5) assert n.value == 5 new(result) result.value = value -proc newSinglyLinkedNode*[T](value: T): <//>(SinglyLinkedNode[T]) = +proc newSinglyLinkedNode*[T](value: T): SinglyLinkedNode[T] = ## Creates a new singly linked node with the given `value`. runnableExamples: - var n = newSinglyLinkedNode[int](5) + let n = newSinglyLinkedNode[int](5) assert n.value == 5 new(result) result.value = value -func toSinglyLinkedList*[T](elems: openArray[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = - ## Creates a new `SinglyLinkedList` from members of `elems`. - runnableExamples: - import sequtils - let a = [1, 2, 3, 4, 5].toSinglyLinkedList - assert a.toSeq == [1, 2, 3, 4, 5] - result = initSinglyLinkedList[T]() - for elem in elems.items: - result.append(elem) - -func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = - ## Creates a new `DoublyLinkedList` from members of `elems`. - runnableExamples: - import sequtils - let a = [1, 2, 3, 4, 5].toDoublyLinkedList - assert a.toSeq == [1, 2, 3, 4, 5] - result = initDoublyLinkedList[T]() - for elem in elems.items: - result.append(elem) - template itemsListImpl() {.dirty.} = - var it = L.head + var it {.cursor.} = L.head while it != nil: yield it.value it = it.next template itemsRingImpl() {.dirty.} = - var it = L.head + var it {.cursor.} = L.head if it != nil: while true: yield it.value @@ -216,101 +182,91 @@ template itemsRingImpl() {.dirty.} = iterator items*[T](L: SomeLinkedList[T]): T = ## Yields every value of `L`. ## - ## See also: + ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedList[T]>`_ - ## - ## **Examples:** - ## - ## .. code-block:: - ## var a = initSinglyLinkedList[int]() - ## for i in 1 .. 3: - ## a.append(10*i) - ## - ## for x in a: # the same as: for x in items(a): - ## echo x - ## - ## # 10 - ## # 20 - ## # 30 + runnableExamples: + from std/sugar import collect + from std/sequtils import toSeq + let a = collect(initSinglyLinkedList): + for i in 1..3: 10 * i + assert toSeq(items(a)) == toSeq(a) + assert toSeq(a) == @[10, 20, 30] + itemsListImpl() iterator items*[T](L: SomeLinkedRing[T]): T = ## Yields every value of `L`. ## - ## See also: + ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedRing[T]>`_ - ## - ## **Examples:** - ## - ## .. code-block:: - ## var a = initSinglyLinkedRing[int]() - ## for i in 1 .. 3: - ## a.append(10*i) - ## - ## for x in a: # the same as: for x in items(a): - ## echo x - ## - ## # 10 - ## # 20 - ## # 30 + runnableExamples: + from std/sugar import collect + from std/sequtils import toSeq + let a = collect(initSinglyLinkedRing): + for i in 1..3: 10 * i + assert toSeq(items(a)) == toSeq(a) + assert toSeq(a) == @[10, 20, 30] + itemsRingImpl() iterator mitems*[T](L: var SomeLinkedList[T]): var T = ## Yields every value of `L` so that you can modify it. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedList[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedList[T]>`_ runnableExamples: var a = initSinglyLinkedList[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): - x = 5*x - 1 + x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]" + itemsListImpl() iterator mitems*[T](L: var SomeLinkedRing[T]): var T = ## Yields every value of `L` so that you can modify it. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedRing[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedRing[T]>`_ runnableExamples: var a = initSinglyLinkedRing[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): - x = 5*x - 1 + x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]" + itemsRingImpl() iterator nodes*[T](L: SomeLinkedList[T]): SomeLinkedNode[T] = ## Iterates over every node of `x`. Removing the current node from the ## list during traversal is supported. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedList[T]>`_ ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ runnableExamples: var a = initDoublyLinkedList[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: a.remove(x) else: - x.value = 5*x.value - 1 + x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = L.head + var it {.cursor.} = L.head while it != nil: - var nxt = it.next + let nxt = it.next yield it it = nxt @@ -318,31 +274,35 @@ iterator nodes*[T](L: SomeLinkedRing[T]): SomeLinkedNode[T] = ## Iterates over every node of `x`. Removing the current node from the ## list during traversal is supported. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedRing[T]>`_ ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ runnableExamples: var a = initDoublyLinkedRing[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: a.remove(x) else: - x.value = 5*x.value - 1 + x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = L.head + var it {.cursor.} = L.head if it != nil: while true: - var nxt = it.next + let nxt = it.next yield it it = nxt if it == L.head: break proc `$`*[T](L: SomeLinkedCollection[T]): string = ## Turns a list into its string representation for logging and printing. + runnableExamples: + let a = [1, 2, 3, 4].toSinglyLinkedList + assert $a == "[1, 2, 3, 4]" + result = "[" for x in nodes(L): if result.len > 1: result.add(", ") @@ -353,12 +313,10 @@ proc find*[T](L: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = ## Searches in the list for a value. Returns `nil` if the value does not ## exist. ## - ## See also: + ## **See also:** ## * `contains proc <#contains,SomeLinkedCollection[T],T>`_ runnableExamples: - var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + let a = [9, 8].toSinglyLinkedList assert a.find(9).value == 9 assert a.find(1) == nil @@ -367,14 +325,13 @@ proc find*[T](L: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = proc contains*[T](L: SomeLinkedCollection[T], value: T): bool {.inline.} = ## Searches in the list for a value. Returns `false` if the value does not - ## exist, `true` otherwise. + ## exist, `true` otherwise. This allows the usage of the `in` and `notin` + ## operators. ## - ## See also: + ## **See also:** ## * `find proc <#find,SomeLinkedCollection[T],T>`_ runnableExamples: - var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + let a = [9, 8].toSinglyLinkedList assert a.contains(9) assert 8 in a assert(not a.contains(1)) @@ -382,20 +339,65 @@ proc contains*[T](L: SomeLinkedCollection[T], value: T): bool {.inline.} = result = find(L, value) != nil -proc append*[T](L: var SinglyLinkedList[T], - n: SinglyLinkedNode[T]) {.inline.} = +proc prepend*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = + ## Prepends a shallow copy of `b` to the beginning of `a`. + ## + ## **See also:** + ## * `prependMoved proc <#prependMoved,T,T>`_ + ## for moving the second list instead of copying + runnableExamples: + from std/sequtils import toSeq + var a = [4, 5].toSinglyLinkedList + let b = [1, 2, 3].toSinglyLinkedList + a.prepend(b) + assert a.toSeq == [1, 2, 3, 4, 5] + assert b.toSeq == [1, 2, 3] + a.prepend(a) + assert a.toSeq == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5] + + var tmp = b.copy + tmp.addMoved(a) + a = tmp + +proc prependMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = + ## Moves `b` before the head of `a`. Efficiency: O(1). + ## Note that `b` becomes empty after the operation unless it has the same address as `a`. + ## Self-prepending results in a cycle. + ## + ## **See also:** + ## * `prepend proc <#prepend,T,T>`_ + ## for prepending a copy of a list + runnableExamples: + import std/[sequtils, enumerate, sugar] + var + a = [4, 5].toSinglyLinkedList + b = [1, 2, 3].toSinglyLinkedList + c = [0, 1].toSinglyLinkedList + a.prependMoved(b) + assert a.toSeq == [1, 2, 3, 4, 5] + assert b.toSeq == [] + c.prependMoved(c) + let s = collect: + for i, ci in enumerate(c): + if i == 6: break + ci + assert s == [0, 1, 0, 1, 0, 1] + + b.addMoved(a) + swap a, b + +proc add*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedList[int]() - n = newSinglyLinkedNode[int](9) - a.append(n) + var a = initSinglyLinkedList[int]() + let n = newSinglyLinkedNode[int](9) + a.add(n) assert a.contains(9) n.next = nil @@ -405,34 +407,34 @@ proc append*[T](L: var SinglyLinkedList[T], L.tail = n if L.head == nil: L.head = n -proc append*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = +proc add*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value runnableExamples: var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newSinglyLinkedNode(value)) + + add(L, newSinglyLinkedNode(value)) proc prepend*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedList[int]() - n = newSinglyLinkedNode[int](9) + var a = initSinglyLinkedList[int]() + let n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -443,10 +445,10 @@ proc prepend*[T](L: var SinglyLinkedList[T], proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for prepending a node runnableExamples: @@ -454,19 +456,20 @@ proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = a.prepend(9) a.prepend(8) assert a.contains(9) + prepend(L, newSinglyLinkedNode(value)) func copy*[T](a: SinglyLinkedList[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a shallow copy of `a`. runnableExamples: - import sequtils + from std/sequtils import toSeq type Foo = ref object x: int var f = Foo(x: 1) a = [f].toSinglyLinkedList let b = a.copy - a.add [f].toSinglyLinkedList + a.add([f].toSinglyLinkedList) assert a.toSeq == [f, f] assert b.toSeq == [f] # b isn't modified... f.x = 42 @@ -475,57 +478,58 @@ func copy*[T](a: SinglyLinkedList[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} let c = [1, 2, 3].toSinglyLinkedList assert $c == $c.copy + result = initSinglyLinkedList[T]() for x in a.items: - result.append(x) + result.add(x) proc addMoved*[T](a, b: var SinglyLinkedList[T]) {.since: (1, 5, 1).} = ## Moves `b` to the end of `a`. Efficiency: O(1). ## Note that `b` becomes empty after the operation unless it has the same address as `a`. ## Self-adding results in a cycle. ## - ## See also: - ## * `add proc <#add,T,T>`_ - ## for adding a copy of a list + ## **See also:** + ## * `add proc <#add,T,T>`_ for adding a copy of a list runnableExamples: - import sequtils, std/enumerate, std/sugar + import std/[sequtils, enumerate, sugar] var a = [1, 2, 3].toSinglyLinkedList b = [4, 5].toSinglyLinkedList c = [0, 1].toSinglyLinkedList - a.addMoved b + a.addMoved(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [] - c.addMoved c + c.addMoved(c) let s = collect: for i, ci in enumerate(c): if i == 6: break ci assert s == [0, 1, 0, 1, 0, 1] - if a.tail != nil: - a.tail.next = b.head - a.tail = b.tail - if a.head == nil: - a.head = b.head + + if b.head != nil: + if a.head == nil: + a.head = b.head + else: + a.tail.next = b.head + a.tail = b.tail if a.addr != b.addr: b.head = nil b.tail = nil -proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = +proc add*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,DoublyLinkedList[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedList[int]() - n = newDoublyLinkedNode[int](9) - a.append(n) + var a = initDoublyLinkedList[int]() + let n = newDoublyLinkedNode[int](9) + a.add(n) assert a.contains(9) n.next = nil @@ -536,11 +540,11 @@ proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = L.tail = n if L.head == nil: L.head = n -proc append*[T](L: var DoublyLinkedList[T], value: T) = +proc add*[T](L: var DoublyLinkedList[T], value: T) = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for prepending a node @@ -549,25 +553,25 @@ proc append*[T](L: var DoublyLinkedList[T], value: T) = ## for removing a node runnableExamples: var a = initDoublyLinkedList[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newDoublyLinkedNode(value)) + + add(L, newDoublyLinkedNode(value)) proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedList[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedList[int]() - n = newDoublyLinkedNode[int](9) + var a = initDoublyLinkedList[int]() + let n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -582,10 +586,10 @@ proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = proc prepend*[T](L: var DoublyLinkedList[T], value: T) = ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ @@ -595,57 +599,64 @@ proc prepend*[T](L: var DoublyLinkedList[T], value: T) = a.prepend(9) a.prepend(8) assert a.contains(9) + prepend(L, newDoublyLinkedNode(value)) func copy*[T](a: DoublyLinkedList[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a shallow copy of `a`. runnableExamples: + from std/sequtils import toSeq type Foo = ref object x: int - var f = Foo(x: 1) - let + var + f = Foo(x: 1) a = [f].toDoublyLinkedList - b = a.copy + let b = a.copy + a.add([f].toDoublyLinkedList) + assert a.toSeq == [f, f] + assert b.toSeq == [f] # b isn't modified... f.x = 42 assert a.head.value.x == 42 - assert b.head.value.x == 42 + assert b.head.value.x == 42 # ... but the elements are not deep copied let c = [1, 2, 3].toDoublyLinkedList assert $c == $c.copy + result = initDoublyLinkedList[T]() for x in a.items: - result.append(x) + result.add(x) proc addMoved*[T](a, b: var DoublyLinkedList[T]) {.since: (1, 5, 1).} = ## Moves `b` to the end of `a`. Efficiency: O(1). ## Note that `b` becomes empty after the operation unless it has the same address as `a`. ## Self-adding results in a cycle. ## - ## See also: + ## **See also:** ## * `add proc <#add,T,T>`_ ## for adding a copy of a list runnableExamples: - import sequtils, std/enumerate, std/sugar + import std/[sequtils, enumerate, sugar] var a = [1, 2, 3].toDoublyLinkedList b = [4, 5].toDoublyLinkedList c = [0, 1].toDoublyLinkedList - a.addMoved b + a.addMoved(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [] - c.addMoved c + c.addMoved(c) let s = collect: for i, ci in enumerate(c): if i == 6: break ci assert s == [0, 1, 0, 1, 0, 1] + if b.head != nil: - b.head.prev = a.tail - if a.tail != nil: - a.tail.next = b.head - a.tail = b.tail - if a.head == nil: - a.head = b.head + if a.head == nil: + a.head = b.head + else: + b.head.prev = a.tail + a.tail.next = b.head + a.tail = b.tail if a.addr != b.addr: b.head = nil b.tail = nil @@ -653,32 +664,82 @@ proc addMoved*[T](a, b: var DoublyLinkedList[T]) {.since: (1, 5, 1).} = proc add*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = ## Appends a shallow copy of `b` to the end of `a`. ## - ## See also: + ## **See also:** ## * `addMoved proc <#addMoved,SinglyLinkedList[T],SinglyLinkedList[T]>`_ ## * `addMoved proc <#addMoved,DoublyLinkedList[T],DoublyLinkedList[T]>`_ ## for moving the second list instead of copying runnableExamples: - import sequtils + from std/sequtils import toSeq var a = [1, 2, 3].toSinglyLinkedList let b = [4, 5].toSinglyLinkedList - a.add b + a.add(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [4, 5] - a.add a + a.add(a) assert a.toSeq == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5] + var tmp = b.copy - a.addMoved tmp + a.addMoved(tmp) + +proc remove*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]): bool {.discardable.} = + ## Removes a node `n` from `L`. + ## Returns `true` if `n` was found in `L`. + ## Efficiency: O(n); the list is traversed until `n` is found. + ## Attempting to remove an element not contained in the list is a no-op. + ## When the list is cyclic, the cycle is preserved after removal. + runnableExamples: + import std/[sequtils, enumerate, sugar] + var a = [0, 1, 2].toSinglyLinkedList + let n = a.head.next + assert n.value == 1 + assert a.remove(n) == true + assert a.toSeq == [0, 2] + assert a.remove(n) == false + assert a.toSeq == [0, 2] + a.addMoved(a) # cycle: [0, 2, 0, 2, ...] + a.remove(a.head) + let s = collect: + for i, ai in enumerate(a): + if i == 4: break + ai + assert s == [2, 2, 2, 2] + + if n == L.head: + L.head = n.next + if L.tail.next == n: + L.tail.next = L.head # restore cycle + else: + var prev {.cursor.} = L.head + while prev.next != n and prev.next != nil: + prev = prev.next + if prev.next == nil: + return false + prev.next = n.next + if L.tail == n: + L.tail = prev # update tail if we removed the last node + true proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Removes a node `n` from `L`. Efficiency: O(1). - runnableExamples: - var - a = initDoublyLinkedList[int]() - n = newDoublyLinkedNode[int](5) - a.append(n) - assert 5 in a + ## This function assumes, for the sake of efficiency, that `n` is contained in `L`, + ## otherwise the effects are undefined. + ## When the list is cyclic, the cycle is preserved after removal. + runnableExamples: + import std/[sequtils, enumerate, sugar] + var a = [0, 1, 2].toSinglyLinkedList + let n = a.head.next + assert n.value == 1 a.remove(n) - assert 5 notin a + assert a.toSeq == [0, 2] + a.remove(n) + assert a.toSeq == [0, 2] + a.addMoved(a) # cycle: [0, 2, 0, 2, ...] + a.remove(a.head) + let s = collect: + for i, ai in enumerate(a): + if i == 4: break + ai + assert s == [2, 2, 2, 2] if n == L.tail: L.tail = n.prev if n == L.head: L.head = n.next @@ -687,59 +748,57 @@ proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = -proc append*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = +proc add*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedRing[int]() - n = newSinglyLinkedNode[int](9) - a.append(n) + var a = initSinglyLinkedRing[int]() + let n = newSinglyLinkedNode[int](9) + a.add(n) assert a.contains(9) if L.head != nil: n.next = L.head assert(L.tail != nil) L.tail.next = n - L.tail = n else: n.next = n L.head = n - L.tail = n + L.tail = n -proc append*[T](L: var SinglyLinkedRing[T], value: T) = +proc add*[T](L: var SinglyLinkedRing[T], value: T) = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value runnableExamples: var a = initSinglyLinkedRing[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newSinglyLinkedNode(value)) + + add(L, newSinglyLinkedNode(value)) proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedRing[int]() - n = newSinglyLinkedNode[int](9) + var a = initSinglyLinkedRing[int]() + let n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -755,10 +814,10 @@ proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for prepending a node runnableExamples: @@ -766,25 +825,25 @@ proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = a.prepend(9) a.prepend(8) assert a.contains(9) + prepend(L, newSinglyLinkedNode(value)) -proc append*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = +proc add*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,DoublyLinkedRing[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedRing[int]() - n = newDoublyLinkedNode[int](9) - a.append(n) + var a = initDoublyLinkedRing[int]() + let n = newDoublyLinkedNode[int](9) + a.add(n) assert a.contains(9) if L.head != nil: @@ -797,11 +856,11 @@ proc append*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = n.next = n L.head = n -proc append*[T](L: var DoublyLinkedRing[T], value: T) = +proc add*[T](L: var DoublyLinkedRing[T], value: T) = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for prepending a node @@ -810,25 +869,25 @@ proc append*[T](L: var DoublyLinkedRing[T], value: T) = ## for removing a node runnableExamples: var a = initDoublyLinkedRing[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newDoublyLinkedNode(value)) + + add(L, newDoublyLinkedNode(value)) proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedRing[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedRing[int]() - n = newDoublyLinkedNode[int](9) + var a = initDoublyLinkedRing[int]() + let n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -845,10 +904,10 @@ proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ @@ -858,15 +917,17 @@ proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = a.prepend(9) a.prepend(8) assert a.contains(9) + prepend(L, newDoublyLinkedNode(value)) proc remove*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = ## Removes `n` from `L`. Efficiency: O(1). + ## This function assumes, for the sake of efficiency, that `n` is contained in `L`, + ## otherwise the effects are undefined. runnableExamples: - var - a = initDoublyLinkedRing[int]() - n = newDoublyLinkedNode[int](5) - a.append(n) + var a = initDoublyLinkedRing[int]() + let n = newDoublyLinkedNode[int](5) + a.add(n) assert 5 in a a.remove(n) assert 5 notin a @@ -874,9 +935,81 @@ proc remove*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = n.next.prev = n.prev n.prev.next = n.next if n == L.head: - var p = L.head.prev + let p = L.head.prev if p == L.head: # only one element left: L.head = nil else: - L.head = L.head.prev + L.head = p + +proc append*[T](a: var (SinglyLinkedList[T] | SinglyLinkedRing[T]), + b: SinglyLinkedList[T] | SinglyLinkedNode[T] | T) = + ## Alias for `a.add(b)`. + ## + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## * `add proc <#add,SinglyLinkedList[T],T>`_ + ## * `add proc <#add,T,T>`_ + a.add(b) + +proc append*[T](a: var (DoublyLinkedList[T] | DoublyLinkedRing[T]), + b: DoublyLinkedList[T] | DoublyLinkedNode[T] | T) = + ## Alias for `a.add(b)`. + ## + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## * `add proc <#add,DoublyLinkedList[T],T>`_ + ## * `add proc <#add,T,T>`_ + a.add(b) + +proc appendMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = + ## Alias for `a.addMoved(b)`. + ## + ## **See also:** + ## * `addMoved proc <#addMoved,SinglyLinkedList[T],SinglyLinkedList[T]>`_ + ## * `addMoved proc <#addMoved,DoublyLinkedList[T],DoublyLinkedList[T]>`_ + a.addMoved(b) + +func toSinglyLinkedList*[T](elems: openArray[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a new `SinglyLinkedList` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toSinglyLinkedList + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initSinglyLinkedList[T]() + for elem in elems.items: + result.add(elem) + +func toSinglyLinkedRing*[T](elems: openArray[T]): SinglyLinkedRing[T] = + ## Creates a new `SinglyLinkedRing` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toSinglyLinkedRing + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initSinglyLinkedRing[T]() + for elem in elems.items: + result.add(elem) + +func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a new `DoublyLinkedList` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toDoublyLinkedList + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initDoublyLinkedList[T]() + for elem in elems.items: + result.add(elem) + +func toDoublyLinkedRing*[T](elems: openArray[T]): DoublyLinkedRing[T] = + ## Creates a new `DoublyLinkedRing` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toDoublyLinkedRing + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initDoublyLinkedRing[T]() + for elem in elems.items: + result.add(elem) diff --git a/lib/pure/collections/sequtils.nim b/lib/pure/collections/sequtils.nim index 7aa885794..3c0d8dc0e 100644 --- a/lib/pure/collections/sequtils.nim +++ b/lib/pure/collections/sequtils.nim @@ -8,13 +8,13 @@ # ## Although this module has `seq` in its name, it implements operations -## not only for `seq`:idx: type, but for three built-in container types under -## the `openArray` umbrella: +## not only for the `seq`:idx: type, but for three built-in container types +## under the `openArray` umbrella: ## * sequences ## * strings ## * array ## -## The system module defines several common functions, such as: +## The `system` module defines several common functions, such as: ## * `newSeq[T]` for creating new sequences of type `T` ## * `@` for converting arrays and strings to sequences ## * `add` for adding new elements to strings and sequences @@ -27,28 +27,28 @@ ## languages. ## ## For functional style programming you have different options at your disposal: -## * `sugar.collect macro<sugar.html#collect.m%2Cuntyped%2Cuntyped>`_ -## * pass `anonymous proc<manual.html#procedures-anonymous-procs>`_ -## * import `sugar module<sugar.html>`_ and use -## `=> macro<sugar.html#%3D>.m,untyped,untyped>`_ +## * the `sugar.collect macro<sugar.html#collect.m%2Cuntyped%2Cuntyped>`_ +## * pass an `anonymous proc<manual.html#procedures-anonymous-procs>`_ +## * import the `sugar module<sugar.html>`_ and use +## the `=> macro<sugar.html#%3D>.m,untyped,untyped>`_ ## * use `...It templates<#18>`_ ## (`mapIt<#mapIt.t,typed,untyped>`_, ## `filterIt<#filterIt.t,untyped,untyped>`_, etc.) ## -## The chaining of functions is possible thanks to the +## Chaining of functions is possible thanks to the ## `method call syntax<manual.html#procedures-method-call-syntax>`_. runnableExamples: - import sugar + import std/sugar # Creating a sequence from 1 to 10, multiplying each member by 2, # keeping only the members which are not divisible by 6. let - foo = toSeq(1..10).map(x => x*2).filter(x => x mod 6 != 0) - bar = toSeq(1..10).mapIt(it*2).filterIt(it mod 6 != 0) + foo = toSeq(1..10).map(x => x * 2).filter(x => x mod 6 != 0) + bar = toSeq(1..10).mapIt(it * 2).filterIt(it mod 6 != 0) baz = collect: for i in 1..10: - let j = 2*i + let j = 2 * i if j mod 6 != 0: j @@ -62,7 +62,7 @@ runnableExamples: runnableExamples: - from strutils import join + from std/strutils import join let vowels = @"aeiou" @@ -71,7 +71,8 @@ runnableExamples: doAssert (vowels is seq[char]) and (vowels == @['a', 'e', 'i', 'o', 'u']) doAssert foo.filterIt(it notin vowels).join == "sqtls s n wsm mdl" -## **See also**: +## See also +## ======== ## * `strutils module<strutils.html>`_ for common string functions ## * `sugar module<sugar.html>`_ for syntactic sugar macros ## * `algorithm module<algorithm.html>`_ for common generic algorithms @@ -81,20 +82,26 @@ runnableExamples: import std/private/since -import macros +import std/macros +from std/typetraits import supportsCopyMem -when not defined(nimhygiene): - {.pragma: dirty.} +when defined(nimPreviewSlimSystem): + import std/assertions +when defined(nimHasEffectsOf): + {.experimental: "strictEffects".} +else: + {.pragma: effectsOf.} + macro evalOnceAs(expAlias, exp: untyped, letAssigneable: static[bool]): untyped = ## Injects `expAlias` in caller scope, to avoid bugs involving multiple - ## substitution in macro arguments such as - ## https://github.com/nim-lang/Nim/issues/7187 + ## substitution in macro arguments such as + ## https://github.com/nim-lang/Nim/issues/7187. ## `evalOnceAs(myAlias, myExp)` will behave as `let myAlias = myExp` ## except when `letAssigneable` is false (e.g. to handle openArray) where - ## it just forwards `exp` unchanged + ## it just forwards `exp` unchanged. expectKind(expAlias, nnkIdent) var val = exp @@ -113,7 +120,7 @@ func concat*[T](seqs: varargs[seq[T]]): seq[T] = ## Takes several sequences' items and returns them inside a new sequence. ## All sequences must be of the same type. ## - ## See also: + ## **See also:** ## * `distribute func<#distribute,seq[T],Positive>`_ for a reverse ## operation ## @@ -134,6 +141,22 @@ func concat*[T](seqs: varargs[seq[T]]): seq[T] = result[i] = itm inc(i) +func addUnique*[T](s: var seq[T], x: sink T) = + ## Adds `x` to the container `s` if it is not already present. + ## Uses `==` to check if the item is already present. + runnableExamples: + var a = @[1, 2, 3] + a.addUnique(4) + a.addUnique(4) + assert a == @[1, 2, 3, 4] + + for i in 0..high(s): + if s[i] == x: return + when declared(ensureMove): + s.add ensureMove(x) + else: + s.add x + func count*[T](s: openArray[T], x: T): int = ## Returns the number of occurrences of the item `x` in the container `s`. ## @@ -167,7 +190,7 @@ func cycle*[T](s: openArray[T], n: Natural): seq[T] = result[o] = e inc o -func repeat*[T](x: T, n: Natural): seq[T] = +proc repeat*[T](x: T, n: Natural): seq[T] = ## Returns a new sequence with the item `x` repeated `n` times. ## `n` must be a non-negative number (zero or more). ## @@ -183,7 +206,7 @@ func repeat*[T](x: T, n: Natural): seq[T] = func deduplicate*[T](s: openArray[T], isSorted: bool = false): seq[T] = ## Returns a new sequence without duplicates. ## - ## Setting the optional argument ``isSorted`` to ``true`` (default: false) + ## Setting the optional argument `isSorted` to true (default: false) ## uses a faster algorithm for deduplication. ## runnableExamples: @@ -210,7 +233,7 @@ func deduplicate*[T](s: openArray[T], isSorted: bool = false): seq[T] = func minIndex*[T](s: openArray[T]): int {.since: (1, 1).} = ## Returns the index of the minimum value of `s`. - ## ``T`` needs to have a ``<`` operator. + ## `T` needs to have a `<` operator. runnableExamples: let a = @[1, 2, 3, 4] @@ -227,7 +250,7 @@ func minIndex*[T](s: openArray[T]): int {.since: (1, 1).} = func maxIndex*[T](s: openArray[T]): int {.since: (1, 1).} = ## Returns the index of the maximum value of `s`. - ## ``T`` needs to have a ``<`` operator. + ## `T` needs to have a `<` operator. runnableExamples: let a = @[1, 2, 3, 4] @@ -242,18 +265,27 @@ func maxIndex*[T](s: openArray[T]): int {.since: (1, 1).} = for i in 1..high(s): if s[i] > s[result]: result = i +func minmax*[T](x: openArray[T]): (T, T) = + ## The minimum and maximum values of `x`. `T` needs to have a `<` operator. + var l = x[0] + var h = x[0] + for i in 1..high(x): + if x[i] < l: l = x[i] + if h < x[i]: h = x[i] + result = (l, h) + template zipImpl(s1, s2, retType: untyped): untyped = - func zip*[S, T](s1: openArray[S], s2: openArray[T]): retType = + proc zip*[S, T](s1: openArray[S], s2: openArray[T]): retType = ## Returns a new sequence with a combination of the two input containers. ## ## The input containers can be of different types. ## If one container is shorter, the remaining items in the longer container ## are discarded. ## - ## **Note**: For Nim 1.0.x and older version, ``zip`` returned a seq of - ## named tuple with fields ``a`` and ``b``. For Nim versions 1.1.x and newer, - ## ``zip`` returns a seq of unnamed tuples. + ## **Note**: For Nim 1.0.x and older version, `zip` returned a seq of + ## named tuples with fields `a` and `b`. For Nim versions 1.1.x and newer, + ## `zip` returns a seq of unnamed tuples. runnableExamples: let short = @[1, 2, 3] @@ -287,7 +319,7 @@ when (NimMajor, NimMinor) <= (1, 0): else: zipImpl(s1, s2, seq[(S, T)]) -func unzip*[S, T](s: openArray[(S, T)]): (seq[S], seq[T]) {.since: (1, 1).} = +proc unzip*[S, T](s: openArray[(S, T)]): (seq[S], seq[T]) {.since: (1, 1).} = ## Returns a tuple of two sequences split out from a sequence of 2-field tuples. runnableExamples: let @@ -296,8 +328,7 @@ func unzip*[S, T](s: openArray[(S, T)]): (seq[S], seq[T]) {.since: (1, 1).} = unzipped2 = @['a', 'b', 'c'] assert zipped.unzip() == (unzipped1, unzipped2) assert zip(unzipped1, unzipped2).unzip() == (unzipped1, unzipped2) - result[0] = newSeq[S](s.len) - result[1] = newSeq[T](s.len) + result = (newSeq[S](s.len), newSeq[T](s.len)) for i in 0..<s.len: result[0][i] = s[i][0] result[1][i] = s[i][1] @@ -311,7 +342,7 @@ func distribute*[T](s: seq[T], num: Positive, spread = true): seq[seq[T]] = ## `num` empty sequences. ## ## If `spread` is false and the length of `s` is not a multiple of `num`, the - ## func will max out the first sub-sequence with ``1 + len(s) div num`` + ## func will max out the first sub-sequence with `1 + len(s) div num` ## entries, leaving the remainder of elements to the last sequence. ## ## On the other hand, if `spread` is true, the func will distribute evenly @@ -329,7 +360,6 @@ func distribute*[T](s: seq[T], num: Positive, spread = true): seq[seq[T]] = if num < 2: result = @[s] return - let num = int(num) # XXX probably only needed because of .. bug # Create the result and calculate the stride size and the remainder if any. result = newSeq[seq[T]](num) @@ -360,17 +390,17 @@ func distribute*[T](s: seq[T], num: Positive, spread = true): seq[seq[T]] = first = last proc map*[T, S](s: openArray[T], op: proc (x: T): S {.closure.}): - seq[S]{.inline.} = - ## Returns a new sequence with the results of `op` proc applied to every + seq[S] {.inline, effectsOf: op.} = + ## Returns a new sequence with the results of the `op` proc applied to every ## item in the container `s`. ## - ## Since the input is not modified you can use it to + ## Since the input is not modified, you can use it to ## transform the type of the elements in the input container. ## ## Instead of using `map` and `filter`, consider using the `collect` macro ## from the `sugar` module. ## - ## See also: + ## **See also:** ## * `sugar.collect macro<sugar.html#collect.m%2Cuntyped%2Cuntyped>`_ ## * `mapIt template<#mapIt.t,typed,untyped>`_ ## * `apply proc<#apply,openArray[T],proc(T)_2>`_ for the in-place version @@ -386,15 +416,14 @@ proc map*[T, S](s: openArray[T], op: proc (x: T): S {.closure.}): result[i] = op(s[i]) proc apply*[T](s: var openArray[T], op: proc (x: var T) {.closure.}) - {.inline.} = - ## Applies `op` to every item in `s` modifying it directly. + {.inline, effectsOf: op.} = + ## Applies `op` to every item in `s`, modifying it directly. ## - ## Note that container `s` must be declared as a ``var`` - ## and it is required for your input and output types to - ## be the same, since `s` is modified in-place. - ## The parameter function takes a ``var T`` type parameter. + ## Note that the container `s` must be declared as a `var`, + ## since `s` is modified in-place. + ## The parameter function takes a `var T` type parameter. ## - ## See also: + ## **See also:** ## * `applyIt template<#applyIt.t,untyped,untyped>`_ ## * `map proc<#map,openArray[T],proc(T)>`_ ## @@ -406,15 +435,15 @@ proc apply*[T](s: var openArray[T], op: proc (x: var T) {.closure.}) for i in 0 ..< s.len: op(s[i]) proc apply*[T](s: var openArray[T], op: proc (x: T): T {.closure.}) - {.inline.} = + {.inline, effectsOf: op.} = ## Applies `op` to every item in `s` modifying it directly. ## - ## Note that container `s` must be declared as a ``var`` + ## Note that the container `s` must be declared as a `var` ## and it is required for your input and output types to ## be the same, since `s` is modified in-place. - ## The parameter function takes and returns a ``T`` type variable. + ## The parameter function takes and returns a `T` type variable. ## - ## See also: + ## **See also:** ## * `applyIt template<#applyIt.t,untyped,untyped>`_ ## * `map proc<#map,openArray[T],proc(T)>`_ ## @@ -425,24 +454,25 @@ proc apply*[T](s: var openArray[T], op: proc (x: T): T {.closure.}) for i in 0 ..< s.len: s[i] = op(s[i]) -proc apply*[T](s: openArray[T], op: proc (x: T) {.closure.}) {.inline, since: (1, 3).} = - ## Same as `apply` but for proc that do not return and do not mutate `s` directly. +proc apply*[T](s: openArray[T], op: proc (x: T) {.closure.}) {.inline, since: (1, 3), effectsOf: op.} = + ## Same as `apply` but for a proc that does not return anything + ## and does not mutate `s` directly. runnableExamples: var message: string apply([0, 1, 2, 3, 4], proc(item: int) = message.addInt item) assert message == "01234" for i in 0 ..< s.len: op(s[i]) -iterator filter*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): T = +iterator filter*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): T {.effectsOf: pred.} = ## Iterates through a container `s` and yields every item that fulfills the - ## predicate `pred` (function that returns a `bool`). + ## predicate `pred` (a function that returns a `bool`). ## ## Instead of using `map` and `filter`, consider using the `collect` macro ## from the `sugar` module. ## - ## See also: + ## **See also:** ## * `sugar.collect macro<sugar.html#collect.m%2Cuntyped%2Cuntyped>`_ - ## * `fliter proc<#filter,openArray[T],proc(T)>`_ + ## * `filter proc<#filter,openArray[T],proc(T)>`_ ## * `filterIt template<#filterIt.t,untyped,untyped>`_ ## runnableExamples: @@ -457,14 +487,14 @@ iterator filter*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): T = yield s[i] proc filter*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): seq[T] - {.inline.} = - ## Returns a new sequence with all the items of `s` that fulfilled the - ## predicate `pred` (function that returns a `bool`). + {.inline, effectsOf: pred.} = + ## Returns a new sequence with all the items of `s` that fulfill the + ## predicate `pred` (a function that returns a `bool`). ## ## Instead of using `map` and `filter`, consider using the `collect` macro ## from the `sugar` module. ## - ## See also: + ## **See also:** ## * `sugar.collect macro<sugar.html#collect.m%2Cuntyped%2Cuntyped>`_ ## * `filterIt template<#filterIt.t,untyped,untyped>`_ ## * `filter iterator<#filter.i,openArray[T],proc(T)>`_ @@ -484,16 +514,16 @@ proc filter*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): seq[T] result.add(s[i]) proc keepIf*[T](s: var seq[T], pred: proc(x: T): bool {.closure.}) - {.inline.} = - ## Keeps the items in the passed sequence `s` if they fulfilled the - ## predicate `pred` (function that returns a `bool`). + {.inline, effectsOf: pred.} = + ## Keeps the items in the passed sequence `s` if they fulfill the + ## predicate `pred` (a function that returns a `bool`). ## - ## Note that `s` must be declared as a ``var``. + ## Note that `s` must be declared as a `var`. ## ## Similar to the `filter proc<#filter,openArray[T],proc(T)>`_, ## but modifies the sequence directly. ## - ## See also: + ## **See also:** ## * `keepItIf template<#keepItIf.t,seq,untyped>`_ ## * `filter proc<#filter,openArray[T],proc(T)>`_ ## @@ -513,12 +543,51 @@ proc keepIf*[T](s: var seq[T], pred: proc(x: T): bool {.closure.}) inc(pos) setLen(s, pos) -func delete*[T](s: var seq[T]; first, last: Natural) = - ## Deletes in the items of a sequence `s` at positions ``first..last`` - ## (including both ends of a range). - ## This modifies `s` itself, it does not return a copy. +func delete*[T](s: var seq[T]; slice: Slice[int]) = + ## Deletes the items `s[slice]`, raising `IndexDefect` if the slice contains + ## elements out of range. ## + ## This operation moves all elements after `s[slice]` in linear time. runnableExamples: + var a = @[10, 11, 12, 13, 14] + doAssertRaises(IndexDefect): a.delete(4..5) + assert a == @[10, 11, 12, 13, 14] + a.delete(4..4) + assert a == @[10, 11, 12, 13] + a.delete(1..2) + assert a == @[10, 13] + a.delete(1..<1) # empty slice + assert a == @[10, 13] + when compileOption("boundChecks"): + if not (slice.a < s.len and slice.a >= 0 and slice.b < s.len): + raise newException(IndexDefect, $(slice: slice, len: s.len)) + if slice.b >= slice.a: + template defaultImpl = + var i = slice.a + var j = slice.b + 1 + var newLen = s.len - j + i + while i < newLen: + when defined(gcDestructors): + s[i] = move(s[j]) + else: + s[i].shallowCopy(s[j]) + inc(i) + inc(j) + setLen(s, newLen) + when nimvm: defaultImpl() + else: + when defined(js): + let n = slice.b - slice.a + 1 + let first = slice.a + {.emit: "`s`.splice(`first`, `n`);".} + else: + defaultImpl() + +func delete*[T](s: var seq[T]; first, last: Natural) {.deprecated: "use `delete(s, first..last)`".} = + ## Deletes the items of a sequence `s` at positions `first..last` + ## (including both ends of the range). + ## This modifies `s` itself, it does not return a copy. + runnableExamples("--warning:deprecated:off"): let outcome = @[1, 1, 1, 1, 1, 1, 1, 1] var dest = @[1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] dest.delete(3, 8) @@ -527,8 +596,8 @@ func delete*[T](s: var seq[T]; first, last: Natural) = if first >= s.len: return var i = first - var j = min(len(s), last+1) - var newLen = len(s)-j+i + var j = min(len(s), last + 1) + var newLen = len(s) - j + i while i < newLen: when defined(gcDestructors): s[i] = move(s[j]) @@ -542,7 +611,7 @@ func insert*[T](dest: var seq[T], src: openArray[T], pos = 0) = ## Inserts items from `src` into `dest` at position `pos`. This modifies ## `dest` itself, it does not return a copy. ## - ## Notice that `src` and `dest` must be of the same type. + ## Note that the elements of `src` and `dest` must be of the same type. ## runnableExamples: var dest = @[1, 1, 1, 1, 1, 1, 1, 1] @@ -573,7 +642,7 @@ func insert*[T](dest: var seq[T], src: openArray[T], pos = 0) = template filterIt*(s, pred: untyped): untyped = - ## Returns a new sequence with all the items of `s` that fulfilled the + ## Returns a new sequence with all the items of `s` that fulfill the ## predicate `pred`. ## ## Unlike the `filter proc<#filter,openArray[T],proc(T)>`_ and @@ -584,9 +653,9 @@ template filterIt*(s, pred: untyped): untyped = ## Instead of using `mapIt` and `filterIt`, consider using the `collect` macro ## from the `sugar` module. ## - ## See also: + ## **See also:** ## * `sugar.collect macro<sugar.html#collect.m%2Cuntyped%2Cuntyped>`_ - ## * `fliter proc<#filter,openArray[T],proc(T)>`_ + ## * `filter proc<#filter,openArray[T],proc(T)>`_ ## * `filter iterator<#filter.i,openArray[T],proc(T)>`_ ## runnableExamples: @@ -604,13 +673,13 @@ template filterIt*(s, pred: untyped): untyped = template keepItIf*(varSeq: seq, pred: untyped) = ## Keeps the items in the passed sequence (must be declared as a `var`) - ## if they fulfilled the predicate. + ## if they fulfill the predicate. ## ## Unlike the `keepIf proc<#keepIf,seq[T],proc(T)>`_, ## the predicate needs to be an expression using ## the `it` variable for testing, like: `keepItIf("abcxyz", it == 'x')`. ## - ## See also: + ## **See also:** ## * `keepIf proc<#keepIf,seq[T],proc(T)>`_ ## * `filterIt template<#filterIt.t,untyped,untyped>`_ ## @@ -633,7 +702,7 @@ template keepItIf*(varSeq: seq, pred: untyped) = since (1, 1): template countIt*(s, pred: untyped): int = - ## Returns a count of all the items that fulfilled the predicate. + ## Returns a count of all the items that fulfill the predicate. ## ## The predicate needs to be an expression using ## the `it` variable for testing, like: `countIt(@[1, 2, 3], it > 2)`. @@ -650,23 +719,23 @@ since (1, 1): if pred: result += 1 result -proc all*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): bool = +proc all*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): bool {.effectsOf: pred.} = ## Iterates through a container and checks if every item fulfills the ## predicate. ## - ## See also: + ## **See also:** ## * `allIt template<#allIt.t,untyped,untyped>`_ ## * `any proc<#any,openArray[T],proc(T)>`_ ## runnableExamples: let numbers = @[1, 4, 5, 8, 9, 7, 4] - assert all(numbers, proc (x: int): bool = return x < 10) == true - assert all(numbers, proc (x: int): bool = return x < 9) == false + assert all(numbers, proc (x: int): bool = x < 10) == true + assert all(numbers, proc (x: int): bool = x < 9) == false for i in s: if not pred(i): return false - return true + true template allIt*(s, pred: untyped): bool = ## Iterates through a container and checks if every item fulfills the @@ -676,7 +745,7 @@ template allIt*(s, pred: untyped): bool = ## the predicate needs to be an expression using ## the `it` variable for testing, like: `allIt("abba", it == 'a')`. ## - ## See also: + ## **See also:** ## * `all proc<#all,openArray[T],proc(T)>`_ ## * `anyIt template<#anyIt.t,untyped,untyped>`_ ## @@ -692,33 +761,33 @@ template allIt*(s, pred: untyped): bool = break result -proc any*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): bool = - ## Iterates through a container and checks if some item fulfills the - ## predicate. +proc any*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): bool {.effectsOf: pred.} = + ## Iterates through a container and checks if at least one item + ## fulfills the predicate. ## - ## See also: + ## **See also:** ## * `anyIt template<#anyIt.t,untyped,untyped>`_ ## * `all proc<#all,openArray[T],proc(T)>`_ ## runnableExamples: let numbers = @[1, 4, 5, 8, 9, 7, 4] - assert any(numbers, proc (x: int): bool = return x > 8) == true - assert any(numbers, proc (x: int): bool = return x > 9) == false + assert any(numbers, proc (x: int): bool = x > 8) == true + assert any(numbers, proc (x: int): bool = x > 9) == false for i in s: if pred(i): return true - return false + false template anyIt*(s, pred: untyped): bool = - ## Iterates through a container and checks if some item fulfills the - ## predicate. + ## Iterates through a container and checks if at least one item + ## fulfills the predicate. ## ## Unlike the `any proc<#any,openArray[T],proc(T)>`_, ## the predicate needs to be an expression using ## the `it` variable for testing, like: `anyIt("abba", it == 'a')`. ## - ## See also: + ## **See also:** ## * `any proc<#any,openArray[T],proc(T)>`_ ## * `allIt template<#allIt.t,untyped,untyped>`_ ## @@ -747,7 +816,7 @@ template toSeq1(s: not iterator): untyped = i += 1 result else: - var result: seq[OutType] = @[] + var result: seq[OutType]# = @[] for it in s: result.add(it) result @@ -764,7 +833,7 @@ template toSeq2(iter: iterator): untyped = result else: type OutType = typeof(iter2()) - var result: seq[OutType] = @[] + var result: seq[OutType]# = @[] when compiles(iter2()): evalOnceAs(iter4, iter, false) let iter3 = iter4() @@ -827,7 +896,7 @@ template foldl*(sequence, operation: untyped): untyped = ## the sequence of numbers 1, 2 and 3 will be parenthesized as (((1) - 2) - ## 3). ## - ## See also: + ## **See also:** ## * `foldl template<#foldl.t,,,>`_ with a starting parameter ## * `foldr template<#foldr.t,untyped,untyped>`_ ## @@ -870,9 +939,9 @@ template foldl*(sequence, operation, first): untyped = ## ## The `operation` parameter should be an expression which uses the variables ## `a` and `b` for each step of the fold. The `first` parameter is the - ## start value (the first `a`) and therefor defines the type of the result. + ## start value (the first `a`) and therefore defines the type of the result. ## - ## See also: + ## **See also:** ## * `foldr template<#foldr.t,untyped,untyped>`_ ## runnableExamples: @@ -903,7 +972,7 @@ template foldr*(sequence, operation: untyped): untyped = ## the sequence of numbers 1, 2 and 3 will be parenthesized as (1 - (2 - ## (3))). ## - ## See also: + ## **See also:** ## * `foldl template<#foldl.t,untyped,untyped>`_ ## * `foldl template<#foldl.t,,,>`_ with a starting parameter ## @@ -932,7 +1001,7 @@ template foldr*(sequence, operation: untyped): untyped = result template mapIt*(s: typed, op: untyped): untyped = - ## Returns a new sequence with the results of `op` proc applied to every + ## Returns a new sequence with the results of the `op` proc applied to every ## item in the container `s`. ## ## Since the input is not modified you can use it to @@ -944,7 +1013,7 @@ template mapIt*(s: typed, op: untyped): untyped = ## Instead of using `mapIt` and `filterIt`, consider using the `collect` macro ## from the `sugar` module. ## - ## See also: + ## **See also:** ## * `sugar.collect macro<sugar.html#collect.m%2Cuntyped%2Cuntyped>`_ ## * `map proc<#map,openArray[T],proc(T)>`_ ## * `applyIt template<#applyIt.t,untyped,untyped>`_ for the in-place version @@ -955,16 +1024,10 @@ template mapIt*(s: typed, op: untyped): untyped = strings = nums.mapIt($(4 * it)) assert strings == @["4", "8", "12", "16"] - when defined(nimHasTypeof): - type OutType = typeof(( - block: - var it{.inject.}: typeof(items(s), typeOfIter); - op), typeOfProc) - else: - type OutType = typeof(( - block: - var it{.inject.}: typeof(items(s)); - op)) + type OutType = typeof(( + block: + var it{.inject.}: typeof(items(s), typeOfIter); + op), typeOfProc) when OutType is not (proc): # Here, we avoid to create closures in loops. # This avoids https://github.com/nim-lang/Nim/issues/12625 @@ -982,7 +1045,7 @@ template mapIt*(s: typed, op: untyped): untyped = i += 1 result else: - var result: seq[OutType] = @[] + var result: seq[OutType]# = @[] # use `items` to avoid https://github.com/nim-lang/Nim/issues/12639 for it {.inject.} in items(s): result.add(op) @@ -995,11 +1058,7 @@ template mapIt*(s: typed, op: untyped): untyped = # With this fallback, above code can be simplified to: # [1, 2].mapIt((x: int) => it + x) # In this case, `mapIt` is just syntax sugar for `map`. - - when defined(nimHasTypeof): - type InType = typeof(items(s), typeOfIter) - else: - type InType = typeof(items(s)) + type InType = typeof(items(s), typeOfIter) # Use a help proc `f` to create closures for each element in `s` let f = proc (x: InType): OutType = let it {.inject.} = x @@ -1010,10 +1069,10 @@ template applyIt*(varSeq, op: untyped) = ## Convenience template around the mutable `apply` proc to reduce typing. ## ## The template injects the `it` variable which you can use directly in an - ## expression. The expression has to return the same type as the sequence you - ## are mutating. + ## expression. The expression has to return the same type as the elements + ## of the sequence you are mutating. ## - ## See also: + ## **See also:** ## * `apply proc<#apply,openArray[T],proc(T)_2>`_ ## * `mapIt template<#mapIt.t,typed,untyped>`_ ## @@ -1028,27 +1087,31 @@ template applyIt*(varSeq, op: untyped) = template newSeqWith*(len: int, init: untyped): untyped = - ## Creates a new sequence of length `len`, calling `init` to initialize - ## each value of the sequence. - ## - ## Useful for creating "2D" sequences - sequences containing other sequences - ## or to populate fields of the created sequence. + ## Creates a new `seq` of length `len`, calling `init` to initialize + ## each value of the seq. ## + ## Useful for creating "2D" seqs - seqs containing other seqs + ## or to populate fields of the created seq. runnableExamples: - ## Creates a sequence containing 5 bool sequences, each of length of 3. + ## Creates a seq containing 5 bool seqs, each of length of 3. var seq2D = newSeqWith(5, newSeq[bool](3)) assert seq2D.len == 5 assert seq2D[0].len == 3 assert seq2D[4][2] == false - ## Creates a sequence of 20 random numbers from 1 to 10 - import random - var seqRand = newSeqWith(20, rand(10)) - - var result = newSeq[typeof(init)](len) - for i in 0 ..< len: + ## Creates a seq with random numbers + import std/random + var seqRand = newSeqWith(20, rand(1.0)) + assert seqRand[0] != seqRand[1] + type T = typeof(init) + let newLen = len + when supportsCopyMem(T) and declared(newSeqUninit): + var result = newSeqUninit[T](newLen) + else: # TODO: use `newSeqUnsafe` when that's available + var result = newSeq[T](newLen) + for i in 0 ..< newLen: result[i] = init - result + move(result) # refs bug #7295 func mapLitsImpl(constructor: NimNode; op: NimNode; nested: bool; filter = nnkLiterals): NimNode = @@ -1081,7 +1144,7 @@ macro mapLiterals*(constructor, op: untyped; let b = mapLiterals((1.2, (2.3, 3.4), 4.8), int, nested=false) assert a == (1, (2, 3), 4) assert b == (1, (2.3, 3.4), 4) - + let c = mapLiterals((1, (2, 3), 4, (5, 6)), `$`) let d = mapLiterals((1, (2, 3), 4, (5, 6)), `$`, nested=false) assert c == ("1", ("2", "3"), "4", ("5", "6")) diff --git a/lib/pure/collections/setimpl.nim b/lib/pure/collections/setimpl.nim index 20da6b6c2..360a075d6 100644 --- a/lib/pure/collections/setimpl.nim +++ b/lib/pure/collections/setimpl.nim @@ -7,7 +7,7 @@ # distribution, for details about the copyright. # -# An ``include`` file for the different hash set implementations. +# An `include` file for the different hash set implementations. template maxHash(t): untyped = high(t.data) @@ -62,6 +62,7 @@ template containsOrInclImpl() {.dirty.} = if index >= 0: result = true else: + result = false if mustRehash(s): enlarge(s) index = rawGetKnownHC(s, key, hc) @@ -86,7 +87,9 @@ proc exclImpl[A](s: var HashSet[A], key: A): bool {.inline.} = var j = i # The correctness of this depends on (h+1) in nextTry, var r = j # though may be adaptable to other simple sequences. s.data[i].hcode = 0 # mark current EMPTY - s.data[i].key = default(type(s.data[i].key)) + {.push warning[UnsafeDefault]:off.} + reset(s.data[i].key) + {.pop.} doWhile((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)): i = (i + 1) and msk # increment mod table size if isEmpty(s.data[i].hcode): # end of collision cluster; So all done diff --git a/lib/pure/collections/sets.nim b/lib/pure/collections/sets.nim index a9df9ded8..af13135aa 100644 --- a/lib/pure/collections/sets.nim +++ b/lib/pure/collections/sets.nim @@ -7,7 +7,7 @@ # distribution, for details about the copyright. # -## The ``sets`` module implements an efficient `hash set`:idx: and +## The `sets` module implements an efficient `hash set`:idx: and ## ordered hash set. ## ## Hash sets are different from the `built in set type @@ -25,7 +25,9 @@ ## `difference <#difference,HashSet[A],HashSet[A]>`_, and ## `symmetric difference <#symmetricDifference,HashSet[A],HashSet[A]>`_ ## -## .. code-block:: +## **Examples:** +## +## ```Nim ## echo toHashSet([9, 5, 1]) # {9, 1, 5} ## echo toOrderedSet([9, 5, 1]) # {9, 5, 1} ## @@ -37,10 +39,10 @@ ## echo s1 - s2 # {1, 9} ## echo s1 * s2 # {5} ## echo s1 -+- s2 # {9, 1, 3, 7} -## +## ``` ## ## Note: The data types declared here have *value semantics*: This means -## that ``=`` performs a copy of the set. +## that `=` performs a copy of the set. ## ## **See also:** ## * `intsets module <intsets.html>`_ for efficient int sets @@ -48,12 +50,12 @@ import - hashes, math + std/[hashes, math] -{.pragma: myShallow.} -when not defined(nimhygiene): - {.pragma: dirty.} +when not defined(nimHasEffectsOf): + {.pragma: effectsOf.} +{.pragma: myShallow.} # For "integer-like A" that are too big for intsets/bit-vectors to be practical, # it would be best to shrink hcode to the same size as the integer. Larger # codes should never be needed, and this can pack more entries per cache-line. @@ -64,7 +66,7 @@ type HashSet*[A] {.myShallow.} = object ## \ ## A generic hash set. ## - ## Use `init proc <#init,HashSet[A]>`_ or `initHashSet proc <#initHashSet,int>`_ + ## Use `init proc <#init,HashSet[A]>`_ or `initHashSet proc <#initHashSet>`_ ## before calling other procs on it. data: KeyValuePairSeq[A] counter: int @@ -116,7 +118,7 @@ proc initHashSet*[A](initialSize = defaultInitialSize): HashSet[A] = ## Wrapper around `init proc <#init,HashSet[A]>`_ for initialization of ## hash sets. ## - ## Returns an empty hash set you can assign directly in ``var`` blocks in a + ## Returns an empty hash set you can assign directly in `var` blocks in a ## single line. ## ## Starting from Nim v0.20, sets are initialized by default and it is @@ -128,12 +130,12 @@ proc initHashSet*[A](initialSize = defaultInitialSize): HashSet[A] = var a = initHashSet[int]() a.incl(3) assert len(a) == 1 - + result = default(HashSet[A]) result.init(initialSize) proc `[]`*[A](s: var HashSet[A], key: A): var A = ## Returns the element that is actually stored in `s` which has the same - ## value as `key` or raises the ``KeyError`` exception. + ## value as `key` or raises the `KeyError` exception. ## ## This is useful when one overloaded `hash` and `==` but still needs ## reference semantics for sharing. @@ -167,6 +169,27 @@ proc contains*[A](s: HashSet[A], key: A): bool = var index = rawGet(s, key, hc) result = index >= 0 +proc len*[A](s: HashSet[A]): int = + ## Returns the number of elements in `s`. + ## + ## Due to an implementation detail you can call this proc on variables which + ## have not been initialized yet. The proc will return zero as the length + ## then. + runnableExamples: + var a: HashSet[string] + assert len(a) == 0 + let s = toHashSet([3, 5, 7]) + assert len(s) == 3 + + result = s.counter + +proc card*[A](s: HashSet[A]): int = + ## Alias for `len() <#len,HashSet[A]>`_. + ## + ## Card stands for the `cardinality + ## <http://en.wikipedia.org/wiki/Cardinality>`_ of a set. + result = s.counter + proc incl*[A](s: var HashSet[A], key: A) = ## Includes an element `key` in `s`. ## @@ -228,7 +251,7 @@ iterator items*[A](s: HashSet[A]): A = ## If you need a sequence with the elements you can use `sequtils.toSeq ## template <sequtils.html#toSeq.t,untyped>`_. ## - ## .. code-block:: + ## ```Nim ## type ## pair = tuple[a, b: int] ## var @@ -241,8 +264,12 @@ iterator items*[A](s: HashSet[A]): A = ## assert a.len == 2 ## echo b ## # --> {(a: 1, b: 3), (a: 0, b: 4)} + ## ``` + let length = s.len for h in 0 .. high(s.data): - if isFilled(s.data[h].hcode): yield s.data[h].key + if isFilled(s.data[h].hcode): + yield s.data[h].key + assert(len(s) == length, "the length of the HashSet changed while iterating over it") proc containsOrIncl*[A](s: var HashSet[A], key: A): bool = ## Includes `key` in the set `s` and tells if `key` was already in `s`. @@ -323,7 +350,7 @@ proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = proc pop*[A](s: var HashSet[A]): A = ## Removes and returns an arbitrary element from the set `s`. ## - ## Raises KeyError if the set `s` is empty. + ## Raises `KeyError` if the set `s` is empty. ## ## See also: ## * `clear proc <#clear,HashSet[A]>`_ @@ -355,28 +382,9 @@ proc clear*[A](s: var HashSet[A]) = s.counter = 0 for i in 0 ..< s.data.len: s.data[i].hcode = 0 - s.data[i].key = default(type(s.data[i].key)) - -proc len*[A](s: HashSet[A]): int = - ## Returns the number of elements in `s`. - ## - ## Due to an implementation detail you can call this proc on variables which - ## have not been initialized yet. The proc will return zero as the length - ## then. - runnableExamples: - var a: HashSet[string] - assert len(a) == 0 - let s = toHashSet([3, 5, 7]) - assert len(s) == 3 - - result = s.counter - -proc card*[A](s: HashSet[A]): int = - ## Alias for `len() <#len,HashSet[A]>`_. - ## - ## Card stands for the `cardinality - ## <http://en.wikipedia.org/wiki/Cardinality>`_ of a set. - result = s.counter + {.push warning[UnsafeDefault]:off.} + reset(s.data[i].key) + {.pop.} proc union*[A](s1, s2: HashSet[A]): HashSet[A] = @@ -422,7 +430,7 @@ proc intersection*[A](s1, s2: HashSet[A]): HashSet[A] = assert c == toHashSet(["b"]) result = initHashSet[A](max(min(s1.data.len, s2.data.len), 2)) - + # iterate over the elements of the smaller set if s1.data.len < s2.data.len: for item in s1: @@ -430,7 +438,7 @@ proc intersection*[A](s1, s2: HashSet[A]): HashSet[A] = else: for item in s2: if item in s1: incl(result, item) - + proc difference*[A](s1, s2: HashSet[A]): HashSet[A] = ## Returns the difference of the sets `s1` and `s2`. @@ -556,7 +564,7 @@ proc `==`*[A](s, t: HashSet[A]): bool = s.counter == t.counter and s <= t -proc map*[A, B](data: HashSet[A], op: proc (x: A): B {.closure.}): HashSet[B] = +proc map*[A, B](data: HashSet[A], op: proc (x: A): B {.closure.}): HashSet[B] {.effectsOf: op.} = ## Returns a new set after applying `op` proc on each of the elements of ##`data` set. ## @@ -583,12 +591,12 @@ proc `$`*[A](s: HashSet[A]): string = ## any moment and values are not escaped. ## ## **Examples:** - ## - ## .. code-block:: + ## ```Nim ## echo toHashSet([2, 4, 5]) ## # --> {2, 4, 5} ## echo toHashSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} + ## ``` dollarImpl() @@ -603,12 +611,10 @@ proc isValid*[A](s: HashSet[A]): bool {.deprecated: ## Returns `true` if the set has been initialized (with `initHashSet proc ## <#initHashSet>`_ or `init proc <#init,HashSet[A]>`_). ## - ## **Examples:** - ## - ## .. code-block :: - ## proc savePreferences(options: HashSet[string]) = - ## assert options.isValid, "Pass an initialized set!" - ## # Do stuff here, may crash in release builds! + runnableExamples: + proc savePreferences(options: HashSet[string]) = + assert options.isValid, "Pass an initialized set!" + # Do stuff here, may crash in release builds! result = s.data.len > 0 @@ -652,7 +658,7 @@ proc initOrderedSet*[A](initialSize = defaultInitialSize): OrderedSet[A] = ## Wrapper around `init proc <#init,OrderedSet[A]>`_ for initialization of ## ordered hash sets. ## - ## Returns an empty ordered hash set you can assign directly in ``var`` blocks + ## Returns an empty ordered hash set you can assign directly in `var` blocks ## in a single line. ## ## Starting from Nim v0.20, sets are initialized by default and it is @@ -812,7 +818,9 @@ proc clear*[A](s: var OrderedSet[A]) = for i in 0 ..< s.data.len: s.data[i].hcode = 0 s.data[i].next = 0 - s.data[i].key = default(type(s.data[i].key)) + {.push warning[UnsafeDefault]:off.} + reset(s.data[i].key) + {.pop.} proc len*[A](s: OrderedSet[A]): int {.inline.} = ## Returns the number of elements in `s`. @@ -873,12 +881,12 @@ proc `$`*[A](s: OrderedSet[A]): string = ## any moment and values are not escaped. ## ## **Examples:** - ## - ## .. code-block:: + ## ```Nim ## echo toOrderedSet([2, 4, 5]) ## # --> {2, 4, 5} ## echo toOrderedSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} + ## ``` dollarImpl() @@ -889,7 +897,7 @@ iterator items*[A](s: OrderedSet[A]): A = ## If you need a sequence with the elements you can use `sequtils.toSeq ## template <sequtils.html#toSeq.t,untyped>`_. ## - ## .. code-block:: + ## ```Nim ## var a = initOrderedSet[int]() ## for value in [9, 2, 1, 5, 1, 8, 4, 2]: ## a.incl(value) @@ -901,8 +909,11 @@ iterator items*[A](s: OrderedSet[A]): A = ## # --> Got 5 ## # --> Got 8 ## # --> Got 4 + ## ``` + let length = s.len forAllOrderedPairs: yield s.data[h].key + assert(len(s) == length, "the length of the OrderedSet changed while iterating over it") iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = ## Iterates through (position, value) tuples of OrderedSet `s`. @@ -913,5 +924,7 @@ iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = p.add(x) assert p == @[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'c'), (4, 'd')] + let length = s.len forAllOrderedPairs: yield (idx, s.data[h].key) + assert(len(s) == length, "the length of the OrderedSet changed while iterating over it") diff --git a/lib/pure/collections/sharedlist.nim b/lib/pure/collections/sharedlist.nim index c72477675..ec8f1cd86 100644 --- a/lib/pure/collections/sharedlist.nim +++ b/lib/pure/collections/sharedlist.nim @@ -11,10 +11,12 @@ ## ## Unstable API. +{.deprecated.} + {.push stackTrace: off.} import - locks + std/locks const ElemsPerNode = 100 @@ -35,8 +37,10 @@ template withLock(t, x: untyped) = release(t.lock) proc iterAndMutate*[A](x: var SharedList[A]; action: proc(x: A): bool) = - ## iterates over the list. If 'action' returns true, the + ## Iterates over the list. If `action` returns true, the ## current item is removed from the list. + ## + ## .. warning:: It may not preserve the element order after some modifications. withLock(x): var n = x.head while n != nil: @@ -47,8 +51,9 @@ proc iterAndMutate*[A](x: var SharedList[A]; action: proc(x: A): bool) = if action(n.d[i]): acquire(x.lock) let t = x.tail + dec t.dataLen # TODO considering t.dataLen == 0, + # probably the module should be refactored using doubly linked lists n.d[i] = t.d[t.dataLen] - dec t.dataLen else: acquire(x.lock) inc i diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim index af498d70d..b474ecd31 100644 --- a/lib/pure/collections/sharedtables.nim +++ b/lib/pure/collections/sharedtables.nim @@ -14,8 +14,10 @@ ## ## Unstable API. +{.deprecated.} + import - hashes, math, locks + std/[hashes, math, locks] type KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B] @@ -60,17 +62,27 @@ template withLock(t, x: untyped) = template withValue*[A, B](t: var SharedTable[A, B], key: A, value, body: untyped) = - ## retrieves the value at ``t[key]``. - ## `value` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## sharedTable.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## # value is threadsafe in block - ## value.name = "username" - ## value.uid = 1000 - ## + ## Retrieves the value at `t[key]`. + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + var table: SharedTable[string, string] + init(table) + + table["a"] = "x" + table["b"] = "y" + table["c"] = "z" + + table.withValue("a", value): + assert value[] == "x" + + table.withValue("b", value): + value[] = "modified" + + table.withValue("b", value): + assert value[] == "modified" + + table.withValue("nonexistent", value): + assert false # not called acquire(t.lock) try: var hc: Hash @@ -84,20 +96,33 @@ template withValue*[A, B](t: var SharedTable[A, B], key: A, template withValue*[A, B](t: var SharedTable[A, B], key: A, value, body1, body2: untyped) = - ## retrieves the value at ``t[key]``. - ## `value` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## sharedTable.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## # value is threadsafe in block - ## value.name = "username" - ## value.uid = 1000 - ## do: - ## # block is executed when ``key`` not in ``t`` - ## raise newException(KeyError, "Key not found") - ## + ## Retrieves the value at `t[key]`. + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + var table: SharedTable[string, string] + init(table) + + table["a"] = "x" + table["b"] = "y" + table["c"] = "z" + + + table.withValue("a", value): + value[] = "m" + + var flag = false + table.withValue("d", value): + discard value + doAssert false + do: # if "d" notin table + flag = true + + if flag: + table["d"] = "n" + + assert table.mget("a") == "m" + assert table.mget("d") == "n" + acquire(t.lock) try: var hc: Hash @@ -112,8 +137,8 @@ template withValue*[A, B](t: var SharedTable[A, B], key: A, release(t.lock) proc mget*[A, B](t: var SharedTable[A, B], key: A): var B = - ## retrieves the value at ``t[key]``. The value can be modified. - ## If `key` is not in `t`, the ``KeyError`` exception is raised. + ## Retrieves the value at `t[key]`. The value can be modified. + ## If `key` is not in `t`, the `KeyError` exception is raised. withLock t: var hc: Hash var index = rawGet(t, key, hc) @@ -126,15 +151,15 @@ proc mget*[A, B](t: var SharedTable[A, B], key: A): var B = raise newException(KeyError, "key not found") proc mgetOrPut*[A, B](t: var SharedTable[A, B], key: A, val: B): var B = - ## retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. **Note**: This is inherently ## unsafe in the context of multi-threading since it returns a pointer - ## to ``B``. + ## to `B`. withLock t: mgetOrPutImpl(enlarge) proc hasKeyOrPut*[A, B](t: var SharedTable[A, B], key: A, val: B): bool = - ## returns true if `key` is in the table, otherwise inserts `value`. + ## Returns true if `key` is in the table, otherwise inserts `value`. withLock t: hasKeyOrPutImpl(enlarge) @@ -144,30 +169,29 @@ template tabCellHash(i) = t.data[i].hcode proc withKey*[A, B](t: var SharedTable[A, B], key: A, mapper: proc(key: A, val: var B, pairExists: var bool)) = - ## Computes a new mapping for the ``key`` with the specified ``mapper`` + ## Computes a new mapping for the `key` with the specified `mapper` ## procedure. ## - ## The ``mapper`` takes 3 arguments: + ## The `mapper` takes 3 arguments: ## - ## 1. ``key`` - the current key, if it exists, or the key passed to - ## ``withKey`` otherwise; - ## 2. ``val`` - the current value, if the key exists, or default value + ## 1. `key` - the current key, if it exists, or the key passed to + ## `withKey` otherwise; + ## 2. `val` - the current value, if the key exists, or default value ## of the type otherwise; - ## 3. ``pairExists`` - ``true`` if the key exists, ``false`` otherwise. + ## 3. `pairExists` - `true` if the key exists, `false` otherwise. ## - ## The ``mapper`` can can modify ``val`` and ``pairExists`` values to change + ## The `mapper` can can modify `val` and `pairExists` values to change ## the mapping of the key or delete it from the table. - ## When adding a value, make sure to set ``pairExists`` to ``true`` along - ## with modifying the ``val``. + ## When adding a value, make sure to set `pairExists` to `true` along + ## with modifying the `val`. ## ## The operation is performed atomically and other operations on the table - ## will be blocked while the ``mapper`` is invoked, so it should be short and + ## will be blocked while the `mapper` is invoked, so it should be short and ## simple. ## ## Example usage: ## - ## .. code-block:: nim - ## + ## ```nim ## # If value exists, decrement it. ## # If it becomes zero or less, delete the key ## t.withKey(1'i64) do (k: int64, v: var int, pairExists: var bool): @@ -175,6 +199,7 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, ## dec v ## if v <= 0: ## pairExists = false + ## ``` withLock t: var hc: Hash var index = rawGet(t, key, hc) @@ -191,28 +216,28 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, st_maybeRehashPutImpl(enlarge) proc `[]=`*[A, B](t: var SharedTable[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. + ## Puts a (key, value)-pair into `t`. withLock t: putImpl(enlarge) proc add*[A, B](t: var SharedTable[A, B], key: A, val: B) = - ## puts a new (key, value)-pair into `t` even if ``t[key]`` already exists. + ## Puts a new (key, value)-pair into `t` even if `t[key]` already exists. ## This can introduce duplicate keys into the table! withLock t: addImpl(enlarge) proc del*[A, B](t: var SharedTable[A, B], key: A) = - ## deletes `key` from hash table `t`. + ## Deletes `key` from hash table `t`. withLock t: delImpl(tabMakeEmpty, tabCellEmpty, tabCellHash) proc len*[A, B](t: var SharedTable[A, B]): int = - ## number of elements in `t` + ## Number of elements in `t`. withLock t: result = t.counter proc init*[A, B](t: var SharedTable[A, B], initialSize = 32) = - ## creates a new hash table that is empty. + ## Creates a new hash table that is empty. ## ## This proc must be called before any other usage of `t`. let initialSize = slotsNeeded(initialSize) diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim index c66da513c..3542741fa 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -7,10 +7,13 @@ # distribution, for details about the copyright. # -# An ``include`` file for the different table implementations. +# An `include` file for the different table implementations. include hashcommon +const + defaultInitialSize* = 32 + template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add genHashImpl(key, hc) var h: Hash = hc and maxHash(t) @@ -23,7 +26,7 @@ template rawInsertImpl() {.dirty.} = data[h].val = val data[h].hcode = hc -proc rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline.} = +proc rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline, outParamsAt: [3].} = rawGetDeepImpl() proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B], @@ -31,9 +34,8 @@ proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B], rawInsertImpl() template checkIfInitialized() = - when compiles(defaultInitialSize): - if t.dataLen == 0: - initImpl(t, defaultInitialSize) + if t.dataLen == 0: + initImpl(t, defaultInitialSize) template addImpl(enlarge) {.dirty.} = checkIfInitialized() @@ -43,7 +45,7 @@ template addImpl(enlarge) {.dirty.} = rawInsert(t, t.data, key, val, hc, j) inc(t.counter) -template maybeRehashPutImpl(enlarge) {.dirty.} = +template maybeRehashPutImpl(enlarge, val) {.dirty.} = checkIfInitialized() if mustRehash(t): enlarge(t) @@ -54,28 +56,41 @@ template maybeRehashPutImpl(enlarge) {.dirty.} = template putImpl(enlarge) {.dirty.} = checkIfInitialized() - var hc: Hash + var hc: Hash = default(Hash) var index = rawGet(t, key, hc) if index >= 0: t.data[index].val = val - else: maybeRehashPutImpl(enlarge) + else: maybeRehashPutImpl(enlarge, val) template mgetOrPutImpl(enlarge) {.dirty.} = checkIfInitialized() - var hc: Hash + var hc: Hash = default(Hash) var index = rawGet(t, key, hc) if index < 0: # not present: insert (flipping index) - maybeRehashPutImpl(enlarge) + when declared(val): + maybeRehashPutImpl(enlarge, val) + else: + maybeRehashPutImpl(enlarge, default(B)) # either way return modifiable val result = t.data[index].val +# template mgetOrPutDefaultImpl(enlarge) {.dirty.} = +# checkIfInitialized() +# var hc: Hash = default(Hash) +# var index = rawGet(t, key, hc) +# if index < 0: +# # not present: insert (flipping index) +# maybeRehashPutImpl(enlarge, default(B)) +# # either way return modifiable val +# result = t.data[index].val + template hasKeyOrPutImpl(enlarge) {.dirty.} = checkIfInitialized() - var hc: Hash + var hc: Hash = default(Hash) var index = rawGet(t, key, hc) if index < 0: result = false - maybeRehashPutImpl(enlarge) + maybeRehashPutImpl(enlarge, val) else: result = true # delImplIdx is KnuthV3 Algo6.4R adapted to i=i+1 (from i=i-1) which has come to @@ -117,8 +132,10 @@ template delImplIdx(t, i, makeEmpty, cellEmpty, cellHash) = var j = i # The correctness of this depends on (h+1) in nextTry var r = j # though may be adaptable to other simple sequences. makeEmpty(i) # mark current EMPTY - t.data[i].key = default(type(t.data[i].key)) - t.data[i].val = default(type(t.data[i].val)) + {.push warning[UnsafeDefault]:off.} + reset(t.data[i].key) + reset(t.data[i].val) + {.pop.} while true: i = (i + 1) and msk # increment mod table size if cellEmpty(i): # end of collision cluster; So all done @@ -149,8 +166,10 @@ template clearImpl() {.dirty.} = for i in 0 ..< t.dataLen: when compiles(t.data[i].hcode): # CountTable records don't contain a hcode t.data[i].hcode = 0 - t.data[i].key = default(type(t.data[i].key)) - t.data[i].val = default(type(t.data[i].val)) + {.push warning[UnsafeDefault]:off.} + reset(t.data[i].key) + reset(t.data[i].val) + {.pop.} t.counter = 0 template ctAnd(a, b): bool = @@ -161,7 +180,7 @@ template ctAnd(a, b): bool = template initImpl(result: typed, size: int) = let correctSize = slotsNeeded(size) - when ctAnd(declared(SharedTable), type(result) is SharedTable): + when ctAnd(declared(SharedTable), typeof(result) is SharedTable): init(result, correctSize) else: result.counter = 0 @@ -208,3 +227,5 @@ template equalsImpl(s, t: typed) = if not t.hasKey(key): return false if t.getOrDefault(key) != val: return false return true + else: + return false diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index d7376b065..d414caeed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -7,219 +7,198 @@ # distribution, for details about the copyright. # -## The ``tables`` module implements variants of an efficient `hash table`:idx: +## The `tables` module implements variants of an efficient `hash table`:idx: ## (also often named `dictionary`:idx: in other programming languages) that is ## a mapping from keys to values. ## ## There are several different types of hash tables available: ## * `Table<#Table>`_ is the usual hash table, -## * `OrderedTable<#OrderedTable>`_ is like ``Table`` but remembers insertion order, +## * `OrderedTable<#OrderedTable>`_ is like `Table` but remembers insertion order, ## * `CountTable<#CountTable>`_ is a mapping from a key to its number of occurrences ## ## For consistency with every other data type in Nim these have **value** -## semantics, this means that ``=`` performs a copy of the hash table. +## semantics, this means that `=` performs a copy of the hash table. ## ## For `ref semantics<manual.html#types-reference-and-pointer-types>`_ -## use their ``Ref`` variants: `TableRef<#TableRef>`_, +## use their `Ref` variants: `TableRef<#TableRef>`_, ## `OrderedTableRef<#OrderedTableRef>`_, and `CountTableRef<#CountTableRef>`_. ## -## To give an example, when ``a`` is a ``Table``, then ``var b = a`` gives ``b`` -## as a new independent table. ``b`` is initialised with the contents of ``a``. -## Changing ``b`` does not affect ``a`` and vice versa: -## -## .. code-block:: -## import tables -## -## var -## a = {1: "one", 2: "two"}.toTable # creates a Table -## b = a -## -## echo a, b # output: {1: one, 2: two}{1: one, 2: two} -## -## b[3] = "three" -## echo a, b # output: {1: one, 2: two}{1: one, 2: two, 3: three} -## echo a == b # output: false -## -## On the other hand, when ``a`` is a ``TableRef`` instead, then changes to ``b`` -## also affect ``a``. Both ``a`` and ``b`` **ref** the same data structure: -## -## .. code-block:: -## import tables -## -## var -## a = {1: "one", 2: "two"}.newTable # creates a TableRef -## b = a -## -## echo a, b # output: {1: one, 2: two}{1: one, 2: two} -## -## b[3] = "three" -## echo a, b # output: {1: one, 2: two, 3: three}{1: one, 2: two, 3: three} -## echo a == b # output: true +## To give an example, when `a` is a `Table`, then `var b = a` gives `b` +## as a new independent table. `b` is initialised with the contents of `a`. +## Changing `b` does not affect `a` and vice versa: + +runnableExamples: + var + a = {1: "one", 2: "two"}.toTable # creates a Table + b = a + + assert a == b + + b[3] = "three" + assert 3 notin a + assert 3 in b + assert a != b + +## On the other hand, when `a` is a `TableRef` instead, then changes to `b` +## also affect `a`. Both `a` and `b` **ref** the same data structure: + +runnableExamples: + var + a = {1: "one", 2: "two"}.newTable # creates a TableRef + b = a + + assert a == b + + b[3] = "three" + + assert 3 in a + assert 3 in b + assert a == b + ## ## ---- ## -## Basic usage -## =========== -## -## Table -## ----- -## -## .. code-block:: -## import tables -## from sequtils import zip -## -## let -## names = ["John", "Paul", "George", "Ringo"] -## years = [1940, 1942, 1943, 1940] -## -## var beatles = initTable[string, int]() -## -## for pairs in zip(names, years): -## let (name, birthYear) = pairs -## beatles[name] = birthYear -## -## echo beatles -## # {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940} -## -## -## var beatlesByYear = initTable[int, seq[string]]() -## -## for pairs in zip(years, names): -## let (birthYear, name) = pairs -## if not beatlesByYear.hasKey(birthYear): -## # if a key doesn't exist, we create one with an empty sequence -## # before we can add elements to it -## beatlesByYear[birthYear] = @[] -## beatlesByYear[birthYear].add(name) -## -## echo beatlesByYear -## # {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]} -## -## -## -## OrderedTable -## ------------ -## + +## # Basic usage + + +## ## Table +runnableExamples: + from std/sequtils import zip + + let + names = ["John", "Paul", "George", "Ringo"] + years = [1940, 1942, 1943, 1940] + + var beatles = initTable[string, int]() + + for pairs in zip(names, years): + let (name, birthYear) = pairs + beatles[name] = birthYear + + assert beatles == {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940}.toTable + + + var beatlesByYear = initTable[int, seq[string]]() + + for pairs in zip(years, names): + let (birthYear, name) = pairs + if not beatlesByYear.hasKey(birthYear): + # if a key doesn't exist, we create one with an empty sequence + # before we can add elements to it + beatlesByYear[birthYear] = @[] + beatlesByYear[birthYear].add(name) + + assert beatlesByYear == {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]}.toTable + +## ## OrderedTable ## `OrderedTable<#OrderedTable>`_ is used when it is important to preserve ## the insertion order of keys. -## -## .. code-block:: -## import tables -## -## let -## a = [('z', 1), ('y', 2), ('x', 3)] -## t = a.toTable # regular table -## ot = a.toOrderedTable # ordered tables -## -## echo t # {'x': 3, 'y': 2, 'z': 1} -## echo ot # {'z': 1, 'y': 2, 'x': 3} -## -## -## -## CountTable -## ---------- -## + +runnableExamples: + let + a = [('z', 1), ('y', 2), ('x', 3)] + ot = a.toOrderedTable # ordered tables + + assert $ot == """{'z': 1, 'y': 2, 'x': 3}""" + +## ## CountTable ## `CountTable<#CountTable>`_ is useful for counting number of items of some ## container (e.g. string, sequence or array), as it is a mapping where the ## items are the keys, and their number of occurrences are the values. ## For that purpose `toCountTable proc<#toCountTable,openArray[A]>`_ ## comes handy: -## -## .. code-block:: -## import tables -## -## let myString = "abracadabra" -## let letterFrequencies = toCountTable(myString) -## echo letterFrequencies -## # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} -## + +runnableExamples: + let myString = "abracadabra" + let letterFrequencies = toCountTable(myString) + assert $letterFrequencies == "{'a': 5, 'd': 1, 'b': 2, 'r': 2, 'c': 1}" + ## The same could have been achieved by manually iterating over a container ## and increasing each key's value with `inc proc ## <#inc,CountTable[A],A,int>`_: -## -## .. code-block:: -## import tables -## -## let myString = "abracadabra" -## var letterFrequencies = initCountTable[char]() -## for c in myString: -## letterFrequencies.inc(c) -## echo letterFrequencies -## # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} + +runnableExamples: + let myString = "abracadabra" + var letterFrequencies = initCountTable[char]() + for c in myString: + letterFrequencies.inc(c) + assert $letterFrequencies == "{'d': 1, 'r': 2, 'c': 1, 'a': 5, 'b': 2}" + ## ## ---- ## + +## ## Hashing ## -## -## Hashing -## ------- -## -## If you are using simple standard types like ``int`` or ``string`` for the +## If you are using simple standard types like `int` or `string` for the ## keys of the table you won't have any problems, but as soon as you try to use ## a more complex object as a key you will be greeted by a strange compiler ## error: ## -## Error: type mismatch: got (Person) -## but expected one of: -## hashes.hash(x: openArray[A]): Hash -## hashes.hash(x: int): Hash -## hashes.hash(x: float): Hash -## … +## Error: type mismatch: got (Person) +## but expected one of: +## hashes.hash(x: openArray[A]): Hash +## hashes.hash(x: int): Hash +## hashes.hash(x: float): Hash ## ## What is happening here is that the types used for table keys require to have -## a ``hash()`` proc which will convert them to a `Hash <hashes.html#Hash>`_ +## a `hash()` proc which will convert them to a `Hash <hashes.html#Hash>`_ ## value, and the compiler is listing all the hash functions it knows. -## Additionally there has to be a ``==`` operator that provides the same -## semantics as its corresponding ``hash`` proc. +## Additionally there has to be a `==` operator that provides the same +## semantics as its corresponding `hash` proc. ## -## After you add ``hash`` and ``==`` for your custom type everything will work. -## Currently, however, ``hash`` for objects is not defined, whereas -## ``system.==`` for objects does exist and performs a "deep" comparison (every +## After you add `hash` and `==` for your custom type everything will work. +## Currently, however, `hash` for objects is not defined, whereas +## `system.==` for objects does exist and performs a "deep" comparison (every ## field is compared) which is usually what you want. So in the following -## example implementing only ``hash`` suffices: -## -## .. code-block:: -## import tables, hashes -## -## type -## Person = object -## firstName, lastName: string -## -## proc hash(x: Person): Hash = -## ## Piggyback on the already available string hash proc. -## ## -## ## Without this proc nothing works! -## result = x.firstName.hash !& x.lastName.hash -## result = !$result -## -## var -## salaries = initTable[Person, int]() -## p1, p2: Person -## -## p1.firstName = "Jon" -## p1.lastName = "Ross" -## salaries[p1] = 30_000 -## -## p2.firstName = "소진" -## p2.lastName = "박" -## salaries[p2] = 45_000 +## example implementing only `hash` suffices: + +runnableExamples: + import std/hashes + + type + Person = object + firstName, lastName: string + + proc hash(x: Person): Hash = + ## Piggyback on the already available string hash proc. + ## + ## Without this proc nothing works! + result = x.firstName.hash !& x.lastName.hash + result = !$result + + var + salaries = initTable[Person, int]() + p1, p2: Person + + p1.firstName = "Jon" + p1.lastName = "Ross" + salaries[p1] = 30_000 + + p2.firstName = "소진" + p2.lastName = "박" + salaries[p2] = 45_000 + ## ## ---- ## -## See also -## ======== + +## # See also ## ## * `json module<json.html>`_ for table-like structure which allows ## heterogeneous members -## * `sharedtables module<sharedtables.html>`_ for shared hash table support ## * `strtabs module<strtabs.html>`_ for efficient hash tables ## mapping from strings to strings ## * `hashes module<hashes.html>`_ for helper functions for hashing import std/private/since +import std/[hashes, math, algorithm] -import hashes, math, algorithm + +when not defined(nimHasEffectsOf): + {.pragma: effectsOf.} type KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B] @@ -238,8 +217,6 @@ type ## For creating a new empty TableRef, use `newTable proc ## <#newTable>`_. -const - defaultInitialSize* = 32 # ------------------------------ helpers --------------------------------- @@ -250,18 +227,21 @@ template dataLen(t): untyped = len(t.data) include tableimpl +proc raiseKeyError[T](key: T) {.noinline, noreturn.} = + when compiles($key): + raise newException(KeyError, "key not found: " & $key) + else: + raise newException(KeyError, "key not found") + template get(t, key): untyped = - ## retrieves the value at ``t[key]``. The value can be modified. - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## retrieves the value at `t[key]`. The value can be modified. + ## If `key` is not in `t`, the `KeyError` exception is raised. mixin rawGet var hc: Hash var index = rawGet(t, key, hc) if index >= 0: result = t.data[index].val else: - when compiles($key): - raise newException(KeyError, "key not found: " & $key) - else: - raise newException(KeyError, "key not found") + raiseKeyError(key) proc enlarge[A, B](t: var Table[A, B]) = var n: KeyValuePairSeq[A, B] @@ -298,10 +278,11 @@ proc initTable*[A, B](initialSize = defaultInitialSize): Table[A, B] = let a = initTable[int, string]() b = initTable[char, seq[int]]() + result = default(Table[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var Table[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key @@ -317,9 +298,9 @@ proc `[]=`*[A, B](t: var Table[A, B], key: A, val: sink B) = putImpl(enlarge) proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = - ## Creates a new hash table that contains the given ``pairs``. + ## Creates a new hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `initTable proc<#initTable>`_ @@ -332,10 +313,10 @@ proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = result = initTable[A, B](pairs.len) for key, val in items(pairs): result[key] = val -proc `[]`*[A, B](t: Table[A, B], key: A): B = - ## Retrieves the value at ``t[key]``. +proc `[]`*[A, B](t: Table[A, B], key: A): lent B = + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,Table[A,B],A>`_ whether ## the key exists. ## @@ -344,7 +325,7 @@ proc `[]`*[A, B](t: Table[A, B], key: A): B = ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist - ## * `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## * `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,Table[A,B],A>`_ for checking if a key is in ## the table @@ -356,23 +337,23 @@ proc `[]`*[A, B](t: Table[A, B], key: A): B = get(t, key) proc `[]`*[A, B](t: var Table[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. The value can be modified. + ## Retrieves the value at `t[key]`. The value can be modified. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## ## See also: ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist - ## * `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## * `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,Table[A,B],A>`_ for checking if a key is in ## the table get(t, key) proc hasKey*[A, B](t: Table[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,Table[A,B],A>`_ for use with the `in` operator @@ -391,7 +372,7 @@ proc hasKey*[A, B](t: Table[A, B], key: A): bool = proc contains*[A, B](t: Table[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,Table[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert 'b' in a == true @@ -400,7 +381,7 @@ proc contains*[A, B](t: Table[A, B], key: A): bool = return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,Table[A,B],A>`_ @@ -420,8 +401,8 @@ proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: Table[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -435,12 +416,12 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 - + result = default(B) getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key @@ -453,16 +434,16 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 - + result = default(B) getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## ## Note that while the value returned is of type `var B`, - ## it is easy to accidentally create an copy of the value at `t[key]`. + ## it is easy to accidentally create a copy of the value at `t[key]`. ## Remember that seqs and strings are value types, and therefore ## cannot be copied into a separate variable for modification. ## See the example below. @@ -494,8 +475,20 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) +proc mgetOrPut*[A, B](t: var Table[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.newTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.newTable + + mgetOrPutImpl(enlarge) + proc len*[A, B](t: Table[A, B]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert len(a) == 2 @@ -504,11 +497,11 @@ proc len*[A, B](t: Table[A, B]): int = proc add*[A, B](t: var Table[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## - ## Use `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## Use `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table without introducing duplicates. addImpl(enlarge) @@ -517,7 +510,10 @@ template tabCellEmpty(i) = isEmpty(t.data[i].hcode) template tabCellHash(i) = t.data[i].hcode proc del*[A, B](t: var Table[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. + ## + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. ## ## See also: ## * `pop proc<#pop,Table[A,B],A,B>`_ @@ -532,11 +528,14 @@ proc del*[A, B](t: var Table[A, B], key: A) = delImpl(tabMakeEmpty, tabCellEmpty, tabCellHash) proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. + ## ## See also: ## * `del proc<#del,Table[A,B],A>`_ ## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table @@ -579,12 +578,12 @@ proc clear*[A, B](t: var Table[A, B]) = clearImpl() proc `$`*[A, B](t: Table[A, B]): string = - ## The ``$`` operator for hash tables. Used internally when calling `echo` + ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: Table[A, B]): bool = - ## The ``==`` operator for hash tables. Returns ``true`` if the content of both + ## The `==` operator for hash tables. Returns `true` if the content of both ## tables contains the same key-value pairs. Insert order does not matter. runnableExamples: let @@ -604,17 +603,31 @@ proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) = - ## Retrieves the value at ``t[key]``. - ## - ## ``value`` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## sharedTable.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## value.name = "username" - ## value.uid = 1000 + ## Retrieves the value at `t[key]`. ## + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + type + User = object + name: string + uid: int + + var t = initTable[int, User]() + let u = User(name: "Hello", uid: 99) + t[1] = u + + t.withValue(1, value): + # block is executed only if `key` in `t` + value.name = "Nim" + value.uid = 1314 + + t.withValue(2, value): + value.name = "No" + value.uid = 521 + + assert t[1].name == "Nim" + assert t[1].uid == 1314 + mixin rawGet var hc: Hash var index = rawGet(t, key, hc) @@ -625,20 +638,35 @@ template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) = template withValue*[A, B](t: var Table[A, B], key: A, value, body1, body2: untyped) = - ## Retrieves the value at ``t[key]``. - ## - ## ``value`` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## table.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## value.name = "username" - ## value.uid = 1000 - ## do: - ## # block is executed when ``key`` not in ``t`` - ## raise newException(KeyError, "Key not found") + ## Retrieves the value at `t[key]`. ## + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + type + User = object + name: string + uid: int + + var t = initTable[int, User]() + let u = User(name: "Hello", uid: 99) + t[1] = u + + t.withValue(1, value): + # block is executed only if `key` in `t` + value.name = "Nim" + value.uid = 1314 + + t.withValue(521, value): + doAssert false + do: + # block is executed when `key` not in `t` + t[1314] = User(name: "exist", uid: 521) + + assert t[1].name == "Nim" + assert t[1].uid == 1314 + assert t[1314].name == "exist" + assert t[1314].uid == 521 + mixin rawGet var hc: Hash var index = rawGet(t, key, hc) @@ -651,7 +679,7 @@ template withValue*[A, B](t: var Table[A, B], key: A, iterator pairs*[A, B](t: Table[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,Table[A,B]>`_ @@ -660,7 +688,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -674,6 +702,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = ## # value: [2, 4, 6, 8] ## # key: o ## # value: [1, 5, 7, 9] + ## ``` let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): @@ -681,7 +710,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` (must be + ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -702,8 +731,8 @@ iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: Table[A, B]): A = - ## Iterates over any key in the table ``t``. +iterator keys*[A, B](t: Table[A, B]): lent A = + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,Table[A,B]>`_ @@ -723,8 +752,8 @@ iterator keys*[A, B](t: Table[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: Table[A, B]): B = - ## Iterates over any value in the table ``t``. +iterator values*[A, B](t: Table[A, B]): lent B = + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,Table[A,B]>`_ @@ -745,7 +774,7 @@ iterator values*[A, B](t: Table[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: var Table[A, B]): var B = - ## Iterates over any value in the table ``t`` (must be + ## Iterates over any value in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -768,13 +797,13 @@ iterator mvalues*[A, B](t: var Table[A, B]): var B = iterator allValues*[A, B](t: Table[A, B]; key: A): B {.deprecated: "Deprecated since v1.4; tables with duplicated keys are deprecated".} = - ## Iterates over any value in the table ``t`` that belongs to the given ``key``. + ## Iterates over any value in the table `t` that belongs to the given `key`. ## ## Used if you have a table with duplicate keys (as a result of using ## `add proc<#add,Table[A,B],A,sinkB>`_). ## runnableExamples: - import sequtils, algorithm + import std/[sequtils, algorithm] var a = {'a': 3, 'b': 5}.toTable for i in 1..3: a.add('z', 10*i) @@ -795,7 +824,7 @@ iterator allValues*[A, B](t: Table[A, B]; key: A): B {.deprecated: # ------------------------------------------------------------------- -proc newTable*[A, B](initialSize = defaultInitialSize): <//>TableRef[A, B] = +proc newTable*[A, B](initialSize = defaultInitialSize): TableRef[A, B] = ## Creates a new ref hash table that is empty. ## ## See also: @@ -808,12 +837,13 @@ proc newTable*[A, B](initialSize = defaultInitialSize): <//>TableRef[A, B] = b = newTable[char, seq[int]]() new(result) - result[] = initTable[A, B](initialSize) + {.noSideEffect.}: + result[] = initTable[A, B](initialSize) -proc newTable*[A, B](pairs: openArray[(A, B)]): <//>TableRef[A, B] = - ## Creates a new ref hash table that contains the given ``pairs``. +proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = + ## Creates a new ref hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `newTable proc<#newTable>`_ @@ -824,19 +854,21 @@ proc newTable*[A, B](pairs: openArray[(A, B)]): <//>TableRef[A, B] = assert b == {'a': 5, 'b': 9}.newTable new(result) - result[] = toTable[A, B](pairs) + {.noSideEffect.}: + result[] = toTable[A, B](pairs) -proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): <//>TableRef[C, B] = +proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = ## Index the collection with the proc provided. # TODO: As soon as supported, change collection: A to collection: A[B] result = newTable[C, B]() - for item in collection: - result[index(item)] = item + {.noSideEffect.}: + for item in collection: + result[index(item)] = item proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,TableRef[A,B],A>`_ whether ## the key exists. ## @@ -858,7 +890,7 @@ proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = result = t[][key] proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key @@ -874,7 +906,7 @@ proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: sink B) = t[][key] = val proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,TableRef[A,B],A>`_ for use with the `in` @@ -893,7 +925,7 @@ proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = proc contains*[A, B](t: TableRef[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,TableRef[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert 'b' in a == true @@ -901,8 +933,8 @@ proc contains*[A, B](t: TableRef[A, B], key: A): bool = return hasKey[A, B](t, key) -proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. +proc hasKeyOrPut*[A, B](t: TableRef[A, B], key: A, val: B): bool = + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ @@ -922,8 +954,8 @@ proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -941,8 +973,8 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = getOrDefault(t[], key) proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key @@ -959,7 +991,7 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## Note that while the value returned is of type `var B`, @@ -994,8 +1026,20 @@ proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = doAssert t[25] == @[25, 35] t[].mgetOrPut(key, val) +proc mgetOrPut*[A, B](t: TableRef[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.newTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.newTable + + t[].mgetOrPut(key) + proc len*[A, B](t: TableRef[A, B]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert len(a) == 2 @@ -1004,7 +1048,7 @@ proc len*[A, B](t: TableRef[A, B]): int = proc add*[A, B](t: TableRef[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## @@ -1013,9 +1057,10 @@ proc add*[A, B](t: TableRef[A, B], key: A, val: sink B) {.deprecated: t[].add(key, val) proc del*[A, B](t: TableRef[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## - ## **If duplicate keys were added, this may need to be called multiple times.** + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. ## ## See also: ## * `pop proc<#pop,TableRef[A,B],A,B>`_ @@ -1030,12 +1075,13 @@ proc del*[A, B](t: TableRef[A, B], key: A) = t[].del(key) proc pop*[A, B](t: TableRef[A, B], key: A, val: var B): bool = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## - ## **If duplicate keys were added, this may need to be called multiple times.** + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. ## ## See also: ## * `del proc<#del,TableRef[A,B],A>`_ @@ -1074,13 +1120,13 @@ proc clear*[A, B](t: TableRef[A, B]) = clearImpl() proc `$`*[A, B](t: TableRef[A, B]): string = - ## The ``$`` operator for hash tables. Used internally when calling `echo` + ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: TableRef[A, B]): bool = - ## The ``==`` operator for hash tables. Returns ``true`` if either both tables - ## are ``nil``, or neither is ``nil`` and the content of both tables contains the + ## The `==` operator for hash tables. Returns `true` if either both tables + ## are `nil`, or neither is `nil` and the content of both tables contains the ## same key-value pairs. Insert order does not matter. runnableExamples: let @@ -1095,7 +1141,7 @@ proc `==`*[A, B](s, t: TableRef[A, B]): bool = iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ @@ -1104,7 +1150,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -1118,6 +1164,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## # value: [2, 4, 6, 8] ## # key: o ## # value: [1, 5, 7, 9] + ## ``` let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): @@ -1125,7 +1172,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. The values + ## Iterates over any `(key, value)` pair in the table `t`. The values ## can be modified. ## ## See also: @@ -1146,8 +1193,8 @@ iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: TableRef[A, B]): A = - ## Iterates over any key in the table ``t``. +iterator keys*[A, B](t: TableRef[A, B]): lent A = + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ @@ -1167,8 +1214,8 @@ iterator keys*[A, B](t: TableRef[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: TableRef[A, B]): B = - ## Iterates over any value in the table ``t``. +iterator values*[A, B](t: TableRef[A, B]): lent B = + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ @@ -1189,7 +1236,7 @@ iterator values*[A, B](t: TableRef[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: TableRef[A, B]): var B = - ## Iterates over any value in the table ``t``. The values can be modified. + ## Iterates over any value in the table `t`. The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ @@ -1300,10 +1347,11 @@ proc initOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTable[A, let a = initOrderedTable[int, string]() b = initOrderedTable[char, seq[int]]() + result = default(OrderedTable[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key @@ -1319,9 +1367,9 @@ proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) = putImpl(enlarge) proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = - ## Creates a new ordered hash table that contains the given ``pairs``. + ## Creates a new ordered hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `initOrderedTable proc<#initOrderedTable>`_ @@ -1335,10 +1383,10 @@ proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = result = initOrderedTable[A, B](pairs.len) for key, val in items(pairs): result[key] = val -proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B = - ## Retrieves the value at ``t[key]``. +proc `[]`*[A, B](t: OrderedTable[A, B], key: A): lent B = + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ whether ## the key exists. ## @@ -1360,9 +1408,9 @@ proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B = get(t, key) proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. The value can be modified. + ## Retrieves the value at `t[key]`. The value can be modified. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## ## See also: ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return @@ -1376,7 +1424,7 @@ proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B = get(t, key) proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,OrderedTable[A,B],A>`_ for use with the `in` @@ -1391,12 +1439,12 @@ proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false - var hc: Hash + var hc: Hash = default(Hash) result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert 'b' in a == true @@ -1405,7 +1453,7 @@ proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ @@ -1425,8 +1473,8 @@ proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -1440,12 +1488,12 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 - + result = default(B) getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key @@ -1458,11 +1506,11 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 - + result = default(B) getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## See also: @@ -1481,8 +1529,20 @@ proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) +proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.toOrderedTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.toOrderedTable + + mgetOrPutImpl(enlarge) + proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert len(a) == 2 @@ -1491,7 +1551,7 @@ proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = proc add*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## @@ -1500,7 +1560,7 @@ proc add*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) {.deprecated: addImpl(enlarge) proc del*[A, B](t: var OrderedTable[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## O(n) complexity. ## @@ -1533,9 +1593,9 @@ proc del*[A, B](t: var OrderedTable[A, B], key: A) = h = nxt proc pop*[A, B](t: var OrderedTable[A, B], key: A, val: var B): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## O(n) complexity. @@ -1579,15 +1639,15 @@ proc clear*[A, B](t: var OrderedTable[A, B]) = t.last = -1 proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int, - order = SortOrder.Ascending) = - ## Sorts ``t`` according to the function ``cmp``. + order = SortOrder.Ascending) {.effectsOf: cmp.} = + ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list ## that kept the insertion order, so insertion order is lost after this - ## call but key lookup and insertions remain possible after ``sort`` (in + ## call but key lookup and insertions remain possible after `sort` (in ## contrast to the `sort proc<#sort,CountTable[A]>`_ for count tables). runnableExamples: - import algorithm + import std/[algorithm] var a = initOrderedTable[char, int]() for i, c in "cab": a[c] = 10*i @@ -1638,12 +1698,12 @@ proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int, t.last = tail proc `$`*[A, B](t: OrderedTable[A, B]): string = - ## The ``$`` operator for ordered hash tables. Used internally when calling + ## The `$` operator for ordered hash tables. Used internally when calling ## `echo` on a table. dollarImpl() proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = - ## The ``==`` operator for ordered hash tables. Returns ``true`` if both the + ## The `==` operator for ordered hash tables. Returns `true` if both the ## content and the order are equal. runnableExamples: let @@ -1670,7 +1730,7 @@ proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` in insertion + ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. ## ## See also: @@ -1680,7 +1740,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -1694,6 +1754,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] + ## ``` let L = len(t) forAllOrderedPairs: @@ -1701,7 +1762,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` (must be + ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`) in insertion order. The values can be modified. ## ## See also: @@ -1722,8 +1783,8 @@ iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: OrderedTable[A, B]): A = - ## Iterates over any key in the table ``t`` in insertion order. +iterator keys*[A, B](t: OrderedTable[A, B]): lent A = + ## Iterates over any key in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ @@ -1743,8 +1804,8 @@ iterator keys*[A, B](t: OrderedTable[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: OrderedTable[A, B]): B = - ## Iterates over any value in the table ``t`` in insertion order. +iterator values*[A, B](t: OrderedTable[A, B]): lent B = + ## Iterates over any value in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ @@ -1764,7 +1825,7 @@ iterator values*[A, B](t: OrderedTable[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = - ## Iterates over any value in the table ``t`` (must be + ## Iterates over any value in the table `t` (must be ## declared as `var`) in insertion order. The values ## can be modified. ## @@ -1790,7 +1851,7 @@ iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = # --------------------------- OrderedTableRef ------------------------------- # --------------------------------------------------------------------------- -proc newOrderedTable*[A, B](initialSize = defaultInitialSize): <//>OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that is empty. ## ## See also: @@ -1803,12 +1864,13 @@ proc newOrderedTable*[A, B](initialSize = defaultInitialSize): <//>OrderedTableR a = newOrderedTable[int, string]() b = newOrderedTable[char, seq[int]]() new(result) - result[] = initOrderedTable[A, B](initialSize) + {.noSideEffect.}: + result[] = initOrderedTable[A, B](initialSize) -proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): <//>OrderedTableRef[A, B] = - ## Creates a new ordered ref hash table that contains the given ``pairs``. +proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = + ## Creates a new ordered ref hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `newOrderedTable proc<#newOrderedTable>`_ @@ -1820,13 +1882,14 @@ proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): <//>OrderedTableRef[A, B] assert b == {'a': 5, 'b': 9}.newOrderedTable result = newOrderedTable[A, B](pairs.len) - for key, val in items(pairs): result[key] = val + {.noSideEffect.}: + for key, val in items(pairs): result[key] = val proc `[]`*[A, B](t: OrderedTableRef[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ whether ## the key exists. ## @@ -1847,7 +1910,7 @@ proc `[]`*[A, B](t: OrderedTableRef[A, B], key: A): var B = result = t[][key] proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key @@ -1863,7 +1926,7 @@ proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) = t[][key] = val proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,OrderedTableRef[A,B],A>`_ for use with the `in` @@ -1882,7 +1945,7 @@ proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert 'b' in a == true @@ -1890,8 +1953,8 @@ proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = return hasKey[A, B](t, key) -proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. +proc hasKeyOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): bool = + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ @@ -1911,8 +1974,8 @@ proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = result = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -1930,8 +1993,8 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = getOrDefault(t[], key) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key @@ -1948,7 +2011,7 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## See also: @@ -1967,8 +2030,20 @@ proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = result = t[].mgetOrPut(key, val) +proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.toOrderedTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.toOrderedTable + + t[].mgetOrPut(key) + proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert len(a) == 2 @@ -1977,7 +2052,7 @@ proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## @@ -1986,7 +2061,7 @@ proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) {.deprecated: t[].add(key, val) proc del*[A, B](t: OrderedTableRef[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## See also: ## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table @@ -2000,9 +2075,9 @@ proc del*[A, B](t: OrderedTableRef[A, B], key: A) = t[].del(key) proc pop*[A, B](t: OrderedTableRef[A, B], key: A, val: var B): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: @@ -2036,15 +2111,15 @@ proc clear*[A, B](t: OrderedTableRef[A, B]) = clear(t[]) proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int, - order = SortOrder.Ascending) = - ## Sorts ``t`` according to the function ``cmp``. + order = SortOrder.Ascending) {.effectsOf: cmp.} = + ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list ## that kept the insertion order, so insertion order is lost after this - ## call but key lookup and insertions remain possible after ``sort`` (in + ## call but key lookup and insertions remain possible after `sort` (in ## contrast to the `sort proc<#sort,CountTableRef[A]>`_ for count tables). runnableExamples: - import algorithm + import std/[algorithm] var a = newOrderedTable[char, int]() for i, c in "cab": a[c] = 10*i @@ -2057,13 +2132,13 @@ proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int, t[].sort(cmp, order = order) proc `$`*[A, B](t: OrderedTableRef[A, B]): string = - ## The ``$`` operator for hash tables. Used internally when calling `echo` + ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = - ## The ``==`` operator for ordered hash tables. Returns true if either both - ## tables are ``nil``, or neither is ``nil`` and the content and the order of + ## The `==` operator for ordered hash tables. Returns true if either both + ## tables are `nil`, or neither is `nil` and the content and the order of ## both are equal. runnableExamples: let @@ -2078,7 +2153,7 @@ proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` in insertion + ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. ## ## See also: @@ -2088,7 +2163,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -2102,6 +2177,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] + ## ``` let L = len(t) forAllOrderedPairs: @@ -2109,7 +2185,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` in insertion + ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. The values can be modified. ## ## See also: @@ -2130,8 +2206,8 @@ iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: OrderedTableRef[A, B]): A = - ## Iterates over any key in the table ``t`` in insertion order. +iterator keys*[A, B](t: OrderedTableRef[A, B]): lent A = + ## Iterates over any key in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ @@ -2151,8 +2227,8 @@ iterator keys*[A, B](t: OrderedTableRef[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: OrderedTableRef[A, B]): B = - ## Iterates over any value in the table ``t`` in insertion order. +iterator values*[A, B](t: OrderedTableRef[A, B]): lent B = + ## Iterates over any value in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ @@ -2172,7 +2248,7 @@ iterator values*[A, B](t: OrderedTableRef[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B = - ## Iterates over any value in the table ``t`` in insertion order. The values + ## Iterates over any value in the table `t` in insertion order. The values ## can be modified. ## ## See also: @@ -2262,22 +2338,22 @@ proc initCountTable*[A](initialSize = defaultInitialSize): CountTable[A] = ## * `toCountTable proc<#toCountTable,openArray[A]>`_ ## * `newCountTable proc<#newCountTable>`_ for creating a ## `CountTableRef` + result = default(CountTable[A]) initImpl(result, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = - ## Creates a new count table with every member of a container ``keys`` + ## Creates a new count table with every member of a container `keys` ## having a count of how many times it occurs in that container. result = initCountTable[A](keys.len) for key in items(keys): result.inc(key) proc `[]`*[A](t: CountTable[A], key: A): int = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise ``0`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise `0` is returned. ## ## See also: ## * `getOrDefault<#getOrDefault,CountTable[A],A,int>`_ to return ## a custom value if the key doesn't exist - ## * `mget proc<#mget,CountTable[A],A>`_ ## * `[]= proc<#[]%3D,CountTable[A],A,int>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,CountTable[A],A>`_ for checking if a key @@ -2290,7 +2366,7 @@ template cntCellEmpty(i) = t.data[i].val == 0 template cntCellHash(i) = hash(t.data[i].key) proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key @@ -2308,7 +2384,7 @@ proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = insertImpl() proc inc*[A](t: var CountTable[A], key: A, val = 1) = - ## Increments ``t[key]`` by ``val`` (default: 1). + ## Increments `t[key]` by `val` (default: 1). runnableExamples: var a = toCountTable("aab") a.inc('a') @@ -2326,11 +2402,11 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) = insertImpl() proc len*[A](t: CountTable[A]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. result = t.counter proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the smallest `val`. Efficiency: O(n) ## ## See also: ## * `largest proc<#largest,CountTable[A]>`_ @@ -2343,7 +2419,7 @@ proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = result.val = t.data[minIdx].val proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) ## ## See also: ## * `smallest proc<#smallest,CountTable[A]>`_ @@ -2355,7 +2431,7 @@ proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = result.val = t.data[maxIdx].val proc hasKey*[A](t: CountTable[A], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,CountTable[A],A>`_ for use with the `in` @@ -2368,12 +2444,12 @@ proc hasKey*[A](t: CountTable[A], key: A): bool = proc contains*[A](t: CountTable[A], key: A): bool = ## Alias of `hasKey proc<#hasKey,CountTable[A],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. return hasKey[A](t, key) proc getOrDefault*[A](t: CountTable[A], key: A; default: int = 0): int = - ## Retrieves the value at ``t[key]`` if``key`` is in ``t``. Otherwise, the - ## integer value of ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## integer value of `default` is returned. ## ## See also: ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key @@ -2382,7 +2458,7 @@ proc getOrDefault*[A](t: CountTable[A], key: A; default: int = 0): int = ctget(t, key, default) proc del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} = - ## Deletes ``key`` from table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from table `t`. Does nothing if the key does not exist. ## ## See also: ## * `pop proc<#pop,CountTable[A],A,int>`_ @@ -2399,9 +2475,9 @@ proc del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} = delImplNoHCode(cntMakeEmpty, cntCellEmpty, cntCellHash) proc pop*[A](t: var CountTable[A], key: A, val: var int): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: @@ -2438,13 +2514,13 @@ proc sort*[A](t: var CountTable[A], order = SortOrder.Descending) = ## Sorts the count table so that, by default, the entry with the ## highest counter comes first. ## - ## **WARNING:** This is destructive! Once sorted, you must not modify ``t`` afterwards! + ## .. warning:: This is destructive! Once sorted, you must not modify `t` afterwards! ## ## You can use the iterators `pairs<#pairs.i,CountTable[A]>`_, ## `keys<#keys.i,CountTable[A]>`_, and `values<#values.i,CountTable[A]>`_ - ## to iterate over ``t`` in the sorted order. + ## to iterate over `t` in the sorted order. runnableExamples: - import algorithm, sequtils + import std/[algorithm, sequtils] var a = toCountTable("abracadabra") doAssert a == "aaaaabbrrcd".toCountTable a.sort() @@ -2482,18 +2558,18 @@ when (NimMajor, NimMinor) <= (1, 0): result.inc(key, value) proc `$`*[A](t: CountTable[A]): string = - ## The ``$`` operator for count tables. Used internally when calling `echo` + ## The `$` operator for count tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A](s, t: CountTable[A]): bool = - ## The ``==`` operator for count tables. Returns ``true`` if both tables + ## The `==` operator for count tables. Returns `true` if both tables ## contain the same keys with the same count. Insert order does not matter. equalsImpl(s, t) iterator pairs*[A](t: CountTable[A]): (A, int) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTable[A]>`_ @@ -2502,7 +2578,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = toCountTable("abracadabra") ## ## for k, v in pairs(a): @@ -2519,6 +2595,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = ## # value: 1 ## # key: r ## # value: 2 + ## ``` let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: @@ -2526,7 +2603,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A](t: var CountTable[A]): (A, var int) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` (must be + ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -2544,8 +2621,8 @@ iterator mpairs*[A](t: var CountTable[A]): (A, var int) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A](t: CountTable[A]): A = - ## Iterates over any key in the table ``t``. +iterator keys*[A](t: CountTable[A]): lent A = + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ @@ -2563,7 +2640,7 @@ iterator keys*[A](t: CountTable[A]): A = assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A](t: CountTable[A]): int = - ## Iterates over any value in the table ``t``. + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ @@ -2581,7 +2658,7 @@ iterator values*[A](t: CountTable[A]): int = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A](t: var CountTable[A]): var int = - ## Iterates over any value in the table ``t`` (must be + ## Iterates over any value in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -2611,7 +2688,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = proc inc*[A](t: CountTableRef[A], key: A, val = 1) -proc newCountTable*[A](initialSize = defaultInitialSize): <//>CountTableRef[A] = +proc newCountTable*[A](initialSize = defaultInitialSize): CountTableRef[A] = ## Creates a new ref count table that is empty. ## ## See also: @@ -2620,17 +2697,19 @@ proc newCountTable*[A](initialSize = defaultInitialSize): <//>CountTableRef[A] = ## * `initCountTable proc<#initCountTable>`_ for creating a ## `CountTable` new(result) - result[] = initCountTable[A](initialSize) + {.noSideEffect.}: + result[] = initCountTable[A](initialSize) -proc newCountTable*[A](keys: openArray[A]): <//>CountTableRef[A] = - ## Creates a new ref count table with every member of a container ``keys`` +proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = + ## Creates a new ref count table with every member of a container `keys` ## having a count of how many times it occurs in that container. result = newCountTable[A](keys.len) - for key in items(keys): result.inc(key) + {.noSideEffect.}: + for key in items(keys): result.inc(key) proc `[]`*[A](t: CountTableRef[A], key: A): int = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise ``0`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise `0` is returned. ## ## See also: ## * `getOrDefault<#getOrDefault,CountTableRef[A],A,int>`_ to return @@ -2643,40 +2722,42 @@ proc `[]`*[A](t: CountTableRef[A], key: A): int = result = t[][key] proc `[]=`*[A](t: CountTableRef[A], key: A, val: int) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key ## * `inc proc<#inc,CountTableRef[A],A,int>`_ for incrementing a ## value of a key assert val > 0 - t[][key] = val + {.noSideEffect.}: + t[][key] = val proc inc*[A](t: CountTableRef[A], key: A, val = 1) = - ## Increments ``t[key]`` by ``val`` (default: 1). + ## Increments `t[key]` by `val` (default: 1). runnableExamples: var a = newCountTable("aab") a.inc('a') a.inc('b', 10) doAssert a == newCountTable("aaabbbbbbbbbbb") - t[].inc(key, val) + {.noSideEffect.}: + t[].inc(key, val) proc smallest*[A](t: CountTableRef[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the smallest `val`. Efficiency: O(n) ## ## See also: ## * `largest proc<#largest,CountTableRef[A]>`_ t[].smallest proc largest*[A](t: CountTableRef[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) ## ## See also: ## * `smallest proc<#smallest,CountTable[A]>`_ t[].largest proc hasKey*[A](t: CountTableRef[A], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,CountTableRef[A],A>`_ for use with the `in` @@ -2688,12 +2769,12 @@ proc hasKey*[A](t: CountTableRef[A], key: A): bool = proc contains*[A](t: CountTableRef[A], key: A): bool = ## Alias of `hasKey proc<#hasKey,CountTableRef[A],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. return hasKey[A](t, key) proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int = - ## Retrieves the value at ``t[key]`` if``key`` is in ``t``. Otherwise, the - ## integer value of ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## integer value of `default` is returned. ## ## See also: ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key @@ -2702,11 +2783,11 @@ proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int = result = t[].getOrDefault(key, default) proc len*[A](t: CountTableRef[A]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. result = t.counter proc del*[A](t: CountTableRef[A], key: A) {.since: (1, 1).} = - ## Deletes ``key`` from table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from table `t`. Does nothing if the key does not exist. ## ## See also: ## * `pop proc<#pop,CountTableRef[A],A,int>`_ @@ -2714,9 +2795,9 @@ proc del*[A](t: CountTableRef[A], key: A) {.since: (1, 1).} = del(t[], key) proc pop*[A](t: CountTableRef[A], key: A, val: var int): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: @@ -2740,7 +2821,7 @@ proc sort*[A](t: CountTableRef[A], order = SortOrder.Descending) = ## ## You can use the iterators `pairs<#pairs.i,CountTableRef[A]>`_, ## `keys<#keys.i,CountTableRef[A]>`_, and `values<#values.i,CountTableRef[A]>`_ - ## to iterate over ``t`` in the sorted order. + ## to iterate over `t` in the sorted order. t[].sort(order = order) proc merge*[A](s, t: CountTableRef[A]) = @@ -2755,13 +2836,13 @@ proc merge*[A](s, t: CountTableRef[A]) = s[].merge(t[]) proc `$`*[A](t: CountTableRef[A]): string = - ## The ``$`` operator for count tables. Used internally when calling `echo` + ## The `$` operator for count tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A](s, t: CountTableRef[A]): bool = - ## The ``==`` operator for count tables. Returns ``true`` if either both tables - ## are ``nil``, or neither is ``nil`` and both contain the same keys with the same + ## The `==` operator for count tables. Returns `true` if either both tables + ## are `nil`, or neither is `nil` and both contain the same keys with the same ## count. Insert order does not matter. if isNil(s): result = isNil(t) elif isNil(t): result = false @@ -2769,7 +2850,7 @@ proc `==`*[A](s, t: CountTableRef[A]): bool = iterator pairs*[A](t: CountTableRef[A]): (A, int) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ @@ -2778,7 +2859,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = newCountTable("abracadabra") ## ## for k, v in pairs(a): @@ -2795,6 +2876,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = ## # value: 1 ## # key: r ## # value: 2 + ## ``` let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: @@ -2802,7 +2884,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. The values can + ## Iterates over any `(key, value)` pair in the table `t`. The values can ## be modified. ## ## See also: @@ -2821,7 +2903,7 @@ iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = assert(len(t) == L, "table modified while iterating over it") iterator keys*[A](t: CountTableRef[A]): A = - ## Iterates over any key in the table ``t``. + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ @@ -2839,7 +2921,7 @@ iterator keys*[A](t: CountTableRef[A]): A = assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A](t: CountTableRef[A]): int = - ## Iterates over any value in the table ``t``. + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTableRef[A]>`_ @@ -2857,7 +2939,7 @@ iterator values*[A](t: CountTableRef[A]): int = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A](t: CountTableRef[A]): var int = - ## Iterates over any value in the table ``t``. The values can be modified. + ## Iterates over any value in the table `t`. The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ @@ -2873,3 +2955,18 @@ iterator mvalues*[A](t: CountTableRef[A]): var int = if t.data[h].val != 0: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") + +proc hash*[K,V](s: Table[K,V]): Hash = + for p in pairs(s): + result = result xor hash(p) + result = !$result + +proc hash*[K,V](s: OrderedTable[K,V]): Hash = + for p in pairs(s): + result = result !& hash(p) + result = !$result + +proc hash*[V](s: CountTable[V]): Hash = + for p in pairs(s): + result = result xor hash(p) + result = !$result |