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/critbits.nim69
-rw-r--r--lib/pure/collections/deques.nim54
-rw-r--r--lib/pure/collections/intsets.nim24
-rw-r--r--lib/pure/collections/sequtils.nim157
-rw-r--r--lib/pure/collections/sets.nim32
-rw-r--r--lib/pure/collections/sharedtables.nim12
-rw-r--r--lib/pure/collections/tables.nim105
7 files changed, 365 insertions, 88 deletions
diff --git a/lib/pure/collections/critbits.nim b/lib/pure/collections/critbits.nim
index 34f5c5470..c94e08098 100644
--- a/lib/pure/collections/critbits.nim
+++ b/lib/pure/collections/critbits.nim
@@ -74,18 +74,19 @@ proc rawInsert[T](c: var CritBitTree[T], key: string): Node[T] =
     var newByte = 0
     block blockX:
       while newbyte < key.len:
-        if it.key[newbyte] != key[newbyte]:
-          newotherbits = it.key[newbyte].ord xor key[newbyte].ord
+        let ch = if newbyte < it.key.len: it.key[newbyte] else: '\0'
+        if ch != key[newbyte]:
+          newotherbits = ch.ord xor key[newbyte].ord
           break blockX
         inc newbyte
-      if it.key[newbyte] != '\0':
+      if newbyte < it.key.len:
         newotherbits = it.key[newbyte].ord
       else:
         return it
     while (newOtherBits and (newOtherBits-1)) != 0:
       newOtherBits = newOtherBits and (newOtherBits-1)
     newOtherBits = newOtherBits xor 255
-    let ch = it.key[newByte]
+    let ch = if newByte < it.key.len: it.key[newByte] else: '\0'
     let dir = (1 + (ord(ch) or newOtherBits)) shr 8
 
     var inner: Node[T]
@@ -162,18 +163,20 @@ proc containsOrIncl*(c: var CritBitTree[void], key: string): bool =
   var n = rawInsert(c, key)
   result = c.count == oldCount
 
-proc inc*(c: var CritBitTree[int]; key: string) =
-  ## counts the 'key'.
-  let oldCount = c.count
+proc inc*(c: var CritBitTree[int]; key: string, val: int = 1) =
+  ## increments `c[key]` by `val`.
   var n = rawInsert(c, key)
-  if c.count == oldCount:
-    # not a new key:
-    inc n.val
+  inc n.val, val
 
 proc incl*(c: var CritBitTree[void], key: string) =
   ## includes `key` in `c`.
   discard rawInsert(c, key)
 
+proc incl*[T](c: var CritBitTree[T], key: string, val: T) =
+  ## inserts `key` with value `val` into `c`.
+  var n = rawInsert(c, key)
+  n.val = val
+
 proc `[]=`*[T](c: var CritBitTree[T], key: string, val: T) =
   ## puts a (key, value)-pair into `t`.
   var n = rawInsert(c, key)
@@ -321,10 +324,14 @@ proc `$`*[T](c: CritBitTree[T]): string =
       const avgItemLen = 16
     result = newStringOfCap(c.count * avgItemLen)
     result.add("{")
-    for key, val in pairs(c):
-      if result.len > 1: result.add(", ")
-      result.add($key)
-      when T isnot void:
+    when T is void:
+      for key in keys(c):
+        if result.len > 1: result.add(", ")
+        result.addQuoted(key)
+    else:
+      for key, val in pairs(c):
+        if result.len > 1: result.add(", ")
+        result.addQuoted(key)
         result.add(": ")
         result.addQuoted(val)
     result.add("}")
@@ -351,3 +358,37 @@ when isMainModule:
   assert toSeq(r.items) == @["abc", "definition", "prefix", "xyz"]
 
   assert toSeq(r.itemsWithPrefix("de")) == @["definition"]
+  var c = CritBitTree[int]()
+
+  c.inc("a")
+  assert c["a"] == 1
+
+  c.inc("a", 4)
+  assert c["a"] == 5
+
+  c.inc("a", -5)
+  assert c["a"] == 0
+
+  c.inc("b", 2)
+  assert c["b"] == 2
+
+  c.inc("c", 3)
+  assert c["c"] == 3
+
+  c.inc("a", 1)
+  assert c["a"] == 1
+
+  var cf = CritBitTree[float]()
+
+  cf.incl("a", 1.0)
+  assert cf["a"] == 1.0
+
+  cf.incl("b", 2.0)
+  assert cf["b"] == 2.0
+
+  cf.incl("c", 3.0)
+  assert cf["c"] == 3.0
+
+  assert cf.len == 3
+  cf.excl("c")
+  assert cf.len == 2
diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim
index 328308a9b..e8342e208 100644
--- a/lib/pure/collections/deques.nim
+++ b/lib/pure/collections/deques.nim
@@ -38,7 +38,7 @@
 ## Note: For inter thread communication use
 ## a `Channel <channels.html>`_ instead.
 
