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