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