Implementation of a deque (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.
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.popLast()
Note: For inter thread communication use a Channel instead.
Deque[T] = object 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 module.
proc len[T](deq: Deque[T]): int {...}{.inline.}
proc `[]`[T](deq: Deque[T]; i: Natural): T {...}{.inline.}
proc `[]`[T](deq: var Deque[T]; i: Natural): var T {...}{.inline.}
proc `[]=`[T](deq: var Deque[T]; i: Natural; val: T) {...}{.inline.}
proc contains[T](deq: Deque[T]; item: T): bool {...}{.inline.}
in
operator. It is the equivalent of deq.find(item) >= 0
.if x in q: assert q.contains x
proc addFirst[T](deq: var Deque[T]; item: T)
proc addLast[T](deq: var Deque[T]; item: T)
proc peekFirst[T](deq: Deque[T]): T {...}{.inline.}
proc peekLast[T](deq: Deque[T]): T {...}{.inline.}
proc popFirst[T](deq: var Deque[T]): T {...}{.inline, discardable.}
proc popLast[T](deq: var Deque[T]): T {...}{.inline, discardable.}
proc clear[T](deq: var Deque[T]) {...}{.inline.}
proc shrink[T](deq: var Deque[T]; fromFirst = 0; fromLast = 0)
Remove fromFirst elements from the front of the deque and fromLast elements from the back. If the supplied number of elements exceeds the total number of elements in the deque, the deque will remain empty.
Any user defined destructors
proc `$`[T](deq: Deque[T]): string
iterator items[T](deq: Deque[T]): T
iterator mitems[T](deq: var Deque[T]): var T
iterator pairs[T](deq: Deque[T]): tuple[key: int, val: T]
© 2006–2018 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/deques.html