1 files changed, 106 insertions, 0 deletions
diff --git a/tests/stdlib/theapqueue.nim b/tests/stdlib/theapqueue.nim
new file mode 100644
index 000000000..afb09c7e3
--- /dev/null
+++ b/tests/stdlib/theapqueue.nim
@@ -0,0 +1,106 @@
+discard """
+  matrix: "--mm:refc; --mm:orc"
+"""
+
+import std/heapqueue
+import std/assertions
+
+proc toSortedSeq[T](h: HeapQueue[T]): seq[T] =
+  var tmp = h
+  result = @[]
+  while tmp.len > 0:
+    result.add(pop(tmp))
+
+proc heapProperty[T](h: HeapQueue[T]): bool =
+  for k in 0 .. h.len - 2: # the last element is always a leaf
+    let left = 2 * k + 1
+    if left < h.len and h[left] < h[k]:
+      return false
+    let right = left + 1
+    if right < h.len and h[right] < h[k]:
+      return false
+  true
+
+template main() =
+  block: # simple sanity test
+    var heap = initHeapQueue[int]()
+    let data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
+    for item in data:
+      push(heap, item)
+    doAssert(heap == data.toHeapQueue)
+    doAssert(heap[0] == 0)
+    doAssert(heap.toSortedSeq == @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
+
+  block: # test del
+    var heap = initHeapQueue[int]()
+    let data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
+    for item in data: push(heap, item)
+
+    heap.del(0)
+    doAssert(heap[0] == 1)
+
+    heap.del(heap.find(7))
+    doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 5, 6, 8, 9])
+
+    heap.del(heap.find(5))
+    doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 6, 8, 9])
+
+    heap.del(heap.find(6))
+    doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 8, 9])
+
+    heap.del(heap.find(2))
+    doAssert(heap.toSortedSeq == @[1, 3, 4, 8, 9])
+
+    doAssert(heap.find(2) == -1)
+
+  block: # test del last
+    var heap = initHeapQueue[int]()
+    let data = [1, 2, 3]
+    for item in data: push(heap, item)
+
+    heap.del(2)
+    doAssert(heap.toSortedSeq == @[1, 2])
+
+    heap.del(1)
+    doAssert(heap.toSortedSeq == @[1])
+
+    heap.del(0)
+    doAssert(heap.toSortedSeq == @[])
+
+  block: # testing the heap proeprty
+    var heap = [1, 4, 2, 5].toHeapQueue
+    doAssert heapProperty(heap)
+
+    heap.push(42)
+    doAssert heapProperty(heap)
+    heap.push(0)
+    doAssert heapProperty(heap)
+    heap.push(3)
+    doAssert heapProperty(heap)
+    heap.push(3)
+    doAssert heapProperty(heap)
+
+    # [0, 3, 1, 4, 42, 2, 3, 5]
+
+    discard heap.pop()
+    doAssert heapProperty(heap)
+    discard heap.pop()
+    doAssert heapProperty(heap)
+
+    heap.del(2)
+    doAssert heapProperty(heap)
+
+    # [2, 3, 5, 4, 42]
+
+    discard heap.replace(12)
+    doAssert heapProperty(heap)
+    discard heap.replace(1)
+    doAssert heapProperty(heap)
+
+    discard heap.pushpop(2)
+    doAssert heapProperty(heap)
+    discard heap.pushpop(0)
+    doAssert heapProperty(heap)
+
+static: main()
+main()