Improve the heapqueue module (#17034)

Improve documentation
Optimize toHeapQueue
Rename siftup and siftdown
Add tests for the heap property

1 files changed, 83 insertions, 34 deletions

diff --git a/tests/stdlib/theapqueue.nim b/tests/stdlib/theapqueue.nim
index 20e23e878..3b68166af 100644
--- a/tests/stdlib/theapqueue.nim
+++ b/tests/stdlib/theapqueue.nim
@@ -1,4 +1,4 @@
-import heapqueue
+import std/heapqueue
 
 
 proc toSortedSeq[T](h: HeapQueue[T]): seq[T] =
@@ -7,47 +7,96 @@ proc toSortedSeq[T](h: HeapQueue[T]): seq[T] =
   while tmp.len > 0:
     result.add(pop(tmp))
 
-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])
+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
 
-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)
+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])
 
-  heap.del(0)
-  doAssert(heap[0] == 1)
+  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(heap.find(7))
-  doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 5, 6, 8, 9])
+    heap.del(0)
+    doAssert(heap[0] == 1)
 
-  heap.del(heap.find(5))
-  doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 6, 8, 9])
+    heap.del(heap.find(7))
+    doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 5, 6, 8, 9])
 
-  heap.del(heap.find(6))
-  doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 8, 9])
+    heap.del(heap.find(5))
+    doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 6, 8, 9])
 
-  heap.del(heap.find(2))
-  doAssert(heap.toSortedSeq == @[1, 3, 4, 8, 9])
+    heap.del(heap.find(6))
+    doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 8, 9])
 
-  doAssert(heap.find(2) == -1)
+    heap.del(heap.find(2))
+    doAssert(heap.toSortedSeq == @[1, 3, 4, 8, 9])
 
-block: # Test del last
-  var heap = initHeapQueue[int]()
-  let data = [1, 2, 3]
-  for item in data: push(heap, item)
+    doAssert(heap.find(2) == -1)
 
-  heap.del(2)
-  doAssert(heap.toSortedSeq == @[1, 2])
+  block: # test del last
+    var heap = initHeapQueue[int]()
+    let data = [1, 2, 3]
+    for item in data: push(heap, item)
 
-  heap.del(1)
-  doAssert(heap.toSortedSeq == @[1])
+    heap.del(2)
+    doAssert(heap.toSortedSeq == @[1, 2])
 
-  heap.del(0)
-  doAssert(heap.toSortedSeq == @[])
+    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()