summary refs log tree commit diff stats
path: root/lib/pure/collections
diff options
context:
space:
mode:
Diffstat (limited to 'lib/pure/collections')
-rw-r--r--lib/pure/collections/deques.nim121
-rw-r--r--lib/pure/collections/hashcommon.nim5
-rw-r--r--lib/pure/collections/heapqueue.nim15
-rw-r--r--lib/pure/collections/lists.nim76
-rw-r--r--lib/pure/collections/sequtils.nim25
-rw-r--r--lib/pure/collections/setimpl.nim4
-rw-r--r--lib/pure/collections/sets.nim30
-rw-r--r--lib/pure/collections/sharedlist.nim2
-rw-r--r--lib/pure/collections/sharedtables.nim6
-rw-r--r--lib/pure/collections/tableimpl.nim33
-rw-r--r--lib/pure/collections/tables.nim92
11 files changed, 286 insertions, 123 deletions
diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim
index ed58028c8..d2b0099f2 100644
--- a/lib/pure/collections/deques.nim
+++ b/lib/pure/collections/deques.nim
@@ -50,7 +50,7 @@ runnableExamples:
 
 import std/private/since
 
-import math
+import std/[assertions, hashes, math]
 
 type
   Deque*[T] = object
@@ -59,20 +59,29 @@ 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) =
-  if deq.mask == 0:
+  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.
   ##
@@ -85,22 +94,22 @@ proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] =
   ## * `toDeque proc <#toDeque,openArray[T]>`_
   result.initImpl(initialSize)
 
-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")
@@ -114,7 +123,7 @@ proc `[]`*[T](deq: Deque[T], i: Natural): lent 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
@@ -125,7 +134,7 @@ 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: sink T) {.inline.} =
   ## Sets the `i`-th element of `deq` to `val`.
@@ -137,7 +146,7 @@ proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink 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): lent T {.inline.} =
   ## Accesses the backwards indexed `i`-th element.
@@ -190,10 +199,8 @@ iterator items*[T](deq: Deque[T]): lent T =
     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.
@@ -207,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`.
@@ -220,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.
@@ -242,8 +245,9 @@ 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):
@@ -251,8 +255,7 @@ proc expandIfNeeded[T](deq: var Deque[T]) =
       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: sink T) =
@@ -267,9 +270,8 @@ proc addFirst*[T](deq: var Deque[T], item: sink 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: sink T) =
   ## Adds an `item` to the end of `deq`.
@@ -283,9 +285,8 @@ proc addLast*[T](deq: var Deque[T], item: sink 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 toDeque*[T](x: openArray[T]): Deque[T] {.since: (1, 3).} =
   ## Creates a new deque that contains the elements of `x` (in the same order).
@@ -314,7 +315,7 @@ proc peekFirst*[T](deq: Deque[T]): lent 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]): lent T {.inline.} =
   ## Returns the last element of `deq`, but does not remove it from the deque.
@@ -344,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`,
@@ -377,9 +378,8 @@ proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} =
     assert $a == "[20, 30, 40, 50]"
 
   emptyCheck(deq)
-  dec deq.count
-  result = move 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`.
@@ -394,9 +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 = move 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.
@@ -410,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) =
@@ -430,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 - 1) and deq.mask])
-    deq.tail = (deq.tail - 1) and deq.mask
-
-  dec deq.count, fromFirst + fromLast
+    dec deq.tail
 
 proc `$`*[T](deq: Deque[T]): string =
   ## Turns a deque into its string representation.
@@ -455,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 8fd4c6e08..17785c8c7 100644
--- a/lib/pure/collections/hashcommon.nim
+++ b/lib/pure/collections/hashcommon.nim
@@ -58,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
diff --git a/lib/pure/collections/heapqueue.nim b/lib/pure/collections/heapqueue.nim
index bcfdf37c2..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]
@@ -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/lists.nim b/lib/pure/collections/lists.nim
index 6e3ddf397..6b88747ef 100644
--- a/lib/pure/collections/lists.nim
+++ b/lib/pure/collections/lists.nim
@@ -165,28 +165,6 @@ 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 {.cursor.} = L.head
   while it != nil:
@@ -286,7 +264,7 @@ iterator nodes*[T](L: SomeLinkedList[T]): SomeLinkedNode[T] =
         x.value = 5 * x.value - 1
     assert $a == "[49, 99, 199, 249]"
 
-  var it = L.head
+  var it {.cursor.} = L.head
   while it != nil:
     let nxt = it.next
     yield it
@@ -311,7 +289,7 @@ iterator nodes*[T](L: SomeLinkedRing[T]): SomeLinkedNode[T] =
         x.value = 5 * x.value - 1
     assert $a == "[49, 99, 199, 249]"
 
-  var it = L.head
+  var it {.cursor.} = L.head
   if it != nil:
     while true:
       let nxt = it.next
@@ -406,9 +384,7 @@ 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](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} =
   ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1).
@@ -733,7 +709,7 @@ proc remove*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]): bool {.disc
     if L.tail.next == n:
       L.tail.next = L.head # restore cycle
   else:
-    var prev = L.head
+    var prev {.cursor.} = L.head
     while prev.next != n and prev.next != nil:
       prev = prev.next
     if prev.next == nil:
@@ -993,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 e2adba910..3c0d8dc0e 100644
--- a/lib/pure/collections/sequtils.nim
+++ b/lib/pure/collections/sequtils.nim
@@ -82,7 +82,8 @@ runnableExamples:
 
 import std/private/since
 
-import macros
+import std/macros
+from std/typetraits import supportsCopyMem
 
 when defined(nimPreviewSlimSystem):
   import std/assertions
@@ -140,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`.
   ##
