diff options
Diffstat (limited to 'lib/pure/collections')
| -rw-r--r-- | lib/pure/collections/deques.nim | 121 | ||||
| -rw-r--r-- | lib/pure/collections/hashcommon.nim | 5 | ||||
| -rw-r--r-- | lib/pure/collections/heapqueue.nim | 15 | ||||
| -rw-r--r-- | lib/pure/collections/lists.nim | 26 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 5 |
5 files changed, 118 insertions, 54 deletions
diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim index b07138e84..d2b0099f2 100644 --- a/lib/pure/collections/deques.nim +++ b/lib/pure/collections/deques.nim @@ -50,7 +50,7 @@ runnableExamples: import std/private/since -import std/math +import std/[assertions, hashes, math] type Deque*[T] = object @@ -59,20 +59,29 @@ type ## To initialize an empty deque, ## use the `initDeque proc <#initDeque,int>`_. data: seq[T] - head, tail, count, mask: int + + # `head` and `tail` are masked only when accessing an element of `data` + # so that `tail - head == data.len` when the deque is full. + # They are uint so that incrementing/decrementing them doesn't cause + # over/underflow. You can get a number of items with `tail - head` + # even if `tail` or `head` is wraps around and `tail < head`, because + # `tail - head == (uint.high + 1 + tail) - head` when `tail < head`. + head, tail: uint const defaultInitialSize* = 4 template initImpl(result: typed, initialSize: int) = let correctSize = nextPowerOfTwo(initialSize) - result.mask = correctSize - 1 newSeq(result.data, correctSize) template checkIfInitialized(deq: typed) = - if deq.mask == 0: + if deq.data.len == 0: initImpl(deq, defaultInitialSize) +func mask[T](deq: Deque[T]): uint {.inline.} = + uint(deq.data.len) - 1 + proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] = ## Creates a new empty deque. ## @@ -85,22 +94,22 @@ proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] = ## * `toDeque proc <#toDeque,openArray[T]>`_ result.initImpl(initialSize) -proc len*[T](deq: Deque[T]): int {.inline.} = +func len*[T](deq: Deque[T]): int {.inline.} = ## Returns the number of elements of `deq`. - result = deq.count + int(deq.tail - deq.head) template emptyCheck(deq) = # Bounds check for the regular deque access. when compileOption("boundChecks"): - if unlikely(deq.count < 1): + if unlikely(deq.len < 1): raise newException(IndexDefect, "Empty deque.") template xBoundsCheck(deq, i) = # Bounds check for the array like accesses. when compileOption("boundChecks"): # `-d:danger` or `--checks:off` should disable this. - if unlikely(i >= deq.count): # x < deq.low is taken care by the Natural parameter + if unlikely(i >= deq.len): # x < deq.low is taken care by the Natural parameter raise newException(IndexDefect, - "Out of bounds: " & $i & " > " & $(deq.count - 1)) + "Out of bounds: " & $i & " > " & $(deq.len - 1)) if unlikely(i < 0): # when used with BackwardsIndex raise newException(IndexDefect, "Out of bounds: " & $i & " < 0") @@ -114,7 +123,7 @@ proc `[]`*[T](deq: Deque[T], i: Natural): lent T {.inline.} = doAssertRaises(IndexDefect, echo a[8]) xBoundsCheck(deq, i) - return deq.data[(deq.head + i) and deq.mask] + return deq.data[(deq.head + i.uint) and deq.mask] proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} = ## Accesses the `i`-th element of `deq` and returns a mutable @@ -125,7 +134,7 @@ proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} = assert a[0] == 11 xBoundsCheck(deq, i) - return deq.data[(deq.head + i) and deq.mask] + return deq.data[(deq.head + i.uint) and deq.mask] proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} = ## Sets the `i`-th element of `deq` to `val`. @@ -137,7 +146,7 @@ proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} = checkIfInitialized(deq) xBoundsCheck(deq, i) - deq.data[(deq.head + i) and deq.mask] = val + deq.data[(deq.head + i.uint) and deq.mask] = val proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): lent T {.inline.} = ## Accesses the backwards indexed `i`-th element. @@ -190,10 +199,8 @@ iterator items*[T](deq: Deque[T]): lent T = let a = [10, 20, 30, 40, 50].toDeque assert toSeq(a.items) == @[10, 20, 30, 40, 50] - var i = deq.head - for c in 0 ..< deq.count: - yield deq.data[i] - i = (i + 1) and deq.mask + for c in 0 ..< deq.len: + yield deq.data[(deq.head + c.uint) and deq.mask] iterator mitems*[T](deq: var Deque[T]): var T = ## Yields every element of `deq`, which can be modified. @@ -207,10 +214,8 @@ iterator mitems*[T](deq: var Deque[T]): var T = x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]" - var i = deq.head - for c in 0 ..< deq.count: - yield deq.data[i] - i = (i + 1) and deq.mask + for c in 0 ..< deq.len: + yield deq.data[(deq.head + c.uint) and deq.mask] iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] = ## Yields every `(position, value)`-pair of `deq`. @@ -220,10 +225,8 @@ iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] = let a = [10, 20, 30].toDeque assert toSeq(a.pairs) == @[(0, 10), (1, 20), (2, 30)] - var i = deq.head - for c in 0 ..< deq.count: - yield (c, deq.data[i]) - i = (i + 1) and deq.mask + for c in 0 ..< deq.len: + yield (c, deq.data[(deq.head + c.uint) and deq.mask]) proc contains*[T](deq: Deque[T], item: T): bool {.inline.} = ## Returns true if `item` is in `deq` or false if not found. @@ -242,8 +245,9 @@ proc contains*[T](deq: Deque[T], item: T): bool {.inline.} = proc expandIfNeeded[T](deq: var Deque[T]) = checkIfInitialized(deq) - var cap = deq.mask + 1 - if unlikely(deq.count >= cap): + let cap = deq.data.len + assert deq.len <= cap + if unlikely(deq.len == cap): var n = newSeq[T](cap * 2) var i = 0 for x in mitems(deq): @@ -251,8 +255,7 @@ proc expandIfNeeded[T](deq: var Deque[T]) = else: n[i] = move(x) inc i deq.data = move(n) - deq.mask = cap * 2 - 1 - deq.tail = deq.count + deq.tail = cap.uint deq.head = 0 proc addFirst*[T](deq: var Deque[T], item: sink T) = @@ -267,9 +270,8 @@ proc addFirst*[T](deq: var Deque[T], item: sink T) = assert $a == "[50, 40, 30, 20, 10]" expandIfNeeded(deq) - inc deq.count - deq.head = (deq.head - 1) and deq.mask - deq.data[deq.head] = item + dec deq.head + deq.data[deq.head and deq.mask] = item proc addLast*[T](deq: var Deque[T], item: sink T) = ## Adds an `item` to the end of `deq`. @@ -283,9 +285,8 @@ proc addLast*[T](deq: var Deque[T], item: sink T) = assert $a == "[10, 20, 30, 40, 50]" expandIfNeeded(deq) - inc deq.count - deq.data[deq.tail] = item - deq.tail = (deq.tail + 1) and deq.mask + deq.data[deq.tail and deq.mask] = item + inc deq.tail proc toDeque*[T](x: openArray[T]): Deque[T] {.since: (1, 3).} = ## Creates a new deque that contains the elements of `x` (in the same order). @@ -314,7 +315,7 @@ proc peekFirst*[T](deq: Deque[T]): lent T {.inline.} = assert len(a) == 5 emptyCheck(deq) - result = deq.data[deq.head] + result = deq.data[deq.head and deq.mask] proc peekLast*[T](deq: Deque[T]): lent T {.inline.} = ## Returns the last element of `deq`, but does not remove it from the deque. @@ -344,7 +345,7 @@ proc peekFirst*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} = assert $a == "[99, 20, 30, 40, 50]" emptyCheck(deq) - result = deq.data[deq.head] + result = deq.data[deq.head and deq.mask] proc peekLast*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} = ## Returns a mutable reference to the last element of `deq`, @@ -377,9 +378,8 @@ proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} = assert $a == "[20, 30, 40, 50]" emptyCheck(deq) - dec deq.count - result = move deq.data[deq.head] - deq.head = (deq.head + 1) and deq.mask + result = move deq.data[deq.head and deq.mask] + inc deq.head proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} = ## Removes and returns the last element of the `deq`. @@ -394,9 +394,8 @@ proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} = assert $a == "[10, 20, 30, 40]" emptyCheck(deq) - dec deq.count - deq.tail = (deq.tail - 1) and deq.mask - result = move deq.data[deq.tail] + dec deq.tail + result = move deq.data[deq.tail and deq.mask] proc clear*[T](deq: var Deque[T]) {.inline.} = ## Resets the deque so that it is empty. @@ -410,7 +409,6 @@ proc clear*[T](deq: var Deque[T]) {.inline.} = assert len(a) == 0 for el in mitems(deq): destroy(el) - deq.count = 0 deq.tail = deq.head proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) = @@ -430,19 +428,17 @@ proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) = a.shrink(fromFirst = 2, fromLast = 1) assert $a == "[30, 40]" - if fromFirst + fromLast > deq.count: + if fromFirst + fromLast > deq.len: clear(deq) return for i in 0 ..< fromFirst: - destroy(deq.data[deq.head]) - deq.head = (deq.head + 1) and deq.mask + destroy(deq.data[deq.head and deq.mask]) + inc deq.head for i in 0 ..< fromLast: destroy(deq.data[(deq.tail - 1) and deq.mask]) - deq.tail = (deq.tail - 1) and deq.mask - - dec deq.count, fromFirst + fromLast + dec deq.tail proc `$`*[T](deq: Deque[T]): string = ## Turns a deque into its string representation. @@ -455,3 +451,30 @@ proc `$`*[T](deq: Deque[T]): string = if result.len > 1: result.add(", ") result.addQuoted(x) result.add("]") + +func `==`*[T](deq1, deq2: Deque[T]): bool = + ## The `==` operator for Deque. + ## Returns `true` if both deques contains the same values in the same order. + runnableExamples: + var a, b = initDeque[int]() + a.addFirst(2) + a.addFirst(1) + b.addLast(1) + b.addLast(2) + doAssert a == b + + if deq1.len != deq2.len: + return false + + for i in 0 ..< deq1.len: + if deq1.data[(deq1.head + i.uint) and deq1.mask] != deq2.data[(deq2.head + i.uint) and deq2.mask]: + return false + + true + +func hash*[T](deq: Deque[T]): Hash = + ## Hashing of Deque. + var h: Hash = 0 + for x in deq: + h = h !& hash(x) + !$h diff --git a/lib/pure/collections/hashcommon.nim b/lib/pure/collections/hashcommon.nim index 8fd4c6e08..17785c8c7 100644 --- a/lib/pure/collections/hashcommon.nim +++ b/lib/pure/collections/hashcommon.nim @@ -58,7 +58,10 @@ proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} = template genHashImpl(key, hc: typed) = hc = hash(key) if hc == 0: # This almost never taken branch should be very predictable. - hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. + when sizeof(int) < 4: + hc = 31415 # Value doesn't matter; Any non-zero favorite is fine <= 16-bit. + else: + hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. template genHash(key: typed): Hash = var res: Hash diff --git a/lib/pure/collections/heapqueue.nim b/lib/pure/collections/heapqueue.nim index bcfdf37c2..96f9b4430 100644 --- a/lib/pure/collections/heapqueue.nim +++ b/lib/pure/collections/heapqueue.nim @@ -47,6 +47,9 @@ runnableExamples: import std/private/since +when defined(nimPreviewSlimSystem): + import std/assertions + type HeapQueue*[T] = object ## A heap queue, commonly known as a priority queue. data: seq[T] @@ -73,6 +76,13 @@ proc `[]`*[T](heap: HeapQueue[T], i: Natural): lent T {.inline.} = ## Accesses the i-th element of `heap`. heap.data[i] +iterator items*[T](heap: HeapQueue[T]): lent T {.inline, since: (2, 1, 1).} = + ## Iterates over each item of `heap`. + let L = len(heap) + for i in 0 .. high(heap.data): + yield heap.data[i] + assert(len(heap) == L, "the length of the HeapQueue changed while iterating over it") + proc heapCmp[T](x, y: T): bool {.inline.} = x < y proc siftup[T](heap: var HeapQueue[T], startpos, p: int) = @@ -178,6 +188,11 @@ proc find*[T](heap: HeapQueue[T], x: T): int {.since: (1, 3).} = for i in 0 ..< heap.len: if heap[i] == x: return i +proc contains*[T](heap: HeapQueue[T], x: T): bool {.since: (2, 1, 1).} = + ## Returns true if `x` is in `heap` or false if not found. This is a shortcut + ## for `find(heap, x) >= 0`. + result = find(heap, x) >= 0 + proc del*[T](heap: var HeapQueue[T], index: Natural) = ## Removes the element at `index` from `heap`, maintaining the heap invariant. runnableExamples: diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index b9d5c48eb..6b88747ef 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -384,9 +384,7 @@ proc prependMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = assert s == [0, 1, 0, 1, 0, 1] b.addMoved(a) - when defined(js): # XXX: swap broken in js; bug #16771 - (b, a) = (a, b) - else: swap a, b + swap a, b proc add*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). @@ -983,6 +981,17 @@ func toSinglyLinkedList*[T](elems: openArray[T]): SinglyLinkedList[T] {.since: ( for elem in elems.items: result.add(elem) +func toSinglyLinkedRing*[T](elems: openArray[T]): SinglyLinkedRing[T] = + ## Creates a new `SinglyLinkedRing` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toSinglyLinkedRing + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initSinglyLinkedRing[T]() + for elem in elems.items: + result.add(elem) + func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a new `DoublyLinkedList` from the members of `elems`. runnableExamples: @@ -993,3 +1002,14 @@ func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: ( result = initDoublyLinkedList[T]() for elem in elems.items: result.add(elem) + +func toDoublyLinkedRing*[T](elems: openArray[T]): DoublyLinkedRing[T] = + ## Creates a new `DoublyLinkedRing` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toDoublyLinkedRing + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initDoublyLinkedRing[T]() + for elem in elems.items: + result.add(elem) diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index 8e4a3c35f..d414caeed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -278,6 +278,7 @@ proc initTable*[A, B](initialSize = defaultInitialSize): Table[A, B] = let a = initTable[int, string]() b = initTable[char, seq[int]]() + result = default(Table[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var Table[A, B], key: A, val: sink B) = @@ -1346,6 +1347,7 @@ proc initOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTable[A, let a = initOrderedTable[int, string]() b = initOrderedTable[char, seq[int]]() + result = default(OrderedTable[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) = @@ -1437,7 +1439,7 @@ proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false - var hc: Hash + var hc: Hash = default(Hash) result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = @@ -2336,6 +2338,7 @@ proc initCountTable*[A](initialSize = defaultInitialSize): CountTable[A] = ## * `toCountTable proc<#toCountTable,openArray[A]>`_ ## * `newCountTable proc<#newCountTable>`_ for creating a ## `CountTableRef` + result = default(CountTable[A]) initImpl(result, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = |