Debian Codegraph @

test/include/srfi-146-tests.scm

raw
1 ;; -*- coding:utf-8 -*-
2 ;; Copyright (C) Marc Nieper-Wißkirchen (2016, 2017). All Rights
3 ;; Reserved.
4
5 ;; Permission is hereby granted, free of charge, to any person
6 ;; obtaining a copy of this software and associated documentation
7 ;; files (the "Software"), to deal in the Software without
8 ;; restriction, including without limitation the rights to use, copy,
9 ;; modify, merge, publish, distribute, sublicense, and/or sell copies
10 ;; of the Software, and to permit persons to whom the Software is
11 ;; furnished to do so, subject to the following conditions:
12
13 ;; The above copyright notice and this permission notice shall be
14 ;; included in all copies or substantial portions of the Software.
15
16 ;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 ;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 ;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 ;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20 ;; BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21 ;; ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 ;; CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 ;; SOFTWARE.
24
25 (define-library (srfi 146 test)
26 (export run-tests)
27 (import (scheme base)
28 (srfi 1)
29 (srfi 8)
30 (srfi 64)
31 (srfi 128)
32 (srfi 146))
33 (begin
34 (define (run-tests)
35 (test-begin "SRFI 146")
36
37 (test-group "Predicates"
38 (define mapping0 (mapping comparator))
39 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
40 (define mapping2 (mapping comparator 'c 1 'd 2 'e 3))
41 (define mapping3 (mapping comparator 'd 1 'e 2 'f 3))
42
43 (test-assert "mapping?: a mapping"
44 (mapping? (mapping comparator)))
45
46 (test-assert "mapping?: not a mapping"
47 (not (mapping? (list 1 2 3))))
48
49 (test-assert "mapping-empty?: empty mapping"
50 (mapping-empty? mapping0))
51
52 (test-assert "mapping-empty?: non-empty mapping"
53 (not (mapping-empty? mapping1)))
54
55 (test-assert "mapping-contains?: containing"
56 (mapping-contains? mapping1 'b))
57
58 (test-assert "mapping-contains?: not containing"
59 (not (mapping-contains? mapping1 '2)))
60
61 (test-assert "mapping-disjoint?: disjoint"
62 (mapping-disjoint? mapping1 mapping3))
63
64 (test-assert "mapping-disjoint?: not disjoint"
65 (not (mapping-disjoint? mapping1 mapping2))))
66
67 (test-group "Accessors"
68 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
69
70 (test-equal "mapping-ref: key found"
71 2
72 (mapping-ref mapping1 'b))
73
74 (test-equal "mapping-ref: key not found/with failure"
75 42
76 (mapping-ref mapping1 'd (lambda () 42)))
77
78 (test-error "mapping-ref: key not found/without failure"
79 (mapping-ref mapping1 'd))
80
81 (test-equal "mapping-ref: with success procedure"
82 (* 2 2)
83 (mapping-ref mapping1 'b (lambda () #f) (lambda (x) (* x x))))
84
85 (test-equal "mapping-ref/default: key found"
86 3
87 (mapping-ref/default mapping1 'c 42))
88
89 (test-equal "mapping-ref/default: key not found"
90 42
91 (mapping-ref/default mapping1 'd 42))
92
93 (test-equal "mapping-key-comparator"
94 comparator
95 (mapping-key-comparator mapping1)))
96
97 (test-group "Updaters"
98 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
99 (define mapping2 (mapping-set mapping1 'c 4 'd 4 'd 5))
100 (define mapping3 (mapping-update mapping1 'b (lambda (x) (* x x))))
101 (define mapping4 (mapping-update/default mapping1 'd (lambda (x) (* x x)) 4))
102 (define mapping5 (mapping-adjoin mapping1 'c 4 'd 4 'd 5))
103 (define mapping0 (mapping comparator))
104
105 (test-equal "mapping-adjoin: key already in mapping"
106 3
107 (mapping-ref mapping5 'c))
108
109 (test-equal "mapping-adjoin: key set earlier"
110 4
111 (mapping-ref mapping5 'd))
112
113 (test-equal "mapping-set: key already in mapping"
114 4
115 (mapping-ref mapping2 'c))
116
117 (test-equal "mapping-set: key set earlier"
118 5
119 (mapping-ref mapping2 'd))
120
121 (test-equal "mapping-replace: key not in mapping"
122 #f
123 (mapping-ref/default (mapping-replace mapping1 'd 4) 'd #f))
124
125 (test-equal "mapping-replace: key in mapping"
126 6
127 (mapping-ref (mapping-replace mapping1 'c 6) 'c))
128
129 (test-equal "mapping-delete"
130 42
131 (mapping-ref/default (mapping-delete mapping1 'b) 'b 42))
132
133 (test-equal "mapping-delete-all"
134 42
135 (mapping-ref/default (mapping-delete-all mapping1 '(a b)) 'b 42))
136
137 (test-equal "mapping-intern: key in mapping"
138 (list mapping1 2)
139 (receive result
140 (mapping-intern mapping1 'b (lambda () (error "should not have been invoked")))
141 result))
142
143 (test-equal "mapping-intern: key not in mapping"
144 (list 42 42)
145 (receive (mapping value)
146 (mapping-intern mapping1 'd (lambda () 42))
147 (list value (mapping-ref mapping 'd))))
148
149 (test-equal "mapping-update"
150 4
151 (mapping-ref mapping3 'b))
152
153 (test-equal "mapping-update/default"
154 16
155 (mapping-ref mapping4 'd))
156
157 (test-equal "mapping-pop: empty mapping"
158 'empty
159 (mapping-pop mapping0 (lambda () 'empty)))
160
161 (test-equal "mapping-pop: non-empty mapping"
162 (list 2 'a 1)
163 (receive (mapping key value)
164 (mapping-pop mapping1)
165 (list (mapping-size mapping) key value)))
166
167 (test-equal
168 '("success updated"
169 "failure ignored"
170 ((0 . "zero") (1 . "one") (2 . "two [seen]") (3 . "three")
171 (4 . "four") (5 . "five")))
172 (let ((m1 (mapping (make-default-comparator)
173 1 "one"
174 3 "three"
175 0 "zero"
176 4 "four"
177 2 "two"
178 5 "five")))
179 (define (f/ignore insert ignore)
180 (ignore "failure ignored"))
181 (define (s/update key val update remove)
182 (update key
183 (string-append val " [seen]")
184 "success updated"))
185 (let*-values (((m2 v2) (mapping-search m1 2 f/ignore s/update))
186 ((m3 v3) (mapping-search m2 42 f/ignore s/update)))
187 (list v2 v3 (mapping->alist m3))))))
188
189 (test-group "The whole mapping"
190 (define mapping0 (mapping comparator))
191 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
192
193 (test-equal "mapping-size: empty mapping"
194 0
195 (mapping-size mapping0))
196
197 (test-equal "mapping-size: non-empty mapping"
198 3
199 (mapping-size mapping1))
200
201 (test-equal "mapping-find: found in mapping"
202 (list 'b 2)
203 (receive result
204 (mapping-find (lambda (key value)
205 (and (eq? key 'b)
206 (= value 2)))
207 mapping1
208 (lambda () (error "should not have been called")))
209 result))
210
211 (test-equal "mapping-find: not found in mapping"
212 (list 42)
213 (receive result
214 (mapping-find (lambda (key value)
215 (eq? key 'd))
216 mapping1
217 (lambda ()
218 42))
219 result))
220
221 (test-equal "mapping-count"
222 2
223 (mapping-count (lambda (key value)
224 (>= value 2))
225 mapping1))
226
227 (test-assert "mapping-any?: found"
228 (mapping-any? (lambda (key value)
229 (= value 3))
230 mapping1))
231
232 (test-assert "mapping-any?: not found"
233 (not (mapping-any? (lambda (key value)
234 (= value 4))
235 mapping1)))
236
237 (test-assert "mapping-every?: true"
238 (mapping-every? (lambda (key value)
239 (<= value 3))
240 mapping1))
241
242 (test-assert "mapping-every?: false"
243 (not (mapping-every? (lambda (key value)
244 (<= value 2))
245 mapping1)))
246
247 (test-equal "mapping-keys"
248 3
249 (length (mapping-keys mapping1)))
250
251 (test-equal "mapping-values"
252 6
253 (fold + 0 (mapping-values mapping1)))
254
255 (test-equal "mapping-entries"
256 (list 3 6)
257 (receive (keys values)
258 (mapping-entries mapping1)
259 (list (length keys) (fold + 0 values)))))
260
261 (test-group "Mapping and folding"
262 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
263 (define mapping2 (mapping-map (lambda (key value)
264 (values (symbol->string key)
265 (* 10 value)))
266 comparator
267 mapping1))
268
269 (test-equal "mapping-map"
270 20
271 (mapping-ref mapping2 "b"))
272
273 (test-equal "mapping-for-each"
274 6
275 (let ((counter 0))
276 (mapping-for-each (lambda (key value)
277 (set! counter (+ counter value)))
278 mapping1)
279 counter))
280
281 (test-equal "mapping-fold"
282 6
283 (mapping-fold (lambda (key value acc)
284 (+ value acc))
285 0
286 mapping1))
287
288 (test-equal "mapping-map->list"
289 (+ (* 1 1) (* 2 2) (* 3 3))
290 (fold + 0 (mapping-map->list (lambda (key value)
291 (* value value))
292 mapping1)))
293
294 (test-equal "mapping-filter"
295 2
296 (mapping-size (mapping-filter (lambda (key value)
297 (<= value 2))
298 mapping1)))
299
300 (test-equal "mapping-remove"
301 1
302 (mapping-size (mapping-remove (lambda (key value)
303 (<= value 2))
304 mapping1)))
305
306 (test-equal "mapping-partition"
307 (list 1 2)
308 (receive result
309 (mapping-partition (lambda (key value)
310 (eq? 'b key))
311 mapping1)
312 (map mapping-size result)))
313
314 (test-group "Copying and conversion"
315 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
316 (define mapping2 (alist->mapping comparator '((a . 1) (b . 2) (c . 3))))
317 (define mapping3 (alist->mapping! (mapping-copy mapping1) '((d . 4) '(c . 5))))
318
319 (test-equal "mapping-copy: same size"
320 3
321 (mapping-size (mapping-copy mapping1)))
322
323 (test-equal "mapping-copy: same comparator"
324 comparator
325 (mapping-key-comparator (mapping-copy mapping1)))
326
327 (test-equal "mapping->alist"
328 (cons 'b 2)
329 (assq 'b (mapping->alist mapping1)))
330
331 (test-equal "alist->mapping"
332 2
333 (mapping-ref mapping2 'b)
334 )
335
336 (test-equal "alist->mapping!: new key"
337 4
338 (mapping-ref mapping3 'd))
339
340 (test-equal "alist->mapping!: existing key"
341 3
342 (mapping-ref mapping3 'c)))
343
344 (test-group "Submappings"
345 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
346 (define mapping2 (mapping comparator 'a 1 'b 2 'c 3))
347 (define mapping3 (mapping comparator 'a 1 'c 3))
348 (define mapping4 (mapping comparator 'a 1 'c 3 'd 4))
349 (define mapping5 (mapping comparator 'a 1 'b 2 'c 6))
350 (define mapping6 (mapping (make-comparator (comparator-type-test-predicate comparator)
351 (comparator-equality-predicate comparator)
352 (comparator-ordering-predicate comparator)
353 (comparator-hash-function comparator))
354 'a 1 'b 2 'c 3))
355
356 (test-assert "mapping=?: equal mappings"
357 (mapping=? comparator mapping1 mapping2))
358
359 (test-assert "mapping=?: unequal mappings"
360 (not (mapping=? comparator mapping1 mapping4)))
361
362 (test-assert "mapping=?: different comparators"
363 (not (mapping=? comparator mapping1 mapping6)))
364
365 (test-assert "mapping<?: proper subset"
366 (mapping<? comparator mapping3 mapping1))
367
368 (test-assert "mapping<?: improper subset"
369 (not (mapping<? comparator mapping3 mapping1 mapping2)))
370
371 (test-assert "mapping>?: proper superset"
372 (mapping>? comparator mapping2 mapping3))
373
374 (test-assert "mapping>?: improper superset"
375 (not (mapping>? comparator mapping1 mapping2 mapping3)))
376
377 (test-assert "mapping<=?: subset"
378 (mapping<=? comparator mapping3 mapping2 mapping1))
379
380 (test-assert "mapping<=?: non-matching values"
381 (not (mapping<=? comparator mapping3 mapping5)))
382
383 (test-assert "mapping<=?: not a subset"
384 (not (mapping<=? comparator mapping2 mapping4)))
385
386 (test-assert "mapping>=?: superset"
387 (mapping>=? comparator mapping4 mapping3))
388
389 (test-assert "mapping>=?: not a superset"
390 (not (mapping>=? comparator mapping5 mapping3))))
391
392 (test-group "Set theory operations"
393 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
394 (define mapping2 (mapping comparator 'a 1 'b 2 'd 4))
395 (define mapping3 (mapping comparator 'a 1 'b 2))
396 (define mapping4 (mapping comparator 'a 1 'b 2 'c 4))
397 (define mapping5 (mapping comparator 'a 1 'c 3))
398 (define mapping6 (mapping comparator 'd 4 'e 5 'f 6))
399
400 (test-equal "mapping-union: new association"
401 4
402 (mapping-ref (mapping-union mapping1 mapping2) 'd))
403
404 (test-equal "mapping-union: existing association"
405 3
406 (mapping-ref (mapping-union mapping1 mapping4) 'c))
407
408 (test-equal "mapping-union: three mappings"
409 6
410 (mapping-size (mapping-union mapping1 mapping2 mapping6)))
411
412 (test-equal "mapping-intersection: existing association"
413 3
414 (mapping-ref (mapping-intersection mapping1 mapping4) 'c))
415
416 (test-equal "mapping-intersection: removed association"
417 42
418 (mapping-ref/default (mapping-intersection mapping1 mapping5) 'b 42))
419
420 (test-equal "mapping-difference"
421 2
422 (mapping-size (mapping-difference mapping2 mapping6)))
423
424 (test-equal "mapping-xor"
425 4
426 (mapping-size (mapping-xor mapping2 mapping6))))
427
428 (test-group "Additional procedures for mappings with ordered keys"
429 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
430 (define mapping2 (mapping comparator 'a 1 'b 2 'c 3 'd 4))
431 (define mapping3 (mapping comparator 'a 1 'b 2 'c 3 'd 4 'e 5))
432 (define mapping4 (mapping comparator 'a 1 'b 2 'c 3 'd 4 'e 5 'f 6))
433 (define mapping5 (mapping comparator 'f 6 'g 7 'h 8))
434
435 (test-equal "mapping-min-key"
436 '(a a a a)
437 (map mapping-min-key (list mapping1 mapping2 mapping3 mapping4)))
438
439 (test-equal "mapping-max-key"
440 '(c d e f)
441 (map mapping-max-key (list mapping1 mapping2 mapping3 mapping4)))
442
443 (test-equal "mapping-min-value"
444 '(1 1 1 1)
445 (map mapping-min-value (list mapping1 mapping2 mapping3 mapping4)))
446
447 (test-equal "mapping-max-value"
448 '(3 4 5 6)
449 (map mapping-max-value (list mapping1 mapping2 mapping3 mapping4)))
450
451 (test-equal "mapping-key-predecessor"
452 '(c d d d)
453 (map (lambda (mapping)
454 (mapping-key-predecessor mapping 'e (lambda () #f)))
455 (list mapping1 mapping2 mapping3 mapping4)))
456
457 (test-equal "mapping-key-successor"
458 '(#f #f e e)
459 (map (lambda (mapping)
460 (mapping-key-successor mapping 'd (lambda () #f)))
461 (list mapping1 mapping2 mapping3 mapping4)))
462
463 (test-equal "mapping-range=: contained"
464 '(4)
465 (mapping-values (mapping-range= mapping4 'd)))
466
467 (test-equal "mapping-range=: not contained"
468 '()
469 (mapping-values (mapping-range= mapping4 'z)))
470
471 (test-equal "mapping-range<"
472 '(1 2 3)
473 (mapping-values (mapping-range< mapping4 'd)))
474
475 (test-equal "mapping-range<="
476 '(1 2 3 4)
477 (mapping-values (mapping-range<= mapping4 'd)))
478
479 (test-equal "mapping-range>"
480 '(5 6)
481 (mapping-values (mapping-range> mapping4 'd)))
482
483 (test-equal "mapping-range>="
484 '(4 5 6)
485 (mapping-values (mapping-range>= mapping4 'd)))
486
487 (test-equal "mapping-split"
488 '((1 2 3) (1 2 3 4) (4) (4 5 6) (5 6))
489 (receive mappings
490 (mapping-split mapping4 'd)
491 (map mapping-values mappings)))
492
493 (test-equal "mapping-catenate"
494 '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5) (f . 6) (g . 7) (h . 8))
495 (mapping->alist (mapping-catenate comparator mapping2 'e 5 mapping5)))
496
497 (test-equal "mapping-map/monotone"
498 '((1 . 1) (2 . 4) (3 . 9))
499 (mapping->alist
500 (mapping-map/monotone (lambda (key value)
501 (values value (* value value)))
502 comparator
503 mapping1)))
504
505 (test-equal "mapping-fold/reverse"
506 '(1 2 3)
507 (mapping-fold/reverse (lambda (key value acc)
508 (cons value acc))
509 '() mapping1)))
510
511 (test-group "Comparators"
512 (define mapping1 (mapping comparator 'a 1 'b 2 'c 3))
513 (define mapping2 (mapping comparator 'a 1 'b 2 'c 3))
514 (define mapping3 (mapping comparator 'a 1 'b 2))
515 (define mapping4 (mapping comparator 'a 1 'b 2 'c 4))
516 (define mapping5 (mapping comparator 'a 1 'c 3))
517 (define mapping0 (mapping comparator mapping1 "a" mapping2 "b" mapping3 "c" mapping4 "d" mapping5 "e"))
518
519
520 (test-assert "mapping-comparator"
521 (comparator? mapping-comparator))
522
523 (test-equal "mapping-keyed mapping"
524 (list "a" "a" "c" "d" "e")
525 (list (mapping-ref mapping0 mapping1)
526 (mapping-ref mapping0 mapping2)
527 (mapping-ref mapping0 mapping3)
528 (mapping-ref mapping0 mapping4)
529 (mapping-ref mapping0 mapping5)))
530
531 (test-group "Ordering comparators"
532 (test-assert "=?: equal mappings"
533 (=? comparator mapping1 mapping2))
534
535 (test-assert "=?: unequal mappings"
536 (not (=? comparator mapping1 mapping4)))
537
538 (test-assert "<?: case 1"
539 (<? comparator mapping3 mapping4))
540
541 (test-assert "<?: case 2"
542 (<? comparator mapping1 mapping4))
543
544 (test-assert "<?: case 3"
545 (<? comparator mapping1 mapping5)))))
546
547 (test-end "SRFI 146"))
548
549 (define comparator (make-default-comparator))))