-import math
+import math, typetraits
 
 type
   Deque*[T] = object
@@ -160,16 +160,15 @@ proc peekLast*[T](deq: Deque[T]): T {.inline.} =
   emptyCheck(deq)
   result = deq.data[(deq.tail - 1) and deq.mask]
 
-template default[T](t: typedesc[T]): T =
-  var v: T
-  v
+template destroy(x: untyped) =
+  reset(x)
 
 proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} =
   ## Remove and returns the first element of the `deq`.
   emptyCheck(deq)
   dec deq.count
   result = deq.data[deq.head]
-  deq.data[deq.head] = default(type(result))
+  destroy(deq.data[deq.head])
   deq.head = (deq.head + 1) and deq.mask
 
 proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} =
@@ -178,7 +177,34 @@ proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} =
   dec deq.count
   deq.tail = (deq.tail - 1) and deq.mask
   result = deq.data[deq.tail]
-  deq.data[deq.tail] = default(type(result))
+  destroy(deq.data[deq.tail])
+
+proc clear*[T](deq: var Deque[T]) {.inline.} =
+  ## Resets the deque so that it is empty.
+  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) =
+  ## Remove `fromFirst` elements from the front of the deque and
+  ## `fromLast` elements from the back. If the supplied number of
+  ## elements exceeds the total number of elements in the deque,
+  ## the deque will remain empty.
+  ##
+  ## Any user defined destructors
+  if fromFirst + fromLast > deq.count:
+    clear(deq)
+    return
+
+  for i in 0 ..< fromFirst:
+    destroy(deq.data[deq.head])
+    deq.head = (deq.head + 1) and deq.mask
+
+  for i in 0 ..< fromLast:
+    destroy(deq.data[deq.tail])
+    deq.tail = (deq.tail - 1) and deq.mask
+
+  dec deq.count, fromFirst + fromLast
 
 proc `$`*[T](deq: Deque[T]): string =
   ## Turn a deque into its string representation.
@@ -215,6 +241,22 @@ when isMainModule:
   assert deq.find(6) >= 0
   assert deq.find(789) < 0
 
+  block:
+    var d = initDeque[int](1)
+    d.addLast 7
+    d.addLast 8
+    d.addLast 10
+    d.addFirst 5
+    d.addFirst 2
+    d.addFirst 1
+    d.addLast 20
+    d.shrink(fromLast = 2)
+    doAssert($d == "[1, 2, 5, 7, 8]")
+    d.shrink(2, 1)
+    doAssert($d == "[5, 7]")
+    d.shrink(2, 2)
+    doAssert d.len == 0
+
   for i in -2 .. 10:
     if i in deq:
       assert deq.contains(i) and deq.find(i) >= 0
diff --git a/lib/pure/collections/intsets.nim b/lib/pure/collections/intsets.nim
index bfecfe447..545958977 100644
--- a/lib/pure/collections/intsets.nim
+++ b/lib/pure/collections/intsets.nim
@@ -184,7 +184,7 @@ proc missingOrExcl*(s: var IntSet, key: int) : bool =
   ## `key` is removed from `s` and false is returned.
   var count = s.elems
   exclImpl(s, key)
-  result = count == s.elems 
+  result = count == s.elems
 
 proc containsOrIncl*(s: var IntSet, key: int): bool =
   ## returns true if `s` contains `key`, otherwise `key` is included in `s`
@@ -212,7 +212,10 @@ proc initIntSet*: IntSet =
 
   #newSeq(result.data, InitIntSetSize)
   #result.max = InitIntSetSize-1
-  result.data = nil
+  when defined(nimNoNilSeqs):
+    result.data = @[]
+  else:
+    result.data = nil
   result.max = 0
   result.counter = 0
   result.head = nil
@@ -222,7 +225,10 @@ proc clear*(result: var IntSet) =
   #setLen(result.data, InitIntSetSize)
   #for i in 0..InitIntSetSize-1: result.data[i] = nil
   #result.max = InitIntSetSize-1
-  result.data = nil
+  when defined(nimNoNilSeqs):
+    result.data = @[]
+  else:
+    result.data = nil
   result.max = 0
   result.counter = 0
   result.head = nil
