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/LockFreeHash.nim8
-rw-r--r--lib/pure/collections/chains.nim44
-rw-r--r--lib/pure/collections/heapqueue.nim107
-rw-r--r--lib/pure/collections/queues.nim219
-rw-r--r--lib/pure/collections/rtarrays.nim2
-rw-r--r--lib/pure/collections/sequtils.nim44
-rw-r--r--lib/pure/collections/sets.nim18
-rw-r--r--lib/pure/collections/sharedtables.nim53
-rw-r--r--lib/pure/collections/tableimpl.nim25
-rw-r--r--lib/pure/collections/tables.nim168
10 files changed, 603 insertions, 85 deletions
diff --git a/lib/pure/collections/LockFreeHash.nim b/lib/pure/collections/LockFreeHash.nim
index a3ead81e3..954d62491 100644
--- a/lib/pure/collections/LockFreeHash.nim
+++ b/lib/pure/collections/LockFreeHash.nim
@@ -52,7 +52,7 @@ when sizeof(int) == 4: # 32bit
   {.deprecated: [TRaw: Raw].}
 elif sizeof(int) == 8: # 64bit
   type
-    Raw = range[0..4611686018427387903]
+    Raw = range[0'i64..4611686018427387903'i64]
     ## The range of uint values that can be stored directly in a value slot
     ## when on a 64 bit platform
   {.deprecated: [TRaw: Raw].}
@@ -74,7 +74,7 @@ type
     copyDone: int
     next: PConcTable[K,V]
     data: EntryArr
