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.

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

関連:

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.

  ソース 編集

プロシージャ

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

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

initialSize must be a power of two (default: 4). 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.}
Return the number of elements of deq.   ソース 編集
proc `[]`[T](deq: Deque[T]; i: Natural): T {...}{.inline.}
Access the i-th element of deq.

用例:

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])
  ソース 編集
proc `[]`[T](deq: var Deque[T]; i: Natural): var T {...}{.inline.}
Access the i-th element of deq and return a mutable reference to it.

用例:

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])
  ソース 編集
proc `[]=`[T](deq: var Deque[T]; i: Natural; val: T) {...}{.inline.}
Change the i-th element of deq.

用例:

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]"
  ソース 編集
proc `[]`[T](deq: Deque[T]; i: BackwardsIndex): T {...}{.inline.}

Access the backwards indexed i-th element.

deq[^1] is the last element.

用例:

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])
  ソース 編集
proc `[]`[T](deq: var Deque[T]; i: BackwardsIndex): var T {...}{.inline.}

Access the backwards indexed i-th element.

deq[^1] is the last element.

用例:

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])
  ソース 編集
proc `[]=`[T](deq: var Deque[T]; i: BackwardsIndex; x: T) {...}{.inline.}

Change the backwards indexed i-th element.

deq[^1] is the last element.

用例:

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]"
  ソース 編集
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)
  ソース 編集
proc addFirst[T](deq: var Deque[T]; item: T)

Add an item to the beginning of the deq.

関連:

用例:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addFirst(10 * i)
assert $a == "[50, 40, 30, 20, 10]"
  ソース 編集
proc addLast[T](deq: var Deque[T]; item: T)

Add an item to the end of the deq.

関連:

用例:

var a = initDeque[int]()
for i in 1 .. 5:
  a.addLast(10 * i)
assert $a == "[10, 20, 30, 40, 50]"
  ソース 編集
proc peekFirst[T](deq: Deque[T]): T {...}{.inline.}

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

関連:

用例:

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
  ソース 編集
proc peekLast[T](deq: Deque[T]): T {...}{.inline.}

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

関連:

用例:

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
  ソース 編集
proc popFirst[T](deq: var Deque[T]): T {...}{.inline, discardable.}

Remove and returns the first element of the deq.

関連:

用例:

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]"
  ソース 編集
proc popLast[T](deq: var Deque[T]): T {...}{.inline, discardable.}

Remove and returns the last element of the deq.

関連:

用例:

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]"
  ソース 編集
proc clear[T](deq: var Deque[T]) {...}{.inline.}

Resets the deque so that it is empty.

関連:

用例:

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
  ソース 編集
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.

関連:

用例:

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]"
  ソース 編集
proc `$`[T](deq: Deque[T]): string
Turn a deque into its string representation.   ソース 編集

イテレータ

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

Yield every element of deq.

用例:

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
  ソース 編集
iterator mitems[T](deq: var Deque[T]): var T
Yield every element of deq, which can be modified.

用例:

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]"
  ソース 編集
iterator pairs[T](deq: Deque[T]): tuple[key: int, val: T]

Yield every (position, value) of deq.

用例:

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
  ソース 編集