diff options
Diffstat (limited to 'lib/pure/collections/queues.nim')
-rwxr-xr-x | lib/pure/collections/queues.nim | 89 |
1 files changed, 0 insertions, 89 deletions
diff --git a/lib/pure/collections/queues.nim b/lib/pure/collections/queues.nim deleted file mode 100755 index 5481272f0..000000000 --- a/lib/pure/collections/queues.nim +++ /dev/null @@ -1,89 +0,0 @@ -# -# -# Nimrod'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 - TQueue* {.pure, final.}[T] = object ## a queue - data: seq[T] - rd, wr, count, mask: int - -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]") - |