-{.deprecated: [TEntry: Entry, TEntryArr: EntryArr.}
+{.deprecated: [TEntry: Entry, TEntryArr: EntryArr].}
 
 proc setVal[K,V](table: var PConcTable[K,V], key: int, val: int,
   expVal: int, match: bool): int
@@ -244,9 +244,9 @@ proc copySlot[K,V](idx: int, oldTbl: var PConcTable[K,V], newTbl: var PConcTable
     echo("oldVal is Tomb!!!, should not happen")
   if pop(oldVal) != 0:
     result = setVal(newTbl, pop(oldKey), pop(oldVal), 0, true) == 0
-  if result:
+  #if result:
     #echo("Copied a Slot! idx= " & $idx & " key= " & $oldKey & " val= " & $oldVal)
-  else:
+  #else:
     #echo("copy slot failed")
   # Our copy is done so we disable the old slot
   while not ok:
diff --git a/lib/pure/collections/chains.nim b/lib/pure/collections/chains.nim
new file mode 100644
index 000000000..6b2ecd272
--- /dev/null
+++ b/lib/pure/collections/chains.nim
@@ -0,0 +1,44 @@
+#
+#
+#            Nim's Runtime Library
+#        (c) Copyright 2016 Andreas Rumpf
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+## Template based implementation of singly and doubly linked lists.
+## The involved types should have 'prev' or 'next' fields and the
+## list header should have 'head' or 'tail' fields.
+
+template prepend*(header, node) =
+  when compiles(header.head):
+    when compiles(node.prev):
+      if header.head != nil:
+        header.head.prev = node
+    node.next = header.head
+    header.head = node
+  when compiles(header.tail):
+    if header.tail == nil:
+      header.tail = node
+
+template append*(header, node) =
+  when compiles(header.head):
+    if header.head == nil:
+      header.head = node
+  when compiles(header.tail):
+    when compiles(node.prev):
+      node.prev = header.tail
+    if header.tail != nil:
+      header.tail.next = node
+    header.tail = node
+
+template unlink*(header, node) =
+  if node.next != nil:
+    node.next.prev = node.prev
+  if node.prev != nil:
+    node.prev.next = node.next
+  if header.head == node:
+    header.head = node.prev
+  if header.tail == node:
+    header.tail = node.next
diff --git a/lib/pure/collections/heapqueue.nim b/lib/pure/collections/heapqueue.nim
new file mode 100644
index 000000000..149a1c9fc
--- /dev/null
+++ b/lib/pure/collections/heapqueue.nim
@@ -0,0 +1,107 @@
+##[ Heap queue algorithm (a.k.a. priority queue). Ported from Python heapq.
+
+Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for
+all k, counting elements from 0.  For the sake of comparison,
+non-existing elements are considered to be infinite.  The interesting
+property of a heap is that a[0] is always its smallest element.
+
+]##
+
+type HeapQueue*[T] = distinct seq[T]
+
+proc newHeapQueue*[T](): HeapQueue[T] {.inline.} = HeapQueue[T](newSeq[T]())
+proc newHeapQueue*[T](h: var HeapQueue[T]) {.inline.} = h = HeapQueue[T](newSeq[T]())
+
+proc len*[T](h: HeapQueue[T]): int {.inline.} = seq[T](h).len
+proc `[]`*[T](h: HeapQueue[T], i: int): T {.inline.} = seq[T](h)[i]
+proc `[]=`[T](h: var HeapQueue[T], i: int, v: T) {.inline.} = seq[T](h)[i] = v
+proc add[T](h: var HeapQueue[T], v: T) {.inline.} = seq[T](h).add(v)
+
+proc heapCmp[T](x, y: T): bool {.inline.} =
+  return (x < y)
+
+# 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
+# is the index of a leaf with a possibly out-of-order value.  Restore the
+# heap invariant.
+proc siftdown[T](heap: var HeapQueue[T], startpos, p: int) =
+  var pos = p
+  var newitem = heap[pos]
+  # Follow the path to the root, moving parents down until finding a place
+  # newitem fits.
+  while pos > startpos:
+    let parentpos = (pos - 1) shr 1
+    let parent = heap[parentpos]
+    if heapCmp(newitem, parent):
+      heap[pos] = parent
+      pos = parentpos
+    else:
+      break
+  heap[pos] = newitem
+
+proc siftup[T](heap: var HeapQueue[T], p: int) =
+  let endpos = len(heap)
+  var pos = p
+  let startpos = pos
+  let newitem = heap[pos]
+  # Bubble up the smaller child until hitting a leaf.
+  var childpos = 2*pos + 1    # leftmost child position
+  while childpos < endpos:
+    # Set childpos to index of smaller child.
+    let rightpos = childpos + 1
+    if rightpos < endpos and not heapCmp(heap[childpos], heap[rightpos]):
+      childpos = rightpos
+    # Move the smaller child up.
+    heap[pos] = heap[childpos]
+    pos = childpos
+    childpos = 2*pos + 1
+  # The leaf at pos is empty now.  Put newitem there, and bubble it up
+  # to its final resting place (by sifting its parents down).
+  heap[pos] = newitem
+  siftdown(heap, startpos, pos)
+    
+proc push*[T](heap: var HeapQueue[T], item: T) =
+  ## Push item onto heap, maintaining the heap invariant.
+  (seq[T](heap)).add(item)
+  siftdown(heap, 0, len(heap)-1)
+
+proc pop*[T](heap: var HeapQueue[T]): T =
+  ## Pop the smallest item off the heap, maintaining the heap invariant.
+  let lastelt = seq[T](heap).pop()
+  if heap.len > 0:
+    result = heap[0]
+    heap[0] = lastelt
+    siftup(heap, 0)
+  else:
+    result = lastelt
+
+proc replace*[T](heap: var HeapQueue[T], item: T): T =
+  ## Pop and return the current smallest value, and add the new item.
+  ## This is more efficient than pop() followed by push(), and can be
+  ## more appropriate when using a fixed-size heap.  Note that the value
+  ## returned may be larger than item!  That constrains reasonable uses of
+  ## this routine unless written as part of a conditional replacement:
+
+  ##    if item > heap[0]:
+  ##        item = replace(heap, item)
+  result = heap[0]
+  heap[0] = item
+  siftup(heap, 0)
+
+proc pushpop*[T](heap: var HeapQueue[T], item: T): T =
+  ## Fast version of a push followed by a pop.
+  if heap.len > 0 and heapCmp(heap[0], item):
+    swap(item, heap[0])
+    siftup(heap, 0)
+  return item
+
+when isMainModule:
+  # Simple sanity test
+  var heap = newHeapQueue[int]()
+  let data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
+  for item in data:
+    push(heap, item)
+  doAssert(heap[0] == 0)
+  var sort = newSeq[int]()
+  while heap.len > 0:
+    sort.add(pop(heap))
+  doAssert(sort == @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
diff --git a/lib/pure/collections/queues.nim b/lib/pure/collections/queues.nim
index b9bf33bff..399e4d413 100644
--- a/lib/pure/collections/queues.nim
+++ b/lib/pure/collections/queues.nim
@@ -8,56 +8,142 @@
 #
 
 ## Implementation of a `queue`:idx:. The underlying implementation uses a ``seq``.
+##
+## None of the procs that get an individual value from the queue can be used
+## on an empty queue.
+## If compiled with `boundChecks` option, those procs will raise an `IndexError`
+## on such access. This should not be relied upon, as `-d:release` will
+## disable those checks and may return garbage or crash the program.
+##
+## As such, a check to see if the queue is empty is needed before any
+## access, unless your program logic guarantees it indirectly.
+##
+## .. code-block:: Nim
+##   proc foo(a, b: Positive) =  # assume random positive values for `a` and `b`
+##     var q = initQueue[int]()  # initializes the object
+##     for i in 1 ..< a: q.add i  # populates the queue
+##
+##     if b < q.len:  # checking before indexed access
+##       echo "The element at index position ", b, " is ", q[b]
+##
+##     # The following two lines don't need any checking on access due to the
+##     # logic of the program, but that would not be the case if `a` could be 0.
+##     assert q.front == 1
+##     assert q.back == a
+##
+##     while q.len > 0:  # checking if the queue is empty
+##       echo q.pop()
+##
 ## Note: For inter thread communication use
 ## a `Channel <channels.html>`_ instead.
 
 import math
 
 type
-  Queue*[T] = object ## a queue
+  Queue*[T] = object ## A queue.
     data: seq[T]
     rd, wr, count, mask: int
 
 {.deprecated: [TQueue: Queue].}
 
-proc initQueue*[T](initialSize=4): Queue[T] =
-  ## creates a new queue. `initialSize` needs to be a power of 2.
+proc initQueue*[T](initialSize: int = 4): Queue[T] =
+  ## Create a new queue.
+  ## Optionally, the initial capacity can be reserved via `initialSize` as a
+  ## performance optimization. The length of a newly created queue will still
+  ## be 0.
+  ##
+  ## `initialSize` needs to be a power of two. If you need to accept runtime
+  ## values for this you could use the ``nextPowerOfTwo`` proc from the
+  ## `math <math.html>`_ module.
   assert isPowerOfTwo(initialSize)
   result.mask = initialSize-1
   newSeq(result.data, initialSize)
 
-proc len*[T](q: Queue[T]): int =
-  ## returns the number of elements of `q`.
+proc len*[T](q: Queue[T]): int {.inline.}=
+  ## Return the number of elements of `q`.
   result = q.count
 
+template emptyCheck(q) =
+  # Bounds check for the regular queue access.
+  when compileOption("boundChecks"):
+    if unlikely(q.count < 1):
+      raise newException(IndexError, "Empty queue.")
+
+template xBoundsCheck(q, i) =
+  # Bounds check for the array like accesses.
+  when compileOption("boundChecks"):  # d:release should disable this.
+    if unlikely(i >= q.count):  # x < q.low is taken care by the Natural parameter
+      raise newException(IndexError,
+                         "Out of bounds: " & $i & " > " & $(q.count - 1))
+
+proc front*[T](q: Queue[T]): T {.inline.}=
+  ## Return the oldest element of `q`. Equivalent to `q.pop()` but does not
+  ## remove it from the queue.
+  emptyCheck(q)
+  result = q.data[q.rd]
+
+proc back*[T](q: Queue[T]): T {.inline.} =
+  ## Return the newest element of `q` but does not remove it from the queue.
+  emptyCheck(q)
+  result = q.data[q.wr - 1 and q.mask]
+
+proc `[]`*[T](q: Queue[T], i: Natural) : T {.inline.} =
+  ## Access the i-th element of `q` by order of insertion.
+  ## q[0] is the oldest (the next one q.pop() will extract),
+  ## q[^1] is the newest (last one added to the queue).
+  xBoundsCheck(q, i)
+  return q.data[q.rd + i and q.mask]
+
+proc `[]`*[T](q: var Queue[T], i: Natural): var T {.inline.} =
+  ## Access the i-th element of `q` and returns a mutable
+  ## reference to it.
+  xBoundsCheck(q, i)
+  return q.data[q.rd + i and q.mask]
+
+proc `[]=`* [T] (q: var Queue[T], i: Natural, val : T) {.inline.} =
+  ## Change the i-th element of `q`.
+  xBoundsCheck(q, i)
+  q.data[q.rd + i and q.mask] = val
+
 iterator items*[T](q: Queue[T]): T =
-  ## yields every element of `q`.
+  ## Yield every element of `q`.
   var i = q.rd
-  var c = q.count
-  while c > 0:
-    dec c
+  for c in 0 ..< q.count:
     yield q.data[i]
     i = (i + 1) and q.mask
 
 iterator mitems*[T](q: var Queue[T]): var T =
-  ## yields every element of `q`.
+  ## Yield every element of `q`.
   var i = q.rd
-  var c = q.count
-  while c > 0:
-    dec c
+  for c in 0 ..< q.count:
     yield q.data[i]
     i = (i + 1) and q.mask
 
+iterator pairs*[T](q: Queue[T]): tuple[key: int, val: T] =
+  ## Yield every (position, value) of `q`.
+  var i = q.rd
+  for c in 0 ..< q.count:
+    yield (c, q.data[i])
+    i = (i + 1) and q.mask
+
+proc contains*[T](q: Queue[T], item: T): bool {.inline.} =
+  ## Return true if `item` is in `q` or false if not found. Usually used
+  ## via the ``in`` operator. It is the equivalent of ``q.find(item) >= 0``.
+  ##
+  ## .. code-block:: Nim
+  ##   if x in q:
+  ##     assert q.contains x
+  for e in q:
+    if e == item: return true
+  return false
+
 proc add*[T](q: var Queue[T], item: T) =
-  ## adds an `item` to the end of the queue `q`.
+  ## Add an `item` to the end of the queue `q`.
   var cap = q.mask+1
-  if q.count >= cap:
-    var n: seq[T]
-    newSeq(n, cap*2)
-    var i = 0
-    for x in items(q):
+  if unlikely(q.count >= cap):
+    var n = newSeq[T](cap*2)
+    for i, x in q:  # don't use copyMem because the GC and because it's slower.
       shallowCopy(n[i], x)
-      inc i
     shallowCopy(q.data, n)
     q.mask = cap*2 - 1
     q.wr = q.count
@@ -66,37 +152,104 @@ proc add*[T](q: var Queue[T], item: T) =
   q.data[q.wr] = item
   q.wr = (q.wr + 1) and q.mask
 
-proc enqueue*[T](q: var Queue[T], item: T) =
-  ## alias for the ``add`` operation.
-  add(q, item)
-
-proc dequeue*[T](q: var Queue[T]): T =
-  ## removes and returns the first element of the queue `q`.
-  assert q.count > 0
+proc default[T](t: typedesc[T]): T {.inline.} = discard
+proc pop*[T](q: var Queue[T]): T {.inline, discardable.} =
+  ## Remove and returns the first (oldest) element of the queue `q`.
+  emptyCheck(q)
   dec q.count
   result = q.data[q.rd]
+  q.data[q.rd] = default(type(result))
   q.rd = (q.rd + 1) and q.mask
 
+proc enqueue*[T](q: var Queue[T], item: T) =
+  ## Alias for the ``add`` operation.
+  q.add(item)
+
+proc dequeue*[T](q: var Queue[T]): T =
+  ## Alias for the ``pop`` operation.
+  q.pop()
+
 proc `$`*[T](q: Queue[T]): string =
-  ## turns a queue into its string representation.
+  ## Turn a queue into its string representation.
   result = "["
-  for x in items(q):
+  for x in items(q):  # Don't remove the items here for reasons that don't fit in this margin.
     if result.len > 1: result.add(", ")
     result.add($x)
   result.add("]")
 
 when isMainModule:
-  var q = initQueue[int]()
+  var q = initQueue[int](1)
   q.add(123)
   q.add(9)
-  q.add(4)
-  var first = q.dequeue
+  q.enqueue(4)
+  var first = q.dequeue()
   q.add(56)
   q.add(6)
-  var second = q.dequeue
+  var second = q.pop()
   q.add(789)
 
   assert first == 123
   assert second == 9
   assert($q == "[4, 56, 6, 789]")
 
+  assert q[0] == q.front and q.front == 4
+  assert q[^1] == q.back and q.back == 789
+  q[0] = 42
+  q[^1] = 7
+
+  assert 6 in q and 789 notin q
+  assert q.find(6) >= 0
+  assert q.find(789) < 0
+
+  for i in -2 .. 10:
+    if i in q:
+      assert q.contains(i) and q.find(i) >= 0
+    else:
+      assert(not q.contains(i) and q.find(i) < 0)
+
+  when compileOption("boundChecks"):
+    try:
+      echo q[99]
+      assert false
+    except IndexError:
+      discard
+
+    try:
+      assert q.len == 4
+      for i in 0 ..< 5: q.pop()
+      assert false
+    except IndexError:
+      discard
+
+  # grabs some types of resize error.
+  q = initQueue[int]()
+  for i in 1 .. 4: q.add i
+  q.pop()
+  q.pop()
+  for i in 5 .. 8: q.add i
+  assert $q == "[3, 4, 5, 6, 7, 8]"
+
+  # Similar to proc from the documentation example
+  proc foo(a, b: Positive) = # assume random positive values for `a` and `b`.
+    var q = initQueue[int]()
+    assert q.len == 0
+    for i in 1 .. a: q.add i
+
+    if b < q.len: # checking before indexed access.
+      assert q[b] == b + 1
+
+    # The following two lines don't need any checking on access due to the logic
+    # of the program, but that would not be the case if `a` could be 0.
+    assert q.front == 1
+    assert q.back == a
+
+    while q.len > 0: # checking if the queue is empty
+      assert q.pop() > 0
+
+  #foo(0,0)
+  foo(8,5)
+  foo(10,9)
+  foo(1,1)
+  foo(2,1)
+  foo(1,5)
+  foo(3,2)
diff --git a/lib/pure/collections/rtarrays.nim b/lib/pure/collections/rtarrays.nim
index 9d8085643..2abe9d1f8 100644
--- a/lib/pure/collections/rtarrays.nim
+++ b/lib/pure/collections/rtarrays.nim
@@ -18,7 +18,7 @@ type
   RtArray*[T] = object  ##
     L: Natural
     spart: seq[T]
-    apart: array [ArrayPartSize, T]
+    apart: array[ArrayPartSize, T]
   UncheckedArray* {.unchecked.}[T] = array[0..100_000_000, T]
 
 template usesSeqPart(x): expr = x.L > ArrayPartSize
diff --git a/lib/pure/collections/sequtils.nim b/lib/pure/collections/sequtils.nim
index 0e3824a81..f458b7636 100644
--- a/lib/pure/collections/sequtils.nim
+++ b/lib/pure/collections/sequtils.nim
@@ -20,6 +20,8 @@
 ## **Note**: This interface will change as soon as the compiler supports
 ## closures and proper coroutines.
 
+include "system/inclrtl"
+
 when not defined(nimhygiene):
   {.pragma: dirty.}
 
@@ -355,7 +357,7 @@ proc insert*[T](dest: var seq[T], src: openArray[T], pos=0) =
     inc(j)
 
 
-template filterIt*(seq1, pred: expr): expr =
+template filterIt*(seq1, pred: untyped): untyped =
   ## Returns a new sequence with all the items that fulfilled the predicate.
   ##
   ## Unlike the `proc` version, the predicate needs to be an expression using
@@ -369,12 +371,12 @@ template filterIt*(seq1, pred: expr): expr =
   ##      notAcceptable = filterIt(temperatures, it > 50 or it < -10)
   ##    assert acceptable == @[-2.0, 24.5, 44.31]
   ##    assert notAcceptable == @[-272.15, 99.9, -113.44]
-  var result {.gensym.} = newSeq[type(seq1[0])]()
+  var result = newSeq[type(seq1[0])]()
   for it {.inject.} in items(seq1):
     if pred: result.add(it)
   result
 
-template keepItIf*(varSeq: seq, pred: expr) =
+template keepItIf*(varSeq: seq, pred: untyped) =
   ## Convenience template around the ``keepIf`` proc to reduce typing.
   ##
   ## Unlike the `proc` version, the predicate needs to be an expression using
@@ -409,7 +411,7 @@ proc all*[T](seq1: seq[T], pred: proc(item: T): bool {.closure.}): bool =
       return false
   return true
 
-template allIt*(seq1, pred: expr): bool {.immediate.} =
+template allIt*(seq1, pred: untyped): bool =
   ## Checks if every item fulfills the predicate.
   ##
   ## Example:
@@ -418,7 +420,7 @@ template allIt*(seq1, pred: expr): bool {.immediate.} =
   ##   let numbers = @[1, 4, 5, 8, 9, 7, 4]
   ##   assert allIt(numbers, it < 10) == true
   ##   assert allIt(numbers, it < 9) == false
-  var result {.gensym.} = true
+  var result = true
   for it {.inject.} in items(seq1):
     if not pred:
       result = false
@@ -440,7 +442,7 @@ proc any*[T](seq1: seq[T], pred: proc(item: T): bool {.closure.}): bool =
       return true
   return false
 
-template anyIt*(seq1, pred: expr): bool {.immediate.} =
+template anyIt*(seq1, pred: untyped): bool =
   ## Checks if some item fulfills the predicate.
   ##
   ## Example:
@@ -449,14 +451,14 @@ template anyIt*(seq1, pred: expr): bool {.immediate.} =
   ##   let numbers = @[1, 4, 5, 8, 9, 7, 4]
   ##   assert anyIt(numbers, it > 8) == true
   ##   assert anyIt(numbers, it > 9) == false
-  var result {.gensym.} = false
+  var result = false
   for it {.inject.} in items(seq1):
     if pred:
       result = true
       break
   result
 
-template toSeq*(iter: expr): expr {.immediate.} =
+template toSeq*(iter: untyped): untyped {.oldimmediate.} =
   ## Transforms any iterator into a sequence.
   ##
   ## Example:
@@ -482,7 +484,7 @@ template toSeq*(iter: expr): expr {.immediate.} =
       result.add(x)
     result
 
-template foldl*(sequence, operation: expr): expr =
+template foldl*(sequence, operation: untyped): untyped =
   ## Template to fold a sequence from left to right, returning the accumulation.
   ##
   ## The sequence is required to have at least a single element. Debug versions
@@ -510,7 +512,7 @@ template foldl*(sequence, operation: expr): expr =
   ##   assert concatenation == "nimiscool"
   let s = sequence
   assert s.len > 0, "Can't fold empty sequences"
-  var result {.gensym.}: type(s[0])
+  var result: type(s[0])
   result = s[0]
   for i in 1..<s.len:
     let
@@ -519,7 +521,7 @@ template foldl*(sequence, operation: expr): expr =
     result = operation
   result
 
-template foldl*(sequence, operation: expr, first): expr =
+template foldl*(sequence, operation, first): untyped =
   ## Template to fold a sequence from left to right, returning the accumulation.
   ##
   ## This version of ``foldl`` gets a starting parameter. This makes it possible
@@ -535,7 +537,7 @@ template foldl*(sequence, operation: expr, first): expr =
   ##     numbers = @[0, 8, 1, 5]
   ##     digits = foldl(numbers, a & (chr(b + ord('0'))), "")
   ##   assert digits == "0815"
-  var result {.gensym.}: type(first)
+  var result: type(first)
   result = first
   for x in items(sequence):
     let
@@ -544,7 +546,7 @@ template foldl*(sequence, operation: expr, first): expr =
     result = operation
   result
 
-template foldr*(sequence, operation: expr): expr =
+template foldr*(sequence, operation: untyped): untyped =
   ## Template to fold a sequence from right to left, returning the accumulation.
   ##
   ## The sequence is required to have at least a single element. Debug versions
@@ -572,7 +574,7 @@ template foldr*(sequence, operation: expr): expr =
   ##   assert concatenation == "nimiscool"
   let s = sequence
   assert s.len > 0, "Can't fold empty sequences"
-  var result {.gensym.}: type(s[0])
+  var result: type(s[0])
   result = sequence[s.len - 1]
   for i in countdown(s.len - 2, 0):
     let
@@ -581,7 +583,7 @@ template foldr*(sequence, operation: expr): expr =
     result = operation
   result
 
-template mapIt*(seq1, typ, op: expr): expr {.deprecated.}=
+template mapIt*(seq1, typ, op: untyped): untyped =
   ## Convenience template around the ``map`` proc to reduce typing.
   ##
   ## The template injects the ``it`` variable which you can use directly in an
@@ -596,13 +598,13 @@ template mapIt*(seq1, typ, op: expr): expr {.deprecated.}=
   ##   assert strings == @["4", "8", "12", "16"]
   ## **Deprecated since version 0.12.0:** Use the ``mapIt(seq1, op)``
   ##   template instead.
-  var result {.gensym.}: seq[typ] = @[]
+  var result: seq[typ] = @[]
   for it {.inject.} in items(seq1):
     result.add(op)
   result
 
 
-template mapIt*(seq1, op: expr): expr =
+template mapIt*(seq1, op: untyped): untyped =
   ## Convenience template around the ``map`` proc to reduce typing.
   ##
   ## The template injects the ``it`` variable which you can use directly in an
@@ -631,7 +633,7 @@ template mapIt*(seq1, op: expr): expr =
       result.add(op)
   result
 
-template applyIt*(varSeq, op: expr) =
+template applyIt*(varSeq, op: untyped) =
   ## Convenience template around the mutable ``apply`` proc to reduce typing.
   ##
   ## The template injects the ``it`` variable which you can use directly in an
@@ -648,7 +650,7 @@ template applyIt*(varSeq, op: expr) =
 
 
 
-template newSeqWith*(len: int, init: expr): expr =
+template newSeqWith*(len: int, init: untyped): untyped =
   ## creates a new sequence, calling `init` to initialize each value. Example:
   ##
   ## .. code-block::
@@ -657,10 +659,10 @@ template newSeqWith*(len: int, init: expr): expr =
   ##   seq2D[1][0] = true
   ##   seq2D[0][1] = true
   ##
-  ##   import math
+  ##   import random
   ##   var seqRand = newSeqWith(20, random(10))
   ##   echo seqRand
-  var result {.gensym.} = newSeq[type(init)](len)
+  var result = newSeq[type(init)](len)
   for i in 0 .. <len:
     result[i] = init
   result
diff --git a/lib/pure/collections/sets.nim b/lib/pure/collections/sets.nim
index 20f73ded3..552e41ef7 100644
--- a/lib/pure/collections/sets.nim
+++ b/lib/pure/collections/sets.nim
@@ -58,7 +58,7 @@ proc isValid*[A](s: HashSet[A]): bool =
   ## initialized. Example:
   ##
   ## .. code-block ::
-  ##   proc savePreferences(options: Set[string]) =
+  ##   proc savePreferences(options: HashSet[string]) =
   ##     assert options.isValid, "Pass an initialized set!"
   ##     # Do stuff here, may crash in release builds!
   result = not s.data.isNil
@@ -72,7 +72,7 @@ proc len*[A](s: HashSet[A]): int =
   ##
   ## .. code-block::
   ##
-  ##   var values: Set[int]
+  ##   var values: HashSet[int]
   ##   assert(not values.isValid)
   ##   assert values.len == 0
   result = s.counter
@@ -256,11 +256,13 @@ proc incl*[A](s: var HashSet[A], other: HashSet[A]) =
   assert other.isValid, "The set `other` needs to be initialized."
   for item in other: incl(s, item)
 
-template doWhile(a: expr, b: stmt): stmt =
+template doWhile(a, b) =
   while true:
     b
     if not a: break
 
+proc default[T](t: typedesc[T]): T {.inline.} = discard
+
 proc excl*[A](s: var HashSet[A], key: A) =
   ## Excludes `key` from the set `s`.
   ##
@@ -277,12 +279,14 @@ proc excl*[A](s: var HashSet[A], key: A) =
   var msk = high(s.data)
   if i >= 0:
     s.data[i].hcode = 0
+    s.data[i].key = default(type(s.data[i].key))
     dec(s.counter)
     while true:         # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1
       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
-      doWhile ((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)):
+      s.data[i].key = default(type(s.data[i].key))
+      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
           return
@@ -334,7 +338,7 @@ proc init*[A](s: var HashSet[A], initialSize=64) =
   ## existing values and calling `excl() <#excl,TSet[A],A>`_ on them. Example:
   ##
   ## .. code-block ::
-  ##   var a: Set[int]
+  ##   var a: HashSet[int]
   ##   a.init(4)
   ##   a.incl(2)
   ##   a.init
@@ -367,7 +371,7 @@ proc toSet*[A](keys: openArray[A]): HashSet[A] =
   result = initSet[A](rightSize(keys.len))
   for key in items(keys): result.incl(key)
 
-template dollarImpl(): stmt {.dirty.} =
+template dollarImpl() {.dirty.} =
   result = "{"
   for key in items(s):
     if result.len > 1: result.add(", ")
@@ -611,7 +615,7 @@ proc card*[A](s: OrderedSet[A]): int {.inline.} =
   ## <http://en.wikipedia.org/wiki/Cardinality>`_ of a set.
   result = s.counter
 
-template forAllOrderedPairs(yieldStmt: stmt) {.dirty, immediate.} =
+template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} =
   var h = s.first
   while h >= 0:
     var nxt = s.data[h].next
diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim
index 20e1bb7a9..17600b272 100644
--- a/lib/pure/collections/sharedtables.nim
+++ b/lib/pure/collections/sharedtables.nim
@@ -45,6 +45,59 @@ template withLock(t, x: untyped) =
   x
   release(t.lock)
 
+template withValue*[A, B](t: var SharedTable[A, B], key: A,
+                          value, body: untyped) =
+  ## retrieves the value at ``t[key]``. 
+  ## `value` can be modified in the scope of the ``withValue`` call.
+  ##
+  ## .. code-block:: nim
+  ##
+  ##   sharedTable.withValue(key, value) do:
+  ##     # block is executed only if ``key`` in ``t``
+  ##     # value is threadsafe in block
+  ##     value.name = "username" 
+  ##     value.uid = 1000
+  ##
+  acquire(t.lock)
+  try:
+    var hc: Hash
+    var index = rawGet(t, key, hc)
+    let hasKey = index >= 0
+    if hasKey:
+      var value {.inject.} = addr(t.data[index].val)
+      body
+  finally:
+    release(t.lock)
+
+template withValue*[A, B](t: var SharedTable[A, B], key: A,
+                          value, body1, body2: untyped) =
+  ## retrieves the value at ``t[key]``. 
+  ## `value` can be modified in the scope of the ``withValue`` call.
+  ## 
+  ## .. code-block:: nim
+  ##
+  ##   sharedTable.withValue(key, value) do:
+  ##     # block is executed only if ``key`` in ``t``
+  ##     # value is threadsafe in block
+  ##     value.name = "username" 
+  ##     value.uid = 1000
+  ##   do:
+  ##     # block is executed when ``key`` not in ``t``
+  ##     raise newException(KeyError, "Key not found")
+  ##
+  acquire(t.lock)
+  try:
+    var hc: Hash
+    var index = rawGet(t, key, hc)
+    let hasKey = index >= 0
+    if hasKey:
+      var value {.inject.} = addr(t.data[index].val)
+      body1
+    else:
+      body2
+  finally:
+    release(t.lock)
+
 proc mget*[A, B](t: var SharedTable[A, B], key: A): var B =
   ## retrieves the value at ``t[key]``. The value can be modified.
   ## If `key` is not in `t`, the ``KeyError`` exception is raised.
diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim
index e4ec05b1c..be3507137 100644
--- a/lib/pure/collections/tableimpl.nim
+++ b/lib/pure/collections/tableimpl.nim
@@ -72,14 +72,14 @@ proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B],
                      key: A, val: B, hc: Hash, h: Hash) =
   rawInsertImpl()
 