@@ -1086,8 +1103,12 @@ template newSeqWith*(len: int, init: untyped): untyped =
     import std/random
     var seqRand = newSeqWith(20, rand(1.0))
     assert seqRand[0] != seqRand[1]
+  type T = typeof(init)
   let newLen = len
-  var result = newSeq[typeof(init)](newLen)
+  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
   move(result) # refs bug #7295
diff --git a/lib/pure/collections/setimpl.nim b/lib/pure/collections/setimpl.nim
index dbd4ce1d5..360a075d6 100644
--- a/lib/pure/collections/setimpl.nim
+++ b/lib/pure/collections/setimpl.nim
@@ -87,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 7e193af1a..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,7 @@
 
 
 import
-  hashes, math
+  std/[hashes, math]
 
 when not defined(nimHasEffectsOf):
   {.pragma: effectsOf.}
@@ -249,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
@@ -262,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):
@@ -379,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] =
@@ -586,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()
 
 
@@ -813,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`.
@@ -874,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()
 
 
@@ -890,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)
@@ -902,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 e61883220..ec8f1cd86 100644
--- a/lib/pure/collections/sharedlist.nim
+++ b/lib/pure/collections/sharedlist.nim
@@ -16,7 +16,7 @@
 {.push stackTrace: off.}
 
 import
-  locks
+  std/locks
 
 const
   ElemsPerNode = 100
diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim
index 816ab49ab..b474ecd31 100644
--- a/lib/pure/collections/sharedtables.nim
+++ b/lib/pure/collections/sharedtables.nim
@@ -17,7 +17,7 @@
 {.deprecated.}
 
 import
-  hashes, math, locks
+  std/[hashes, math, locks]
 
 type
   KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B]
@@ -191,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):
@@ -200,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)
diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim
index 112aaa7d0..3542741fa 100644
--- a/lib/pure/collections/tableimpl.nim
+++ b/lib/pure/collections/tableimpl.nim
@@ -45,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)
@@ -59,7 +59,7 @@ template putImpl(enlarge) {.dirty.} =
   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()
@@ -67,17 +67,30 @@ template mgetOrPutImpl(enlarge) {.dirty.} =
   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 = 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
@@ -119,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
@@ -151,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 =
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim
index d4056897d..d414caeed 100644
--- a/lib/pure/collections/tables.nim
+++ b/lib/pure/collections/tables.nim
@@ -136,14 +136,11 @@ runnableExamples:
 ## a more complex object as a key you will be greeted by a strange compiler
 ## error:
 ##
-## .. code::
-##
-##   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>`_
@@ -197,7 +194,7 @@ runnableExamples:
 
 
 import std/private/since
-import hashes, math, algorithm
+import std/[hashes, math, algorithm]
 
 
 when not defined(nimHasEffectsOf):
@@ -281,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) =
@@ -315,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.
@@ -477,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:
@@ -678,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]
@@ -692,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):
@@ -1015,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:
@@ -1127,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]
@@ -1141,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):
@@ -1323,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) =
@@ -1358,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.
@@ -1414,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 =
@@ -1504,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:
@@ -1703,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]
@@ -1717,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:
@@ -1992,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:
@@ -2113,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]
@@ -2127,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:
@@ -2287,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] =
@@ -2526,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):
@@ -2543,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:
@@ -2806,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):
@@ -2823,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:
@@ -2915,4 +2969,4 @@ proc hash*[K,V](s: OrderedTable[K,V]): Hash =
 proc hash*[V](s: CountTable[V]): Hash =
   for p in pairs(s):
     result = result xor hash(p)
-  result = !$result
\ No newline at end of file
+  result = !$result
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2025-07-13 01:34:57 +0000