Debian Codegraph @

ext/sparse/test.scm

raw
1 ;;
2 ;; testing data.sparse
3 ;;
4
5 (use gauche.test)
6 (use gauche.generator)
7 (use data.random)
8 (use util.match)
9 (use scheme.list)
10 (use srfi.27)
11
12 (test-start "data.sparse")
13 (use data.sparse)
14 (test-module 'data.sparse)
15 (use gauche.collection)
16
17 (define (simple-test name obj %ref %set! %exists? %fold key1 key2
18 :optional (val1 'ok) (val2 'okok) (val3 'okokok))
19 (test* #"~name basic set!/ref" val1
20 (begin (%set! obj (key1) val1)
21 (%ref obj (key1))))
22 (test* #"~name generic set!/ref" val1
23 (begin (set! (~ obj (key1)) val1)
24 (~ obj (key1))))
25 (test* #"~name referencing nokey" (test-error)
26 (%ref obj (key2)))
27 (test* #"~name referencing nokey fallback" 'huh?
28 (%ref obj (key2) 'huh?))
29 (test* #"~name exists?" #t (%exists? obj (key1)))
30 (test* #"~name exists?" #f (%exists? obj (key2)))
31 (test* #"~name replace" val2
32 (begin (%set! obj (key1) val2)
33 (%ref obj (key1))))
34 (test* #"~name add" val3
35 (begin (%set! obj (key2) val3)
36 (%ref obj (key2))))
37 (test* #"~name ref" val2 (%ref obj (key1)))
38 (test* #"~name generic setter" val1
39 (begin (set! (%ref obj (key1)) val1)
40 (%ref obj (key1))))
41 (test* #"~name folder" '(2 #t)
42 (let1 lis (%fold obj acons '())
43 (list (length lis)
44 (every (^p (eqv? (%ref obj (car p)) (cdr p))) lis))))
45 )
46
47 (define (const x) (^[] x))
48
49 ;; To test sparse table seriously, set *data-set-size* larger number
50 ;; like 20000. The default size is chosen not to take too long for the tests.
51 (define *data-set-size* 5000)
52
53 (define *data-set*
54 (rlet1 ht (make-hash-table 'eqv?)
55 (let loop ([i 0])
56 (unless (= i *data-set-size*)
57 (let1 k (random-integer (expt 2 32))
58 (cond [(hash-table-exists? ht k) (loop i)]
59 [else (hash-table-put! ht k (* k k)) (loop (+ i 1))]))))))
60
61 (define (heavy-test name obj %ref %set! %cnt %clr %keys %vals %del %copy
62 %check keygen valgen)
63 (test* #"~name many set!" *data-set-size*
64 (let/cc return
65 (hash-table-fold *data-set*
66 (^[k v cnt]
67 (let ([kk (keygen k)]
68 [vv (valgen v)])
69 (if (and (not (%ref obj kk #f))
70 (begin (%set! obj kk vv)
71 (equal? vv (%ref obj kk #f))))
72 (+ cnt 1)
73 (return
74 `(error ,cnt ,kk ,vv ,(%ref obj kk #f))))))
75 0)))
76
77 (test* #"~name many numelements" *data-set-size* (%cnt obj))
78
79 (when %check (test* #"~name many check" #t (begin (%check obj) #t)))
80
81 (test* #"~name many ref" *data-set-size*
82 (let/cc return
83 (hash-table-fold *data-set*
84 (^[k v cnt]
85 (let ([kk (keygen k)]
86 [vv (valgen v)])
87 (if (equal? (%ref obj kk) vv)
88 (+ cnt 1)
89 (return `(error ,cnt ,kk ,vv ,(%ref obj kk))))))
90 0)))
91 (test* #"~name keys" *data-set-size*
92 (let/cc return
93 (let1 tt (make-sparse-table 'equal?)
94 (hash-table-for-each *data-set*
95 (^[k v]
96 (sparse-table-set! tt (keygen k) #t)))
97 (fold (^[k cnt] (if (sparse-table-ref tt k #f)
98 (+ cnt 1)
99 (return `(error ,cnt ,k))))
100 0 (%keys obj)))))
101 (test* #"~name values" *data-set-size*
102 (let/cc return
103 (let1 tt (make-sparse-table 'equal?)
104 (hash-table-for-each *data-set*
105 (^[k v]
106 (sparse-table-set! tt (valgen v) #t)))
107 (fold (^[v cnt] (if (sparse-table-ref tt v #f)
108 (+ cnt 1)
109 (return `(error ,cnt ,v))))
110 0 (%vals obj)))))
111 (test* #"~name generic iteration" *data-set-size*
112 (fold (^[kv cnt] (if (equal? (%ref obj (car kv)) (cdr kv))
113 (+ cnt 1)
114 cnt))
115 0 obj))
116 (test* #"~name many copy" (list *data-set-size* #t #t)
117 (let* ([new (%copy obj)]
118 [keys (%keys new)])
119 (list (length keys)
120 (if %check (begin (%check new) #t) #t)
121 (every (^k (equal? (%ref new k) (%ref obj k))) keys))))
122
123 (test* #"~name many clear!" 0 (begin (%clr obj) (%cnt obj)))
124 (test* #"~name many ref2" *data-set-size*
125 (let/cc return
126 (hash-table-fold *data-set*
127 (^[k v cnt]
128 (let ([kk (keygen k)]
129 [vv (valgen v)])
130 (if (%ref obj kk #f)
131 (return `(error ,cnt ,kk ,vv ,(%ref obj kk)))
132 (+ cnt 1))))
133 0)))
134 (test* #"~name many delete!" '(#t 0)
135 (begin
136 (hash-table-for-each *data-set*
137 (^[k v] (%set! obj (keygen k) (valgen v))))
138 (when %check (%check obj))
139 (let1 r
140 (hash-table-fold *data-set*
141 (^[k v s]
142 (when %check (%check obj))
143 (and s (%del obj (keygen k))))
144 #t)
145 (list r (%cnt obj)))))
146 )
147
148 ;; sparse vector-------------------------------------------------
149 (test-section "sparse-vector")
150
151 (define (spvec-simple tag)
152 (apply simple-test #"sparse-~(or tag \"\")vector" (make-sparse-vector tag)
153 sparse-vector-ref sparse-vector-set! sparse-vector-exists?
154 sparse-vector-fold
155 (const 0) (const 1)
156 (if (memq tag '(f16 f32 f64))
157 '(3.0 6.0 9.0)
158 '(3 6 9))))
159
160 (for-each spvec-simple '(#f s8 u8 s16 u16 s32 u32 s64 u64 f16 f32 f64))
161
162 (define (spvec-heavy tag valgen)
163 (heavy-test #"sparse-~(or tag \"\")vector"
164 (make-sparse-vector tag)
165 sparse-vector-ref sparse-vector-set!
166 sparse-vector-num-entries sparse-vector-clear!
167 sparse-vector-keys sparse-vector-values sparse-vector-delete!
168 sparse-vector-copy #f
169 values valgen))
170
171 (spvec-heavy #f values)
172 (spvec-heavy 's8 (^x (- (logand x #xff) #x80)))
173 (spvec-heavy 'u8 (^x (logand x #xff)))
174 (spvec-heavy 's16 (^x (- (logand x #xffff) #x8000)))
175 (spvec-heavy 'u16 (^x (logand x #xffff)))
176 (spvec-heavy 's32 (^x (- (logand x #xffffffff) #x80000000)))
177 (spvec-heavy 'u32 (^x (logand x #xffffffff)))
178 (spvec-heavy 's64 (^x (- (logand x #xffffffffffffffff)
179 #x8000000000000000)))
180 (spvec-heavy 'u64 (^x (logand x #xffffffffffffffff)))
181 (spvec-heavy 'f16 (^x (exact->inexact (logand x #x3ff))))
182 (spvec-heavy 'f32 (^x (exact->inexact (logand x #xfffff))))
183 (spvec-heavy 'f64 exact->inexact)
184
185
186 ;; sparse table----------------------------------------------------
187 (test-section "sparse-table")
188
189 (define (sptab-simple type key1 key2)
190 (simple-test #"sparse-table (~type)" (make-sparse-table type)
191 sparse-table-ref sparse-table-set! sparse-table-exists?
192 sparse-table-fold
193 key1 key2))
194
195 (sptab-simple 'eq? (const 'a) (const 'b))
196 (sptab-simple 'eqv? (cut / 3) (cut / 2))
197 (sptab-simple 'equal? (cut list 1) (cut list 2))
198 (sptab-simple 'string=? (cut string #\a) (cut string #\b))
199
200 (define (sptab-heavy type keygen)
201 (heavy-test #"sparse-table (~type)" (make-sparse-table type)
202 sparse-table-ref sparse-table-set! sparse-table-num-entries
203 sparse-table-clear! sparse-table-keys sparse-table-values
204 sparse-table-delete! sparse-table-copy %sparse-table-check
205 keygen values))
206
207 (sptab-heavy 'eqv? values)
208 (sptab-heavy 'equal? (^k (list k k)))
209 (sptab-heavy 'string=? (^k (number->string k 36)))
210
211 ;; The following tests use specifically crafted keys that
212 ;; have the same hash value, so we go through 'chained' leaf path.
213
214 (let ([t (make-sparse-table 'equal?)]
215 [keys '((0 . 5) (1 . 0) #(0 5) #(1 0))])
216
217 (define (vals tab) (map (cut sparse-table-ref tab <> #f) keys))
218
219 (sparse-table-set! t '(0 . 5) 'a)
220 (sparse-table-set! t '(1 . 0) 'b)
221 (sparse-table-set! t '#(0 5) 'c)
222 (sparse-table-set! t '#(1 0) 'd)
223
224 (test* "key conflicts / ref" '(a b c d) (vals t))
225 (test* "key conflicts / set" '((z . a) (z . b) (z . c) (z . d))
226 (begin (for-each (cut sparse-table-push! t <> 'z) keys)
227 (vals t)))
228 (let1 u (sparse-table-copy t)
229 (test* "key conflicts / copy 1" '((z . a) (z . b) (z . c) (z . d))
230 (vals u))
231 (test* "key conflicts / copy 2" '((z z z z) (a b c d))
232 (let1 z (map (cut sparse-table-pop! u <>) keys)
233 (list z (vals u))))
234 (test* "key conflicts / copy (original)" '((z . a) (z . b) (z . c) (z . d))
235 (vals t))
236
237 (test* "key conflicts delete 1" '(#f b c d)
238 (begin (sparse-table-delete! u '(0 . 5)) (vals u)))
239 (test* "key conflicts delete 2" '(#f b #f d)
240 (begin (sparse-table-delete! u '#(0 5)) (vals u)))
241 (test* "key conflicts delete 3" '(#f b #f #f)
242 (begin (sparse-table-delete! u '#(1 0)) (vals u)))
243 (test* "key conflicts delete 4" '(#f #f #f #f)
244 (begin (sparse-table-delete! u '(1 . 0)) (vals u)))
245 ))
246
247 ;; custom comparator
248 (let ()
249 (define c (make-comparator #t (^[a b] (= (modulo a 3) (modulo b 3))) #f
250 (^x (modulo x 3))))
251 (define t (make-sparse-table c))
252
253 (dotimes [x 10] (sparse-table-set! t x (+ x 100)))
254 (test* "custom comparator" '((0 . 109) (1 . 107) (2 . 108))
255 (sort-by (sparse-table-map t cons) car))
256 (test* "sparse-table-comparator" c
257 (sparse-table-comparator t)))
258
259 (let ([predefs `((eq? . ,eq-comparator)
260 (eqv? . ,eqv-comparator)
261 (equal? . ,equal-comparator)
262 (string=? . ,string-comparator))])
263 (test* "predefined comparators" predefs
264 (map (^p (cons (car p)
265 ($ sparse-table-comparator
266 $ make-sparse-table (car p))))
267 predefs)))
268
269
270 ;; Default value behavior
271 (let ()
272 (define z (make-sparse-vector #f :default 99))
273 (define y (make-sparse-vector #f :default '(a)))
274
275 (test* "sparse vector with default value" 99
276 (sparse-vector-ref z (expt 2 1000)))
277 (test* "sparse-vector-inc! with default value" '(100 10)
278 (begin
279 (sparse-vector-inc! z 3 1)
280 (sparse-vector-inc! z 5 1 9)
281 (list (sparse-vector-ref z 3)
282 (sparse-vector-ref z 5))))
283 (test* "sparse-vector-pop! with default value" 'a
284 (sparse-vector-pop! y 0))
285 (test* "sparse-vector-push! with default value" '(b a)
286 (begin
287 (sparse-vector-push! y 1 'b)
288 (sparse-vector-ref y 1)))
289 )
290
291 ;; sparse matrix----------------------------------------------------
292 (test-section "sparse-matrix")
293
294 (set! (random-data-seed) 42) ; for consistent result
295
296 (let ()
297 (define data
298 (delete-duplicates
299 (generator->list
300 (gmap cons
301 (lists-of 2 (integers$ (if (> (greatest-fixnum) (expt 2 32))
302 (expt 2 32)
303 (expt 2 16))))
304 (strings-of))
305 1000)
306 (^[a b] (equal? (car a) (car b)))))
307
308 (test* "set! and ref" (list (length data) #f)
309 (let1 mat (make-sparse-matrix)
310 (dolist [d data]
311 (match-let1 ((x y) . v) d
312 (sparse-matrix-set! mat x y v)))
313 (list
314 (sparse-matrix-num-entries mat)
315 (any (^[d]
316 (match-let1 ((x y) . v) d
317 (if (equal? (sparse-matrix-ref mat x y) v)
318 #f
319 (list x y v (sparse-matrix-ref mat x y)))))
320 data))))
321
322 (test* "fold" '(() ())
323 (let ([mat (make-sparse-matrix)]
324 [tab (make-hash-table 'equal?)]
325 [bad '()])
326 (dolist [d data]
327 (match-let1 ((x y) . v) d
328 (sparse-matrix-set! mat x y v)
329 (hash-table-put! tab (cons x y) v)))
330 ($ sparse-matrix-for-each mat
331 (^[x y v]
332 (unless (equal? v (hash-table-get tab (cons x y) #f))
333 (push! bad (list x y (hash-table-get tab (cons x y) #f) v)))
334 (hash-table-delete! tab (cons x y))))
335 (list bad (hash-table->alist tab))))
336
337 (test* "setter, default value" '(a b (z . a) (a . a))
338 (let* ([mat (make-sparse-matrix #f :default 'a)]
339 [a (sparse-matrix-ref mat 100 200)]
340 [_ (set! (sparse-matrix-ref mat 100 200) 'b)]
341 [b (sparse-matrix-ref mat 100 200)]
342 [_ (sparse-matrix-push! mat 200 100 'z)]
343 [za (sparse-matrix-ref mat 200 100)]
344 [_ (sparse-matrix-update! mat 300 400
345 (^x (cons x x)))]
346 [aa (sparse-matrix-ref mat 300 400)])
347 (list a b za aa)))
348
349 (test* "uniform" '(#f 3 #t 13)
350 (let* ([mat (make-sparse-matrix 'u8)]
351 [A (sparse-matrix-exists? mat 123 456)]
352 [_ (sparse-matrix-set! mat 123 456 3)]
353 [a (sparse-matrix-ref mat 123 456)]
354 [B (sparse-matrix-exists? mat 123 456)]
355 [_ (sparse-matrix-inc! mat 123 456 10)]
356 [b (sparse-matrix-ref mat 123 456)])
357 (list A a B b)))
358 )
359
360 (test-end)