-template addImpl(enlarge) {.dirty, immediate.} =
+template addImpl(enlarge) {.dirty.} =
   if mustRehash(t.dataLen, t.counter): enlarge(t)
   var hc: Hash
   var j = rawGetDeep(t, key, hc)
   rawInsert(t, t.data, key, val, hc, j)
   inc(t.counter)
 
-template maybeRehashPutImpl(enlarge) {.dirty, immediate.} =
+template maybeRehashPutImpl(enlarge) {.oldimmediate, dirty.} =
   if mustRehash(t.dataLen, t.counter):
     enlarge(t)
     index = rawGetKnownHC(t, key, hc)
@@ -87,13 +87,13 @@ template maybeRehashPutImpl(enlarge) {.dirty, immediate.} =
   rawInsert(t, t.data, key, val, hc, index)
   inc(t.counter)
 
-template putImpl(enlarge) {.dirty, immediate.} =
+template putImpl(enlarge) {.oldimmediate, dirty.} =
   var hc: Hash
   var index = rawGet(t, key, hc)
   if index >= 0: t.data[index].val = val
   else: maybeRehashPutImpl(enlarge)
 
-template mgetOrPutImpl(enlarge) {.dirty, immediate.} =
+template mgetOrPutImpl(enlarge) {.dirty.} =
   var hc: Hash
   var index = rawGet(t, key, hc)
   if index < 0:
