diff options
Diffstat (limited to 'lib/pure/collections')
| -rw-r--r-- | lib/pure/collections/deques.nim | 266 | ||||
| -rw-r--r-- | lib/pure/collections/queues.nim | 4 | ||||
| -rw-r--r-- | lib/pure/collections/sequtils.nim | 4 | ||||
| -rw-r--r-- | lib/pure/collections/tableimpl.nim | 14 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 103 |
5 files changed, 357 insertions, 34 deletions
diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim new file mode 100644 index 000000000..c25429778 --- /dev/null +++ b/lib/pure/collections/deques.nim @@ -0,0 +1,266 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2012 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Implementation of a `deque`:idx: (double-ended queue). +## The underlying implementation uses a ``seq``. +## +## None of the procs that get an individual value from the deque can be used +## on an empty deque. +## If compiled with `boundChecks` option, those procs will raise an `IndexError` +## on such access. This should not be relied upon, as `-d:release` will +## disable those checks and may return garbage or crash the program. +## +## As such, a check to see if the deque is empty is needed before any +## access, unless your program logic guarantees it indirectly. +## +## .. code-block:: Nim +## proc foo(a, b: Positive) = # assume random positive values for `a` and `b` +## var deq = initDeque[int]() # initializes the object +## for i in 1 ..< a: deq.addLast i # populates the deque +## +## if b < deq.len: # checking before indexed access +## echo "The element at index position ", b, " is ", deq[b] +## +## # The following two lines don't need any checking on access due to the +## # logic of the program, but that would not be the case if `a` could be 0. +## assert deq.peekFirst == 1 +## assert deq.peekLast == a +## +## while deq.len > 0: # checking if the deque is empty +## echo deq.removeLast() +## +## Note: For inter thread communication use +## a `Channel <channels.html>`_ instead. + +import math + +type + Deque*[T] = object + ## A double-ended queue backed with a ringed seq buffer. + data: seq[T] + head, tail, count, mask: int + +proc initDeque*[T](initialSize: int = 4): Deque[T] = + ## Create a new deque. + ## Optionally, the initial capacity can be reserved via `initialSize` as a + ## performance optimization. The length of a newly created deque will still + ## be 0. + ## + ## `initialSize` needs to be a power of two. If you need to accept runtime + ## values for this you could use the ``nextPowerOfTwo`` proc from the + ## `math <math.html>`_ module. + assert isPowerOfTwo(initialSize) + result.mask = initialSize-1 + newSeq(result.data, initialSize) + +proc len*[T](deq: Deque[T]): int {.inline.} = + ## Return the number of elements of `deq`. + result = deq.count + +template emptyCheck(deq) = + # Bounds check for the regular deque access. + when compileOption("boundChecks"): + if unlikely(deq.count < 1): + raise newException(IndexError, "Empty deque.") + +template xBoundsCheck(deq, i) = + # Bounds check for the array like accesses. + when compileOption("boundChecks"): # d:release should disable this. + if unlikely(i >= deq.count): # x < deq.low is taken care by the Natural parameter + raise newException(IndexError, + "Out of bounds: " & $i & " > " & $(deq.count - 1)) + +proc `[]`*[T](deq: Deque[T], i: Natural) : T {.inline.} = + ## Access the i-th element of `deq` by order from first to last. + ## deq[0] is the first, deq[^1] is the last. + xBoundsCheck(deq, i) + return deq.data[(deq.first + i) and deq.mask] + +proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} = + ## Access the i-th element of `deq` and returns a mutable + ## reference to it. + xBoundsCheck(deq, i) + return deq.data[(deq.head + i) and deq.mask] + +proc `[]=`* [T] (deq: var Deque[T], i: Natural, val : T) {.inline.} = + ## Change the i-th element of `deq`. + xBoundsCheck(deq, i) + deq.data[(deq.head + i) and deq.mask] = val + +iterator items*[T](deq: Deque[T]): T = + ## Yield every element of `deq`. + var i = deq.head + for c in 0 ..< deq.count: + yield deq.data[i] + i = (i + 1) and deq.mask + +iterator mitems*[T](deq: var Deque[T]): var T = + ## Yield every element of `deq`. + var i = deq.head + for c in 0 ..< deq.count: + yield deq.data[i] + i = (i + 1) and deq.mask + +iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] = + ## Yield every (position, value) of `deq`. + var i = deq.head + for c in 0 ..< deq.count: + yield (c, deq.data[i]) + i = (i + 1) and deq.mask + +proc contains*[T](deq: Deque[T], item: T): bool {.inline.} = + ## Return true if `item` is in `deq` or false if not found. Usually used + ## via the ``in`` operator. It is the equivalent of ``deq.find(item) >= 0``. + ## + ## .. code-block:: Nim + ## if x in q: + ## assert q.contains x + for e in deq: + if e == item: return true + return false + +proc expandIfNeeded[T](deq: var Deque[T]) = + var cap = deq.mask + 1 + if unlikely(deq.count >= cap): + var n = newSeq[T](cap * 2) + for i, x in deq: # don't use copyMem because the GC and because it's slower. + shallowCopy(n[i], x) + shallowCopy(deq.data, n) + deq.mask = cap * 2 - 1 + deq.tail = deq.count + deq.head = 0 + +proc addFirst*[T](deq: var Deque[T], item: T) = + ## Add an `item` to the beginning of the `deq`. + expandIfNeeded(deq) + inc deq.count + deq.head = (deq.head - 1) and deq.mask + deq.data[deq.head] = item + +proc addLast*[T](deq: var Deque[T], item: T) = + ## Add an `item` to the end of the `deq`. + expandIfNeeded(deq) + inc deq.count + deq.data[deq.tail] = item + deq.tail = (deq.tail + 1) and deq.mask + +proc peekFirst*[T](deq: Deque[T]): T {.inline.}= + ## Returns the first element of `deq`, but does not remove it from the deque. + emptyCheck(deq) + result = deq.data[deq.head] + +proc peekLast*[T](deq: Deque[T]): T {.inline.} = + ## Returns the last element of `deq`, but does not remove it from the deque. + emptyCheck(deq) + result = deq.data[(deq.tail - 1) and deq.mask] + +proc default[T](t: typedesc[T]): T {.inline.} = discard +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)) + deq.head = (deq.head + 1) and deq.mask + +proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} = + ## Remove and returns the last element of the `deq`. + emptyCheck(deq) + dec deq.count + deq.tail = (deq.tail - 1) and deq.mask + result = deq.data[deq.tail] + deq.data[deq.tail] = default(type(result)) + +proc `$`*[T](deq: Deque[T]): string = + ## Turn a deque into its string representation. + result = "[" + for x in deq: + if result.len > 1: result.add(", ") + result.add($x) + result.add("]") + +when isMainModule: + var deq = initDeque[int](1) + deq.addLast(4) + deq.addFirst(9) + deq.addFirst(123) + var first = deq.popFirst() + deq.addLast(56) + assert(deq.peekLast() == 56) + deq.addLast(6) + assert(deq.peekLast() == 6) + var second = deq.popFirst() + deq.addLast(789) + assert(deq.peekLast() == 789) + + assert first == 123 + assert second == 9 + assert($deq == "[4, 56, 6, 789]") + + assert deq[0] == deq.peekFirst and deq.peekFirst == 4 + assert deq[^1] == deq.peekLast and deq.peekLast == 789 + deq[0] = 42 + deq[^1] = 7 + + assert 6 in deq and 789 notin deq + assert deq.find(6) >= 0 + assert deq.find(789) < 0 + + for i in -2 .. 10: + if i in deq: + assert deq.contains(i) and deq.find(i) >= 0 + else: + assert(not deq.contains(i) and deq.find(i) < 0) + + when compileOption("boundChecks"): + try: + echo deq[99] + assert false + except IndexError: + discard + + try: + assert deq.len == 4 + for i in 0 ..< 5: deq.popFirst() + assert false + except IndexError: + discard + + # grabs some types of resize error. + deq = initDeque[int]() + for i in 1 .. 4: deq.addLast i + deq.popFirst() + deq.popLast() + for i in 5 .. 8: deq.addFirst i + assert $deq == "[8, 7, 6, 5, 2, 3]" + + # Similar to proc from the documentation example + proc foo(a, b: Positive) = # assume random positive values for `a` and `b`. + var deq = initDeque[int]() + assert deq.len == 0 + for i in 1 .. a: deq.addLast i + + if b < deq.len: # checking before indexed access. + assert deq[b] == b + 1 + + # The following two lines don't need any checking on access due to the logic + # of the program, but that would not be the case if `a` could be 0. + assert deq.peekFirst == 1 + assert deq.peekLast == a + + while deq.len > 0: # checking if the deque is empty + assert deq.popFirst() > 0 + + #foo(0,0) + foo(8,5) + foo(10,9) + foo(1,1) + foo(2,1) + foo(1,5) + foo(3,2) \ No newline at end of file diff --git a/lib/pure/collections/queues.nim b/lib/pure/collections/queues.nim index 399e4d413..e4d7eeef1 100644 --- a/lib/pure/collections/queues.nim +++ b/lib/pure/collections/queues.nim @@ -39,8 +39,10 @@ import math +{.warning: "`queues` module is deprecated - use `deques` instead".} + type - Queue*[T] = object ## A queue. + Queue* {.deprecated.} [T] = object ## A queue. data: seq[T] rd, wr, count, mask: int diff --git a/lib/pure/collections/sequtils.nim b/lib/pure/collections/sequtils.nim index f458b7636..45a148fbf 100644 --- a/lib/pure/collections/sequtils.nim +++ b/lib/pure/collections/sequtils.nim @@ -228,7 +228,7 @@ proc apply*[T](data: var seq[T], op: proc (x: var T) {.closure.}) ## var a = @["1", "2", "3", "4"] ## echo repr(a) ## # --> ["1", "2", "3", "4"] - ## map(a, proc(x: var string) = x &= "42") + ## apply(a, proc(x: var string) = x &= "42") ## echo repr(a) ## # --> ["142", "242", "342", "442"] ## @@ -247,7 +247,7 @@ proc apply*[T](data: var seq[T], op: proc (x: T): T {.closure.}) ## var a = @["1", "2", "3", "4"] ## echo repr(a) ## # --> ["1", "2", "3", "4"] - ## map(a, proc(x: string): string = x & "42") + ## apply(a, proc(x: string): string = x & "42") ## echo repr(a) ## # --> ["142", "242", "342", "442"] ## diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim index a3dfd43a1..674fdddd2 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -39,16 +39,22 @@ template rawGetKnownHCImpl() {.dirty.} = h = nextTry(h, maxHash(t)) result = -1 - h # < 0 => MISSING; insert idx = -1 - result -template rawGetImpl() {.dirty.} = +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() template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add - hc = hash(key) - if hc == 0: - hc = 314159265 + genHashImpl(key, hc) var h: Hash = hc and maxHash(t) while isFilled(t.data[h].hcode): h = nextTry(h, maxHash(t)) diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index 778ea5ca3..e6e72d9ed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -224,7 +224,7 @@ template withValue*[A, B](t: var Table[A, B], key: A, iterator allValues*[A, B](t: Table[A, B]; key: A): B = ## iterates over any value in the table `t` that belongs to the given `key`. - var h: Hash = hash(key) and high(t.data) + var h: Hash = genHash(key) and high(t.data) while isFilled(t.data[h].hcode): if t.data[h].key == key: yield t.data[h].val @@ -338,7 +338,7 @@ proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = ## returns true iff `key` is in the table `t`. result = t[].hasKey(key) -template equalsImpl(t) = +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: @@ -348,7 +348,9 @@ template equalsImpl(t) = return true proc `==`*[A, B](s, t: Table[A, B]): bool = - equalsImpl(t) + ## The `==` operator for hash tables. Returns ``true`` iff the content of both + ## tables contains the same key-value pairs. Insert order does not matter. + equalsImpl(s, t) proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = ## Index the collection with the proc provided. @@ -436,9 +438,12 @@ proc `$`*[A, B](t: TableRef[A, B]): string = dollarImpl() proc `==`*[A, B](s, t: TableRef[A, B]): bool = + ## The `==` operator for hash tables. Returns ``true`` iff either both tables + ## are ``nil`` or none is ``nil`` and the content of both tables contains the + ## same key-value pairs. Insert order does not matter. if isNil(s): result = isNil(t) elif isNil(t): result = false - else: equalsImpl(t[]) + else: equalsImpl(s[], t[]) proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = ## Index the collection with the proc provided. @@ -464,13 +469,17 @@ proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = ## returns the number of keys in `t`. result = t.counter -proc clear*[A, B](t: var OrderedTable[A, B] | OrderedTableRef[A, B]) = +proc clear*[A, B](t: var OrderedTable[A, B]) = ## Resets the table so that it is empty. clearImpl() t.first = -1 t.last = -1 -template forAllOrderedPairs(yieldStmt: untyped) {.oldimmediate, dirty.} = +proc clear*[A, B](t: var OrderedTableRef[A, B]) = + ## Resets the table so that is is empty. + clear(t[]) + +template forAllOrderedPairs(yieldStmt: untyped): typed {.dirty.} = var h = t.first while h >= 0: var nxt = t.data[h].next @@ -606,6 +615,15 @@ proc `$`*[A, B](t: OrderedTable[A, B]): string = ## The `$` operator for ordered hash tables. dollarImpl() +proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = + ## The `==` operator for ordered hash tables. Returns true iff both the + ## content and the order are equal. + if s.counter == t.counter: + forAllOrderedPairs: + if s.data[h] != t.data[h]: return false + result = true + else: result = false + 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 @@ -656,13 +674,6 @@ proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = ## returns the number of keys in `t`. result = t.counter -template forAllOrderedPairs(yieldStmt: untyped) {.oldimmediate, dirty.} = - var h = t.first - while h >= 0: - var nxt = t.data[h].next - if isFilled(t.data[h].hcode): yieldStmt - h = nxt - iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## iterates over any (key, value) pair in the table `t` in insertion ## order. @@ -738,7 +749,7 @@ proc newOrderedTable*[A, B](initialSize=64): OrderedTableRef[A, B] = ## values for this you could use the ``nextPowerOfTwo`` proc from the ## `math <math.html>`_ module or the ``rightSize`` proc from this module. new(result) - result[] = initOrderedTable[A, B]() + result[] = initOrderedTable[A, B](initialSize) proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = ## creates a new ordered hash table that contains the given `pairs`. @@ -749,6 +760,14 @@ proc `$`*[A, B](t: OrderedTableRef[A, B]): string = ## The `$` operator for ordered hash tables. dollarImpl() +proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = + ## The `==` operator for ordered hash tables. Returns true iff either both + ## tables are ``nil`` or none is ``nil`` and the content and the order of + ## both are equal. + if isNil(s): result = isNil(t) + elif isNil(t): result = false + else: result = s[] == t[] + 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 @@ -759,20 +778,22 @@ proc sort*[A, B](t: OrderedTableRef[A, B], proc del*[A, B](t: var OrderedTable[A, B], key: A) = ## deletes `key` from ordered hash table `t`. O(n) comlexity. - var prev = -1 - let hc = hash(key) - forAllOrderedPairs: - if t.data[h].hcode == hc: - if t.first == h: - t.first = t.data[h].next + var n: OrderedKeyValuePairSeq[A, B] + newSeq(n, len(t.data)) + var h = t.first + t.first = -1 + t.last = -1 + swap(t.data, n) + let hc = genHash(key) + while h >= 0: + var nxt = n[h].next + if isFilled(n[h].hcode): + if n[h].hcode == hc and n[h].key == key: + dec t.counter else: - t.data[prev].next = t.data[h].next - var zeroValue : type(t.data[h]) - t.data[h] = zeroValue - dec t.counter - break - else: - prev = h + var j = -1 - rawGetKnownHC(t, n[h].key, n[h].hcode) + rawInsert(t, t.data, n[h].key, n[h].val, n[h].hcode, j) + h = nxt proc del*[A, B](t: var OrderedTableRef[A, B], key: A) = ## deletes `key` from ordered hash table `t`. O(n) comlexity. @@ -916,11 +937,17 @@ proc `$`*[A](t: CountTable[A]): string = ## The `$` operator for count tables. dollarImpl() +proc `==`*[A](s, t: CountTable[A]): bool = + ## The `==` operator for count tables. Returns ``true`` iff both tables + ## contain the same keys with the same count. Insert order does not matter. + equalsImpl(s, t) + proc inc*[A](t: var CountTable[A], key: A, val = 1) = ## increments `t[key]` by `val`. 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) @@ -1040,6 +1067,14 @@ proc `$`*[A](t: CountTableRef[A]): string = ## The `$` operator for count tables. dollarImpl() +proc `==`*[A](s, t: CountTableRef[A]): bool = + ## The `==` operator for count tables. Returns ``true`` iff either both tables + ## are ``nil`` or none is ``nil`` and both contain the same keys with the same + ## count. Insert order does not matter. + if isNil(s): result = isNil(t) + elif isNil(t): result = false + else: result = s[] == t[] + proc inc*[A](t: CountTableRef[A], key: A, val = 1) = ## increments `t[key]` by `val`. t[].inc(key, val) @@ -1124,6 +1159,20 @@ when isMainModule: doAssert(prev < i) prev = i + block: # Deletion from OrderedTable should account for collision groups. See issue #5057. + # The bug is reproducible only with exact keys + const key1 = "boy_jackpot.inGamma" + const key2 = "boy_jackpot.outBlack" + + var t = { + key1: 0, + key2: 0 + }.toOrderedTable() + + t.del(key1) + assert(t.len == 1) + assert(key2 in t) + var t1 = initCountTable[string]() t2 = initCountTable[string]() |