diff options
Diffstat (limited to 'lib/pure/collections')
| -rw-r--r-- | lib/pure/collections/critbits.nim | 19 | ||||
| -rw-r--r-- | lib/pure/collections/deques.nim | 190 | ||||
| -rw-r--r-- | lib/pure/collections/hashcommon.nim | 22 | ||||
| -rw-r--r-- | lib/pure/collections/heapqueue.nim | 17 | ||||
| -rw-r--r-- | lib/pure/collections/intsets.nim | 2 | ||||
| -rw-r--r-- | lib/pure/collections/lists.nim | 384 | ||||
| -rw-r--r-- | lib/pure/collections/sequtils.nim | 147 | ||||
| -rw-r--r-- | lib/pure/collections/setimpl.nim | 5 | ||||
| -rw-r--r-- | lib/pure/collections/sets.nim | 55 | ||||
| -rw-r--r-- | lib/pure/collections/sharedlist.nim | 11 | ||||
| -rw-r--r-- | lib/pure/collections/sharedtables.nim | 93 | ||||
| -rw-r--r-- | lib/pure/collections/tableimpl.nim | 51 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 246 |
13 files changed, 769 insertions, 473 deletions
diff --git a/lib/pure/collections/critbits.nim b/lib/pure/collections/critbits.nim index e12984995..24257dacb 100644 --- a/lib/pure/collections/critbits.nim +++ b/lib/pure/collections/critbits.nim @@ -36,6 +36,9 @@ runnableExamples: import std/private/since +when defined(nimPreviewSlimSystem): + import std/assertions + type NodeObj[T] {.acyclic.} = object byte: int ## byte index of the difference @@ -197,7 +200,7 @@ 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 = +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. ## @@ -270,7 +273,7 @@ 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:** @@ -284,7 +287,7 @@ 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) = +proc `[]=`*[T](c: var CritBitTree[T], key: string, val: sink T) = ## Alias for `incl <#incl,CritBitTree[T],string,T>`_. ## ## **See also:** @@ -300,7 +303,7 @@ template get[T](c: CritBitTree[T], key: string): T = n.val -func `[]`*[T](c: CritBitTree[T], key: string): T {.inline.} = +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. @@ -342,7 +345,7 @@ iterator keys*[T](c: CritBitTree[T]): string = 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. ## @@ -415,7 +418,7 @@ iterator keysWithPrefix*[T](c: CritBitTree[T], prefix: string): string = let top = allprefixedAux(c, prefix) for x in leaves(top): yield x.key -iterator valuesWithPrefix*[T](c: CritBitTree[T], prefix: string): T = +iterator valuesWithPrefix*[T](c: CritBitTree[T], prefix: string): lent T = ## Yields all values of `c` starting with `prefix` of the ## corresponding keys. ## @@ -518,7 +521,7 @@ func commonPrefixLen*[T](c: CritBitTree[T]): int {.inline, since((1, 3)).} = else: c.root.byte else: 0 -proc toCritBitTree*[T](pairs: openArray[(string, T)]): CritBitTree[T] {.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] @@ -526,7 +529,7 @@ proc toCritBitTree*[T](pairs: openArray[(string, T)]): CritBitTree[T] {.since: ( for item in pairs: result.incl item[0], item[1] -proc toCritBitTree*(items: openArray[string]): 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] diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim index c8bbb1cc6..d2b0099f2 100644 --- a/lib/pure/collections/deques.nim +++ b/lib/pure/collections/deques.nim @@ -10,8 +10,9 @@ ## An implementation of a `deque`:idx: (double-ended queue). ## The underlying implementation uses a `seq`. ## -## Note that none of the procs that get an individual value from the deque should be used -## on an empty deque. +## .. 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 then the procs may return garbage or crash the program. @@ -46,11 +47,10 @@ runnableExamples: ## See also ## ======== ## * `lists module <lists.html>`_ for singly and doubly linked lists and rings -## * `channels module <channels_builtin.html>`_ for inter-thread communication import std/private/since -import math +import std/[assertions, hashes, math] type Deque*[T] = object @@ -59,20 +59,28 @@ type ## 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 = defaultInitialSize): Deque[T] = ## Creates a new empty deque. @@ -86,41 +94,27 @@ proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] = ## * `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: - 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 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.} = +proc `[]`*[T](deq: Deque[T], i: Natural): lent T {.inline.} = ## Accesses the `i`-th element of `deq`. runnableExamples: let a = [10, 20, 30, 40, 50].toDeque @@ -129,7 +123,7 @@ proc `[]`*[T](deq: Deque[T], i: Natural): T {.inline.} = 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 returns a mutable @@ -140,9 +134,9 @@ proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} = 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.} = +proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} = ## Sets the `i`-th element of `deq` to `val`. runnableExamples: var a = [10, 20, 30, 40, 50].toDeque @@ -152,9 +146,9 @@ proc `[]=`*[T](deq: var Deque[T], i: Natural, val: T) {.inline.} = 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.} = +proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): lent T {.inline.} = ## Accesses the backwards indexed `i`-th element. ## ## `deq[^1]` is the last element. @@ -180,7 +174,7 @@ proc `[]`*[T](deq: var Deque[T], i: BackwardsIndex): var T {.inline.} = xBoundsCheck(deq, deq.len - int(i)) return deq[deq.len - int(i)] -proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: T) {.inline.} = +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. @@ -194,27 +188,25 @@ 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,Deque[T]>`_ + ## * `mitems iterator <#mitems.i,Deque[T]>`_ runnableExamples: from std/sequtils import toSeq let a = [10, 20, 30, 40, 50].toDeque assert toSeq(a.items) == @[10, 20, 30, 40, 50] - 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 mitems*[T](deq: var Deque[T]): var T = ## Yields every element of `deq`, which can be modified. ## ## **See also:** - ## * `items iterator <#items,Deque[T]>`_ + ## * `items iterator <#items.i,Deque[T]>`_ runnableExamples: var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" @@ -222,10 +214,8 @@ iterator mitems*[T](deq: var Deque[T]): var T = 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)`-pair of `deq`. @@ -235,10 +225,8 @@ iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] = let a = [10, 20, 30].toDeque assert toSeq(a.pairs) == @[(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 + 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. @@ -257,24 +245,24 @@ proc contains*[T](deq: Deque[T], item: T): bool {.inline.} = 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) = +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>`_ + ## * `addLast proc <#addLast,Deque[T],sinkT>`_ runnableExamples: var a = initDeque[int]() for i in 1 .. 5: @@ -282,15 +270,14 @@ proc addFirst*[T](deq: var Deque[T], item: T) = 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) = +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>`_ + ## * `addFirst proc <#addFirst,Deque[T],sinkT>`_ runnableExamples: var a = initDeque[int]() for i in 1 .. 5: @@ -298,11 +285,24 @@ proc addLast*[T](deq: var Deque[T], item: T) = 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 peekFirst*[T](deq: Deque[T]): T {.inline.} = +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]): lent T {.inline.} = ## Returns the first element of `deq`, but does not remove it from the deque. ## ## **See also:** @@ -315,9 +315,9 @@ proc peekFirst*[T](deq: Deque[T]): T {.inline.} = 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:** @@ -345,7 +345,7 @@ proc peekFirst*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} = 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 a mutable reference to the last element of `deq`, @@ -378,10 +378,8 @@ proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} = 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`. @@ -396,10 +394,8 @@ proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} = 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. @@ -413,7 +409,6 @@ proc clear*[T](deq: var Deque[T]) {.inline.} = 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) = @@ -433,19 +428,17 @@ proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) = a.shrink(fromFirst = 2, fromLast = 1) 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. @@ -458,3 +451,30 @@ proc `$`*[T](deq: Deque[T]): string = 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 030446176..17785c8c7 100644 --- a/lib/pure/collections/hashcommon.nim +++ b/lib/pure/collections/hashcommon.nim @@ -10,6 +10,11 @@ # An `include` file which contains common code for # hash sets and tables. +when defined(nimPreviewSlimSystem): + import std/assertions + +import std / outparams + const growthFactor = 2 @@ -33,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 @@ -63,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 @@ -74,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 89e532951..96f9b4430 100644 --- a/lib/pure/collections/heapqueue.nim +++ b/lib/pure/collections/heapqueue.nim @@ -47,6 +47,9 @@ runnableExamples: 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] @@ -59,7 +62,7 @@ proc initHeapQueue*[T](): HeapQueue[T] = ## ## **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`. @@ -73,6 +76,13 @@ proc `[]`*[T](heap: HeapQueue[T], i: Natural): lent T {.inline.} = ## Accesses the i-th element of `heap`. heap.data[i] +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 heapCmp[T](x, y: T): bool {.inline.} = x < y proc siftup[T](heap: var HeapQueue[T], startpos, p: int) = @@ -178,6 +188,11 @@ proc find*[T](heap: HeapQueue[T], x: T): int {.since: (1, 3).} = 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: diff --git a/lib/pure/collections/intsets.nim b/lib/pure/collections/intsets.nim index 05e5addcc..765a23e97 100644 --- a/lib/pure/collections/intsets.nim +++ b/lib/pure/collections/intsets.nim @@ -8,7 +8,7 @@ # ## Specialization of the generic `packedsets module <packedsets.html>`_ -## for ordinal sparse sets. +## (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 c1fcb0743..6b88747ef 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -19,15 +19,15 @@ ## ## ## Lists runnableExamples: - var l = initDoublyLinkedList[int]() + var list = initDoublyLinkedList[int]() let a = newDoublyLinkedNode[int](3) b = newDoublyLinkedNode[int](7) c = newDoublyLinkedNode[int](9) - l.add(a) - l.add(b) - l.prepend(c) + list.add(a) + list.add(b) + list.prepend(c) assert a.next == b assert a.prev == c @@ -38,15 +38,15 @@ runnableExamples: ## ## Rings runnableExamples: - var l = initSinglyLinkedRing[int]() + var ring = initSinglyLinkedRing[int]() let a = newSinglyLinkedNode[int](3) b = newSinglyLinkedNode[int](7) c = newSinglyLinkedNode[int](9) - l.add(a) - l.add(b) - l.prepend(c) + ring.add(a) + ring.add(b) + ring.prepend(c) assert c.next == a assert a.next == b @@ -56,19 +56,18 @@ runnableExamples: ## # 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(nimHasCursor): - {.pragma: cursor.} +when defined(nimPreviewSlimSystem): + import std/assertions type DoublyLinkedNodeObj*[T] = object ## A node of a doubly linked list. ## ## It consists of a `value` field, and pointers to `next` and `prev`. - next*: <//>(DoublyLinkedNode[T]) + next*: DoublyLinkedNode[T] prev* {.cursor.}: DoublyLinkedNode[T] value*: T DoublyLinkedNode*[T] = ref DoublyLinkedNodeObj[T] @@ -77,23 +76,23 @@ type ## A node of a singly linked list. ## ## It consists of a `value` field, and a pointer to `next`. - next*: <//>(SinglyLinkedNode[T]) + next*: SinglyLinkedNode[T] value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] SinglyLinkedList*[T] = object ## A singly linked list. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] DoublyLinkedList*[T] = object ## A doubly linked list. - head*: <//>(DoublyLinkedNode[T]) + head*: DoublyLinkedNode[T] tail* {.cursor.}: DoublyLinkedNode[T] SinglyLinkedRing*[T] = object ## A singly linked ring. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] DoublyLinkedRing*[T] = object @@ -148,7 +147,7 @@ proc initDoublyLinkedRing*[T](): DoublyLinkedRing[T] = 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: let n = newDoublyLinkedNode[int](5) @@ -157,7 +156,7 @@ proc newDoublyLinkedNode*[T](value: T): <//>(DoublyLinkedNode[T]) = 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: let n = newSinglyLinkedNode[int](5) @@ -166,44 +165,22 @@ proc newSinglyLinkedNode*[T](value: T): <//>(SinglyLinkedNode[T]) = new(result) result.value = value -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 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) - template itemsListImpl() {.dirty.} = - var it = list.head + var it {.cursor.} = L.head while it != nil: yield it.value it = it.next template itemsRingImpl() {.dirty.} = - var it = ring.head + var it {.cursor.} = L.head if it != nil: while true: yield it.value it = it.next - if it == ring.head: break + if it == L.head: break -iterator items*[T](list: SomeLinkedList[T]): T = - ## Yields every value of `list`. +iterator items*[T](L: SomeLinkedList[T]): T = + ## Yields every value of `L`. ## ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ @@ -218,8 +195,8 @@ iterator items*[T](list: SomeLinkedList[T]): T = itemsListImpl() -iterator items*[T](ring: SomeLinkedRing[T]): T = - ## Yields every value of `ring`. +iterator items*[T](L: SomeLinkedRing[T]): T = + ## Yields every value of `L`. ## ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ @@ -234,8 +211,8 @@ iterator items*[T](ring: SomeLinkedRing[T]): T = itemsRingImpl() -iterator mitems*[T](list: var SomeLinkedList[T]): var T = - ## Yields every value of `list` so that you can modify it. +iterator mitems*[T](L: var SomeLinkedList[T]): var T = + ## Yields every value of `L` so that you can modify it. ## ## **See also:** ## * `items iterator <#items.i,SomeLinkedList[T]>`_ @@ -251,8 +228,8 @@ iterator mitems*[T](list: var SomeLinkedList[T]): var T = itemsListImpl() -iterator mitems*[T](ring: var SomeLinkedRing[T]): var T = - ## Yields every value of `ring` so that you can modify it. +iterator mitems*[T](L: var SomeLinkedRing[T]): var T = + ## Yields every value of `L` so that you can modify it. ## ## **See also:** ## * `items iterator <#items.i,SomeLinkedRing[T]>`_ @@ -268,7 +245,7 @@ iterator mitems*[T](ring: var SomeLinkedRing[T]): var T = itemsRingImpl() -iterator nodes*[T](list: SomeLinkedList[T]): SomeLinkedNode[T] = +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. ## @@ -287,13 +264,13 @@ iterator nodes*[T](list: SomeLinkedList[T]): SomeLinkedNode[T] = x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = list.head + var it {.cursor.} = L.head while it != nil: let nxt = it.next yield it it = nxt -iterator nodes*[T](ring: SomeLinkedRing[T]): SomeLinkedNode[T] = +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. ## @@ -312,27 +289,27 @@ iterator nodes*[T](ring: SomeLinkedRing[T]): SomeLinkedNode[T] = x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = ring.head + var it {.cursor.} = L.head if it != nil: while true: let nxt = it.next yield it it = nxt - if it == ring.head: break + if it == L.head: break -proc `$`*[T](l: SomeLinkedCollection[T]): string = +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): + for x in nodes(L): if result.len > 1: result.add(", ") result.addQuoted(x.value) result.add("]") -proc find*[T](l: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = +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. ## @@ -343,10 +320,10 @@ proc find*[T](l: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = assert a.find(9).value == 9 assert a.find(1) == nil - for x in nodes(l): + for x in nodes(L): if x.value == value: return x -proc contains*[T](l: SomeLinkedCollection[T], value: T): bool {.inline.} = +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. This allows the usage of the `in` and `notin` ## operators. @@ -360,7 +337,7 @@ proc contains*[T](l: SomeLinkedCollection[T], value: T): bool {.inline.} = assert(not a.contains(1)) assert 2 notin a - result = find(l, value) != nil + result = find(L, value) != nil proc prepend*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = ## Prepends a shallow copy of `b` to the beginning of `a`. @@ -407,12 +384,10 @@ proc prependMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = assert s == [0, 1, 0, 1, 0, 1] b.addMoved(a) - when defined(js): # XXX: swap broken in js; bug #16771 - (b, a) = (a, b) - else: swap a, b + swap a, b -proc add*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = - ## Appends (adds to the end) a node `n` to `list`. Efficiency: O(1). +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:** ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value @@ -426,14 +401,14 @@ proc add*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = assert a.contains(9) n.next = nil - if list.tail != nil: - assert(list.tail.next == nil) - list.tail.next = n - list.tail = n - if list.head == nil: list.head = n + if L.tail != nil: + assert(L.tail.next == nil) + L.tail.next = n + L.tail = n + if L.head == nil: L.head = n -proc add*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = - ## Appends (adds to the end) a value to `list`. Efficiency: O(1). +proc add*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value @@ -446,11 +421,11 @@ proc add*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = a.add(8) assert a.contains(9) - add(list, newSinglyLinkedNode(value)) + add(L, newSinglyLinkedNode(value)) -proc prepend*[T](list: var SinglyLinkedList[T], +proc prepend*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = - ## Prepends (adds to the beginning) a node to `list`. Efficiency: O(1). + ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ @@ -463,12 +438,12 @@ proc prepend*[T](list: var SinglyLinkedList[T], a.prepend(n) assert a.contains(9) - n.next = list.head - list.head = n - if list.tail == nil: list.tail = n + n.next = L.head + L.head = n + if L.tail == nil: L.tail = n -proc prepend*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = - ## Prepends (adds to the beginning) a node to `list`. Efficiency: O(1). +proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = + ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ @@ -482,7 +457,7 @@ proc prepend*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = a.prepend(8) assert a.contains(9) - prepend(list, newSinglyLinkedNode(value)) + prepend(L, newSinglyLinkedNode(value)) func copy*[T](a: SinglyLinkedList[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a shallow copy of `a`. @@ -531,17 +506,18 @@ proc addMoved*[T](a, b: var SinglyLinkedList[T]) {.since: (1, 5, 1).} = 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 add*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## Appends (adds to the end) a node `n` to `list`. Efficiency: O(1). +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:** ## * `add proc <#add,DoublyLinkedList[T],T>`_ for appending a value @@ -557,15 +533,15 @@ proc add*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = assert a.contains(9) n.next = nil - n.prev = list.tail - if list.tail != nil: - assert(list.tail.next == nil) - list.tail.next = n - list.tail = n - if list.head == nil: list.head = n + n.prev = L.tail + if L.tail != nil: + assert(L.tail.next == nil) + L.tail.next = n + L.tail = n + if L.head == nil: L.head = n -proc add*[T](list: var DoublyLinkedList[T], value: T) = - ## Appends (adds to the end) a value to `list`. Efficiency: O(1). +proc add*[T](L: var DoublyLinkedList[T], value: T) = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ @@ -581,10 +557,10 @@ proc add*[T](list: var DoublyLinkedList[T], value: T) = a.add(8) assert a.contains(9) - add(list, newDoublyLinkedNode(value)) + add(L, newDoublyLinkedNode(value)) -proc prepend*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## Prepends (adds to the beginning) a node `n` to `list`. Efficiency: O(1). +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:** ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ @@ -600,15 +576,15 @@ proc prepend*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = assert a.contains(9) n.prev = nil - n.next = list.head - if list.head != nil: - assert(list.head.prev == nil) - list.head.prev = n - list.head = n - if list.tail == nil: list.tail = n + n.next = L.head + if L.head != nil: + assert(L.head.prev == nil) + L.head.prev = n + L.head = n + if L.tail == nil: L.tail = n -proc prepend*[T](list: var DoublyLinkedList[T], value: T) = - ## Prepends (adds to the beginning) a value to `list`. Efficiency: O(1). +proc prepend*[T](L: var DoublyLinkedList[T], value: T) = + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ @@ -624,7 +600,7 @@ proc prepend*[T](list: var DoublyLinkedList[T], value: T) = a.prepend(8) assert a.contains(9) - prepend(list, newDoublyLinkedNode(value)) + prepend(L, newDoublyLinkedNode(value)) func copy*[T](a: DoublyLinkedList[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a shallow copy of `a`. @@ -675,12 +651,12 @@ proc addMoved*[T](a, b: var DoublyLinkedList[T]) {.since: (1, 5, 1).} = 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 @@ -705,9 +681,9 @@ proc add*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = var tmp = b.copy a.addMoved(tmp) -proc remove*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]): bool {.discardable.} = - ## Removes a node `n` from `list`. - ## Returns `true` if `n` was found in `list`. +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. @@ -728,22 +704,24 @@ proc remove*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]): bool {.d ai assert s == [2, 2, 2, 2] - if n == list.head: - list.head = n.next - if list.tail.next == n: - list.tail.next = list.head # restore cycle + if n == L.head: + L.head = n.next + if L.tail.next == n: + L.tail.next = L.head # restore cycle else: - var prev = list.head + 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](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## Removes a node `n` from `list`. Efficiency: O(1). - ## This function assumes, for the sake of efficiency, that `n` is contained in `list`, +proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = + ## Removes a node `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. ## When the list is cyclic, the cycle is preserved after removal. runnableExamples: @@ -763,15 +741,15 @@ proc remove*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ai assert s == [2, 2, 2, 2] - if n == list.tail: list.tail = n.prev - if n == list.head: list.head = n.next + if n == L.tail: L.tail = n.prev + if n == L.head: L.head = n.next if n.next != nil: n.next.prev = n.prev if n.prev != nil: n.prev.next = n.next -proc add*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = - ## Appends (adds to the end) a node `n` to `ring`. Efficiency: O(1). +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:** ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value @@ -784,17 +762,17 @@ proc add*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = a.add(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - assert(ring.tail != nil) - ring.tail.next = n + if L.head != nil: + n.next = L.head + assert(L.tail != nil) + L.tail.next = n else: n.next = n - ring.head = n - ring.tail = n + L.head = n + L.tail = n -proc add*[T](ring: var SinglyLinkedRing[T], value: T) = - ## Appends (adds to the end) a value to `ring`. Efficiency: O(1). +proc add*[T](L: var SinglyLinkedRing[T], value: T) = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ @@ -808,10 +786,10 @@ proc add*[T](ring: var SinglyLinkedRing[T], value: T) = a.add(8) assert a.contains(9) - add(ring, newSinglyLinkedNode(value)) + add(L, newSinglyLinkedNode(value)) -proc prepend*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = - ## Prepends (adds to the beginning) a node `n` to `ring`. Efficiency: O(1). +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:** ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ @@ -824,17 +802,17 @@ proc prepend*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = a.prepend(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - assert(ring.tail != nil) - ring.tail.next = n + if L.head != nil: + n.next = L.head + assert(L.tail != nil) + L.tail.next = n else: n.next = n - ring.tail = n - ring.head = n + L.tail = n + L.head = n -proc prepend*[T](ring: var SinglyLinkedRing[T], value: T) = - ## Prepends (adds to the beginning) a value to `ring`. Efficiency: O(1). +proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ @@ -848,12 +826,12 @@ proc prepend*[T](ring: var SinglyLinkedRing[T], value: T) = a.prepend(8) assert a.contains(9) - prepend(ring, newSinglyLinkedNode(value)) + prepend(L, newSinglyLinkedNode(value)) -proc add*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## Appends (adds to the end) a node `n` to `ring`. Efficiency: O(1). +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:** ## * `add proc <#add,DoublyLinkedRing[T],T>`_ for appending a value @@ -868,18 +846,18 @@ proc add*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = a.add(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - n.prev = ring.head.prev - ring.head.prev.next = n - ring.head.prev = n + if L.head != nil: + n.next = L.head + n.prev = L.head.prev + L.head.prev.next = n + L.head.prev = n else: n.prev = n n.next = n - ring.head = n + L.head = n -proc add*[T](ring: var DoublyLinkedRing[T], value: T) = - ## Appends (adds to the end) a value to `ring`. Efficiency: O(1). +proc add*[T](L: var DoublyLinkedRing[T], value: T) = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ @@ -895,10 +873,10 @@ proc add*[T](ring: var DoublyLinkedRing[T], value: T) = a.add(8) assert a.contains(9) - add(ring, newDoublyLinkedNode(value)) + add(L, newDoublyLinkedNode(value)) -proc prepend*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## Prepends (adds to the beginning) a node `n` to `ring`. Efficiency: O(1). +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:** ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ @@ -913,18 +891,18 @@ proc prepend*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = a.prepend(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - n.prev = ring.head.prev - ring.head.prev.next = n - ring.head.prev = n + if L.head != nil: + n.next = L.head + n.prev = L.head.prev + L.head.prev.next = n + L.head.prev = n else: n.prev = n n.next = n - ring.head = n + L.head = n -proc prepend*[T](ring: var DoublyLinkedRing[T], value: T) = - ## Prepends (adds to the beginning) a value to `ring`. Efficiency: O(1). +proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ @@ -940,11 +918,11 @@ proc prepend*[T](ring: var DoublyLinkedRing[T], value: T) = a.prepend(8) assert a.contains(9) - prepend(ring, newDoublyLinkedNode(value)) + prepend(L, newDoublyLinkedNode(value)) -proc remove*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## Removes `n` from `ring`. Efficiency: O(1). - ## This function assumes, for the sake of efficiency, that `n` is contained in `ring`, +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]() @@ -956,13 +934,13 @@ proc remove*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = n.next.prev = n.prev n.prev.next = n.next - if n == ring.head: - let p = ring.head.prev - if p == ring.head: + if n == L.head: + let p = L.head.prev + if p == L.head: # only one element left: - ring.head = nil + L.head = nil else: - ring.head = p + L.head = p proc append*[T](a: var (SinglyLinkedList[T] | SinglyLinkedRing[T]), b: SinglyLinkedList[T] | SinglyLinkedNode[T] | T) = @@ -991,3 +969,47 @@ proc appendMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = ## * `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 e937b8394..3c0d8dc0e 100644 --- a/lib/pure/collections/sequtils.nim +++ b/lib/pure/collections/sequtils.nim @@ -82,7 +82,17 @@ runnableExamples: import std/private/since -import macros +import std/macros +from std/typetraits import supportsCopyMem + +when defined(nimPreviewSlimSystem): + import std/assertions + + +when defined(nimHasEffectsOf): + {.experimental: "strictEffects".} +else: + {.pragma: effectsOf.} macro evalOnceAs(expAlias, exp: untyped, letAssigneable: static[bool]): untyped = @@ -131,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`. ## @@ -164,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). ## @@ -239,9 +265,18 @@ 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. @@ -284,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 @@ -293,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] @@ -356,7 +390,7 @@ 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.} = + seq[S] {.inline, effectsOf: op.} = ## Returns a new sequence with the results of the `op` proc applied to every ## item in the container `s`. ## @@ -382,7 +416,7 @@ 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.} = + {.inline, effectsOf: op.} = ## Applies `op` to every item in `s`, modifying it directly. ## ## Note that the container `s` must be declared as a `var`, @@ -401,7 +435,7 @@ 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 the container `s` must be declared as a `var` @@ -420,7 +454,7 @@ 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).} = +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: @@ -429,7 +463,7 @@ proc apply*[T](s: openArray[T], op: proc (x: T) {.closure.}) {.inline, since: (1 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` (a function that returns a `bool`). ## @@ -453,7 +487,7 @@ 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.} = + {.inline, effectsOf: pred.} = ## Returns a new sequence with all the items of `s` that fulfill the ## predicate `pred` (a function that returns a `bool`). ## @@ -480,7 +514,7 @@ 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.} = + {.inline, effectsOf: pred.} = ## Keeps the items in the passed sequence `s` if they fulfill the ## predicate `pred` (a function that returns a `bool`). ## @@ -509,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) = +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: + 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) @@ -646,7 +719,7 @@ 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. ## @@ -688,7 +761,7 @@ template allIt*(s, pred: untyped): bool = break result -proc any*[T](s: openArray[T], pred: proc(x: T): bool {.closure.}): bool = +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. ## @@ -743,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 @@ -760,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() @@ -866,7 +939,7 @@ 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:** ## * `foldr template<#foldr.t,untyped,untyped>`_ @@ -972,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) @@ -1014,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 = diff --git a/lib/pure/collections/setimpl.nim b/lib/pure/collections/setimpl.nim index 7ebd22760..360a075d6 100644 --- a/lib/pure/collections/setimpl.nim +++ b/lib/pure/collections/setimpl.nim @@ -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(typeof(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 3f91d9030..af13135aa 100644 --- a/lib/pure/collections/sets.nim +++ b/lib/pure/collections/sets.nim @@ -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,7 +39,7 @@ ## 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. @@ -48,7 +50,10 @@ import - hashes, math + std/[hashes, math] + +when not defined(nimHasEffectsOf): + {.pragma: effectsOf.} {.pragma: myShallow.} # For "integer-like A" that are too big for intsets/bit-vectors to be practical, @@ -61,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 @@ -125,7 +130,7 @@ 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 = @@ -246,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 @@ -259,6 +264,7 @@ 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): @@ -344,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]>`_ @@ -376,7 +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(typeof(s.data[i].key)) + {.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 @@ -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(typeof(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,6 +909,7 @@ iterator items*[A](s: OrderedSet[A]): A = ## # --> Got 5 ## # --> Got 8 ## # --> Got 4 + ## ``` let length = s.len forAllOrderedPairs: yield s.data[h].key 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 4ac3befb6..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]`. + ## 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 - ## + 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]`. + ## 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") - ## + 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,7 +137,7 @@ 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. + ## 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 @@ -126,7 +151,7 @@ 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`. @@ -134,7 +159,7 @@ proc mgetOrPut*[A, B](t: var SharedTable[A, B], key: A, val: B): var B = 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) @@ -166,8 +191,7 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, ## ## 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 27c339177..3542741fa 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -11,6 +11,9 @@ 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(typeof(t.data[i].key)) - t.data[i].val = default(typeof(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(typeof(t.data[i].key)) - t.data[i].val = default(typeof(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 = @@ -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 f77642349..d414caeed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -136,12 +136,11 @@ runnableExamples: ## 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>`_ @@ -189,7 +188,6 @@ runnableExamples: ## ## * `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 @@ -198,6 +196,10 @@ runnableExamples: import std/private/since import std/[hashes, math, algorithm] + +when not defined(nimHasEffectsOf): + {.pragma: effectsOf.} + type KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B] KeyValuePairSeq[A, B] = seq[KeyValuePair[A, B]] @@ -215,8 +217,6 @@ type ## For creating a new empty TableRef, use `newTable proc ## <#newTable>`_. -const - defaultInitialSize* = 32 # ------------------------------ helpers --------------------------------- @@ -227,6 +227,12 @@ 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. @@ -235,10 +241,7 @@ template get(t, key): untyped = 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] @@ -275,6 +278,7 @@ 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) = @@ -309,7 +313,7 @@ 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 = +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. @@ -321,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 @@ -342,7 +346,7 @@ proc `[]`*[A, B](t: var Table[A, B], key: A): var 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 @@ -412,7 +416,7 @@ 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 = @@ -430,7 +434,7 @@ 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 = @@ -439,7 +443,7 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = ## ## ## 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. @@ -471,6 +475,18 @@ 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`. runnableExamples: @@ -485,7 +501,7 @@ proc add*[A, B](t: var Table[A, B], key: A, val: sink B) {.deprecated: ## ## **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) @@ -496,6 +512,9 @@ 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. ## + ## .. 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>`_ ## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table @@ -514,6 +533,9 @@ proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool = ## 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 @@ -594,17 +616,17 @@ template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) = let u = User(name: "Hello", uid: 99) t[1] = u - t.withValue(1, value) do: + t.withValue(1, value): # block is executed only if `key` in `t` value.name = "Nim" value.uid = 1314 - t.withValue(2, value) do: + t.withValue(2, value): value.name = "No" value.uid = 521 - doAssert t[1].name == "Nim" - doAssert t[1].uid == 1314 + assert t[1].name == "Nim" + assert t[1].uid == 1314 mixin rawGet var hc: Hash @@ -629,16 +651,22 @@ template withValue*[A, B](t: var Table[A, B], key: A, let u = User(name: "Hello", uid: 99) t[1] = u - t.withValue(1, value) do: + t.withValue(1, value): # block is executed only if `key` in `t` value.name = "Nim" value.uid = 1314 - # do: - # # block is executed when `key` not in `t` - # raise newException(KeyError, "Key not found") - doAssert t[1].name == "Nim" - doAssert t[1].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) @@ -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): @@ -702,7 +731,7 @@ 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 = +iterator keys*[A, B](t: Table[A, B]): lent A = ## Iterates over any key in the table `t`. ## ## See also: @@ -723,7 +752,7 @@ 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 = +iterator values*[A, B](t: Table[A, B]): lent B = ## Iterates over any value in the table `t`. ## ## See also: @@ -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,9 +837,10 @@ 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] = +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. @@ -824,14 +854,16 @@ 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]`. @@ -901,7 +933,7 @@ 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 = +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: @@ -994,6 +1026,18 @@ 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`. runnableExamples: @@ -1015,7 +1059,8 @@ proc add*[A, B](t: TableRef[A, B], key: A, val: sink B) {.deprecated: proc del*[A, B](t: TableRef[A, B], key: A) = ## 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>`_ @@ -1035,7 +1080,8 @@ proc pop*[A, B](t: TableRef[A, B], key: A, val: var B): bool = ## 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>`_ @@ -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): @@ -1146,7 +1193,7 @@ 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 = +iterator keys*[A, B](t: TableRef[A, B]): lent A = ## Iterates over any key in the table `t`. ## ## See also: @@ -1167,7 +1214,7 @@ 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 = +iterator values*[A, B](t: TableRef[A, B]): lent B = ## Iterates over any value in the table `t`. ## ## See also: @@ -1300,6 +1347,7 @@ 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) = @@ -1335,7 +1383,7 @@ 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 = +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. @@ -1391,7 +1439,7 @@ 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 = @@ -1440,7 +1488,7 @@ 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 = @@ -1458,7 +1506,7 @@ 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 = @@ -1481,6 +1529,18 @@ 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`. runnableExamples: @@ -1579,7 +1639,7 @@ 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) = + order = SortOrder.Ascending) {.effectsOf: cmp.} = ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list @@ -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: @@ -1722,7 +1783,7 @@ 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 = +iterator keys*[A, B](t: OrderedTable[A, B]): lent A = ## Iterates over any key in the table `t` in insertion order. ## ## See also: @@ -1743,7 +1804,7 @@ 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 = +iterator values*[A, B](t: OrderedTable[A, B]): lent B = ## Iterates over any value in the table `t` in insertion order. ## ## See also: @@ -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,9 +1864,10 @@ 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] = +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. @@ -1820,7 +1882,8 @@ 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 = @@ -1890,7 +1953,7 @@ 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 = +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: @@ -1967,6 +2030,18 @@ 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`. runnableExamples: @@ -2036,7 +2111,7 @@ 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) = + order = SortOrder.Ascending) {.effectsOf: cmp.} = ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list @@ -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: @@ -2130,7 +2206,7 @@ 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 = +iterator keys*[A, B](t: OrderedTableRef[A, B]): lent A = ## Iterates over any key in the table `t` in insertion order. ## ## See also: @@ -2151,7 +2227,7 @@ 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 = +iterator values*[A, B](t: OrderedTableRef[A, B]): lent B = ## Iterates over any value in the table `t` in insertion order. ## ## See also: @@ -2262,6 +2338,7 @@ 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] = @@ -2371,7 +2448,7 @@ proc contains*[A](t: CountTable[A], key: A): bool = 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 + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## integer value of `default` is returned. ## ## See also: @@ -2501,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): @@ -2518,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: @@ -2543,7 +2621,7 @@ 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 = +iterator keys*[A](t: CountTable[A]): lent A = ## Iterates over any key in the table `t`. ## ## See also: @@ -2610,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: @@ -2619,13 +2697,15 @@ 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] = +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`. @@ -2649,7 +2729,8 @@ proc `[]=`*[A](t: CountTableRef[A], key: A, val: int) = ## * `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). @@ -2658,7 +2739,8 @@ proc inc*[A](t: CountTableRef[A], key: A, val = 1) = 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) @@ -2691,7 +2773,7 @@ proc contains*[A](t: CountTableRef[A], key: A): bool = 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 + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the ## integer value of `default` is returned. ## ## See also: @@ -2777,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): @@ -2794,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: @@ -2872,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 |