1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#
#
# Nim's Runtime Library
# (c) Copyright 2012 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## Implementation of a queue. The underlying implementation uses a ``seq``.
import math
type
Queue*[T] = object ## a queue
data: seq[T]
rd, wr, count, mask: int
{.deprecated: [TQueue: Queue].}
proc initQueue*[T](initialSize=4): TQueue[T] =
## creates a new queue. `initialSize` needs to be a power of 2.
assert isPowerOfTwo(initialSize)
result.mask = initialSize-1
newSeq(result.data, initialSize)
proc len*[T](q: TQueue[T]): int =
## returns the number of elements of `q`.
result = q.count
iterator items*[T](q: TQueue[T]): T =
## yields every element of `q`.
var i = q.rd
var c = q.count
while c > 0:
dec c
yield q.data[i]
i = (i + 1) and q.mask
proc add*[T](q: var TQueue[T], item: T) =
## adds an `item` to the end of the queue `q`.
var cap = q.mask+1
if q.count >= cap:
var n: seq[T]
newSeq(n, cap*2)
var i = 0
for x in items(q):
shallowCopy(n[i], x)
inc i
shallowCopy(q.data, n)
q.mask = cap*2 - 1
q.wr = q.count
q.rd = 0
inc q.count
q.data[q.wr] = item
q.wr = (q.wr + 1) and q.mask
proc enqueue*[T](q: var TQueue[T], item: T) =
## alias for the ``add`` operation.
add(q, item)
proc dequeue*[T](q: var TQueue[T]): T =
## removes and returns the first element of the queue `q`.
assert q.count > 0
dec q.count
result = q.data[q.rd]
q.rd = (q.rd + 1) and q.mask
proc `$`*[T](q: TQueue[T]): string =
## turns a queue into its string representation.
result = "["
for x in items(q):
if result.len > 1: result.add(", ")
result.add($x)
result.add("]")
when isMainModule:
var q = initQueue[int]()
q.add(123)
q.add(9)
q.add(4)
var first = q.dequeue
q.add(56)
q.add(6)
var second = q.dequeue
q.add(789)
assert first == 123
assert second == 9
assert($q == "[4, 56, 6, 789]")
|