Debian Codegraph @

ext/data/test-heap.scm

raw
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)