bugfix: 'set' overloadable; further steps for multi threading support

1 files changed, 89 insertions, 0 deletions

diff --git a/lib/pure/collections/queues.nim b/lib/pure/collections/queues.nim
new file mode 100644
index 000000000..2130d9949
--- /dev/null
+++ b/lib/pure/collections/queues.nim
@@ -0,0 +1,89 @@
+#
+#
+#            Nimrod's Runtime Library
+#        (c) Copyright 2011 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]")
+