mirror of
https://github.com/carp-lang/Carp.git
synced 2024-09-11 05:25:28 +03:00
234 lines
7.2 KiB
Plaintext
234 lines
7.2 KiB
Plaintext
(use Heap)
|
|
|
|
(load "Test.carp")
|
|
(use Test)
|
|
|
|
(deftest test
|
|
(let-do [arr [1 3 4 2 6 1]
|
|
exp [1 2 1 3 6 4]]
|
|
(MinHeap.heapify! &arr)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MinHeap.heapify! works 1"))
|
|
|
|
(let-do [arr [1 1 2 3 6 4]
|
|
exp [1 1 2 3 6 4 4]]
|
|
(MinHeap.push! &arr 4)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MinHeap.push! works I"))
|
|
|
|
(let-do [arr [1 1 2 3 6 4]
|
|
exp [0 1 1 3 6 4 2]]
|
|
(MinHeap.push! &arr 0)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MinHeap.push! works II"))
|
|
|
|
(let-do [arr [1 1 2 3 6 4]
|
|
exp []
|
|
one (MinHeap.pop! &arr)
|
|
one2 (MinHeap.pop! &arr)
|
|
two (MinHeap.pop! &arr)
|
|
three (MinHeap.pop! &arr)
|
|
four (MinHeap.pop! &arr)
|
|
six (MinHeap.pop! &arr)]
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MinHeap.pop! works as expected"))
|
|
|
|
; walk through MaxHeap.heapify! checking each step.
|
|
(let-do [arr [20 0 10 21 11]
|
|
exp [20 0 10 21 11]]
|
|
(MaxHeap.push-up! &arr 1)
|
|
(assert-equal test
|
|
&arr
|
|
&exp
|
|
"MaxHeap.push-up! works 1"))
|
|
|
|
(let-do [arr [20 0 10 21 11]
|
|
exp [20 0 10 21 11]]
|
|
(MaxHeap.push-up! &arr 2)
|
|
(assert-equal test
|
|
&arr
|
|
&exp
|
|
"MaxHeap.push-up! works 2"))
|
|
|
|
(let-do [arr [20 0 10 21 11]
|
|
exp [21 20 10 0 11]]
|
|
(MaxHeap.push-up! &arr 3)
|
|
(assert-equal test
|
|
&arr
|
|
&exp
|
|
"MaxHeap.push-up! works 3"))
|
|
|
|
(let-do [arr [21 20 10 0 11]
|
|
exp [21 20 10 0 11]]
|
|
(MaxHeap.push-up! &arr 4)
|
|
(assert-equal test
|
|
&arr
|
|
&exp
|
|
"MaxHeap.push-up! works 4"))
|
|
|
|
(let-do [arr [1 3 4 2 6 1]
|
|
exp [6 4 3 1 2 1]]
|
|
(MaxHeap.heapify! &arr)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MaxHeap.heapify! works 1"))
|
|
|
|
(let-do [arr [20 0 10]
|
|
exp [20 0 10]]
|
|
(MaxHeap.heapify! &arr)
|
|
(assert-equal test
|
|
&arr
|
|
&exp
|
|
"MaxHeap.Heapify works 2"))
|
|
|
|
(let-do [arr [20 0 10 21]
|
|
exp [21 20 10 0]]
|
|
(MaxHeap.heapify! &arr)
|
|
(assert-equal test
|
|
&arr
|
|
&exp
|
|
"MaxHeap.Heapify 3 works"))
|
|
|
|
(let-do [arr [20 0 10 21 11]
|
|
exp [21 20 10 0 11]]
|
|
(MaxHeap.heapify! &arr)
|
|
(assert-equal test
|
|
&arr
|
|
&exp
|
|
"MaxHeap.Heapify 4 works"))
|
|
|
|
; check that push-down-until! ignored the trailing elements (100, 200, 300)
|
|
; and considers both children (right child max)
|
|
(let-do [arr [3 4 6 2 1 1 100 200 300]
|
|
exp [6 4 3 2 1 1 100 200 300]]
|
|
(MaxHeap.push-down-until! &arr 0 5)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MaxHeap.push-down-until! works I (right)"))
|
|
|
|
; check that push-down-until! ignored the trailing elements (100, 200, 300)
|
|
; and considers both children (left child max)
|
|
(let-do [arr [3 6 4 2 1 1 100 200 300]
|
|
exp [6 3 4 2 1 1 100 200 300]]
|
|
(MaxHeap.push-down-until! &arr 0 5)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MaxHeap.push-down-until! works II (left)"))
|
|
|
|
(let-do [arr [1 3 4 2 6 1]
|
|
exp [1 1 2 3 4 6]]
|
|
(HeapSort.sort! &arr)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"HeapSort.sort! works"))
|
|
(let-do [res (HeapSort.sort [1 3 4 2 6 1])
|
|
exp [1 1 2 3 4 6]]
|
|
(assert-equal test
|
|
&exp
|
|
&res
|
|
"HeapSort.sort works"))
|
|
|
|
(let-do [arr [1 3 4 2 6 1]
|
|
exp [1 1 2 3 4 6]
|
|
res (HeapSort.sorted &arr)]
|
|
(assert-equal test
|
|
&exp
|
|
&res
|
|
"HeapSort.sorted works"))
|
|
|
|
; Check that HeapSort.sorted does not modify input array
|
|
(let-do [arr [1 3 4 2 6 1]
|
|
exp [1 1 2 3 4 6]
|
|
_ (HeapSort.sorted &arr)]
|
|
(assert-equal test
|
|
&arr
|
|
&[1 3 4 2 6 1]
|
|
"HeapSort.sorted does not modify array"))
|
|
|
|
; walk through HeapSort.sort! step by step
|
|
(let-do [arr [1 3 4 2 6 1]
|
|
exp [6 4 3 1 2 1]]
|
|
(MaxHeap.heapify! &arr)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"MaxHeap.heapify! works 2"))
|
|
|
|
(let-do [arr [6 4 3 2 1 1]
|
|
exp [1 4 3 2 1 6]]
|
|
(Array.swap! &arr 0 (- (Array.length &arr) 1))
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"swap works"))
|
|
|
|
(let-do [arr [1 4 3 2 1 6]
|
|
exp [4 2 3 1 1 6]]
|
|
(MaxHeap.push-down-until! &arr 0 (- (Array.length &arr) 1))
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"push down until works"))
|
|
|
|
(let-do [arr [4 2 3 1 1 6]
|
|
exp [1 2 3 1 4 6]]
|
|
(Array.swap! &arr 0 (- (Array.length &arr) 2))
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"swap 2 works"))
|
|
|
|
(let-do [arr [1 2 3 1 4 6]
|
|
exp [3 2 1 1 4 6]]
|
|
(MaxHeap.push-down-until! &arr 0 (- (Array.length &arr) 2))
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"push down until 2 works"))
|
|
|
|
(let-do [arr [3 2 1 1 4 6]
|
|
exp [1 2 1 3 4 6]]
|
|
(Array.swap! &arr 0 (- (Array.length &arr) 3))
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"swap 3 works"))
|
|
|
|
(let-do [arr [1 2 1 3 4 6]
|
|
exp [2 1 1 3 4 6]]
|
|
(MaxHeap.push-down-until! &arr 0 (- (Array.length &arr) 3))
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"push down 3 works"))
|
|
|
|
(let-do [arr [2 1 1 3 4 6]
|
|
exp [1 1 2 3 4 6]]
|
|
(Array.swap! &arr 0 (- (Array.length &arr) 4))
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"swap 4 works"))
|
|
|
|
; minimal case from bug #343
|
|
(let-do [arr [20 0 10 21 11 1 2 22 12 24 23 13 3 14 4 25 5 15 16 6 17 7 8 18 19 9]
|
|
exp (Array.range-or-default 0 25 1)]
|
|
(Array.sort! &arr)
|
|
(assert-equal test
|
|
&exp
|
|
&arr
|
|
"Heapsort.sorted bug #343"))
|
|
)
|