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.nim126
-rw-r--r--lib/pure/collections/hashcommon.nim15
-rw-r--r--lib/pure/collections/heapqueue.nim17
-rw-r--r--lib/pure/collections/lists.nim83
-rw-r--r--lib/pure/collections/sequtils.nim40
-rw-r--r--lib/pure/collections/setimpl.nim5
-rw-r--r--lib/pure/collections/sets.nim38
-rw-r--r--lib/pure/collections/sharedlist.nim2
-rw-r--r--lib/pure/collections/sharedtables.nim6
-rw-r--r--lib/pure/collections/tableimpl.nim49
-rw-r--r--lib/pure/collections/tables.nim150
11 files changed, 358 insertions, 173 deletions
diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim
index 7e9ed32f3..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,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,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")
@@ -115,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
@@ -126,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`.
@@ -138,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.
@@ -191,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.
@@ -208,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`.
@@ -221,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.
@@ -243,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):
@@ -252,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) =
@@ -268,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`.
@@ -284,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).
@@ -315,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.
@@ -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,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`.
@@ -395,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.
@@ -411,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) =
@@ -431,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.
@@ -456,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 02312e2dc..17785c8c7 100644
--- a/lib/pure/collections/hashcommon.nim
+++ b/lib/pure/collections/hashcommon.nim
@@ -38,16 +38,6 @@ proc slotsNeeded(count: Natural): int {.inline.} =
   # Make sure to synchronize with `mustRehash` above
   result = nextPowerOfTwo(count * 3 div 2 + 4)
 
-proc rightSize*(count: Natural): int {.inline, deprecated: "Deprecated since 1.4.0".} =
-  ## It is not needed anymore because
-  ## picking the correct size is done internally.
-  ##
-  ## Returns the value of `initialSize` to support `count` items.
-  ##
-  ## If more items are expected to be added, simply add that
-  ## expected extra amount to the parameter before calling this.
-  result = count
-
 template rawGetKnownHCImpl() {.dirty.} =
   if t.dataLen == 0:
     return -1
@@ -68,7 +58,10 @@ proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} =
 template genHashImpl(key, hc: typed) =
   hc = hash(key)
   if hc == 0: # This almost never taken branch should be very predictable.
-    hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine.
+    when sizeof(int) < 4:
+      hc = 31415 # Value doesn't matter; Any non-zero favorite is fine <= 16-bit.
+    else:
+      hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine.
 
 template genHash(key: typed): Hash =
   var res: Hash
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/lists.nim b/lib/pure/collections/lists.nim
index 829ec2ccb..6b88747ef 100644
--- a/lib/pure/collections/lists.nim
+++ b/lib/pure/collections/lists.nim
@@ -62,9 +62,6 @@ import std/private/since
 when defined(nimPreviewSlimSystem):
   import std/assertions
 
-when not defined(nimHasCursor):
-  {.pragma: cursor.}
-
 type
   DoublyLinkedNodeObj*[T] = object
     ## A node of a doubly linked list.
@@ -168,36 +165,14 @@ 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 = L.head
+  var it {.cursor.} = L.head
   while it != nil:
     yield it.value
     it = it.next
 
 template itemsRingImpl() {.dirty.} =
-  var it = L.head
+  var it {.cursor.} = L.head
   if it != nil:
     while true:
       yield it.value
@@ -289,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
@@ -314,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
@@ -409,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).
@@ -736,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:
@@ -996,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 1773e827b..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`.
   ##
@@ -248,6 +265,15 @@ 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 =
   proc zip*[S, T](s1: openArray[S], s2: openArray[T]): retType =
@@ -851,7 +877,7 @@ template toSeq*(iter: untyped): untyped =
           inc i
         result
     else:
-      var result: seq[typeof(iter)]# = @[]
+      var result: seq[typeof(iter)] = @[]
       for x in iter:
         result.add(x)
       result
@@ -1077,9 +1103,13 @@ template newSeqWith*(len: int, init: untyped): untyped =
     import std/random
     var seqRand = newSeqWith(20, rand(1.0))
     assert seqRand[0] != seqRand[1]
-
-  var result = newSeq[typeof(init)](len)
-  for i in 0 ..< len:
+  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
   move(result) # refs bug #7295
 
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 09648ea65..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.}
@@ -128,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 =
@@ -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):
@@ -347,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]>`_
@@ -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] =
@@ -425,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:
@@ -433,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`.
@@ -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 81079a3d1..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)
@@ -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 cd08dcb9a..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):
@@ -220,8 +217,6 @@ type
     ## For creating a new empty TableRef, use `newTable proc
     ## <#newTable>`_.
 
-const
-  defaultInitialSize* = 32
 
 # ------------------------------ helpers ---------------------------------
 
@@ -283,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) =
@@ -317,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.
@@ -420,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 =
@@ -438,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 =
@@ -447,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.
@@ -479,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:
@@ -680,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]
@@ -694,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):
@@ -828,7 +837,8 @@ proc newTable*[A, B](initialSize = defaultInitialSize): TableRef[A, B] =
       b = newTable[char, seq[int]]()
 
   new(result)
-  result[] = initTable[A, B](initialSize)
+  {.noSideEffect.}:
+    result[] = initTable[A, B](initialSize)
 
 proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] =
   ## Creates a new ref hash table that contains the given `pairs`.
@@ -844,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] =
   ## 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]`.
@@ -1014,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:
@@ -1126,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]
@@ -1140,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):
@@ -1322,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) =
@@ -1357,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.
@@ -1413,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 =
@@ -1462,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 =
@@ -1480,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 =
@@ -1503,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:
@@ -1702,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]
@@ -1716,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:
@@ -1825,7 +1864,8 @@ proc newOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTableRef[A
       a = newOrderedTable[int, string]()
       b = newOrderedTable[char, seq[int]]()
   new(result)
-  result[] = initOrderedTable[A, B](initialSize)
+  {.noSideEffect.}:
+    result[] = initOrderedTable[A, B](initialSize)
 
 proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] =
   ## Creates a new ordered ref hash table that contains the given `pairs`.
@@ -1842,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 =
@@ -1989,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:
@@ -2110,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]
@@ -2124,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:
@@ -2284,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] =
@@ -2393,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:
@@ -2523,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):
@@ -2540,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:
@@ -2641,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] =
   ## 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`.
@@ -2671,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).
@@ -2680,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)
@@ -2713,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:
@@ -2799,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):
@@ -2816,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:
@@ -2894,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
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2025-07-14 05:35:09 +0000