☰

# std/deques

Theme:

- Manual
- Standard library
- Index
- Compiler docs
- Fusion docs
- devel, stable

Search:
Source Edit

An implementation of a deque (double-ended queue). The underlying implementation uses a `seq`.

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.

Example:

    import std/deques
    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 for singly and doubly linked lists and rings

# Imports

since, assertions, hashes, math

# Types

    Deque[T] = object

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

  To initialize an empty deque, use the initDeque proc.

  Source Edit

# Consts

    defaultInitialSize = 4

  Source Edit

# Procs

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

  Turns a deque into its string representation.

  Example:

      let a = [10, 20, 30].toDeque
      assert $a == "[10, 20, 30]"

  Source Edit

    func `==`[T](deq1, deq2: Deque[T]): bool

  The `==` operator for Deque. Returns `true` if both deques contains the same values in the same order.

  Example:

      var a, b = initDeque[int]()
      a.addFirst(2)
      a.addFirst(1)
      b.addLast(1)
      b.addLast(2)
      doAssert a == b

  Source Edit

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

  Accesses the backwards indexed `i`-th element.

  `deq[^1]` is the last element.

  Example:

      let a = [10, 20, 30, 40, 50].toDeque
      assert a[^1] == 50
      assert a[^4] == 20
      doAssertRaises(IndexDefect, echo a[^9])

  Source Edit

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

  Accesses the `i`-th element of `deq`.

  Example:

      let a = [10, 20, 30, 40, 50].toDeque
      assert a[0] == 10
      assert a[3] == 40
      doAssertRaises(IndexDefect, echo a[8])

  Source Edit

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

  Accesses the backwards indexed `i`-th element and returns a mutable reference to it.

  `deq[^1]` is the last element.

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      inc(a[^1])
      assert a[^1] == 51

  Source Edit

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

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

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      inc(a[0])
      assert a[0] == 11

  Source Edit

    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.

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      a[^1] = 99
      a[^3] = 77
      assert $a == "[10, 20, 77, 40, 99]"

  Source Edit

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

  Sets the `i`-th element of `deq` to `val`.

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      a[0] = 99
      a[3] = 66
      assert $a == "[99, 20, 30, 66, 50]"

  Source Edit

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

  Adds an `item` to the beginning of `deq`.

  See also:

  - addLast 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: sink T)

  Adds an `item` to the end of `deq`.

  See also:

  - addFirst 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 clear[T](deq: var Deque[T]) {.inline.}

  Resets the deque so that it is empty.

  See also:

  - shrink proc

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      assert $a == "[10, 20, 30, 40, 50]"
      clear(a)
      assert len(a) == 0

  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`.

  Example:

      let q = [7, 9].toDeque
      assert 7 in q
      assert q.contains(7)
      assert 8 notin q

  Source Edit

    func hash[T](deq: Deque[T]): Hash

  Hashing of Deque. Source Edit

    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 (default: defaultInitialSize). The length of a newly created deque will still be 0.

  See also:

  - toDeque proc
  Source Edit

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

  Returns the number of elements of `deq`. Source Edit

    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:

  - peekFirst proc which returns a mutable reference
  - peekLast proc

  Example:

      let a = [10, 20, 30, 40, 50].toDeque
      assert $a == "[10, 20, 30, 40, 50]"
      assert a.peekFirst == 10
      assert len(a) == 5

  Source Edit

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

  Returns a mutable reference to the first element of `deq`, but does not remove it from the deque.

  See also:

  - peekFirst proc
  - peekLast proc

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      a.peekFirst() = 99
      assert $a == "[99, 20, 30, 40, 50]"

  Source Edit

    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:

  - peekLast proc which returns a mutable reference
  - peekFirst proc

  Example:

      let a = [10, 20, 30, 40, 50].toDeque
      assert $a == "[10, 20, 30, 40, 50]"
      assert a.peekLast == 50
      assert len(a) == 5

  Source Edit

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

  Returns a mutable reference to the last element of `deq`, but does not remove it from the deque.

  See also:

  - peekFirst proc
  - peekLast proc

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      a.peekLast() = 99
      assert $a == "[10, 20, 30, 40, 99]"

  Source Edit

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

  Removes and returns the first element of the `deq`.

  See also:

  - popLast proc
  - shrink proc

  Example:

      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]"

  Source Edit

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

  Removes and returns the last element of the `deq`.

  See also:

  - popFirst proc
  - shrink proc

  Example:

      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]"

  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
  - popFirst proc
  - popLast proc

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      assert $a == "[10, 20, 30, 40, 50]"
      a.shrink(fromFirst = 2, fromLast = 1)
      assert $a == "[30, 40]"

  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:

      let a = toDeque([7, 8, 9])
      assert len(a) == 3
      assert $a == "[7, 8, 9]"

  Source Edit

# Iterators

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

  Yields every element of `deq`.

  See also:

  - mitems iterator

  Example:

      from std/sequtils import toSeq

      let a = [10, 20, 30, 40, 50].toDeque
      assert toSeq(a.items) == @[10, 20, 30, 40, 50]

  Source Edit

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

  Yields every element of `deq`, which can be modified.

  See also:

  - items iterator

  Example:

      var a = [10, 20, 30, 40, 50].toDeque
      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)`-pair of `deq`.

  Example:

      from std/sequtils import toSeq

      let a = [10, 20, 30].toDeque
      assert toSeq(a.pairs) == @[(0, 10), (1, 20), (2, 30)]

  Source Edit