@@ -234,7 +240,10 @@ proc assign*(dest: var IntSet, src: IntSet) =
   ## copies `src` to `dest`. `dest` does not need to be initialized by
   ## `initIntSet`.
   if src.elems <= src.a.len:
-    dest.data = nil
+    when defined(nimNoNilSeqs):
+      dest.data = @[]
+    else:
+      dest.data = nil
     dest.max = 0
     dest.counter = src.counter
     dest.head = nil
@@ -247,11 +256,9 @@ proc assign*(dest: var IntSet, src: IntSet) =
 
     var it = src.head
     while it != nil:
-
       var h = it.key and dest.max
       while dest.data[h] != nil: h = nextTry(h, dest.max)
       assert(dest.data[h] == nil)
-
       var n: PTrunk
       new(n)
       n.next = dest.head
@@ -259,7 +266,6 @@ proc assign*(dest: var IntSet, src: IntSet) =
       n.bits = it.bits
       dest.head = n
       dest.data[h] = n
-
       it = it.next
 
 proc union*(s1, s2: IntSet): IntSet =
@@ -315,7 +321,7 @@ proc len*(s: IntSet): int {.inline.} =
     for _ in s:
       inc(result)
 
-proc card*(s: IntSet): int {.inline.} = 
+proc card*(s: IntSet): int {.inline.} =
   ## alias for `len() <#len>` _.
   result = s.len()
 
@@ -361,7 +367,7 @@ when isMainModule:
   x.incl(1056)
 
   x.incl(1044)
-  x.excl(1044) 
+  x.excl(1044)
 
   assert x.containsOrIncl(888) == false
   assert 888 in x
diff --git a/lib/pure/collections/sequtils.nim b/lib/pure/collections/sequtils.nim
index 511020228..63d910a8e 100644
--- a/lib/pure/collections/sequtils.nim
+++ b/lib/pure/collections/sequtils.nim
@@ -25,6 +25,28 @@ import macros
 when not defined(nimhygiene):
   {.pragma: dirty.}
 
+
+macro evalOnceAs(expAlias, exp: untyped, letAssigneable: static[bool]): untyped =
+  ## Injects ``expAlias`` in caller scope, to avoid bugs involving multiple
+  ##  substitution in macro arguments such as
+  ## https://github.com/nim-lang/Nim/issues/7187
+  ## ``evalOnceAs(myAlias, myExp)`` will behave as ``let myAlias = myExp``
+  ## except when ``letAssigneable`` is false (eg to handle openArray) where
+  ## it just forwards ``exp`` unchanged
+  expectKind(expAlias, nnkIdent)
+  var val = exp
+
+  result = newStmtList()
+  # If `exp` is not a symbol we evaluate it once here and then use the temporary
+  # symbol as alias
+  if exp.kind != nnkSym and letAssigneable:
+    val = genSym()
+    result.add(newLetStmt(val, exp))
+
+  result.add(
+    newProc(name = genSym(nskTemplate, $expAlias), params = [getType(untyped)],
+      body = val, procType = nnkTemplateDef))
+
 proc concat*[T](seqs: varargs[seq[T]]): seq[T] =
   ## Takes several sequences' items and returns them inside a new sequence.
   ##
@@ -161,7 +183,6 @@ proc distribute*[T](s: seq[T], num: Positive, spread = true): seq[seq[T]] =
   ##   assert numbers.distribute(3, false)  == @[@[1, 2, 3], @[4, 5, 6], @[7]]
   ##   assert numbers.distribute(6)[0] == @[1, 2]
   ##   assert numbers.distribute(6)[5] == @[7]
-  assert(not s.isNil, "`s` can't be nil")
   if num < 2:
     result = @[s]
     return
@@ -496,13 +517,17 @@ template toSeq*(iter: untyped): untyped =
   ##         result = true)
   ##   assert odd_numbers == @[1, 3, 5, 7, 9]
 
+  # Note: see also `mapIt` for explanation of some of the implementation
+  # subtleties.
   when compiles(iter.len):
-    var i = 0
-    var result = newSeq[type(iter)](iter.len)
-    for x in iter:
-      result[i] = x
-      inc i
-    result
+    block:
+      evalOnceAs(iter2, iter, true)
+      var result = newSeq[type(iter)](iter2.len)
+      var i = 0
+      for x in iter2:
+        result[i] = x
+        inc i
+      result
   else:
     var result: seq[type(iter)] = @[]
     for x in iter:
@@ -635,8 +660,7 @@ template mapIt*(s, typ, op: untyped): untyped =
     result.add(op)
   result
 
-
-template mapIt*(s, op: untyped): untyped =
+template mapIt*(s: typed, 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
@@ -653,19 +677,24 @@ template mapIt*(s, op: untyped): untyped =
     block:
       var it{.inject.}: type(items(s));
       op))
-  var result: seq[outType]
   when compiles(s.len):
-    let t = s
-    var i = 0
-    result = newSeq[outType](s.len)
-    for it {.inject.} in t:
-      result[i] = op
-      i += 1
+    block: # using a block avoids https://github.com/nim-lang/Nim/issues/8580
+
+      # BUG: `evalOnceAs(s2, s, false)` would lead to C compile errors
+      # (`error: use of undeclared identifier`) instead of Nim compile errors
+      evalOnceAs(s2, s, compiles((let _ = s)))
+
+      var i = 0
+      var result = newSeq[outType](s2.len)
+      for it {.inject.} in s2:
+        result[i] = op
+        i += 1
+      result
   else:
-    result = @[]
+    var result: seq[outType] = @[]
     for it {.inject.} in s:
       result.add(op)
-  result
+    result
 
 template applyIt*(varSeq, op: untyped) =
   ## Convenience template around the mutable ``apply`` proc to reduce typing.
@@ -752,6 +781,14 @@ macro mapLiterals*(constructor, op: untyped;
 
 when isMainModule:
   import strutils
+
+  # helper for testing double substitution side effects which are handled
+  # by `evalOnceAs`
+  var counter = 0
+  proc identity[T](a:T):auto=
+    counter.inc
+    a
+
   block: # concat test
     let
       s1 = @[1, 2, 3]
@@ -854,20 +891,20 @@ when isMainModule:
     doAssert numbers.distribute(6)[0] == @[1, 2]
     doAssert numbers.distribute(6)[5] == @[7]
     let a = @[1, 2, 3, 4, 5, 6, 7]
-    doAssert a.distribute(1, true)   == @[@[1, 2, 3, 4, 5, 6, 7]]
-    doAssert a.distribute(1, false)  == @[@[1, 2, 3, 4, 5, 6, 7]]
-    doAssert a.distribute(2, true)   == @[@[1, 2, 3, 4], @[5, 6, 7]]
-    doAssert a.distribute(2, false)  == @[@[1, 2, 3, 4], @[5, 6, 7]]
-    doAssert a.distribute(3, true)   == @[@[1, 2, 3], @[4, 5], @[6, 7]]
-    doAssert a.distribute(3, false)  == @[@[1, 2, 3], @[4, 5, 6], @[7]]
-    doAssert a.distribute(4, true)   == @[@[1, 2], @[3, 4], @[5, 6], @[7]]
-    doAssert a.distribute(4, false)  == @[@[1, 2], @[3, 4], @[5, 6], @[7]]
-    doAssert a.distribute(5, true)   == @[@[1, 2], @[3, 4], @[5], @[6], @[7]]
-    doAssert a.distribute(5, false)  == @[@[1, 2], @[3, 4], @[5, 6], @[7], @[]]
-    doAssert a.distribute(6, true)   == @[@[1, 2], @[3], @[4], @[5], @[6], @[7]]
-    doAssert a.distribute(6, false)  == @[
+    doAssert a.distribute(1, true) == @[@[1, 2, 3, 4, 5, 6, 7]]
+    doAssert a.distribute(1, false) == @[@[1, 2, 3, 4, 5, 6, 7]]
+    doAssert a.distribute(2, true) == @[@[1, 2, 3, 4], @[5, 6, 7]]
+    doAssert a.distribute(2, false) == @[@[1, 2, 3, 4], @[5, 6, 7]]
+    doAssert a.distribute(3, true) == @[@[1, 2, 3], @[4, 5], @[6, 7]]
+    doAssert a.distribute(3, false) == @[@[1, 2, 3], @[4, 5, 6], @[7]]
+    doAssert a.distribute(4, true) == @[@[1, 2], @[3, 4], @[5, 6], @[7]]
+    doAssert a.distribute(4, false) == @[@[1, 2], @[3, 4], @[5, 6], @[7]]
+    doAssert a.distribute(5, true) == @[@[1, 2], @[3, 4], @[5], @[6], @[7]]
+    doAssert a.distribute(5, false) == @[@[1, 2], @[3, 4], @[5, 6], @[7], @[]]
+    doAssert a.distribute(6, true) == @[@[1, 2], @[3], @[4], @[5], @[6], @[7]]
+    doAssert a.distribute(6, false) == @[
       @[1, 2], @[3, 4], @[5, 6], @[7], @[], @[]]
-    doAssert a.distribute(8, false)  == a.distribute(8, true)
+    doAssert a.distribute(8, false) == a.distribute(8, true)
     doAssert a.distribute(90, false) == a.distribute(90, true)
     var b = @[0]
     for f in 1 .. 25: b.add(f)
@@ -997,6 +1034,12 @@ when isMainModule:
           result = true)
     assert odd_numbers == @[1, 3, 5, 7, 9]
 
+  block:
+    # tests https://github.com/nim-lang/Nim/issues/7187
+    counter = 0
+    let ret = toSeq(@[1, 2, 3].identity().filter(proc (x: int): bool = x < 3))
+    doAssert ret == @[1, 2]
+    doAssert counter == 1
   block: # foldl tests
     let
       numbers = @[5, 9, 11]
@@ -1023,10 +1066,12 @@ when isMainModule:
     assert multiplication == 495, "Multiplication is (5*(9*(11)))"
     assert concatenation == "nimiscool"
 
-  block: # mapIt tests
+  block: # mapIt + applyIt test
+    counter = 0
     var
       nums = @[1, 2, 3, 4]
-      strings = nums.mapIt($(4 * it))
+      strings = nums.identity.mapIt($(4 * it))
+    doAssert counter == 1
     nums.applyIt(it * 3)
     assert nums[0] + nums[3] == 15
     assert strings[2] == "12"
@@ -1044,5 +1089,51 @@ when isMainModule:
     doAssert mapLiterals((1, ("abc"), 2), float, nested=false) == (float(1), "abc", float(2))
     doAssert mapLiterals(([1], ("abc"), 2), `$`, nested=true) == (["1"], "abc", "2")
 
+  block: # mapIt with openArray
+    counter = 0
+    proc foo(x: openArray[int]): seq[int] = x.mapIt(it * 10)
+    doAssert foo([identity(1),identity(2)]) == @[10, 20]
+    doAssert counter == 2
+
+  block: # mapIt with direct openArray
+    proc foo1(x: openArray[int]): seq[int] = x.mapIt(it * 10)
+    counter = 0
+    doAssert foo1(openArray[int]([identity(1),identity(2)])) == @[10,20]
+    doAssert counter == 2
+
+    # Corner cases (openArray litterals should not be common)
+    template foo2(x: openArray[int]): seq[int] = x.mapIt(it * 10)
+    counter = 0
+    doAssert foo2(openArray[int]([identity(1),identity(2)])) == @[10,20]
+    # TODO: this fails; not sure how to fix this case
+    # doAssert counter == 2
+
+    counter = 0
+    doAssert openArray[int]([identity(1), identity(2)]).mapIt(it) == @[1,2]
+    # ditto
+    # doAssert counter == 2
+
+  block: # mapIt empty test, see https://github.com/nim-lang/Nim/pull/8584#pullrequestreview-144723468
+    # NOTE: `[].mapIt(it)` is illegal, just as `let a = @[]` is (lacks type
+    # of elements)
+    doAssert: not compiles(mapIt(@[], it))
+    doAssert: not compiles(mapIt([], it))
+    doAssert newSeq[int](0).mapIt(it) == @[]
+
+  block: # mapIt redifinition check, see https://github.com/nim-lang/Nim/issues/8580
+    let s2 = [1,2].mapIt(it)
+    doAssert s2 == @[1,2]
+
+  block:
+    counter = 0
+    doAssert [1,2].identity().mapIt(it*2).mapIt(it*10) == @[20, 40]
+    # https://github.com/nim-lang/Nim/issues/7187 test case
+    doAssert counter == 1
+
+  block: # mapIt with invalid RHS for `let` (#8566)
+    type X = enum
+      A, B
+    doAssert mapIt(X, $it) == @["A", "B"]
+
   when not defined(testing):
     echo "Finished doc tests"
diff --git a/lib/pure/collections/sets.nim b/lib/pure/collections/sets.nim
index 9e9152fc8..31ca56963 100644
--- a/lib/pure/collections/sets.nim
+++ b/lib/pure/collections/sets.nim
@@ -11,7 +11,7 @@
 ## ordered hash set.
 ##
 ## Hash sets are different from the `built in set type
-## <manual.html#set-type>`_. Sets allow you to store any value that can be
+## <manual.html#types-set-type>`_. Sets allow you to store any value that can be
 ## `hashed <hashes.html>`_ and they don't contain duplicate entries.
 ##
 ## **Note**: The data types declared here have *value semantics*: This means
@@ -74,7 +74,7 @@ proc isValid*[A](s: HashSet[A]): bool =
   ##   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
+  result = s.data.len > 0
 
 proc len*[A](s: HashSet[A]): int =
   ## Returns the number of keys in `s`.
@@ -120,6 +120,13 @@ iterator items*[A](s: HashSet[A]): A =
   for h in 0..high(s.data):
     if isFilled(s.data[h].hcode): yield s.data[h].key
 
+proc hash*[A](s: HashSet[A]): Hash =
+  ## hashing of HashSet
+  assert s.isValid, "The set needs to be initialized."
+  for h in 0..high(s.data):
+    result = result xor s.data[h].hcode
+  result = !$result
+
 const
   growthFactor = 2
 
@@ -340,6 +347,18 @@ proc excl*[A](s: var HashSet[A], other: HashSet[A]) =
   assert other.isValid, "The set `other` needs to be initialized."
   for item in other: discard exclImpl(s, item)
 
+proc pop*[A](s: var HashSet[A]): A =
+  ## Remove and return an arbitrary element from the set `s`.
+  ##
+  ## Raises KeyError if the set `s` is empty.
+  ##
+  for h in 0..high(s.data):
+    if isFilled(s.data[h].hcode):
+      result = s.data[h].key
+      excl(s, result)
+      return result
+  raise newException(KeyError, "set is empty")
+
 proc containsOrIncl*[A](s: var HashSet[A], key: A): bool =
   ## Includes `key` in the set `s` and tells if `key` was added to `s`.
   ##
@@ -635,7 +654,7 @@ proc isValid*[A](s: OrderedSet[A]): bool =
   ##   proc saveTarotCards(cards: OrderedSet[int]) =
   ##     assert cards.isValid, "Pass an initialized set!"
   ##     # Do stuff here, may crash in release builds!
-  result = not s.data.isNil
+  result = s.data.len > 0
 
 proc len*[A](s: OrderedSet[A]): int {.inline.} =
   ## Returns the number of keys in `s`.
@@ -690,6 +709,13 @@ iterator items*[A](s: OrderedSet[A]): A =
   forAllOrderedPairs:
     yield s.data[h].key
 
+proc hash*[A](s: OrderedSet[A]): Hash =
+  ## hashing of OrderedSet
+  assert s.isValid, "The set needs to be initialized."
+  forAllOrderedPairs:
+    result = result !& s.data[h].hcode
+  result = !$result
+
 iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] =
   assert s.isValid, "The set needs to be initialized"
   forAllOrderedPairs:
diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim
index 4f311af87..0292a27a2 100644
--- a/lib/pure/collections/sharedtables.nim
+++ b/lib/pure/collections/sharedtables.nim
@@ -136,11 +136,13 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A,
   ## procedure.
   ##
   ## The ``mapper`` takes 3 arguments:
-  ##   #. ``key`` - the current key, if it exists, or the key passed to
-  ##      ``withKey`` otherwise;
-  ##   #. ``val`` - the current value, if the key exists, or default value
-  ##      of the type otherwise;
-  ##   #. ``pairExists`` - ``true`` if the key exists, ``false`` otherwise.
+  ##
+  ## 1. ``key`` - the current key, if it exists, or the key passed to
+  ##    ``withKey`` otherwise;
+  ## 2. ``val`` - the current value, if the key exists, or default value
+  ##    of the type otherwise;
+  ## 3. ``pairExists`` - ``true`` if the key exists, ``false`` otherwise.
+  ##
   ## The ``mapper`` can can modify ``val`` and ``pairExists`` values to change
   ## the mapping of the key or delete it from the table.
   ## When adding a value, make sure to set ``pairExists`` to ``true`` along
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim
index c97846f92..f85de7546 100644
--- a/lib/pure/collections/tables.nim
+++ b/lib/pure/collections/tables.nim
@@ -158,6 +158,12 @@ template getOrDefaultImpl(t, key): untyped =
   var index = rawGet(t, key, hc)
   if index >= 0: result = t.data[index].val
 