@@ -102,7 +102,7 @@ template mgetOrPutImpl(enlarge) {.dirty, immediate.} =
   # either way return modifiable val
   result = t.data[index].val
 
-template hasKeyOrPutImpl(enlarge) {.dirty, immediate.} =
+template hasKeyOrPutImpl(enlarge) {.dirty.} =
   var hc: Hash
   var index = rawGet(t, key, hc)
   if index < 0:
@@ -110,18 +110,24 @@ template hasKeyOrPutImpl(enlarge) {.dirty, immediate.} =
     maybeRehashPutImpl(enlarge)
   else: result = true
 
-template delImpl() {.dirty, immediate.} =
+proc default[T](t: typedesc[T]): T {.inline.} = discard
+
+template delImpl() {.dirty.} =
   var hc: Hash
   var i = rawGet(t, key, hc)
   let msk = maxHash(t)
   if i >= 0:
     t.data[i].hcode = 0
+    t.data[i].key = default(type(t.data[i].key))
+    t.data[i].val = default(type(t.data[i].val))
     dec(t.counter)
     block outer:
       while true:         # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1
         var j = i         # The correctness of this depends on (h+1) in nextTry,
         var r = j         # though may be adaptable to other simple sequences.
         t.data[i].hcode = 0              # mark current EMPTY
