| 1 |
;; |
| 2 |
;; Testing data.heap |
| 3 |
;; The test uses math.mt-random, so we test it here (the impmentation |
| 4 |
;; doesn't depend on it, though). |
| 5 |
;; |
| 6 |
|
| 7 |
(use gauche.test) |
| 8 |
(test-start "data.heap") |
| 9 |
(test-section "data.heap") |
| 10 |
(use data.heap) |
| 11 |
(test-module 'data.heap) |
| 12 |
|
| 13 |
(use scheme.list) |
| 14 |
(use srfi.27) |
| 15 |
(use gauche.sequence) |
| 16 |
(use util.match) |
| 17 |
|
| 18 |
(let ((rs (make-random-source))) |
| 19 |
(define (do-test data comparator) ; data must be sorted |
| 20 |
(define len (length data)) |
| 21 |
(define heap (make-binary-heap :storage (make-vector len) |
| 22 |
:comparator comparator)) |
| 23 |
(let1 input (shuffle data rs) |
| 24 |
(test* (format "heap(~s) insertion ~s" len input) |
| 25 |
(map-with-index (^[i e] (list i e #t #t)) input) |
| 26 |
(let ([zmin #f] |
| 27 |
[zmax #f]) |
| 28 |
(map-with-index |
| 29 |
(^[i e] |
| 30 |
(begin |
| 31 |
(binary-heap-push! heap e) |
| 32 |
(binary-heap-check heap) |
| 33 |
(when (or (not zmin) |
| 34 |
(< (comparator-compare comparator e zmin) 0)) |
| 35 |
(set! zmin e)) |
| 36 |
(when (or (not zmax) |
| 37 |
(> (comparator-compare comparator e zmax) 0)) |
| 38 |
(set! zmax e)) |
| 39 |
(list i e |
| 40 |
(equal? (binary-heap-find-min heap) zmin) |
| 41 |
(equal? (binary-heap-find-max heap) zmax)))) |
| 42 |
input)))) |
| 43 |
(let1 hp1 (binary-heap-copy heap) |
| 44 |
(test* (format "heap(~s) clear" len) #t |
| 45 |
(begin |
| 46 |
(binary-heap-clear! hp1) |
| 47 |
(binary-heap-empty? hp1)))) |
| 48 |
(let1 hp1 (binary-heap-copy heap) |
| 49 |
(test* (format "heap(~s) deletion from min" len) |
| 50 |
data |
| 51 |
(map-in-order (^_ (begin0 (binary-heap-pop-min! hp1) |
| 52 |
(binary-heap-check hp1))) |
| 53 |
(iota len)))) |
| 54 |
(let1 hp1 (binary-heap-copy heap) |
| 55 |
(test* (format "heap(~s) deletion from max" len) |
| 56 |
(reverse data) |
| 57 |
(map-in-order (^_ (begin0 (binary-heap-pop-max! hp1) |
| 58 |
(binary-heap-check hp1))) |
| 59 |
(iota len)))) |
| 60 |
(let1 hp1 (binary-heap-copy heap) |
| 61 |
(test* (format "heap(~s) deletion mixed" len) |
| 62 |
(map list |
| 63 |
(take data (quotient len 2)) |
| 64 |
(take (reverse data) (quotient len 2))) |
| 65 |
(map-in-order (^_ (let* ([x (binary-heap-pop-min! hp1)] |
| 66 |
[y (binary-heap-pop-max! hp1)]) |
| 67 |
(binary-heap-check hp1) |
| 68 |
(list x y))) |
| 69 |
(iota (quotient len 2))))) |
| 70 |
) |
| 71 |
|
| 72 |
(do-test (iota 15) default-comparator) |
| 73 |
(do-test (iota 253) default-comparator) |
| 74 |
(do-test (reverse (iota 33)) |
| 75 |
(make-comparator/compare number? #t (^[a b] (- (compare a b))) #f)) |
| 76 |
(do-test '(#\a #\b #\c #\d #\e) default-comparator) |
| 77 |
) |
| 78 |
|
| 79 |
(let ((rs (make-random-source))) |
| 80 |
(define (suck-all heap) |
| 81 |
(do ([r '() (cons (binary-heap-pop-min! heap) r)]) |
| 82 |
[(binary-heap-empty? heap) (reverse r)] |
| 83 |
)) |
| 84 |
(define (do-heapify lis builder comparator) |
| 85 |
(test* (format "heapify ~s" lis) |
| 86 |
lis |
| 87 |
(let* ([src (builder (shuffle lis rs))] |
| 88 |
[heap (build-binary-heap src :comparator comparator)]) |
| 89 |
(binary-heap-check heap) |
| 90 |
(suck-all heap)))) |
| 91 |
(define (do-scan lis pred item) |
| 92 |
(test* (format "find, remove, delete ~s" lis) |
| 93 |
(list (boolean (find pred lis)) |
| 94 |
(remove pred lis) |
| 95 |
(delete item lis)) |
| 96 |
(let ([heap (build-binary-heap (list->vector (shuffle lis rs)))]) |
| 97 |
(list (if-let1 r (binary-heap-find pred heap) |
| 98 |
(pred r) |
| 99 |
#f) |
| 100 |
(let1 h (binary-heap-copy heap) |
| 101 |
(binary-heap-remove! h pred) |
| 102 |
(binary-heap-check h) |
| 103 |
(suck-all h)) |
| 104 |
(let1 h (binary-heap-copy heap) |
| 105 |
(binary-heap-delete! h item) |
| 106 |
(binary-heap-check h) |
| 107 |
(suck-all h)))))) |
| 108 |
|
| 109 |
(do-heapify '() list->vector default-comparator) |
| 110 |
(do-heapify '(1) list->vector default-comparator) |
| 111 |
(do-heapify (iota 33) list->vector default-comparator) |
| 112 |
(do-heapify '("a" "aa" "b" "bb" "c" "cc" "d" "dd") list->vector |
| 113 |
string-comparator) |
| 114 |
|
| 115 |
(do-scan '() odd? 1) |
| 116 |
(do-scan (iota 23) odd? 5) |
| 117 |
(do-scan (iota 42) (^n (< (modulo n 3) 2)) 91) |
| 118 |
) |
| 119 |
|
| 120 |
;; check binary-heap-find old & new API |
| 121 |
(let ([h (build-binary-heap (vector 0 8 2 16 11 24 4 10))]) |
| 122 |
(test* "binary-heap-find (new)" 11 |
| 123 |
(binary-heap-find odd? h)) |
| 124 |
(test* "binary-heap-find (new)" #f |
| 125 |
(binary-heap-find (cut > <> 100) h)) |
| 126 |
(test* "binary-heap-find (new)" 'oops |
| 127 |
(binary-heap-find (cut > <> 100) h (constantly 'oops))) |
| 128 |
(test* "binary-heap-find (old)" '11 |
| 129 |
(binary-heap-find h odd?))) |
| 130 |
|
| 131 |
|
| 132 |
(let () |
| 133 |
(define (test-swap source actions) |
| 134 |
;; actions : ((min|max item expected-result expected-min expected-max) ...) |
| 135 |
(let1 hp (build-binary-heap source) |
| 136 |
(dolist [action actions] |
| 137 |
(match-let1 (minmax item xresult xmin xmax) action |
| 138 |
(test* (format "swap ~s ~s ~s" source minmax item) |
| 139 |
(list xresult xmin xmax) |
| 140 |
(let1 r ((ecase minmax |
| 141 |
[(min) binary-heap-swap-min!] |
| 142 |
[(max) binary-heap-swap-max!]) |
| 143 |
hp item) |
| 144 |
(list r |
| 145 |
(binary-heap-find-min hp) |
| 146 |
(binary-heap-find-max hp)))))))) |
| 147 |
|
| 148 |
(test-swap (vector 1 3 5 7 9 11 13 15 17) |
| 149 |
'((min 4 1 3 17) |
| 150 |
(min 2 3 2 17) |
| 151 |
(max 16 17 2 16) |
| 152 |
(max 1 16 1 15) |
| 153 |
(min 20 1 2 20) |
| 154 |
(min 10 2 4 20))) |
| 155 |
(test-swap (vector 1) |
| 156 |
'((min 2 1 2 2) |
| 157 |
(max 1 2 1 1) |
| 158 |
(min 0 1 0 0))) |
| 159 |
(test-swap (vector 3 1) |
| 160 |
'((min 4 1 3 4) |
| 161 |
(max 5 4 3 5) |
| 162 |
(min 6 3 5 6) |
| 163 |
(max 0 6 0 5))) |
| 164 |
(test-swap (vector 4 2 5) |
| 165 |
'((max 3 5 2 4) |
| 166 |
(max 1 4 1 3) |
| 167 |
(max 1 3 1 2) |
| 168 |
(max 1 2 1 1) |
| 169 |
(max 1 1 1 1))) |
| 170 |
) |
| 171 |
|
| 172 |
(test-end) |