+template getOrDefaultImpl(t, key, default: untyped): untyped =
+  mixin rawGet
+  var hc: Hash
+  var index = rawGet(t, key, hc)
+  result = if index >= 0: t.data[index].val else: default
+
 proc `[]`*[A, B](t: Table[A, B], key: A): B {.deprecatedGet.} =
   ## retrieves the value at ``t[key]``. If `key` is not in `t`, the
   ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether
@@ -175,10 +181,18 @@ proc mget*[A, B](t: var Table[A, B], key: A): var B {.deprecated.} =
   ## instead.
   get(t, key)
 
-proc getOrDefault*[A, B](t: Table[A, B], key: A): B = getOrDefaultImpl(t, key)
+proc getOrDefault*[A, B](t: Table[A, B], key: A): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the
+  ## default initialization value for type `B` is returned (e.g. 0 for any
+  ## integer type).
+  getOrDefaultImpl(t, key)
 
-template withValue*[A, B](t: var Table[A, B], key: A,
-                          value, body: untyped) =
+proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default`
+  ## is returned.
+  getOrDefaultImpl(t, key, default)
+
+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.
   ##
@@ -266,7 +280,7 @@ iterator mvalues*[A, B](t: var Table[A, B]): var B =
     if isFilled(t.data[h].hcode): yield t.data[h].val
 
 proc del*[A, B](t: var Table[A, B], key: A) =
-  ## deletes `key` from hash table `t`.
+  ## deletes `key` from hash table `t`. Does nothing if the key does not exist.
   delImpl()
 
 proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool =
@@ -325,8 +339,7 @@ proc initTable*[A, B](initialSize=64): Table[A, B] =
   result.counter = 0
   newSeq(result.data, initialSize)
 
-proc toTable*[A, B](pairs: openArray[(A,
-                    B)]): Table[A, B] =
+proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] =
   ## creates a new hash table that contains the given `pairs`.
   result = initTable[A, B](rightSize(pairs.len))
   for key, val in items(pairs): result[key] = val
@@ -410,7 +423,16 @@ proc mget*[A, B](t: TableRef[A, B], key: A): var B {.deprecated.} =
   ## Use ```[]``` instead.
   t[][key]
 
-proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = getOrDefault(t[], key)
+proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the
+  ## default initialization value for type `B` is returned (e.g. 0 for any
+  ## integer type).
+  getOrDefault(t[], key)
+
+proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default`
+  ## is returned.
+  getOrDefault(t[], key, default)
 
 proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B =
   ## retrieves value at ``t[key]`` or puts ``val`` if not present, either way