+        t.data[i].key = default(type(t.data[i].key))
+        t.data[i].val = default(type(t.data[i].val))
         while true:
           i = (i + 1) and msk            # increment mod table size
           if isEmpty(t.data[i].hcode):   # end of collision cluster; So all done
@@ -133,3 +139,10 @@ template delImpl() {.dirty, immediate.} =
           t.data[j] = t.data[i]
         else:
           shallowCopy(t.data[j], t.data[i]) # data[j] will be marked EMPTY next loop
+
+template clearImpl() {.dirty.} =
+  for i in 0 .. <t.data.len:
+    t.data[i].hcode = 0
+    t.data[i].key = default(type(t.data[i].key))
+    t.data[i].val = default(type(t.data[i].val))
+  t.counter = 0
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim
index 2ed0d2034..9308095aa 100644
--- a/lib/pure/collections/tables.nim
+++ b/lib/pure/collections/tables.nim
@@ -16,6 +16,39 @@
 ## semantics, this means that ``=`` performs a copy of the hash table.
 ## For **reference** semantics use the ``Ref`` variant: ``TableRef``,
 ## ``OrderedTableRef``, ``CountTableRef``.
+## To give an example, when `a` is a Table, then `var b = a` gives `b`
+## as a new independent table. b is initialised with the contents of `a`.
+## Changing `b` does not affect `a` and vice versa:
+##
+## .. code-block::
+##   import tables
+##
+##   var
+##     a = {1: "one", 2: "two"}.toTable  # creates a Table
+##     b = a
+##
+##   echo a, b  # output: {1: one, 2: two}{1: one, 2: two}
+##
+##   b[3] = "three"
+##   echo a, b  # output: {1: one, 2: two}{1: one, 2: two, 3: three}
+##   echo a == b  # output: false
+##
+## On the other hand, when `a` is a TableRef instead, then changes to `b` also affect `a`.
+## Both `a` and `b` reference the same data structure:
+##
+## .. code-block::
+##   import tables
+##
+##   var
+##     a = {1: "one", 2: "two"}.newTable  # creates a TableRef
+##     b = a
+##
+##   echo a, b  # output: {1: one, 2: two}{1: one, 2: two}
+##
+##   b[3] = "three"
+##   echo a, b  # output: {1: one, 2: two, 3: three}{1: one, 2: two, 3: three}
+##   echo a == b  # output: true
+##
 ##
 ## If you are using simple standard types like ``int`` or ``string`` for the
 ## keys of the table you won't have any problems, but as soon as you try to use
