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 IndexDefect on such access. This should not be relied upon, as -d:danger or --checks:off 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.

import deques

var a = initDeque[int]()

doAssertRaises(IndexDefect, 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:

• lists module for singly and doubly linked lists and rings
• channels module for inter-thread communication

Imports

since, math

Types

Deque[T] = object
  data: seq[T]
  head, tail, count, mask: int

A double-ended queue backed with a ringed seq buffer.

To initialize an empty deque use initDeque proc.

Source Edit

Consts

defaultInitialSize = 4

Source Edit

Procs

proc initDeque[T](initialSize: int = 4): Deque[T]

Creates a new empty 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.

See also:

• toDeque proc

Source Edit

proc toDeque[T](x: openArray[T]): Deque[T]

Creates a new deque that contains the elements of x (in the same order).

See also:

• initDeque proc

Example:

var a = toDeque([7, 8, 9])
assert len(a) == 3
assert a.popFirst == 7
assert len(a) == 2

Source Edit

proc len[T](deq: Deque[T]): int {...}{.inline.}

Returns the number of elements of deq. Source Edit

proc `[]`[T](deq: Deque[T]; i: Natural): T {...}{.inline.}

Accesses the i-th element of deq.

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[0] == 10
assert a[3] == 40
doAssertRaises(IndexDefect, echo a[8])

Source Edit

proc `[]`[T](deq: var Deque[T]; i: Natural): var T {...}{.inline.}

Accesses the i-th element of deq and return a mutable reference to it.

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[0] == 10
assert a[3] == 40
doAssertRaises(IndexDefect, echo a[8])

Source Edit

proc `[]=`[T](deq: var Deque[T]; i: Natural; val: T) {...}{.inline.}

Changes the i-th element of deq.

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
a[0] = 99
a[3] = 66
assert $a == "[99, 20, 30, 66, 50]"

Source Edit

proc `[]`[T](deq: Deque[T]; i: BackwardsIndex): T {...}{.inline.}

Accesses the backwards indexed i-th element.

deq[^1] is the last element.

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[^1] == 50
assert a[^4] == 20
doAssertRaises(IndexDefect, echo a[^9])

Source Edit

proc `[]`[T](deq: var Deque[T]; i: BackwardsIndex): var T {...}{.inline.}

Accesses the backwards indexed i-th element.

deq[^1] is the last element.

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert a[^1] == 50
assert a[^4] == 20
doAssertRaises(IndexDefect, echo a[^9])

Source Edit

proc `[]=`[T](deq: var Deque[T]; i: BackwardsIndex; x: T) {...}{.inline.}

Changes the backwards indexed i-th element.

deq[^1] is the last element.

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
a[^1] = 99
a[^3] = 77
assert $a == "[10, 20, 77, 40, 99]"

Source Edit

proc contains[T](deq: Deque[T]; item: T): bool {...}{.inline.}

Returns 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)

Adds an item to the beginning of the deq.

See also:

• addLast proc
• peekFirst proc
• peekLast proc
• popFirst proc
• popLast proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addFirst(10*i)
assert $a == "[50, 40, 30, 20, 10]"

Source Edit

proc addLast[T](deq: var Deque[T]; item: T)

Adds an item to the end of the deq.

See also:

• addFirst proc
• peekFirst proc
• peekLast proc
• popFirst proc
• popLast proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"

Source Edit

proc peekFirst[T](deq: Deque[T]): T {...}{.inline.}

Returns the first element of deq, but does not remove it from the deque.

See also:

• addFirst proc
• addLast proc
• peekLast proc
• popFirst proc
• popLast proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekFirst == 10
assert len(a) == 5

Source Edit

proc peekLast[T](deq: Deque[T]): T {...}{.inline.}

Returns the last element of deq, but does not remove it from the deque.

See also:

• addFirst proc
• addLast proc
• peekFirst proc
• popFirst proc
• popLast proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekLast == 50
assert len(a) == 5

Source Edit

proc peekFirst[T](deq: var Deque[T]): var T {...}{.inline.}

Returns the first element of deq, but does not remove it from the deque.

See also:

• addFirst proc
• addLast proc
• peekLast proc
• popFirst proc
• popLast proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekFirst == 10
assert len(a) == 5

Source Edit

proc peekLast[T](deq: var Deque[T]): var T {...}{.inline.}

Returns the last element of deq, but does not remove it from the deque.

See also:

• addFirst proc
• addLast proc
• peekFirst proc
• popFirst proc
• popLast proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.peekLast == 50
assert len(a) == 5

Source Edit

proc popFirst[T](deq: var Deque[T]): T {...}{.inline, discardable.}

Removes and returns the first element of the deq.

See also:

• addFirst proc
• addLast proc
• peekFirst proc
• peekLast proc
• popLast proc
• clear proc
• shrink proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.popFirst == 10
assert $a == "[20, 30, 40, 50]"

Source Edit

proc popLast[T](deq: var Deque[T]): T {...}{.inline, discardable.}

Removes and returns the last element of the deq.

See also:

• addFirst proc
• addLast proc
• peekFirst proc
• peekLast proc
• popFirst proc
• clear proc
• shrink proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
assert a.popLast == 50
assert $a == "[10, 20, 30, 40]"

Source Edit

proc clear[T](deq: var Deque[T]) {...}{.inline.}

Resets the deque so that it is empty.

See also:

• clear proc
• shrink proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addFirst(10*i)
assert $a == "[50, 40, 30, 20, 10]"
clear(a)
assert len(a) == 0

Source Edit

proc shrink[T](deq: var Deque[T]; fromFirst = 0; fromLast = 0)

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:

• clear proc

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addFirst(10*i)
assert $a == "[50, 40, 30, 20, 10]"
a.shrink(fromFirst = 2, fromLast = 1)
assert $a == "[30, 20]"

Source Edit

proc `$`[T](deq: Deque[T]): string

Turns a deque into its string representation. Source Edit

Iterators

iterator items[T](deq: Deque[T]): T

Yields every element of deq.

Examples:

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

Source Edit

iterator mitems[T](deq: var Deque[T]): var T

Yields every element of deq, which can be modified.

Example:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10*i)
assert $a == "[10, 20, 30, 40, 50]"
for x in mitems(a):
  x = 5*x - 1
assert $a == "[49, 99, 149, 199, 249]"

Source Edit

iterator pairs[T](deq: Deque[T]): tuple[key: int, val: T]

Yields every (position, value) of deq.

Examples:

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

Source Edit