Module deques

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.

Types

Deque[T] = object
  data: seq[T]
  head, tail, count, mask: int
A double-ended queue backed with a ringed seq buffer.   Source Edit

Procs

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.

  Source Edit
proc len[T](deq: Deque[T]): int {...}{.inline.}
Return the number of elements of deq.   Source Edit
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.   Source Edit
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.   Source Edit
proc `[]=`[T](deq: var Deque[T]; i: Natural; val: T) {...}{.inline.}
Change the i-th element of deq.   Source Edit
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.
if x in q:
  assert q.contains x
  Source Edit
proc addFirst[T](deq: var Deque[T]; item: T)
Add an item to the beginning of the deq.   Source Edit
proc addLast[T](deq: var Deque[T]; item: T)
Add an item to the end of the deq.   Source Edit
proc peekFirst[T](deq: Deque[T]): T {...}{.inline.}
Returns the first element of deq, but does not remove it from the deque.   Source Edit
proc peekLast[T](deq: Deque[T]): T {...}{.inline.}
Returns the last element of deq, but does not remove it from the deque.   Source Edit
proc popFirst[T](deq: var Deque[T]): T {...}{.inline, discardable.}
Remove and returns the first element of the deq.   Source Edit
proc popLast[T](deq: var Deque[T]): T {...}{.inline, discardable.}
Remove and returns the last element of the deq.   Source Edit
proc clear[T](deq: var Deque[T]) {...}{.inline.}
Resets the deque so that it is empty.   Source Edit
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

  Source Edit
proc `$`[T](deq: Deque[T]): string
Turn a deque into its string representation.   Source Edit

Iterators

iterator items[T](deq: Deque[T]): T
Yield every element of deq.   Source Edit
iterator mitems[T](deq: var Deque[T]): var T
Yield every element of deq.   Source Edit
iterator pairs[T](deq: Deque[T]): tuple[key: int, val: T]
Yield every (position, value) of deq.   Source Edit