@@ -80,11 +113,15 @@ type
 
 {.deprecated: [TTable: Table, PTable: TableRef].}
 
-template maxHash(t): expr {.immediate.} = high(t.data)
-template dataLen(t): expr = len(t.data)
+template maxHash(t): untyped = high(t.data)
+template dataLen(t): untyped = len(t.data)
 
 include tableimpl
 
+proc clear*[A, B](t: Table[A, B] | TableRef[A, B]) =
+  ## Resets the table so that it is empty.
+  clearImpl()
+
 proc rightSize*(count: Natural): int {.inline.} =
   ## Return the value of `initialSize` to support `count` items.
   ##
@@ -98,7 +135,7 @@ proc len*[A, B](t: Table[A, B]): int =
   ## returns the number of keys in `t`.
   result = t.counter
 
-template get(t, key): untyped {.immediate.} =
+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.
   mixin rawGet
@@ -111,7 +148,7 @@ template get(t, key): untyped {.immediate.} =
     else:
       raise newException(KeyError, "key not found")
 
-template getOrDefaultImpl(t, key): untyped {.immediate.} =
+template getOrDefaultImpl(t, key): untyped =
   mixin rawGet
   var hc: Hash
   var index = rawGet(t, key, hc)
@@ -136,6 +173,51 @@ proc mget*[A, B](t: var Table[A, B], key: A): var B {.deprecated.} =
 
 proc getOrDefault*[A, B](t: Table[A, B], key: A): B = getOrDefaultImpl(t, key)
 