@@ -435,7 +457,7 @@ proc add*[A, B](t: TableRef[A, B], key: A, val: B) =
   t[].add(key, val)
 
 proc del*[A, B](t: TableRef[A, B], key: A) =
-  ## deletes `key` from hash table `t`.
+  ## deletes `key` from hash table `t`. Does nothing if the key does not exist.
   t[].del(key)
 
 proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool =
@@ -562,8 +584,15 @@ proc mget*[A, B](t: var OrderedTable[A, B], key: A): var B {.deprecated.} =
   get(t, key)
 
 proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the
+  ## default initialization value for type `B` is returned (e.g. 0 for any
+  ## integer type).
   getOrDefaultImpl(t, key)
 
+proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default`
+  ## is returned.
+  getOrDefaultImpl(t, key, default)
 
 proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool =
   ## returns true iff `key` is in the table `t`.
@@ -630,8 +659,7 @@ proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] =
   result.last = -1
   newSeq(result.data, initialSize)
 
-proc toOrderedTable*[A, B](pairs: openArray[(A,
-                           B)]): OrderedTable[A, B] =
+proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] =
   ## creates a new ordered hash table that contains the given `pairs`.
   result = initOrderedTable[A, B](rightSize(pairs.len))
   for key, val in items(pairs): result[key] = val
@@ -657,8 +685,7 @@ proc `==`*[A, B](s, t: OrderedTable[A, B]): bool =
     hs = nxts
   return true
 
-proc sort*[A, B](t: var OrderedTable[A, B],
-                 cmp: proc (x,y: (A, B)): int) =
+proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x,y: (A, B)): int) =
   ## sorts `t` according to `cmp`. This modifies the internal list
   ## that kept the insertion order, so insertion order is lost after this
   ## call but key lookup and insertions remain possible after `sort` (in
@@ -748,8 +775,16 @@ proc mget*[A, B](t: OrderedTableRef[A, B], key: A): var B {.deprecated.} =
   result = t[][key]
 
 proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the
+  ## default initialization value for type `B` is returned (e.g. 0 for any
+  ## integer type).
   getOrDefault(t[], key)
 
+proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default`
+  ## is returned.
+  getOrDefault(t[], key, default)
+
 proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B =
   ## retrieves value at ``t[key]`` or puts ``val`` if not present, either way
   ## returning a value which can be modified.
@@ -802,8 +837,7 @@ proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool =
   elif isNil(t): result = false
   else: result = s[] == t[]
 
-proc sort*[A, B](t: OrderedTableRef[A, B],
-                 cmp: proc (x,y: (A, B)): int) =
+proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x,y: (A, B)): int) =
   ## sorts `t` according to `cmp`. This modifies the internal list
   ## that kept the insertion order, so insertion order is lost after this
   ## call but key lookup and insertions remain possible after `sort` (in
