diff options
Diffstat (limited to 'lib/pure/collections/deques.nim')
| -rw-r--r-- | lib/pure/collections/deques.nim | 615 |
1 files changed, 262 insertions, 353 deletions
diff --git a/lib/pure/collections/deques.nim b/lib/pure/collections/deques.nim index 1aa525bd6..d2b0099f2 100644 --- a/lib/pure/collections/deques.nim +++ b/lib/pure/collections/deques.nim @@ -7,186 +7,179 @@ # distribution, for details about the copyright. # -## Implementation of a `deque`:idx: (double-ended queue). -## The underlying implementation uses a ``seq``. +## An 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. +## .. note:: None of the procs that get an individual value from the deque should be used +## on an empty deque. +## +## If compiled with the `boundChecks` option, those procs will raise an `IndexDefect` +## on such access. This should not be relied upon, as `-d:danger` or `--checks:off` will +## disable those checks and then the procs 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 -## import deques -## -## var a = initDeque[int]() -## -## doAssertRaises(IndexError, echo a[0]) -## -## for i in 1 .. 5: -## a.addLast(10*i) -## assert $a == "[10, 20, 30, 40, 50]" -## -## assert a.peekFirst == 10 -## assert a.peekLast == 50 -## assert len(a) == 5 -## -## assert a.popFirst == 10 -## assert a.popLast == 50 -## assert len(a) == 3 -## -## a.addFirst(11) -## a.addFirst(22) -## a.addFirst(33) -## assert $a == "[33, 22, 11, 20, 30, 40]" -## -## a.shrink(fromFirst = 1, fromLast = 2) -## assert $a == "[22, 11, 20]" -## -## -## **See also:** + +runnableExamples: + var a = [10, 20, 30, 40].toDeque + + doAssertRaises(IndexDefect, echo a[4]) + + a.addLast(50) + assert $a == "[10, 20, 30, 40, 50]" + + assert a.peekFirst == 10 + assert a.peekLast == 50 + assert len(a) == 5 + + assert a.popFirst == 10 + assert a.popLast == 50 + assert len(a) == 3 + + a.addFirst(11) + a.addFirst(22) + a.addFirst(33) + assert $a == "[33, 22, 11, 20, 30, 40]" + + a.shrink(fromFirst = 1, fromLast = 2) + assert $a == "[22, 11, 20]" + +## See also +## ======== ## * `lists module <lists.html>`_ for singly and doubly linked lists and rings -## * `channels module <channels.html>`_ for inter-thread communication +import std/private/since -import math +import std/[assertions, hashes, math] type Deque*[T] = object - ## A double-ended queue backed with a ringed seq buffer. + ## A double-ended queue backed with a ringed `seq` buffer. ## - ## To initialize an empty deque use `initDeque proc <#initDeque,int>`_. + ## 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) = - assert isPowerOfTwo(initialSize) - result.mask = initialSize-1 - newSeq(result.data, initialSize) - + let correctSize = nextPowerOfTwo(initialSize) + newSeq(result.data, correctSize) + template checkIfInitialized(deq: typed) = - when compiles(defaultInitialSize): - if deq.mask == 0: - initImpl(deq, defaultInitialSize) + 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 = 4): Deque[T] = - ## Create a new empty deque. +proc initDeque*[T](initialSize: int = defaultInitialSize): Deque[T] = + ## Creates a new empty deque. ## ## Optionally, the initial capacity can be reserved via `initialSize` - ## as a performance optimization. + ## as a performance optimization + ## (default: `defaultInitialSize <#defaultInitialSize>`_). ## The length of a newly created deque will still be 0. ## - ## ``initialSize`` must be a power of two (default: 4). - ## If you need to accept runtime values for this you could use the - ## `nextPowerOfTwo proc<math.html#nextPowerOfTwo,int>`_ from the - ## `math module<math.html>`_. + ## **See also:** + ## * `toDeque proc <#toDeque,openArray[T]>`_ result.initImpl(initialSize) -proc len*[T](deq: Deque[T]): int {.inline.} = - ## Return the number of elements of `deq`. - result = deq.count +func len*[T](deq: Deque[T]): int {.inline.} = + ## Returns the number of elements of `deq`. + int(deq.tail - deq.head) template emptyCheck(deq) = # Bounds check for the regular deque access. when compileOption("boundChecks"): - if unlikely(deq.count < 1): - raise newException(IndexError, "Empty deque.") + 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: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)) + when compileOption("boundChecks"): # `-d:danger` or `--checks:off` should disable this. + if unlikely(i >= deq.len): # x < deq.low is taken care by the Natural parameter + raise newException(IndexDefect, + "Out of bounds: " & $i & " > " & $(deq.len - 1)) if unlikely(i < 0): # when used with BackwardsIndex - raise newException(IndexError, + raise newException(IndexDefect, "Out of bounds: " & $i & " < 0") -proc `[]`*[T](deq: Deque[T], i: Natural): T {.inline.} = - ## Access the i-th element of `deq`. +proc `[]`*[T](deq: Deque[T], i: Natural): lent T {.inline.} = + ## Accesses the `i`-th element of `deq`. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert a[0] == 10 assert a[3] == 40 - doAssertRaises(IndexError, echo a[8]) + 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.} = - ## Access the i-th element of `deq` and return a mutable + ## Accesses the `i`-th element of `deq` and returns a mutable ## reference to it. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) - assert a[0] == 10 - assert a[3] == 40 - doAssertRaises(IndexError, echo a[8]) + var a = [10, 20, 30, 40, 50].toDeque + inc(a[0]) + 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: T) {.inline.} = - ## Change the i-th element of `deq`. +proc `[]=`*[T](deq: var Deque[T], i: Natural, val: sink T) {.inline.} = + ## Sets the `i`-th element of `deq` to `val`. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque a[0] = 99 a[3] = 66 assert $a == "[99, 20, 30, 66, 50]" 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): T {.inline.} = - ## Access the backwards indexed i-th element. +proc `[]`*[T](deq: Deque[T], i: BackwardsIndex): lent T {.inline.} = + ## Accesses the backwards indexed `i`-th element. ## ## `deq[^1]` is the last element. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert a[^1] == 50 assert a[^4] == 20 - doAssertRaises(IndexError, echo a[^9]) + doAssertRaises(IndexDefect, echo a[^9]) xBoundsCheck(deq, deq.len - int(i)) return deq[deq.len - int(i)] proc `[]`*[T](deq: var Deque[T], i: BackwardsIndex): var T {.inline.} = - ## Access the backwards indexed i-th element. + ## Accesses the backwards indexed `i`-th element and returns a mutable + ## reference to it. ## ## `deq[^1]` is the last element. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) - assert a[^1] == 50 - assert a[^4] == 20 - doAssertRaises(IndexError, echo a[^9]) + var a = [10, 20, 30, 40, 50].toDeque + inc(a[^1]) + assert a[^1] == 51 xBoundsCheck(deq, deq.len - int(i)) return deq[deq.len - int(i)] -proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: T) {.inline.} = - ## Change the backwards indexed i-th element. +proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: sink T) {.inline.} = + ## Sets the backwards indexed `i`-th element of `deq` to `x`. ## ## `deq[^1]` is the last element. runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque a[^1] = 99 a[^3] = 77 assert $a == "[10, 20, 77, 40, 99]" @@ -195,166 +188,143 @@ proc `[]=`*[T](deq: var Deque[T], i: BackwardsIndex, x: T) {.inline.} = xBoundsCheck(deq, deq.len - int(i)) deq[deq.len - int(i)] = x -iterator items*[T](deq: Deque[T]): T = - ## Yield every element of `deq`. - ## - ## **Examples:** +iterator items*[T](deq: Deque[T]): lent T = + ## Yields every element of `deq`. ## - ## .. code-block:: - ## var a = initDeque[int]() - ## for i in 1 .. 3: - ## a.addLast(10*i) - ## - ## for x in a: # the same as: for x in items(a): - ## echo x - ## - ## # 10 - ## # 20 - ## # 30 - ## - var i = deq.head - for c in 0 ..< deq.count: - yield deq.data[i] - i = (i + 1) and deq.mask + ## **See also:** + ## * `mitems iterator <#mitems.i,Deque[T]>`_ + runnableExamples: + from std/sequtils import toSeq + + let a = [10, 20, 30, 40, 50].toDeque + assert toSeq(a.items) == @[10, 20, 30, 40, 50] + + 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 = - ## Yield every element of `deq`, which can be modified. + ## Yields every element of `deq`, which can be modified. + ## + ## **See also:** + ## * `items iterator <#items.i,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): - x = 5*x - 1 + 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] = - ## Yield every (position, value) of `deq`. - ## - ## **Examples:** - ## - ## .. code-block:: - ## var a = initDeque[int]() - ## for i in 1 .. 3: - ## a.addLast(10*i) - ## - ## for k, v in pairs(a): - ## echo "key: ", k, ", value: ", v - ## - ## # key: 0, value: 10 - ## # key: 1, value: 20 - ## # key: 2, value: 30 - ## - var i = deq.head - for c in 0 ..< deq.count: - yield (c, deq.data[i]) - i = (i + 1) and deq.mask + ## Yields every `(position, value)`-pair of `deq`. + runnableExamples: + from std/sequtils import toSeq + + let a = [10, 20, 30].toDeque + assert toSeq(a.pairs) == @[(0, 10), (1, 20), (2, 30)] + + 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.} = - ## 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``. + ## Returns true if `item` is in `deq` or false if not found. ## - ## .. code-block:: Nim - ## if x in q: - ## assert q.contains(x) + ## Usually used via the `in` operator. + ## It is the equivalent of `deq.find(item) >= 0`. + runnableExamples: + let q = [7, 9].toDeque + assert 7 in q + assert q.contains(7) + assert 8 notin q + for e in deq: if e == item: return true return false 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): # don't use copyMem because of the GC and because it's slower. - n[i] = move(x) + for x in mitems(deq): + when nimvm: n[i] = x # workaround for VM bug + 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: T) = - ## Add an `item` to the beginning of the `deq`. +proc addFirst*[T](deq: var Deque[T], item: sink T) = + ## Adds an `item` to the beginning of `deq`. ## - ## See also: - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ + ## **See also:** + ## * `addLast proc <#addLast,Deque[T],sinkT>`_ runnableExamples: var a = initDeque[int]() for i in 1 .. 5: - a.addFirst(10*i) + a.addFirst(10 * i) 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: T) = - ## Add an `item` to the end of the `deq`. +proc addLast*[T](deq: var Deque[T], item: sink T) = + ## Adds an `item` to the end of `deq`. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ + ## **See also:** + ## * `addFirst proc <#addFirst,Deque[T],sinkT>`_ runnableExamples: var a = initDeque[int]() for i in 1 .. 5: - a.addLast(10*i) + a.addLast(10 * i) 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). + ## + ## **See also:** + ## * `initDeque proc <#initDeque,int>`_ + runnableExamples: + let a = toDeque([7, 8, 9]) + assert len(a) == 3 + assert $a == "[7, 8, 9]" + + result.initImpl(x.len) + for item in items(x): + result.addLast(item) -proc peekFirst*[T](deq: Deque[T]): T {.inline.} = +proc peekFirst*[T](deq: Deque[T]): lent T {.inline.} = ## Returns the first element of `deq`, but does not remove it from the deque. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ + ## **See also:** + ## * `peekFirst proc <#peekFirst,Deque[T]_2>`_ which returns a mutable reference ## * `peekLast proc <#peekLast,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.peekFirst == 10 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]): T {.inline.} = +proc peekLast*[T](deq: Deque[T]): lent T {.inline.} = ## Returns the last element of `deq`, but does not remove it from the deque. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ + ## **See also:** + ## * `peekLast proc <#peekLast,Deque[T]_2>`_ which returns a mutable reference ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `popLast proc <#popLast,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + let a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.peekLast == 50 assert len(a) == 5 @@ -362,210 +332,149 @@ proc peekLast*[T](deq: Deque[T]): T {.inline.} = emptyCheck(deq) result = deq.data[(deq.tail - 1) and deq.mask] +proc peekFirst*[T](deq: var Deque[T]): var T {.inline, since: (1, 3).} = + ## Returns a mutable reference to the first element of `deq`, + ## but does not remove it from the deque. + ## + ## **See also:** + ## * `peekFirst proc <#peekFirst,Deque[T]>`_ + ## * `peekLast proc <#peekLast,Deque[T]_2>`_ + runnableExamples: + var a = [10, 20, 30, 40, 50].toDeque + a.peekFirst() = 99 + assert $a == "[99, 20, 30, 40, 50]" + + emptyCheck(deq) + 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`, + ## but does not remove it from the deque. + ## + ## **See also:** + ## * `peekFirst proc <#peekFirst,Deque[T]_2>`_ + ## * `peekLast proc <#peekLast,Deque[T]>`_ + runnableExamples: + var a = [10, 20, 30, 40, 50].toDeque + a.peekLast() = 99 + assert $a == "[10, 20, 30, 40, 99]" + + emptyCheck(deq) + result = deq.data[(deq.tail - 1) and deq.mask] + template destroy(x: untyped) = reset(x) proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} = - ## Remove and returns the first element of the `deq`. + ## Removes and returns the first element of the `deq`. ## ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ ## * `popLast proc <#popLast,Deque[T]>`_ - ## * `clear proc <#clear,Deque[T]>`_ ## * `shrink proc <#shrink,Deque[T],int,int>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.popFirst == 10 assert $a == "[20, 30, 40, 50]" emptyCheck(deq) - dec deq.count - result = deq.data[deq.head] - destroy(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.} = - ## Remove and returns the last element of the `deq`. + ## Removes and returns the last element of the `deq`. ## - ## See also: - ## * `addFirst proc <#addFirst,Deque[T],T>`_ - ## * `addLast proc <#addLast,Deque[T],T>`_ - ## * `peekFirst proc <#peekFirst,Deque[T]>`_ - ## * `peekLast proc <#peekLast,Deque[T]>`_ + ## **See also:** ## * `popFirst proc <#popFirst,Deque[T]>`_ - ## * `clear proc <#clear,Deque[T]>`_ ## * `shrink proc <#shrink,Deque[T],int,int>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addLast(10*i) + var a = [10, 20, 30, 40, 50].toDeque assert $a == "[10, 20, 30, 40, 50]" assert a.popLast == 50 assert $a == "[10, 20, 30, 40]" emptyCheck(deq) - dec deq.count - deq.tail = (deq.tail - 1) and deq.mask - result = deq.data[deq.tail] - destroy(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. ## - ## See also: - ## * `clear proc <#clear,Deque[T]>`_ + ## **See also:** ## * `shrink proc <#shrink,Deque[T],int,int>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addFirst(10*i) - assert $a == "[50, 40, 30, 20, 10]" + var a = [10, 20, 30, 40, 50].toDeque + assert $a == "[10, 20, 30, 40, 50]" clear(a) 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) = - ## Remove `fromFirst` elements from the front of the deque and + ## Removes `fromFirst` elements from the front of the deque and ## `fromLast` elements from the back. ## ## If the supplied number of elements exceeds the total number of elements ## in the deque, the deque will remain empty. ## - ## See also: + ## **See also:** ## * `clear proc <#clear,Deque[T]>`_ + ## * `popFirst proc <#popFirst,Deque[T]>`_ + ## * `popLast proc <#popLast,Deque[T]>`_ runnableExamples: - var a = initDeque[int]() - for i in 1 .. 5: - a.addFirst(10*i) - assert $a == "[50, 40, 30, 20, 10]" + var a = [10, 20, 30, 40, 50].toDeque + assert $a == "[10, 20, 30, 40, 50]" a.shrink(fromFirst = 2, fromLast = 1) - assert $a == "[30, 20]" + 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]) - deq.tail = (deq.tail - 1) and deq.mask - - dec deq.count, fromFirst + fromLast + destroy(deq.data[(deq.tail - 1) and deq.mask]) + dec deq.tail proc `$`*[T](deq: Deque[T]): string = - ## Turn a deque into its string representation. + ## Turns a deque into its string representation. + runnableExamples: + let a = [10, 20, 30].toDeque + assert $a == "[10, 20, 30]" + result = "[" for x in deq: 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 -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[deq.len - 1] = 7 - - assert 6 in deq and 789 notin deq - assert deq.find(6) >= 0 - assert deq.find(789) < 0 - - block: - var d = initDeque[int](1) - d.addLast 7 - d.addLast 8 - d.addLast 10 - d.addFirst 5 - d.addFirst 2 - d.addFirst 1 - d.addLast 20 - d.shrink(fromLast = 2) - doAssert($d == "[1, 2, 5, 7, 8]") - d.shrink(2, 1) - doAssert($d == "[5, 7]") - d.shrink(2, 2) - doAssert d.len == 0 - - for i in -2 .. 10: - if i in deq: - assert deq.contains(i) and deq.find(i) >= 0 - else: - assert(not deq.contains(i) and deq.find(i) < 0) + 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 - 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) + true + +func hash*[T](deq: Deque[T]): Hash = + ## Hashing of Deque. + var h: Hash = 0 + for x in deq: + h = h !& hash(x) + !$h |