+template withValue*[A, B](t: var Table[A, B], key: A,
+                          value, body: untyped) =
+  ## retrieves the value at ``t[key]``.
+  ## `value` can be modified in the scope of the ``withValue`` call.
+  ##
+  ## .. code-block:: nim
+  ##
+  ##   sharedTable.withValue(key, value) do:
+  ##     # block is executed only if ``key`` in ``t``
+  ##     value.name = "username"
+  ##     value.uid = 1000
+  ##
+  mixin rawGet
+  var hc: Hash
+  var index = rawGet(t, key, hc)
+  let hasKey = index >= 0
+  if hasKey:
+    var value {.inject.} = addr(t.data[index].val)
+    body
+
+template withValue*[A, B](t: var Table[A, B], key: A,
+                          value, body1, body2: untyped) =
+  ## retrieves the value at ``t[key]``.
+  ## `value` can be modified in the scope of the ``withValue`` call.
+  ##
+  ## .. code-block:: nim
+  ##
+  ##   table.withValue(key, value) do:
+  ##     # block is executed only if ``key`` in ``t``
+  ##     value.name = "username"
+  ##     value.uid = 1000
+  ##   do:
+  ##     # block is executed when ``key`` not in ``t``
+  ##     raise newException(KeyError, "Key not found")
+  ##
+  mixin rawGet
+  var hc: Hash
+  var index = rawGet(t, key, hc)
+  let hasKey = index >= 0
+  if hasKey:
+    var value {.inject.} = addr(t.data[index].val)
+    body1
+  else:
+    body2
+
 iterator allValues*[A, B](t: Table[A, B]; key: A): B =
   ## iterates over any value in the table `t` that belongs to the given `key`.
   var h: Hash = hash(key) and high(t.data)