@@ -811,7 +845,8 @@ proc sort*[A, B](t: OrderedTableRef[A, B],
   t[].sort(cmp)
 
 proc del*[A, B](t: var OrderedTable[A, B], key: A) =
-  ## deletes `key` from ordered hash table `t`. O(n) complexity.
+  ## deletes `key` from ordered hash table `t`. O(n) complexity. Does nothing
+  ## if the key does not exist.
   var n: OrderedKeyValuePairSeq[A, B]
   newSeq(n, len(t.data))
   var h = t.first
@@ -830,7 +865,8 @@ proc del*[A, B](t: var OrderedTable[A, B], key: A) =
     h = nxt
 
 proc del*[A, B](t: var OrderedTableRef[A, B], key: A) =
-  ## deletes `key` from ordered hash table `t`. O(n) complexity.
+  ## deletes `key` from ordered hash table `t`. O(n) complexity.  Does nothing
+  ## if the key does not exist.
   t[].del(key)
 
 # ------------------------------ count tables -------------------------------
@@ -916,9 +952,17 @@ proc mget*[A](t: var CountTable[A], key: A): var int {.deprecated.} =
   ctget(t, key)
 
 proc getOrDefault*[A](t: CountTable[A], key: A): int =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, 0 (the
+  ## default initialization value of `int`), is returned.
   var index = rawGet(t, key)
   if index >= 0: result = t.data[index].val
 
+proc getOrDefault*[A](t: CountTable[A], key: A, default: int): int =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the
+  ## integer value of `default` is returned.
+  var index = rawGet(t, key)
+  result = if index >= 0: t.data[index].val else: default
+
 proc hasKey*[A](t: CountTable[A], key: A): bool =
   ## returns true iff `key` is in the table `t`.
   result = rawGet(t, key) >= 0
@@ -1073,8 +1117,15 @@ proc mget*[A](t: CountTableRef[A], key: A): var int {.deprecated.} =
   result = t[][key]
 
 proc getOrDefault*[A](t: CountTableRef[A], key: A): int =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, 0 (the
+  ## default initialization value of `int`), is returned.
   result = t[].getOrDefault(key)
 
+proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int =
+  ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the
+  ## integer value of `default` is returned.
+  result = t[].getOrDefault(key, default)
+
 proc hasKey*[A](t: CountTableRef[A], key: A): bool =
   ## returns true iff `key` is in the table `t`.
   result = t[].hasKey(key)
@@ -1267,7 +1318,7 @@ when isMainModule:
     #lib/pure/collections/tables.nim(117, 21) template/generic instantiation from here
     #lib/pure/collections/tableimpl.nim(32, 27) Error: undeclared field: 'hcode
     doAssert 0 == t.getOrDefault(testKey)
-    t.inc(testKey,3)
+    t.inc(testKey, 3)
     doAssert 3 == t.getOrDefault(testKey)
 
   block:
@@ -1278,7 +1329,7 @@ when isMainModule:
     doAssert clearTable[42] == "asd"
     clearTable.clear()
     doAssert(not clearTable.hasKey(123123))
-    doAssert clearTable.getOrDefault(42) == nil
+    doAssert clearTable.getOrDefault(42) == ""
 
   block: #5482
     var a = [("wrong?","foo"), ("wrong?", "foo2")].newOrderedTable()
@@ -1334,3 +1385,21 @@ when isMainModule:
   block: # CountTable.smallest
     let t = toCountTable([0, 0, 5, 5, 5])
     doAssert t.smallest == (0, 2)
+
+  block:
+    var tp: Table[string, string] = initTable[string, string]()
+    doAssert "test1" == tp.getOrDefault("test1", "test1")
+    tp["test2"] = "test2"
+    doAssert "test2" == tp.getOrDefault("test2", "test1")
+    var tr: TableRef[string, string] = newTable[string, string]()
+    doAssert "test1" == tr.getOrDefault("test1", "test1")
+    tr["test2"] = "test2"
+    doAssert "test2" == tr.getOrDefault("test2", "test1")
+    var op: OrderedTable[string, string] = initOrderedTable[string, string]()
+    doAssert "test1" == op.getOrDefault("test1", "test1")
+    op["test2"] = "test2"
+    doAssert "test2" == op.getOrDefault("test2", "test1")
+    var orf: OrderedTableRef[string, string] = newOrderedTable[string, string]()
+    doAssert "test1" == orf.getOrDefault("test1", "test1")
+    orf["test2"] = "test2"
+    doAssert "test2" == orf.getOrDefault("test2", "test1")
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2025-02-19 15:43:34 +0000