diff options
Diffstat (limited to 'lib/pure/collections')
| -rw-r--r-- | lib/pure/collections/hashcommon.nim | 68 | ||||
| -rw-r--r-- | lib/pure/collections/lists.nim | 18 | ||||
| -rw-r--r-- | lib/pure/collections/sequtils.nim | 16 | ||||
| -rw-r--r-- | lib/pure/collections/setimpl.nim | 153 | ||||
| -rw-r--r-- | lib/pure/collections/sets.nim | 473 | ||||
| -rw-r--r-- | lib/pure/collections/sharedtables.nim | 10 | ||||
| -rw-r--r-- | lib/pure/collections/tableimpl.nim | 111 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 271 |
8 files changed, 683 insertions, 437 deletions
diff --git a/lib/pure/collections/hashcommon.nim b/lib/pure/collections/hashcommon.nim new file mode 100644 index 000000000..bbc6d401d --- /dev/null +++ b/lib/pure/collections/hashcommon.nim @@ -0,0 +1,68 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2019 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# An ``include`` file which contains common code for +# hash sets and tables. + +const + growthFactor = 2 + +when not defined(nimHasDefault): + template default[T](t: typedesc[T]): T = + var v: T + v + +# hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These +# two procs retain clarity of that encoding without the space cost of an enum. +proc isEmpty(hcode: Hash): bool {.inline.} = + result = hcode == 0 + +proc isFilled(hcode: Hash): bool {.inline.} = + result = hcode != 0 + +proc nextTry(h, maxHash: Hash): Hash {.inline.} = + result = (h + 1) and maxHash + +proc mustRehash(length, counter: int): bool {.inline.} = + assert(length > counter) + result = (length * 2 < counter * 3) or (length - counter < 4) + +template rawGetKnownHCImpl() {.dirty.} = + if t.dataLen == 0: + return -1 + var h: Hash = hc and maxHash(t) # start with real hash value + while isFilled(t.data[h].hcode): + # Compare hc THEN key with boolean short circuit. This makes the common case + # zero ==key's for missing (e.g.inserts) and exactly one ==key for present. + # It does slow down succeeding lookups by one extra Hash cmp&and..usually + # just a few clock cycles, generally worth it for any non-integer-like A. + if t.data[h].hcode == hc and t.data[h].key == key: + return h + h = nextTry(h, maxHash(t)) + result = -1 - h # < 0 => MISSING; insert idx = -1 - result + +proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} = + rawGetKnownHCImpl() + +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. + +template genHash(key: typed): Hash = + var res: Hash + genHashImpl(key, res) + res + +template rawGetImpl() {.dirty.} = + genHashImpl(key, hc) + rawGetKnownHCImpl() + +proc rawGet[X, A](t: X, key: A, hc: var Hash): int {.inline.} = + rawGetImpl() diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index 1fd32c9fa..2278be218 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -80,14 +80,15 @@ type DoublyLinkedNodeObj*[T] = object ## A node a doubly linked list consists of. ## ## It consists of a `value` field, and pointers to `next` and `prev`. - next*, prev*: ref DoublyLinkedNodeObj[T] + next*: <//>(ref DoublyLinkedNodeObj[T]) + prev*: ref DoublyLinkedNodeObj[T] value*: T DoublyLinkedNode*[T] = ref DoublyLinkedNodeObj[T] SinglyLinkedNodeObj*[T] = object ## A node a singly linked list consists of. ## ## It consists of a `value` field, and a pointer to `next`. - next*: ref SinglyLinkedNodeObj[T] + next*: <//>(ref SinglyLinkedNodeObj[T]) value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] @@ -95,19 +96,22 @@ type ## ## Use `initSinglyLinkedList proc <#initSinglyLinkedList>`_ to create ## a new empty list. - head*, tail*: SinglyLinkedNode[T] + head*: <//>(SinglyLinkedNode[T]) + tail*: SinglyLinkedNode[T] DoublyLinkedList*[T] = object ## A doubly linked list. ## ## Use `initDoublyLinkedList proc <#initDoublyLinkedList>`_ to create ## a new empty list. - head*, tail*: DoublyLinkedNode[T] + head*: <//>(DoublyLinkedNode[T]) + tail*: DoublyLinkedNode[T] SinglyLinkedRing*[T] = object ## A singly linked ring. ## ## Use `initSinglyLinkedRing proc <#initSinglyLinkedRing>`_ to create ## a new empty ring. - head*, tail*: SinglyLinkedNode[T] + head*: <//>(SinglyLinkedNode[T]) + tail*: SinglyLinkedNode[T] DoublyLinkedRing*[T] = object ## A doubly linked ring. ## @@ -147,7 +151,7 @@ proc initDoublyLinkedRing*[T](): DoublyLinkedRing[T] = var a = initDoublyLinkedRing[int]() discard -proc newDoublyLinkedNode*[T](value: T): DoublyLinkedNode[T] = +proc newDoublyLinkedNode*[T](value: T): <//>(DoublyLinkedNode[T]) = ## Creates a new doubly linked node with the given `value`. runnableExamples: var n = newDoublyLinkedNode[int](5) @@ -156,7 +160,7 @@ proc newDoublyLinkedNode*[T](value: T): DoublyLinkedNode[T] = new(result) result.value = value -proc newSinglyLinkedNode*[T](value: T): SinglyLinkedNode[T] = +proc newSinglyLinkedNode*[T](value: T): <//>(SinglyLinkedNode[T]) = ## Creates a new singly linked node with the given `value`. runnableExamples: var n = newSinglyLinkedNode[int](5) diff --git a/lib/pure/collections/sequtils.nim b/lib/pure/collections/sequtils.nim index 253340379..e39c1fb80 100644 --- a/lib/pure/collections/sequtils.nim +++ b/lib/pure/collections/sequtils.nim @@ -949,6 +949,14 @@ macro mapLiterals*(constructor, op: untyped; ## works for nested tuples of arrays of sets etc. result = mapLitsImpl(constructor, op, nested.boolVal) +iterator items*[T](xs: iterator: T): T = + ## iterates over each element yielded by a closure iterator. This may + ## not seem particularly useful on its own, but this allows closure + ## iterators to be used by the the mapIt, filterIt, allIt, anyIt, etc. + ## templates. + for x in xs(): + yield x + when isMainModule: import strutils from algorithm import sorted @@ -1382,5 +1390,13 @@ when isMainModule: doAssert outp == @[@["a", "b"], @["c", "d"]] + block: + proc iter(len: int): auto = + result = iterator(): int = + for i in 0..<len: + yield i + + doAssert: iter(3).mapIt(2*it).foldl(a + b) == 6 + when not defined(testing): echo "Finished doc tests" diff --git a/lib/pure/collections/setimpl.nim b/lib/pure/collections/setimpl.nim new file mode 100644 index 000000000..eb131b540 --- /dev/null +++ b/lib/pure/collections/setimpl.nim @@ -0,0 +1,153 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2019 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# An ``include`` file for the different hash set implementations. + + +template maxHash(t): untyped = high(t.data) +template dataLen(t): untyped = len(t.data) + +include hashcommon + +template initImpl(s: typed, size: int) = + assert isPowerOfTwo(size) + when s is OrderedSet: + s.first = -1 + s.last = -1 + s.counter = 0 + newSeq(s.data, size) + +template rawInsertImpl() {.dirty.} = + if data.len == 0: + initImpl(s, defaultInitialSize) + data[h].key = key + data[h].hcode = hc + +proc rawInsert[A](s: var HashSet[A], data: var KeyValuePairSeq[A], key: A, + hc: Hash, h: Hash) = + rawInsertImpl() + +proc enlarge[A](s: var HashSet[A]) = + var n: KeyValuePairSeq[A] + newSeq(n, len(s.data) * growthFactor) + swap(s.data, n) # n is now old seq + for i in countup(0, high(n)): + if isFilled(n[i].hcode): + var j = -1 - rawGetKnownHC(s, n[i].key, n[i].hcode) + rawInsert(s, s.data, n[i].key, n[i].hcode, j) + +template inclImpl() {.dirty.} = + if s.data.len == 0: + initImpl(s, defaultInitialSize) + var hc: Hash + var index = rawGet(s, key, hc) + if index < 0: + if mustRehash(len(s.data), s.counter): + enlarge(s) + index = rawGetKnownHC(s, key, hc) + rawInsert(s, s.data, key, hc, -1 - index) + inc(s.counter) + +template containsOrInclImpl() {.dirty.} = + if s.data.len == 0: + initImpl(s, defaultInitialSize) + var hc: Hash + var index = rawGet(s, key, hc) + if index >= 0: + result = true + else: + if mustRehash(len(s.data), s.counter): + enlarge(s) + index = rawGetKnownHC(s, key, hc) + rawInsert(s, s.data, key, hc, -1 - index) + inc(s.counter) + +template doWhile(a, b) = + while true: + b + if not a: break + +proc exclImpl[A](s: var HashSet[A], key: A) : bool {. inline .} = + var hc: Hash + var i = rawGet(s, key, hc) + var msk = high(s.data) + result = true + + if i >= 0: + result = false + 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 + 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 + r = s.data[i].hcode and msk # "home" location of key@i + shallowCopy(s.data[j], s.data[i]) # data[i] will be marked EMPTY next loop + +template dollarImpl() {.dirty.} = + result = "{" + for key in items(s): + if result.len > 1: result.add(", ") + result.addQuoted(key) + result.add("}") + + + +# --------------------------- OrderedSet ------------------------------ + +proc rawGet[A](t: OrderedSet[A], key: A, hc: var Hash): int {.inline.} = + rawGetImpl() + +proc rawInsert[A](s: var OrderedSet[A], data: var OrderedKeyValuePairSeq[A], + key: A, hc: Hash, h: Hash) = + rawInsertImpl() + data[h].next = -1 + if s.first < 0: s.first = h + if s.last >= 0: data[s.last].next = h + s.last = h + +proc enlarge[A](s: var OrderedSet[A]) = + var n: OrderedKeyValuePairSeq[A] + newSeq(n, len(s.data) * growthFactor) + var h = s.first + s.first = -1 + s.last = -1 + swap(s.data, n) + while h >= 0: + var nxt = n[h].next + if isFilled(n[h].hcode): + var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) + rawInsert(s, s.data, n[h].key, n[h].hcode, j) + h = nxt + +proc exclImpl[A](s: var OrderedSet[A], key: A) : bool {.inline.} = + if len(s.data) == 0: + return true + var n: OrderedKeyValuePairSeq[A] + newSeq(n, len(s.data)) + var h = s.first + s.first = -1 + s.last = -1 + swap(s.data, n) + let hc = genHash(key) + result = true + while h >= 0: + var nxt = n[h].next + if isFilled(n[h].hcode): + if n[h].hcode == hc and n[h].key == key: + dec s.counter + result = false + else: + var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) + rawInsert(s, s.data, n[h].key, n[h].hcode, j) + h = nxt diff --git a/lib/pure/collections/sets.nim b/lib/pure/collections/sets.nim index 29bf31f96..86a72533e 100644 --- a/lib/pure/collections/sets.nim +++ b/lib/pure/collections/sets.nim @@ -26,7 +26,7 @@ ## `symmetric difference <#symmetricDifference,HashSet[A],HashSet[A]>`_ ## ## .. code-block:: -## echo toHashSet([9, 5, 1]) # {9, 1, 5} +## echo toHashSet([9, 5, 1]) # {9, 1, 5} ## echo toOrderedSet([9, 5, 1]) # {9, 5, 1} ## ## let @@ -69,148 +69,32 @@ type data: KeyValuePairSeq[A] counter: int +type + OrderedKeyValuePair[A] = tuple[ + hcode: Hash, next: int, key: A] + OrderedKeyValuePairSeq[A] = seq[OrderedKeyValuePair[A]] + OrderedSet* {.myShallow.} [A] = object ## \ + ## A generic hash set that remembers insertion order. + ## + ## Use `init proc <#init,OrderedSet[A],int>`_ or `initOrderedSet proc + ## <#initOrderedSet,int>`_ before calling other procs on it. + data: OrderedKeyValuePairSeq[A] + counter, first, last: int -# ---------------------- helpers ----------------------------------- - -const growthFactor = 2 - -when not defined(nimHasDefault): - template default[T](t: typedesc[T]): T = - ## Used by clear methods to get a default value. - var v: T - v - -# hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These -# two procs retain clarity of that encoding without the space cost of an enum. -proc isEmpty(hcode: Hash): bool {.inline.} = - result = hcode == 0 - -proc isFilled(hcode: Hash): bool {.inline.} = - result = hcode != 0 - -proc nextTry(h, maxHash: Hash): Hash {.inline.} = - result = (h + 1) and maxHash - -template rawGetKnownHCImpl() {.dirty.} = - var h: Hash = hc and high(s.data) # start with real hash value - while isFilled(s.data[h].hcode): - # Compare hc THEN key with boolean short circuit. This makes the common case - # zero ==key's for missing (e.g.inserts) and exactly one ==key for present. - # It does slow down succeeding lookups by one extra Hash cmp&and..usually - # just a few clock cycles, generally worth it for any non-integer-like A. - if s.data[h].hcode == hc and s.data[h].key == key: # compare hc THEN key - return h - h = nextTry(h, high(s.data)) - result = -1 - h # < 0 => MISSING; insert idx = -1 - result - -template genHash(key: typed): Hash = - var 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. - hc - -template rawGetImpl() {.dirty.} = - hc = genHash(key) - rawGetKnownHCImpl() - -template rawInsertImpl() {.dirty.} = - data[h].key = key - data[h].hcode = hc - -proc rawGetKnownHC[A](s: HashSet[A], key: A, hc: Hash): int {.inline.} = - rawGetKnownHCImpl() - -proc rawGet[A](s: HashSet[A], key: A, hc: var Hash): int {.inline.} = - rawGetImpl() - -proc rawInsert[A](s: var HashSet[A], data: var KeyValuePairSeq[A], key: A, - hc: Hash, h: Hash) = - rawInsertImpl() - -proc enlarge[A](s: var HashSet[A]) = - var n: KeyValuePairSeq[A] - newSeq(n, len(s.data) * growthFactor) - swap(s.data, n) # n is now old seq - for i in countup(0, high(n)): - if isFilled(n[i].hcode): - var j = -1 - rawGetKnownHC(s, n[i].key, n[i].hcode) - rawInsert(s, s.data, n[i].key, n[i].hcode, j) - -template inclImpl() {.dirty.} = - var hc: Hash - var index = rawGet(s, key, hc) - if index < 0: - if mustRehash(len(s.data), s.counter): - enlarge(s) - index = rawGetKnownHC(s, key, hc) - rawInsert(s, s.data, key, hc, -1 - index) - inc(s.counter) - -template containsOrInclImpl() {.dirty.} = - var hc: Hash - var index = rawGet(s, key, hc) - if index >= 0: - result = true - else: - if mustRehash(len(s.data), s.counter): - enlarge(s) - index = rawGetKnownHC(s, key, hc) - rawInsert(s, s.data, key, hc, -1 - index) - inc(s.counter) - -template doWhile(a, b) = - while true: - b - if not a: break - -proc exclImpl[A](s: var HashSet[A], key: A) : bool {. inline .} = - assert s.isValid, "The set needs to be initialized." - var hc: Hash - var i = rawGet(s, key, hc) - var msk = high(s.data) - result = true +const + defaultInitialSize* = 64 - if i >= 0: - result = false - 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 - 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 - r = s.data[i].hcode and msk # "home" location of key@i - shallowCopy(s.data[j], s.data[i]) # data[i] will be marked EMPTY next loop - -proc mustRehash(length, counter: int): bool {.inline.} = - assert(length > counter) - result = (length * 2 < counter * 3) or (length - counter < 4) - -template dollarImpl() {.dirty.} = - result = "{" - for key in items(s): - if result.len > 1: result.add(", ") - result.addQuoted(key) - result.add("}") +include setimpl proc rightSize*(count: Natural): int {.inline.} - - - - - - # --------------------------------------------------------------------- # ------------------------------ HashSet ------------------------------ # --------------------------------------------------------------------- -proc init*[A](s: var HashSet[A], initialSize=64) = +proc init*[A](s: var HashSet[A], initialSize = defaultInitialSize) = ## Initializes a hash set. ## ## The `initialSize` parameter needs to be a power of two (default: 64). @@ -218,9 +102,8 @@ proc init*[A](s: var HashSet[A], initialSize=64) = ## `math.nextPowerOfTwo proc <math.html#nextPowerOfTwo>`_ or `rightSize proc ## <#rightSize,Natural>`_ from this module. ## - ## All set variables must be initialized before - ## use with other procs from this module, with the exception of `isValid proc - ## <#isValid,HashSet[A]>`_ and `len() <#len,HashSet[A]>`_. + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. ## ## You can call this proc on a previously initialized hash set, which will ## discard all its values. This might be more convenient than iterating over @@ -235,42 +118,26 @@ proc init*[A](s: var HashSet[A], initialSize=64) = init(a) assert a.isValid - assert isPowerOfTwo(initialSize) - s.counter = 0 - newSeq(s.data, initialSize) + initImpl(s, initialSize) -proc initHashSet*[A](initialSize=64): HashSet[A] = +proc initHashSet*[A](initialSize = defaultInitialSize): HashSet[A] = ## Wrapper around `init proc <#init,HashSet[A],int>`_ for initialization of ## hash sets. ## ## Returns an empty hash set you can assign directly in ``var`` blocks in a ## single line. ## + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toHashSet proc <#toHashSet,openArray[A]>`_ runnableExamples: var a = initHashSet[int]() - assert a.isValid a.incl(3) assert len(a) == 1 - result.init(initialSize) -proc isValid*[A](s: HashSet[A]): bool = - ## Returns `true` if the set has been initialized (with `initHashSet proc - ## <#initHashSet,int>`_ or `init proc <#init,HashSet[A],int>`_). - ## - ## Most operations over an uninitialized set will crash at runtime and - ## `assert <system.html#assert>`_ in debug builds. You can use this proc in - ## your own procs to verify that sets passed to your procs are correctly - ## initialized. - ## - ## **Examples:** - ## - ## .. code-block :: - ## proc savePreferences(options: HashSet[string]) = - ## assert options.isValid, "Pass an initialized set!" - ## # Do stuff here, may crash in release builds! - result = s.data.len > 0 + result.init(initialSize) proc `[]`*[A](s: var HashSet[A], key: A): var A = ## Returns the element that is actually stored in `s` which has the same @@ -278,7 +145,6 @@ proc `[]`*[A](s: var HashSet[A], key: A): var A = ## ## This is useful when one overloaded `hash` and `==` but still needs ## reference semantics for sharing. - assert s.isValid, "The set needs to be initialized." var hc: Hash var index = rawGet(s, key, hc) if index >= 0: result = s.data[index].key @@ -305,7 +171,6 @@ proc contains*[A](s: HashSet[A], key: A): bool = assert values.contains(2) assert 2 in values - assert s.isValid, "The set needs to be initialized." var hc: Hash var index = rawGet(s, key, hc) result = index >= 0 @@ -325,7 +190,6 @@ proc incl*[A](s: var HashSet[A], key: A) = values.incl(2) assert values.len == 1 - assert s.isValid, "The set needs to be initialized." inclImpl() proc incl*[A](s: var HashSet[A], other: HashSet[A]) = @@ -344,8 +208,6 @@ proc incl*[A](s: var HashSet[A], other: HashSet[A]) = values.incl(others) assert values.len == 5 - assert s.isValid, "The set `s` needs to be initialized." - assert other.isValid, "The set `other` needs to be initialized." for item in other: incl(s, item) proc toHashSet*[A](keys: openArray[A]): HashSet[A] = @@ -368,14 +230,6 @@ proc toHashSet*[A](keys: openArray[A]): HashSet[A] = result = initHashSet[A](rightSize(keys.len)) for key in items(keys): result.incl(key) -proc initSet*[A](initialSize=64): HashSet[A] {.deprecated: - "Deprecated since v0.20, use `initHashSet`"} = initHashSet[A](initialSize) - ## Deprecated since v0.20, use `initHashSet`. - -proc toSet*[A](keys: openArray[A]): HashSet[A] {.deprecated: - "Deprecated since v0.20, use `toHashSet`"} = toHashSet[A](keys) - ## Deprecated since v0.20, use `toHashSet`. - iterator items*[A](s: HashSet[A]): A = ## Iterates over elements of the set `s`. ## @@ -395,8 +249,7 @@ iterator items*[A](s: HashSet[A]): A = ## assert a.len == 2 ## echo b ## # --> {(a: 1, b: 3), (a: 0, b: 4)} - assert s.isValid, "The set needs to be initialized." - for h in 0..high(s.data): + for h in 0 .. high(s.data): if isFilled(s.data[h].hcode): yield s.data[h].key proc containsOrIncl*[A](s: var HashSet[A], key: A): bool = @@ -417,7 +270,6 @@ proc containsOrIncl*[A](s: var HashSet[A], key: A): bool = assert values.containsOrIncl(2) == true assert values.containsOrIncl(3) == false - assert s.isValid, "The set needs to be initialized." containsOrInclImpl() proc excl*[A](s: var HashSet[A], key: A) = @@ -434,6 +286,7 @@ proc excl*[A](s: var HashSet[A], key: A) = s.excl(2) s.excl(2) assert s.len == 3 + discard exclImpl(s, key) proc excl*[A](s: var HashSet[A], other: HashSet[A]) = @@ -453,8 +306,6 @@ proc excl*[A](s: var HashSet[A], other: HashSet[A]) = assert len(numbers) == 3 ## numbers == {1, 3, 5} - assert s.isValid, "The set `s` needs to be initialized." - assert other.isValid, "The set `other` needs to be initialized." for item in other: discard exclImpl(s, item) proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = @@ -474,6 +325,7 @@ proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = assert s.missingOrExcl(4) == true assert s.missingOrExcl(6) == false assert s.missingOrExcl(6) == true + exclImpl(s, key) proc pop*[A](s: var HashSet[A]): A = @@ -489,7 +341,7 @@ proc pop*[A](s: var HashSet[A]): A = assert s.pop == 2 doAssertRaises(KeyError, echo s.pop) - for h in 0..high(s.data): + for h in 0 .. high(s.data): if isFilled(s.data[h].hcode): result = s.data[h].key excl(s, result) @@ -510,7 +362,7 @@ proc clear*[A](s: var HashSet[A]) = assert len(s) == 0 s.counter = 0 - for i in 0..<s.data.len: + for i in 0 ..< s.data.len: s.data[i].hcode = 0 s.data[i].key = default(type(s.data[i].key)) @@ -525,6 +377,7 @@ proc len*[A](s: HashSet[A]): int = assert len(a) == 0 let s = toHashSet([3, 5, 7]) assert len(s) == 3 + result = s.counter proc card*[A](s: HashSet[A]): int = @@ -554,8 +407,6 @@ proc union*[A](s1, s2: HashSet[A]): HashSet[A] = c = union(a, b) assert c == toHashSet(["a", "b", "c"]) - assert s1.isValid, "The set `s1` needs to be initialized." - assert s2.isValid, "The set `s2` needs to be initialized." result = s1 incl(result, s2) @@ -579,9 +430,7 @@ proc intersection*[A](s1, s2: HashSet[A]): HashSet[A] = c = intersection(a, b) assert c == toHashSet(["b"]) - assert s1.isValid, "The set `s1` needs to be initialized." - assert s2.isValid, "The set `s2` needs to be initialized." - result = initHashSet[A](min(s1.data.len, s2.data.len)) + result = initHashSet[A](max(min(s1.data.len, s2.data.len), 2)) for item in s1: if item in s2: incl(result, item) @@ -604,8 +453,6 @@ proc difference*[A](s1, s2: HashSet[A]): HashSet[A] = c = difference(a, b) assert c == toHashSet(["a"]) - assert s1.isValid, "The set `s1` needs to be initialized." - assert s2.isValid, "The set `s2` needs to be initialized." result = initHashSet[A]() for item in s1: if not contains(s2, item): @@ -631,8 +478,6 @@ proc symmetricDifference*[A](s1, s2: HashSet[A]): HashSet[A] = c = symmetricDifference(a, b) assert c == toHashSet(["a", "c"]) - assert s1.isValid, "The set `s1` needs to be initialized." - assert s2.isValid, "The set `s2` needs to be initialized." result = s1 for item in s2: if containsOrIncl(result, item): excl(result, item) @@ -663,8 +508,6 @@ proc disjoint*[A](s1, s2: HashSet[A]): bool = assert disjoint(a, b) == false assert disjoint(a, b - a) == true - assert s1.isValid, "The set `s1` needs to be initialized." - assert s2.isValid, "The set `s2` needs to be initialized." for item in s1: if item in s2: return false return true @@ -681,6 +524,7 @@ proc `<`*[A](s, t: HashSet[A]): bool = c = intersection(a, b) assert c < a and c < b assert(not (a < a)) + s.counter != t.counter and s <= t proc `<=`*[A](s, t: HashSet[A]): bool = @@ -711,6 +555,7 @@ proc `==`*[A](s, t: HashSet[A]): bool = a = toHashSet([1, 2]) b = toHashSet([2, 1]) assert a == b + s.counter == t.counter and s <= t proc map*[A, B](data: HashSet[A], op: proc (x: A): B {.closure.}): HashSet[B] = @@ -729,8 +574,7 @@ proc map*[A, B](data: HashSet[A], op: proc (x: A): B {.closure.}): HashSet[B] = 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): + for h in 0 .. high(s.data): result = result xor s.data[h].hcode result = !$result @@ -747,7 +591,6 @@ proc `$`*[A](s: HashSet[A]): string = ## # --> {2, 4, 5} ## echo toHashSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} - assert s.isValid, "The set needs to be initialized." dollarImpl() proc rightSize*(count: Natural): int {.inline.} = @@ -760,8 +603,28 @@ proc rightSize*(count: Natural): int {.inline.} = result = nextPowerOfTwo(count * 3 div 2 + 4) +proc initSet*[A](initialSize = defaultInitialSize): HashSet[A] {.deprecated: + "Deprecated since v0.20, use `initHashSet`"} = initHashSet[A](initialSize) + ## Deprecated since v0.20, use `initHashSet <#initHashSet,int>`_. +proc toSet*[A](keys: openArray[A]): HashSet[A] {.deprecated: + "Deprecated since v0.20, use `toHashSet`"} = toHashSet[A](keys) + ## Deprecated since v0.20, use `toHashSet <#toHashSet,openArray[A]>`_. +proc isValid*[A](s: HashSet[A]): bool {.deprecated: + "Deprecated since v0.20; sets are initialized by default"} = + ## **Deprecated since v0.20; sets are initialized by default** + ## + ## Returns `true` if the set has been initialized (with `initHashSet proc + ## <#initHashSet,int>`_ or `init proc <#init,HashSet[A],int>`_). + ## + ## **Examples:** + ## + ## .. code-block :: + ## proc savePreferences(options: HashSet[string]) = + ## assert options.isValid, "Pass an initialized set!" + ## # Do stuff here, may crash in release builds! + result = s.data.len > 0 @@ -769,89 +632,19 @@ proc rightSize*(count: Natural): int {.inline.} = # --------------------------- OrderedSet ------------------------------ # --------------------------------------------------------------------- -type - OrderedKeyValuePair[A] = tuple[ - hcode: Hash, next: int, key: A] - OrderedKeyValuePairSeq[A] = seq[OrderedKeyValuePair[A]] - OrderedSet* {.myShallow.} [A] = object ## \ - ## A generic hash set that remembers insertion order. - ## - ## Use `init proc <#init,OrderedSet[A],int>`_ or `initOrderedSet proc - ## <#initOrderedSet,int>`_ before calling other procs on it. - data: OrderedKeyValuePairSeq[A] - counter, first, last: int - - -# ---------------------- helpers ----------------------------------- - template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} = - var h = s.first - var idx = 0 - while h >= 0: - var nxt = s.data[h].next - if isFilled(s.data[h].hcode): - yieldStmt - inc(idx) - h = nxt - -proc rawGetKnownHC[A](s: OrderedSet[A], key: A, hc: Hash): int {.inline.} = - rawGetKnownHCImpl() - -proc rawGet[A](s: OrderedSet[A], key: A, hc: var Hash): int {.inline.} = - rawGetImpl() - -proc rawInsert[A](s: var OrderedSet[A], data: var OrderedKeyValuePairSeq[A], - key: A, hc: Hash, h: Hash) = - rawInsertImpl() - data[h].next = -1 - if s.first < 0: s.first = h - if s.last >= 0: data[s.last].next = h - s.last = h - -proc enlarge[A](s: var OrderedSet[A]) = - var n: OrderedKeyValuePairSeq[A] - newSeq(n, len(s.data) * growthFactor) - var h = s.first - s.first = -1 - s.last = -1 - swap(s.data, n) - while h >= 0: - var nxt = n[h].next - if isFilled(n[h].hcode): - var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) - rawInsert(s, s.data, n[h].key, n[h].hcode, j) - h = nxt - -proc isValid*[A](s: OrderedSet[A]): bool - -proc exclImpl[A](s: var OrderedSet[A], key: A) : bool {. inline .} = - assert s.isValid, "The set needs to be initialized." - var n: OrderedKeyValuePairSeq[A] - newSeq(n, len(s.data)) - var h = s.first - s.first = -1 - s.last = -1 - swap(s.data, n) - let hc = genHash(key) - result = true - while h >= 0: - var nxt = n[h].next - if isFilled(n[h].hcode): - if n[h].hcode == hc and n[h].key == key: - dec s.counter - result = false - else: - var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) - rawInsert(s, s.data, n[h].key, n[h].hcode, j) - h = nxt - - - -# ----------------------------------------------------------------------- - - - -proc init*[A](s: var OrderedSet[A], initialSize=64) = + if s.data.len > 0: + var h = s.first + var idx = 0 + while h >= 0: + var nxt = s.data[h].next + if isFilled(s.data[h].hcode): + yieldStmt + inc(idx) + h = nxt + + +proc init*[A](s: var OrderedSet[A], initialSize = defaultInitialSize) = ## Initializes an ordered hash set. ## ## The `initialSize` parameter needs to be a power of two (default: 64). @@ -859,9 +652,8 @@ proc init*[A](s: var OrderedSet[A], initialSize=64) = ## `math.nextPowerOfTwo proc <math.html#nextPowerOfTwo>`_ or `rightSize proc ## <#rightSize,Natural>`_ from this module. ## - ## All set variables must be initialized before - ## use with other procs from this module, with the exception of `isValid proc - ## <#isValid,HashSet[A]>`_ and `len() <#len,HashSet[A]>`_. + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. ## ## You can call this proc on a previously initialized hash set, which will ## discard all its values. This might be more convenient than iterating over @@ -876,26 +668,25 @@ proc init*[A](s: var OrderedSet[A], initialSize=64) = init(a) assert a.isValid - assert isPowerOfTwo(initialSize) - s.counter = 0 - s.first = -1 - s.last = -1 - newSeq(s.data, initialSize) + initImpl(s, initialSize) -proc initOrderedSet*[A](initialSize=64): OrderedSet[A] = +proc initOrderedSet*[A](initialSize = defaultInitialSize): OrderedSet[A] = ## Wrapper around `init proc <#init,OrderedSet[A],int>`_ for initialization of ## ordered hash sets. ## ## Returns an empty ordered hash set you can assign directly in ``var`` blocks ## in a single line. ## + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toOrderedSet proc <#toOrderedSet,openArray[A]>`_ runnableExamples: var a = initOrderedSet[int]() - assert a.isValid a.incl(3) assert len(a) == 1 + result.init(initialSize) proc toOrderedSet*[A](keys: openArray[A]): OrderedSet[A] = @@ -918,23 +709,6 @@ proc toOrderedSet*[A](keys: openArray[A]): OrderedSet[A] = result = initOrderedSet[A](rightSize(keys.len)) for key in items(keys): result.incl(key) -proc isValid*[A](s: OrderedSet[A]): bool = - ## Returns `true` if the set has been initialized (with `initHashSet proc - ## <#initOrderedSet,int>`_ or `init proc <#init,OrderedSet[A],int>`_). - ## - ## Most operations over an uninitialized set will crash at runtime and - ## `assert <system.html#assert>`_ in debug builds. You can use this proc in - ## your own procs to verify that sets passed to your procs are correctly - ## initialized. - ## - ## **Examples:** - ## - ## .. code-block :: - ## proc savePreferences(options: OrderedSet[string]) = - ## assert options.isValid, "Pass an initialized set!" - ## # Do stuff here, may crash in release builds! - result = s.data.len > 0 - proc contains*[A](s: OrderedSet[A], key: A): bool = ## Returns true if `key` is in `s`. ## @@ -952,7 +726,6 @@ proc contains*[A](s: OrderedSet[A], key: A): bool = assert values.contains(2) assert 2 in values - assert s.isValid, "The set needs to be initialized." var hc: Hash var index = rawGet(s, key, hc) result = index >= 0 @@ -972,7 +745,6 @@ proc incl*[A](s: var OrderedSet[A], key: A) = values.incl(2) assert values.len == 1 - assert s.isValid, "The set needs to be initialized." inclImpl() proc incl*[A](s: var HashSet[A], other: OrderedSet[A]) = @@ -988,8 +760,7 @@ proc incl*[A](s: var HashSet[A], other: OrderedSet[A]) = others = toOrderedSet([3, 4, 5]) values.incl(others) assert values.len == 5 - assert s.isValid, "The set `s` needs to be initialized." - assert other.isValid, "The set `other` needs to be initialized." + for item in items(other): incl(s, item) proc containsOrIncl*[A](s: var OrderedSet[A], key: A): bool = @@ -1009,7 +780,6 @@ proc containsOrIncl*[A](s: var OrderedSet[A], key: A): bool = assert values.containsOrIncl(2) == true assert values.containsOrIncl(3) == false - assert s.isValid, "The set needs to be initialized." containsOrInclImpl() proc excl*[A](s: var OrderedSet[A], key: A) = @@ -1025,6 +795,7 @@ proc excl*[A](s: var OrderedSet[A], key: A) = s.excl(2) s.excl(2) assert s.len == 3 + discard exclImpl(s, key) proc missingOrExcl*[A](s: var OrderedSet[A], key: A): bool = @@ -1044,6 +815,7 @@ proc missingOrExcl*[A](s: var OrderedSet[A], key: A): bool = assert s.missingOrExcl(4) == true assert s.missingOrExcl(6) == false assert s.missingOrExcl(6) == true + exclImpl(s, key) proc clear*[A](s: var OrderedSet[A]) = @@ -1059,7 +831,7 @@ proc clear*[A](s: var OrderedSet[A]) = s.counter = 0 s.first = -1 s.last = -1 - for i in 0..<s.data.len: + for i in 0 ..< s.data.len: s.data[i].hcode = 0 s.data[i].next = 0 s.data[i].key = default(type(s.data[i].key)) @@ -1075,6 +847,7 @@ proc len*[A](s: OrderedSet[A]): int {.inline.} = assert len(a) == 0 let s = toHashSet([3, 5, 7]) assert len(s) == 3 + result = s.counter proc card*[A](s: OrderedSet[A]): int {.inline.} = @@ -1110,7 +883,6 @@ proc `==`*[A](s, t: OrderedSet[A]): bool = 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 @@ -1129,7 +901,6 @@ proc `$`*[A](s: OrderedSet[A]): string = ## # --> {2, 4, 5} ## echo toOrderedSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} - assert s.isValid, "The set needs to be initialized." dollarImpl() @@ -1152,11 +923,9 @@ iterator items*[A](s: OrderedSet[A]): A = ## # --> Got 5 ## # --> Got 8 ## # --> Got 4 - assert s.isValid, "The set needs to be initialized." forAllOrderedPairs: yield s.data[h].key - iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = ## Iterates through (position, value) tuples of OrderedSet `s`. runnableExamples: @@ -1166,12 +935,27 @@ iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = p.add(x) assert p == @[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'c'), (4, 'd')] - assert s.isValid, "The set needs to be initialized" forAllOrderedPairs: yield (idx, s.data[h].key) +proc isValid*[A](s: OrderedSet[A]): bool {.deprecated: + "Deprecated since v0.20; sets are initialized by default"} = + ## **Deprecated since v0.20; sets are initialized by default** + ## + ## Returns `true` if the set has been initialized (with `initHashSet proc + ## <#initOrderedSet,int>`_ or `init proc <#init,OrderedSet[A],int>`_). + ## + ## **Examples:** + ## + ## .. code-block :: + ## proc savePreferences(options: OrderedSet[string]) = + ## assert options.isValid, "Pass an initialized set!" + ## # Do stuff here, may crash in release builds! + result = s.data.len > 0 + + # ----------------------------------------------------------------------- @@ -1179,7 +963,7 @@ iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = when isMainModule and not defined(release): proc testModule() = ## Internal micro test to validate docstrings and such. - block isValidTest: + block isValidTest: # isValid is deprecated var options: HashSet[string] proc savePreferences(options: HashSet[string]) = assert options.isValid, "Pass an initialized set!" @@ -1280,7 +1064,7 @@ when isMainModule and not defined(release): var b = a.map(proc (x: int): string = $x) assert b == toHashSet(["1", "2", "3"]) - block isValidTest: + block isValidTest: # isValid is deprecated var cards: OrderedSet[string] proc saveTarotCards(cards: OrderedSet[string]) = assert cards.isValid, "Pass an initialized set!" @@ -1393,6 +1177,69 @@ when isMainModule and not defined(release): bb.incl(y) assert aa == bb + block setsWithoutInit: + var + a: HashSet[int] + b: HashSet[int] + c: HashSet[int] + d: HashSet[int] + e: HashSet[int] + + doAssert a.containsOrIncl(3) == false + doAssert a.contains(3) + doAssert a.len == 1 + doAssert a.containsOrIncl(3) + a.incl(3) + doAssert a.len == 1 + a.incl(6) + doAssert a.len == 2 + + b.incl(5) + doAssert b.len == 1 + b.excl(5) + b.excl(c) + doAssert b.missingOrExcl(5) + doAssert b.disjoint(c) + + d = b + c + doAssert d.len == 0 + d = b * c + doAssert d.len == 0 + d = b - c + doAssert d.len == 0 + d = b -+- c + doAssert d.len == 0 + + doAssert (d < e) == false + doAssert d <= e + doAssert d == e + + block setsWithoutInit: + var + a: OrderedSet[int] + b: OrderedSet[int] + c: OrderedSet[int] + d: HashSet[int] + + + doAssert a.containsOrIncl(3) == false + doAssert a.contains(3) + doAssert a.len == 1 + doAssert a.containsOrIncl(3) + a.incl(3) + doAssert a.len == 1 + a.incl(6) + doAssert a.len == 2 + + b.incl(5) + doAssert b.len == 1 + doAssert b.missingOrExcl(5) == false + doAssert b.missingOrExcl(5) + + doAssert c.missingOrExcl(9) + d.incl(c) + doAssert d.len == 0 + when not defined(testing): echo "Micro tests run successfully." diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim index 0292a27a2..6ebb00e57 100644 --- a/lib/pure/collections/sharedtables.nim +++ b/lib/pure/collections/sharedtables.nim @@ -29,6 +29,14 @@ template maxHash(t): untyped = t.dataLen-1 include tableimpl +template st_maybeRehashPutImpl(enlarge) {.dirty.} = + if mustRehash(t.dataLen, t.counter): + enlarge(t) + index = rawGetKnownHC(t, key, hc) + index = -1 - index # important to transform for mgetOrPutImpl + rawInsert(t, t.data, key, val, hc, index) + inc(t.counter) + proc enlarge[A, B](t: var SharedTable[A, B]) = let oldSize = t.dataLen let size = oldSize * growthFactor @@ -176,7 +184,7 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, var val: B mapper(key, val, pairExists) if pairExists: - maybeRehashPutImpl(enlarge) + st_maybeRehashPutImpl(enlarge) proc `[]=`*[A, B](t: var SharedTable[A, B], key: A, val: B) = ## puts a (key, value)-pair into `t`. diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim index 3e34b1488..4f9610db3 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -9,49 +9,7 @@ # An ``include`` file for the different table implementations. -# hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These -# two procs retain clarity of that encoding without the space cost of an enum. -proc isEmpty(hcode: Hash): bool {.inline.} = - result = hcode == 0 - -proc isFilled(hcode: Hash): bool {.inline.} = - result = hcode != 0 - -const - growthFactor = 2 - -proc mustRehash(length, counter: int): bool {.inline.} = - assert(length > counter) - result = (length * 2 < counter * 3) or (length - counter < 4) - -proc nextTry(h, maxHash: Hash): Hash {.inline.} = - result = (h + 1) and maxHash - -template rawGetKnownHCImpl() {.dirty.} = - var h: Hash = hc and maxHash(t) # start with real hash value - while isFilled(t.data[h].hcode): - # Compare hc THEN key with boolean short circuit. This makes the common case - # zero ==key's for missing (e.g.inserts) and exactly one ==key for present. - # It does slow down succeeding lookups by one extra Hash cmp&and..usually - # just a few clock cycles, generally worth it for any non-integer-like A. - if t.data[h].hcode == hc and t.data[h].key == key: - return h - h = nextTry(h, maxHash(t)) - result = -1 - h # < 0 => MISSING; insert idx = -1 - result - -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. - -template genHash(key: typed): Hash = - var res: Hash - genHashImpl(key, res) - res - -template rawGetImpl() {.dirty.} = - genHashImpl(key, hc) - rawGetKnownHCImpl() +include hashcommon template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add genHashImpl(key, hc) @@ -65,20 +23,16 @@ template rawInsertImpl() {.dirty.} = data[h].val = val data[h].hcode = hc -proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} = - rawGetKnownHCImpl() - proc rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline.} = rawGetDeepImpl() -proc rawGet[X, A](t: X, key: A, hc: var Hash): int {.inline.} = - rawGetImpl() - 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.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) if mustRehash(t.dataLen, t.counter): enlarge(t) var hc: Hash var j = rawGetDeep(t, key, hc) @@ -86,6 +40,8 @@ template addImpl(enlarge) {.dirty.} = inc(t.counter) template maybeRehashPutImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) if mustRehash(t.dataLen, t.counter): enlarge(t) index = rawGetKnownHC(t, key, hc) @@ -94,12 +50,16 @@ template maybeRehashPutImpl(enlarge) {.dirty.} = inc(t.counter) template putImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) var hc: Hash var index = rawGet(t, key, hc) if index >= 0: t.data[index].val = val else: maybeRehashPutImpl(enlarge) template mgetOrPutImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) var hc: Hash var index = rawGet(t, key, hc) if index < 0: @@ -109,6 +69,8 @@ template mgetOrPutImpl(enlarge) {.dirty.} = result = t.data[index].val template hasKeyOrPutImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) var hc: Hash var index = rawGet(t, key, hc) if index < 0: @@ -116,11 +78,6 @@ template hasKeyOrPutImpl(enlarge) {.dirty.} = maybeRehashPutImpl(enlarge) else: result = true -when not defined(nimHasDefault): - template default[T](t: typedesc[T]): T = - var v: T - v - template delImplIdx(t, i) = let msk = maxHash(t) if i >= 0: @@ -150,9 +107,53 @@ template delImpl() {.dirty.} = delImplIdx(t, i) template clearImpl() {.dirty.} = - for i in 0 ..< t.data.len: + 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(type(t.data[i].key)) t.data[i].val = default(type(t.data[i].val)) t.counter = 0 + +template initImpl(result: typed, size: int) = + assert isPowerOfTwo(size) + result.counter = 0 + newSeq(result.data, size) + +template insertImpl() = # for CountTable + if t.dataLen == 0: initImpl(t, defaultInitialSize) + if mustRehash(len(t.data), t.counter): enlarge(t) + ctRawInsert(t, t.data, key, val) + inc(t.counter) + +template getOrDefaultImpl(t, key): untyped = + mixin rawGet + var hc: Hash + 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 + +template dollarImpl(): untyped {.dirty.} = + if t.len == 0: + result = "{:}" + else: + result = "{" + for key, val in pairs(t): + if result.len > 1: result.add(", ") + result.addQuoted(key) + result.add(": ") + result.addQuoted(val) + result.add("}") + +template equalsImpl(s, t: typed): typed = + 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: + if not t.hasKey(key): return false + if t.getOrDefault(key) != val: return false + return true diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index c6d5cc9e2..98ece4779 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -19,7 +19,7 @@ ## For consistency with every other data type in Nim these have **value** ## semantics, this means that ``=`` performs a copy of the hash table. ## -## For `ref semantics<manual.html#types-ref-and-pointer-types>`_ +## For `ref semantics<manual.html#types-reference-and-pointer-types>`_ ## use their ``Ref`` variants: `TableRef<#TableRef>`_, ## `OrderedTableRef<#OrderedTableRef>`_, and `CountTableRef<#CountTableRef>`_. ## @@ -237,9 +237,13 @@ type ## For creating a new empty TableRef, use `newTable proc ## <#newTable,int>`_. +const + defaultInitialSize* = 64 # ------------------------------ helpers --------------------------------- +# Do NOT move these to tableimpl.nim, because sharedtables uses that +# file and has its own implementation. template maxHash(t): untyped = high(t.data) template dataLen(t): untyped = len(t.data) @@ -260,30 +264,6 @@ template get(t, key): untyped = else: raise newException(KeyError, "key not found") -template getOrDefaultImpl(t, key): untyped = - mixin rawGet - var hc: Hash - 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 - -template dollarImpl(): untyped {.dirty.} = - if t.len == 0: - result = "{:}" - else: - result = "{" - for key, val in pairs(t): - if result.len > 1: result.add(", ") - result.addQuoted(key) - result.add(": ") - result.addQuoted(val) - result.add("}") - proc enlarge[A, B](t: var Table[A, B]) = var n: KeyValuePairSeq[A, B] newSeq(n, len(t.data) * growthFactor) @@ -294,16 +274,8 @@ proc enlarge[A, B](t: var Table[A, B]) = var j: Hash = eh and maxHash(t) while isFilled(t.data[j].hcode): j = nextTry(j, maxHash(t)) - rawInsert(t, t.data, n[i].key, n[i].val, eh, j) + rawInsert(t, t.data, move n[i].key, move n[i].val, eh, j) -template equalsImpl(s, t: typed): typed = - 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: - if not t.hasKey(key): return false - if t.getOrDefault(key) != val: return false - return true @@ -311,7 +283,7 @@ template equalsImpl(s, t: typed): typed = # ------------------------------ Table ------------------------------ # ------------------------------------------------------------------- -proc initTable*[A, B](initialSize=64): Table[A, B] = +proc initTable*[A, B](initialsize = defaultInitialSize): Table[A, B] = ## Creates a new hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -320,6 +292,9 @@ proc initTable*[A, B](initialSize=64): Table[A, B] = ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ ## from this module. ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toTable proc<#toTable,openArray[]>`_ ## * `newTable proc<#newTable,int>`_ for creating a `TableRef` @@ -327,9 +302,7 @@ proc initTable*[A, B](initialSize=64): Table[A, B] = let a = initTable[int, string]() b = initTable[char, seq[int]]() - assert isPowerOfTwo(initialSize) - result.counter = 0 - newSeq(result.data, initialSize) + initImpl(result, initialSize) proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = ## Creates a new hash table that contains the given ``pairs``. @@ -343,6 +316,7 @@ proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = let a = [('a', 5), ('b', 9)] let b = toTable(a) assert b == {'a': 5, 'b': 9}.toTable + result = initTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result[key] = val @@ -398,6 +372,7 @@ proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.toTable + putImpl(enlarge) proc hasKey*[A, B](t: Table[A, B], key: A): bool = @@ -414,6 +389,7 @@ proc hasKey*[A, B](t: Table[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + var hc: Hash result = rawGet(t, key, hc) >= 0 @@ -424,6 +400,7 @@ proc contains*[A, B](t: Table[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = @@ -443,6 +420,7 @@ proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.toTable + hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: Table[A, B], key: A): B = @@ -461,6 +439,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 + getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = @@ -478,6 +457,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 + getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = @@ -497,6 +477,7 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.toTable + mgetOrPutImpl(enlarge) proc len*[A, B](t: Table[A, B]): int = @@ -504,6 +485,7 @@ proc len*[A, B](t: Table[A, B]): int = runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: var Table[A, B], key: A, val: B) = @@ -527,6 +509,7 @@ proc del*[A, B](t: var Table[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.toTable a.del('z') doAssert a == {'b': 9, 'c': 13}.toTable + delImpl() proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool = @@ -568,6 +551,7 @@ proc clear*[A, B](t: var Table[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clearImpl() proc `$`*[A, B](t: Table[A, B]): string = @@ -583,6 +567,7 @@ proc `==`*[A, B](s, t: Table[A, B]): bool = a = {'a': 5, 'b': 9, 'c': 13}.toTable b = {'b': 9, 'c': 13, 'a': 5}.toTable doAssert a == b + equalsImpl(s, t) proc rightSize*(count: Natural): int {.inline.} = @@ -692,6 +677,7 @@ iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.toTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) @@ -709,6 +695,7 @@ iterator keys*[A, B](t: Table[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key @@ -726,6 +713,7 @@ iterator values*[A, B](t: Table[A, B]): B = }.toTable for v in a.values: doAssert v.len == 4 + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -744,6 +732,7 @@ iterator mvalues*[A, B](t: var Table[A, B]): var B = for v in a.mvalues: v.add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -779,7 +768,7 @@ iterator allValues*[A, B](t: Table[A, B]; key: A): B = # ------------------------------------------------------------------- -proc newTable*[A, B](initialSize=64): TableRef[A, B] = +proc newTable*[A, B](initialsize = defaultInitialSize): <//>TableRef[A, B] = ## Creates a new ref hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -796,10 +785,11 @@ proc newTable*[A, B](initialSize=64): TableRef[A, B] = let a = newTable[int, string]() b = newTable[char, seq[int]]() + new(result) result[] = initTable[A, B](initialSize) -proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = +proc newTable*[A, B](pairs: openArray[(A, B)]): <//>TableRef[A, B] = ## Creates a new ref hash table that contains the given ``pairs``. ## ## ``pairs`` is a container consisting of ``(key, value)`` tuples. @@ -811,10 +801,11 @@ proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = let a = [('a', 5), ('b', 9)] let b = newTable(a) assert b == {'a': 5, 'b': 9}.newTable + new(result) result[] = toTable[A, B](pairs) -proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = +proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): <//>TableRef[C, B] = ## Index the collection with the proc provided. # TODO: As soon as supported, change collection: A to collection: A[B] result = newTable[C, B]() @@ -842,6 +833,7 @@ proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] + result = t[][key] proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: B) = @@ -857,6 +849,7 @@ proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.newTable + t[][key] = val proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = @@ -874,6 +867,7 @@ proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + result = t[].hasKey(key) proc contains*[A, B](t: TableRef[A, B], key: A): bool = @@ -883,6 +877,7 @@ proc contains*[A, B](t: TableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = @@ -902,6 +897,7 @@ proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.newTable + t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = @@ -920,6 +916,7 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = let a = {'a': 5, 'b': 9}.newTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 + getOrDefault(t[], key) proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = @@ -937,6 +934,7 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.newTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 + getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = @@ -956,6 +954,7 @@ proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.newTable + t[].mgetOrPut(key, val) proc len*[A, B](t: TableRef[A, B]): int = @@ -963,6 +962,7 @@ proc len*[A, B](t: TableRef[A, B]): int = runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: TableRef[A, B], key: A, val: B) = @@ -988,6 +988,7 @@ proc del*[A, B](t: TableRef[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.newTable a.del('z') doAssert a == {'b': 9, 'c': 13}.newTable + t[].del(key) proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool = @@ -1012,6 +1013,7 @@ proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool = doAssert a.take('z', i) == false doAssert a == {'a': 5, 'c': 13}.newTable doAssert i == 0 + result = t[].take(key, val) proc clear*[A, B](t: TableRef[A, B]) = @@ -1025,6 +1027,7 @@ proc clear*[A, B](t: TableRef[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clearImpl() proc `$`*[A, B](t: TableRef[A, B]): string = @@ -1041,6 +1044,7 @@ proc `==`*[A, B](s, t: TableRef[A, B]): bool = a = {'a': 5, 'b': 9, 'c': 13}.newTable b = {'b': 9, 'c': 13, 'a': 5}.newTable doAssert a == b + if isNil(s): result = isNil(t) elif isNil(t): result = false else: equalsImpl(s[], t[]) @@ -1089,6 +1093,7 @@ iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.newTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) @@ -1106,6 +1111,7 @@ iterator keys*[A, B](t: TableRef[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key @@ -1123,6 +1129,7 @@ iterator values*[A, B](t: TableRef[A, B]): B = }.newTable for v in a.values: doAssert v.len == 4 + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -1140,6 +1147,7 @@ iterator mvalues*[A, B](t: TableRef[A, B]): var B = for v in a.mvalues: v.add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -1218,7 +1226,7 @@ template forAllOrderedPairs(yieldStmt: untyped): typed {.dirty.} = # ---------------------------------------------------------------------- -proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = +proc initOrderedTable*[A, B](initialsize = defaultInitialSize): OrderedTable[A, B] = ## Creates a new ordered hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -1227,6 +1235,9 @@ proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ ## from this module. ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_ ## * `newOrderedTable proc<#newOrderedTable,int>`_ for creating an @@ -1235,11 +1246,9 @@ proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = let a = initOrderedTable[int, string]() b = initOrderedTable[char, seq[int]]() - assert isPowerOfTwo(initialSize) - result.counter = 0 + initImpl(result, initialSize) result.first = -1 result.last = -1 - newSeq(result.data, initialSize) proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = ## Creates a new ordered hash table that contains the given ``pairs``. @@ -1254,6 +1263,7 @@ proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = let a = [('a', 5), ('b', 9)] let b = toOrderedTable(a) assert b == {'a': 5, 'b': 9}.toOrderedTable + result = initOrderedTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result[key] = val @@ -1278,6 +1288,7 @@ proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B = doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] + get(t, key) proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B= @@ -1309,6 +1320,7 @@ proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.toOrderedTable + putImpl(enlarge) proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = @@ -1326,6 +1338,7 @@ proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + var hc: Hash result = rawGet(t, key, hc) >= 0 @@ -1336,6 +1349,7 @@ proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = @@ -1355,6 +1369,7 @@ proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.toOrderedTable + hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = @@ -1373,6 +1388,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 + getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = @@ -1390,6 +1406,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 + getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = @@ -1409,6 +1426,7 @@ proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.toOrderedTable + mgetOrPutImpl(enlarge) proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = @@ -1416,6 +1434,7 @@ proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: var OrderedTable[A, B], key: A, val: B) = @@ -1440,6 +1459,7 @@ proc del*[A, B](t: var OrderedTable[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.toOrderedTable a.del('z') doAssert a == {'b': 9, 'c': 13}.toOrderedTable + var n: OrderedKeyValuePairSeq[A, B] newSeq(n, len(t.data)) var h = t.first @@ -1467,6 +1487,7 @@ proc clear*[A, B](t: var OrderedTable[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clearImpl() t.first = -1 t.last = -1 @@ -1602,6 +1623,7 @@ iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'o': @[1, 5, 7, 9, 11], 'e': @[2, 4, 6, 8, 12]}.toOrderedTable + forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) @@ -1619,6 +1641,7 @@ iterator keys*[A, B](t: OrderedTable[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.toOrderedTable + forAllOrderedPairs: yield t.data[h].key @@ -1636,6 +1659,7 @@ iterator values*[A, B](t: OrderedTable[A, B]): B = }.toOrderedTable for v in a.values: doAssert v.len == 4 + forAllOrderedPairs: yield t.data[h].val @@ -1666,7 +1690,7 @@ iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = # --------------------------- OrderedTableRef ------------------------------- # --------------------------------------------------------------------------- -proc newOrderedTable*[A, B](initialSize=64): OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](initialsize = defaultInitialSize): <//>OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -1687,7 +1711,7 @@ proc newOrderedTable*[A, B](initialSize=64): OrderedTableRef[A, B] = new(result) result[] = initOrderedTable[A, B](initialSize) -proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): <//>OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that contains the given ``pairs``. ## ## ``pairs`` is a container consisting of ``(key, value)`` tuples. @@ -1700,6 +1724,7 @@ proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = let a = [('a', 5), ('b', 9)] let b = newOrderedTable(a) assert b == {'a': 5, 'b': 9}.newOrderedTable + result = newOrderedTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result.add(key, val) @@ -1740,6 +1765,7 @@ proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.newOrderedTable + t[][key] = val proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = @@ -1757,6 +1783,7 @@ proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + result = t[].hasKey(key) proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = @@ -1766,6 +1793,7 @@ proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = @@ -1785,6 +1813,7 @@ proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.newOrderedTable + result = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = @@ -1803,6 +1832,7 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 + getOrDefault(t[], key) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = @@ -1820,6 +1850,7 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 + getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = @@ -1839,6 +1870,7 @@ proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.newOrderedTable + result = t[].mgetOrPut(key, val) proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = @@ -1846,6 +1878,7 @@ proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = @@ -1868,6 +1901,7 @@ proc del*[A, B](t: var OrderedTableRef[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.newOrderedTable a.del('z') doAssert a == {'b': 9, 'c': 13}.newOrderedTable + t[].del(key) proc clear*[A, B](t: var OrderedTableRef[A, B]) = @@ -1880,6 +1914,7 @@ proc clear*[A, B](t: var OrderedTableRef[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clear(t[]) proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x,y: (A, B)): int, order = SortOrder.Ascending) = @@ -1899,6 +1934,7 @@ proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x,y: (A, B)): int, order = doAssert a == {'a': 10, 'b': 20, 'c': 0}.newOrderedTable a.sort(system.cmp, order=SortOrder.Descending) doAssert a == {'c': 0, 'b': 20, 'a': 10}.newOrderedTable + t[].sort(cmp, order=order) proc `$`*[A, B](t: OrderedTableRef[A, B]): string = @@ -1915,6 +1951,7 @@ proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable b = {'b': 9, 'c': 13, 'a': 5}.newOrderedTable doAssert a != b + if isNil(s): result = isNil(t) elif isNil(t): result = false else: result = s[] == t[] @@ -1964,6 +2001,7 @@ iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'o': @[1, 5, 7, 9, 11], 'e': @[2, 4, 6, 8, 12]}.newOrderedTable + forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) @@ -1981,6 +2019,7 @@ iterator keys*[A, B](t: OrderedTableRef[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.newOrderedTable + forAllOrderedPairs: yield t.data[h].key @@ -1998,6 +2037,7 @@ iterator values*[A, B](t: OrderedTableRef[A, B]): B = }.newOrderedTable for v in a.values: doAssert v.len == 4 + forAllOrderedPairs: yield t.data[h].val @@ -2016,6 +2056,7 @@ iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B = for v in a.mvalues: v.add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.newOrderedTable + forAllOrderedPairs: yield t.data[h].val @@ -2046,7 +2087,7 @@ type # ------------------------------ helpers --------------------------------- -proc rawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], +proc ctRawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], key: A, val: int) = var h: Hash = hash(key) and high(data) while data[h].val != 0: h = nextTry(h, high(data)) @@ -2057,10 +2098,12 @@ proc enlarge[A](t: var CountTable[A]) = var n: seq[tuple[key: A, val: int]] newSeq(n, len(t.data) * growthFactor) for i in countup(0, high(t.data)): - if t.data[i].val != 0: rawInsert(t, n, t.data[i].key, t.data[i].val) + if t.data[i].val != 0: ctRawInsert(t, n, t.data[i].key, t.data[i].val) swap(t.data, n) proc rawGet[A](t: CountTable[A], key: A): int = + if t.data.len == 0: + return -1 var h: Hash = hash(key) and high(t.data) # start with real hash value while t.data[h].val != 0: if t.data[h].key == key: return h @@ -2075,7 +2118,7 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) # ---------------------------------------------------------------------- -proc initCountTable*[A](initialSize=64): CountTable[A] = +proc initCountTable*[A](initialsize = defaultInitialSize): CountTable[A] = ## Creates a new count table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -2084,13 +2127,14 @@ proc initCountTable*[A](initialSize=64): CountTable[A] = ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ ## from this module. ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toCountTable proc<#toCountTable,openArray[A]>`_ ## * `newCountTable proc<#newCountTable,int>`_ for creating a ## `CountTableRef` - assert isPowerOfTwo(initialSize) - result.counter = 0 - newSeq(result.data, initialSize) + initImpl(result, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = ## Creates a new count table with every member of a container ``keys`` @@ -2130,9 +2174,7 @@ proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = if h >= 0: t.data[h].val = val else: - if mustRehash(len(t.data), t.counter): enlarge(t) - rawInsert(t, t.data, key, val) - inc(t.counter) + insertImpl() proc inc*[A](t: var CountTable[A], key: A, val = 1) = ## Increments ``t[key]`` by ``val`` (default: 1). @@ -2141,14 +2183,13 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) = a.inc('a') a.inc('b', 10) doAssert a == toCountTable("aaabbbbbbbbbbb") + var index = rawGet(t, key) if index >= 0: inc(t.data[index].val, val) if t.data[index].val == 0: dec(t.counter) else: - if mustRehash(len(t.data), t.counter): enlarge(t) - rawInsert(t, t.data, key, val) - inc(t.counter) + insertImpl() proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) @@ -2229,6 +2270,7 @@ proc sort*[A](t: var CountTable[A], order = SortOrder.Descending) = doAssert toSeq(a.values) == @[5, 2, 2, 1, 1] a.sort(SortOrder.Ascending) doAssert toSeq(a.values) == @[1, 1, 2, 2, 5] + t.data.sort(cmp=ctCmp, order=order) proc merge*[A](s: var CountTable[A], t: CountTable[A]) = @@ -2238,6 +2280,7 @@ proc merge*[A](s: var CountTable[A], t: CountTable[A]) = let b = toCountTable("bcc") a.merge(b) doAssert a == toCountTable("aaabbbccc") + for key, value in t: s.inc(key, value) @@ -2248,6 +2291,7 @@ proc merge*[A](s, t: CountTable[A]): CountTable[A] = a = toCountTable("aaabbc") b = toCountTable("bcc") doAssert merge(a, b) == toCountTable("aaabbbccc") + result = initCountTable[A](nextPowerOfTwo(max(s.len, t.len))) for table in @[s, t]: for key, value in table: @@ -2306,6 +2350,7 @@ iterator mpairs*[A](t: var CountTable[A]): (A, var int) = for k, v in mpairs(a): v = 2 doAssert a == toCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) @@ -2320,6 +2365,7 @@ iterator keys*[A](t: CountTable[A]): A = for k in keys(a): a[k] = 2 doAssert a == toCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].key @@ -2334,6 +2380,7 @@ iterator values*[A](t: CountTable[A]): int = let a = toCountTable("abracadabra") for v in values(a): assert v < 10 + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2349,6 +2396,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = for v in mvalues(a): v = 2 doAssert a == toCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2364,7 +2412,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = proc inc*[A](t: CountTableRef[A], key: A, val = 1) -proc newCountTable*[A](initialSize=64): CountTableRef[A] = +proc newCountTable*[A](initialsize = defaultInitialSize): <//>CountTableRef[A] = ## Creates a new ref count table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -2381,7 +2429,7 @@ proc newCountTable*[A](initialSize=64): CountTableRef[A] = new(result) result[] = initCountTable[A](initialSize) -proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = +proc newCountTable*[A](keys: openArray[A]): <//>CountTableRef[A] = ## Creates a new ref count table with every member of a container ``keys`` ## having a count of how many times it occurs in that container. result = newCountTable[A](rightSize(keys.len)) @@ -2493,6 +2541,7 @@ proc merge*[A](s, t: CountTableRef[A]) = b = newCountTable("bcc") a.merge(b) doAssert a == newCountTable("aaabbbccc") + s[].merge(t[]) proc `$`*[A](t: CountTableRef[A]): string = @@ -2551,6 +2600,7 @@ iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = for k, v in mpairs(a): v = 2 doAssert a == newCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) @@ -2565,6 +2615,7 @@ iterator keys*[A](t: CountTableRef[A]): A = for k in keys(a): a[k] = 2 doAssert a == newCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].key @@ -2579,6 +2630,7 @@ iterator values*[A](t: CountTableRef[A]): int = let a = newCountTable("abracadabra") for v in values(a): assert v < 10 + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2593,6 +2645,7 @@ iterator mvalues*[A](t: CountTableRef[A]): var int = for v in mvalues(a): v = 2 doAssert a == newCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2813,3 +2866,99 @@ when isMainModule: doAssert "test1" == orf.getOrDefault("test1", "test1") orf["test2"] = "test2" doAssert "test2" == orf.getOrDefault("test2", "test1") + + block tableWithoutInit: + var + a: Table[string, int] + b: Table[string, int] + c: Table[string, int] + d: Table[string, int] + e: Table[string, int] + + a["a"] = 7 + doAssert a.hasKey("a") + doAssert a.len == 1 + doAssert a["a"] == 7 + a["a"] = 9 + doAssert a.len == 1 + doAssert a["a"] == 9 + + doAssert b.hasKeyOrPut("b", 5) == false + doAssert b.hasKey("b") + doAssert b.hasKeyOrPut("b", 8) + doAssert b["b"] == 5 + + doAssert c.getOrDefault("a") == 0 + doAssert c.getOrDefault("a", 3) == 3 + c["a"] = 6 + doAssert c.getOrDefault("a", 3) == 6 + + doAssert d.mgetOrPut("a", 3) == 3 + doAssert d.mgetOrPut("a", 6) == 3 + + var x = 99 + doAssert e.take("a", x) == false + doAssert x == 99 + e["a"] = 77 + doAssert e.take("a", x) + doAssert x == 77 + + block orderedTableWithoutInit: + var + a: OrderedTable[string, int] + b: OrderedTable[string, int] + c: OrderedTable[string, int] + d: OrderedTable[string, int] + + a["a"] = 7 + doAssert a.hasKey("a") + doAssert a.len == 1 + doAssert a["a"] == 7 + a["a"] = 9 + doAssert a.len == 1 + doAssert a["a"] == 9 + + doAssert b.hasKeyOrPut("b", 5) == false + doAssert b.hasKey("b") + doAssert b.hasKeyOrPut("b", 8) + doAssert b["b"] == 5 + + doAssert c.getOrDefault("a") == 0 + doAssert c.getOrDefault("a", 3) == 3 + c["a"] = 6 + doAssert c.getOrDefault("a", 3) == 6 + + doAssert d.mgetOrPut("a", 3) == 3 + doAssert d.mgetOrPut("a", 6) == 3 + + block countTableWithoutInit: + var + a: CountTable[string] + b: CountTable[string] + c: CountTable[string] + d: CountTable[string] + e: CountTable[string] + + a["a"] = 7 + doAssert a.hasKey("a") + doAssert a.len == 1 + doAssert a["a"] == 7 + a["a"] = 9 + doAssert a.len == 1 + doAssert a["a"] == 9 + + doAssert b["b"] == 0 + b.inc("b") + doAssert b["b"] == 1 + + doAssert c.getOrDefault("a") == 0 + doAssert c.getOrDefault("a", 3) == 3 + c["a"] = 6 + doAssert c.getOrDefault("a", 3) == 6 + + e["f"] = 3 + merge(d, e) + doAssert d.hasKey("f") + d.inc("f") + merge(d, e) + doAssert d["f"] == 7 |