@@ -229,7 +311,7 @@ proc toTable*[A, B](pairs: openArray[(A,
   result = initTable[A, B](rightSize(pairs.len))
   for key, val in items(pairs): result[key] = val
 
-template dollarImpl(): stmt {.dirty.} =
+template dollarImpl(): untyped {.dirty.} =
   if t.len == 0:
     result = "{:}"
   else:
@@ -249,18 +331,17 @@ proc hasKey*[A, B](t: TableRef[A, B], key: A): bool =
   ## returns true iff `key` is in the table `t`.
   result = t[].hasKey(key)
 
-template equalsImpl() =
+template equalsImpl(t) =
   if s.counter == t.counter:
     # different insertion orders mean different 'data' seqs, so we have
     # to use the slow route here:
     for key, val in s:
-      # prefix notation leads to automatic dereference in case of PTable
       if not t.hasKey(key): return false
-      if t[key] != val: return false
+      if t.getOrDefault(key) != val: return false
     return true
 
 proc `==`*[A, B](s, t: Table[A, B]): bool =
-  equalsImpl()
+  equalsImpl(t)
 
 proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] =
   ## Index the collection with the proc provided.
@@ -350,7 +431,7 @@ proc `$`*[A, B](t: TableRef[A, B]): string =
 proc `==`*[A, B](s, t: TableRef[A, B]): bool =
   if isNil(s): result = isNil(t)
   elif isNil(t): result = false
-  else: equalsImpl()
+  else: equalsImpl(t[])
 
 proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] =
   ## Index the collection with the proc provided.
@@ -376,7 +457,13 @@ proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} =
   ## returns the number of keys in `t`.
   result = t.counter
 
-template forAllOrderedPairs(yieldStmt: stmt) {.dirty, immediate.} =
+proc clear*[A, B](t: OrderedTable[A, B] | OrderedTableRef[A, B]) =
+  ## Resets the table so that it is empty.
+  clearImpl()
+  t.first = -1
+  t.last = -1
+
+template forAllOrderedPairs(yieldStmt: untyped) {.oldimmediate, dirty.} =
   var h = t.first
   while h >= 0:
     var nxt = t.data[h].next
@@ -562,7 +649,7 @@ proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} =
   ## returns the number of keys in `t`.
   result = t.counter
 
-template forAllOrderedPairs(yieldStmt: stmt) {.dirty, immediate.} =
+template forAllOrderedPairs(yieldStmt: untyped) {.oldimmediate, dirty.} =
   var h = t.first
   while h >= 0:
     var nxt = t.data[h].next
@@ -663,6 +750,27 @@ proc sort*[A, B](t: OrderedTableRef[A, B],
   ## contrast to the `sort` for count tables).
   t[].sort(cmp)
 
+proc del*[A, B](t: var OrderedTable[A, B], key: A) =
+  ## deletes `key` from ordered hash table `t`. O(n) comlexity.
+  var prev = -1
+  let hc = hash(key)
+  forAllOrderedPairs:
+    if t.data[h].hcode == hc:
+      if t.first == h:
+        t.first = t.data[h].next
+      else:
+        t.data[prev].next = t.data[h].next
+      var zeroValue : type(t.data[h])
+      t.data[h] = zeroValue
+      dec t.counter
+      break
+    else:
+      prev = h
+
+proc del*[A, B](t: var OrderedTableRef[A, B], key: A) =
+  ## deletes `key` from ordered hash table `t`. O(n) comlexity.
+  t[].del(key)
+
 # ------------------------------ count tables -------------------------------
 
 type
@@ -678,6 +786,11 @@ proc len*[A](t: CountTable[A]): int =
   ## returns the number of keys in `t`.
   result = t.counter
 
+proc clear*[A](t: CountTable[A] | CountTableRef[A]) =
+  ## Resets the table so that it is empty.
+  clearImpl()
+  t.counter = 0
+
 iterator pairs*[A](t: CountTable[A]): (A, int) =
   ## iterates over any (key, value) pair in the table `t`.
   for h in 0..high(t.data):
@@ -711,7 +824,7 @@ proc rawGet[A](t: CountTable[A], key: A): int =
     h = nextTry(h, high(t.data))
   result = -1 - h                   # < 0 => MISSING; insert idx = -1 - result
 
-template ctget(t, key: untyped): untyped {.immediate.} =
+template ctget(t, key: untyped): untyped =
   var index = rawGet(t, key)
   if index >= 0: result = t.data[index].val
   else:
@@ -984,6 +1097,26 @@ when isMainModule:
   s3[p1] = 30_000
   s3[p2] = 45_000
 
+  block: # Ordered table should preserve order after deletion
+    var
+      s4 = initOrderedTable[int, int]()
+    s4[1] = 1
+    s4[2] = 2
+    s4[3] = 3
+
+    var prev = 0
+    for i in s4.values:
+      doAssert(prev < i)
+      prev = i
+
+    s4.del(2)
+    doAssert(2 notin s4)
+    doAssert(s4.len == 2)
+    prev = 0
+    for i in s4.values:
+      doAssert(prev < i)
+      prev = i
+
   var
     t1 = initCountTable[string]()
     t2 = initCountTable[string]()
@@ -1040,3 +1173,12 @@ when isMainModule:
     doAssert 0 == t.getOrDefault(testKey)
     t.inc(testKey,3)
     doAssert 3 == t.getOrDefault(testKey)
+
+  # Clear tests
+  var clearTable = newTable[int, string]()
+  clearTable[42] = "asd"
+  clearTable[123123] = "piuyqwb "
+  doAssert clearTable[42] == "asd"
+  clearTable.clear()
+  doAssert(not clearTable.hasKey(123123))
+  doAssert clearTable.getOrDefault(42) == nil
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2025-06-24 20:24:22 +0000