Debian Codegraph @

test/include/srfi-217-test.scm

raw
1 ;;; Copyright (C) 2020 Wolfgang Corcoran-Mathe
2 ;;;
3 ;;; Permission is hereby granted, free of charge, to any person obtaining a
4 ;;; copy of this software and associated documentation files (the
5 ;;; "Software"), to deal in the Software without restriction, including
6 ;;; without limitation the rights to use, copy, modify, merge, publish,
7 ;;; distribute, sublicense, and/or sell copies of the Software, and to
8 ;;; permit persons to whom the Software is furnished to do so, subject to
9 ;;; the following conditions:
10 ;;;
11 ;;; The above copyright notice and this permission notice shall be included
12 ;;; in all copies or substantial portions of the Software.
13 ;;;
14 ;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15 ;;; OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 ;;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 ;;; IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18 ;;; CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 ;;; TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20 ;;; SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21
22 (import (scheme base)
23 (scheme write)
24 (srfi 217)
25 (only (srfi 1) iota any every last take-while drop-while count
26 fold filter remove last partition)
27 )
28
29 (cond-expand
30 ((library (srfi 78))
31 (import (srfi 78)))
32 (else
33 (begin
34 (define *tests-failed* 0)
35 (define-syntax check
36 (syntax-rules (=>)
37 ((check expr => expected)
38 (if (equal? expr expected)
39 (begin
40 (display 'expr)
41 (display " => ")
42 (display expected)
43 (display " ; correct")
44 (newline))
45 (begin
46 (set! *tests-failed* (+ *tests-failed* 1))
47 (display "FAILED: for ")
48 (display 'expr)
49 (display " expected ")
50 (display expected)
51 (display " but got ")
52 (display expr)
53 (newline))))))
54 (define (check-report)
55 (if (zero? *tests-failed*)
56 (begin
57 (display "All tests passed.")
58 (newline))
59 (begin
60 (display "TESTS FAILED: ")
61 (display *tests-failed*)
62 (newline)))))))
63
64 ;;; (chibi test) / SRFI 78 shims
65
66 (define-syntax test-assert
67 (syntax-rules ()
68 ((_ expr)
69 (check expr => #t))))
70
71 (define-syntax test-not
72 (syntax-rules ()
73 ((_ expr)
74 (check expr => #f))))
75
76 (define-syntax test
77 (syntax-rules ()
78 ((_ expected expr)
79 (check expr => expected))))
80
81 (define-syntax test-equal
82 (syntax-rules ()
83 ((_ equal expected expr)
84 (check (equal expr expected) => #t))))
85
86 ;; Reify multiple values as lists. Unfortunately, this looks rather
87 ;; ugly on output. Why doesn't SRFI 78 provide a real MV test form?
88 (define-syntax test-values
89 (syntax-rules ()
90 ((test-values expected expr)
91 (check (let-values ((vs expr)) vs)
92 => (let-values ((us expected)) us)))))
93
94 ;;;; Utility
95
96 (define (print-header message)
97 (newline)
98 (display ";;; ")
99 (display message)
100 (display " ...")
101 (newline))
102
103 (define (init xs)
104 (if (null? (cdr xs))
105 '()
106 (cons (car xs) (init (cdr xs)))))
107
108 (define (constantly x)
109 (lambda (_) x))
110
111 (define pos-seq (iota 20 100 3))
112 (define neg-seq (iota 20 -100 3))
113 (define mixed-seq (iota 20 -10 3))
114 (define sparse-seq (iota 20 -10000 1003))
115
116 (define pos-set (list->iset pos-seq))
117 (define pos-set+ (iset-adjoin pos-set 9))
118 (define neg-set (list->iset neg-seq))
119 (define mixed-set (list->iset mixed-seq))
120 (define dense-set (make-range-iset 0 49))
121 (define sparse-set (list->iset sparse-seq))
122
123 (define all-test-sets
124 (list pos-set neg-set mixed-set dense-set sparse-set))
125
126 ;; Most other test groups use iset=?, so test this first.
127 (define (check-iset=?)
128 (print-header "iset=?")
129
130 (test-assert (iset=? (iset) (iset)))
131 (test-not (iset=? (iset 1) (iset)))
132 (test-not (iset=? (iset) (iset 1)))
133 (test-assert (iset=? (iset 1 2 3 4) (iset 1 2 3 4)))
134 (test-assert (iset=? (iset 1 2 3 4) (iset 2 1 4 3) (iset 3 2 1 4)))
135 (test-not (iset=? (iset 1 2 3 4) (iset 2 3 4)))
136 (test-not (iset=? pos-set neg-set))
137 )
138
139 (define (check-copying-and-conversion)
140 (print-header "Copying and conversion")
141
142 ;;; iset-copy
143 (test-assert (not (eqv? (iset-copy pos-set) pos-set)))
144 (test-assert (every (lambda (set)
145 (iset-every? (lambda (n) (iset-contains? set n))
146 (iset-copy set)))
147 all-test-sets))
148
149 ;;; iset->list
150
151 (test '() (iset->list (iset)))
152 (test pos-seq (iset->list pos-set))
153 (test neg-seq (iset->list neg-set))
154 (test mixed-seq (iset->list mixed-set))
155 (test sparse-seq (iset->list sparse-set))
156
157 (test-equal iset=? (iset 1) (list->iset! (iset) '(1)))
158 (test-equal iset=?
159 (iset-adjoin pos-set 2 4 6)
160 (list->iset! (iset-copy pos-set) '(2 4 6)))
161 )
162
163 (define (check-constructors)
164 (print-header "Constructors")
165
166 (test-equal iset=?
167 (list->iset (iota 10 0 4))
168 (iset-unfold (lambda (i) (> i 36))
169 values
170 (lambda (i) (+ i 4))
171 0))
172
173 (test-equal iset=?
174 (list->iset (iota 20 -10))
175 (make-range-iset -10 10))
176 (test-equal iset=?
177 (list->iset (iota 10 -10 2))
178 (make-range-iset -10 10 2))
179 )
180
181 (define (check-predicates)
182 (print-header "Predicates")
183
184 (test-not (iset-contains? (iset) 1))
185 (test-assert (every (lambda (n) (iset-contains? pos-set n))
186 (iota 20 100 3)))
187 (test-assert (not (any (lambda (n) (iset-contains? pos-set n))
188 (iota 20 -100 3))))
189
190 (test-assert (iset-empty? (iset)))
191 (test-not (iset-empty? pos-set))
192
193 (test-assert (iset-disjoint? (iset) (iset)))
194 (test-assert (iset-disjoint? pos-set neg-set))
195 (test-assert (iset-disjoint? (iset) pos-set))
196 (test-not (iset-disjoint? dense-set sparse-set))
197 (test-not (iset-disjoint? (make-range-iset 20 30) (make-range-iset 29 39)))
198 )
199
200 (define (check-accessors)
201 (print-header "Accessors")
202
203 (test 103 (iset-member pos-set 103 #f))
204 (test 'z (iset-member pos-set 104 'z))
205
206 (test-not (iset-min (iset)))
207 (test 1 (iset-min (iset 1 2 3)))
208 (test (car pos-seq) (iset-min pos-set))
209 (test (car neg-seq) (iset-min neg-set))
210 (test (car mixed-seq) (iset-min mixed-set))
211
212 (test-not (iset-max (iset)))
213 (test 3 (iset-max (iset 1 2 3)))
214 (test (last pos-seq) (iset-max pos-set))
215 (test (last neg-seq) (iset-max neg-set))
216 (test (last mixed-seq) (iset-max mixed-set))
217 )
218
219 (define (check-updaters)
220 (print-header "Updaters")
221
222 (test '(1) (iset->list (iset-adjoin (iset) 1)))
223 (test-assert (iset-contains? (iset-adjoin neg-set 10) 10))
224 (test-assert (iset-contains? (iset-adjoin dense-set 100) 100))
225 (test-assert (iset-contains? (iset-adjoin sparse-set 100) 100))
226 (test-equal iset=?
227 (list->iset (cons -3 (iota 20 100 3)))
228 (iset-adjoin pos-set -3))
229
230 (test '() (iset->list (iset-delete (iset 1) 1)))
231 (test-not (iset-contains? (iset-delete neg-set 10) 10))
232 (test-not (iset-contains? (iset-delete dense-set 1033) 1033))
233 (test-not (iset-contains? (iset-delete sparse-set 30) 30))
234 (test-equal iset=?
235 (list->iset (cdr (iota 20 100 3)))
236 (iset-delete pos-set 100))
237
238 (test-assert (iset-empty? (iset-delete-all (iset) '())))
239 (test-equal iset=? pos-set (iset-delete-all pos-set '()))
240 (test-equal iset=?
241 (iset 100 103 106)
242 (iset-delete-all pos-set (iota 17 109 3)))
243
244 ;; iset-search insertion
245 (test-assert
246 (call-with-values
247 (lambda ()
248 (iset-search mixed-set
249 1
250 (lambda (insert _) (insert #t))
251 (lambda (x update _) (update 1 #t))))
252 (lambda (set _) (iset=? (iset-adjoin mixed-set 1) set))))
253
254 ;; iset-search ignore
255 (test-assert
256 (call-with-values
257 (lambda ()
258 (iset-search mixed-set
259 1
260 (lambda (_ ignore) (ignore #t))
261 (lambda (x _ remove) (remove #t))))
262 (lambda (set _) (iset=? mixed-set set))))
263
264 ;; iset-search update with same element.
265 (test-assert
266 (call-with-values
267 (lambda ()
268 (iset-search mixed-set
269 2
270 (lambda (insert _) (insert #t))
271 (lambda (x update _) (update 2 #t))))
272 (lambda (set _) (iset=? mixed-set set))))
273
274 ;; iset-search update with different element.
275 (test-assert
276 (call-with-values
277 (lambda ()
278 (iset-search mixed-set
279 2
280 (lambda (insert _) (insert #t))
281 (lambda (x update _) (update 3 #t))))
282 (lambda (set _)
283 (iset=? (iset-adjoin (iset-delete mixed-set 2) 3) set))))
284
285 ;; iset-search remove
286 (test-assert
287 (call-with-values
288 (lambda ()
289 (iset-search mixed-set
290 2
291 (lambda (_ ignore) (ignore #t))
292 (lambda (x _ remove) (remove #t))))
293 (lambda (set _) (iset=? (iset-delete mixed-set 2) set))))
294
295 ;;; iset-delete-min / -max
296
297 (test-values (values #t #t)
298 (let-values (((n mixed-set*) (iset-delete-min mixed-set)))
299 (values (= n (car mixed-seq))
300 (iset=? mixed-set* (list->iset (cdr mixed-seq))))))
301 (test-values (values #t #t)
302 (let-values (((n sparse-set*) (iset-delete-min sparse-set)))
303 (values (= n (car sparse-seq))
304 (iset=? sparse-set* (list->iset (cdr sparse-seq))))))
305
306 (test-values (values #t #t)
307 (let-values (((n mixed-set*) (iset-delete-max mixed-set)))
308 (values (= n (last mixed-seq))
309 (iset=? mixed-set* (list->iset (init mixed-seq))))))
310 (test-values (values #t #t)
311 (let-values (((n sparse-set*) (iset-delete-max sparse-set)))
312 (values (= n (last sparse-seq))
313 (iset=? sparse-set* (list->iset (init sparse-seq))))))
314 )
315
316 (define (check-whole-set)
317 (print-header "Whole set operations")
318
319 (test 0 (iset-size (iset)))
320 (test (length pos-seq) (iset-size pos-set))
321 (test (length mixed-seq) (iset-size mixed-set))
322 (test (length sparse-seq) (iset-size sparse-set))
323
324 (test 8 (iset-find even? (iset 1 3 5 7 8 9 10) (lambda () #f)))
325 (test 'z (iset-find negative? pos-set (lambda () 'z)))
326
327 (test #f (iset-any? even? (iset)))
328 (test-assert (iset-any? even? pos-set))
329 (test-not (iset-any? negative? pos-set))
330 (test-assert (iset-any? (lambda (n) (> n 100)) sparse-set))
331 (test-not (iset-any? (lambda (n) (> n 100)) dense-set))
332
333 (test #t (iset-every? even? (iset)))
334 (test-not (iset-every? even? pos-set))
335 (test-assert (iset-every? negative? neg-set))
336 (test-not (iset-every? (lambda (n) (> n 100)) sparse-set))
337 (test-assert (iset-every? (lambda (n) (< n 100)) dense-set))
338
339 (test 0 (iset-count even? (iset)))
340 (test (count even? pos-seq) (iset-count even? pos-set))
341 (test (count even? neg-seq) (iset-count even? neg-set))
342 (test (count even? sparse-seq) (iset-count even? sparse-set))
343 )
344
345 (define (check-iterators)
346 (print-header "Iterators")
347
348 ;;; folds
349
350 (test (fold + 0 pos-seq) (iset-fold + 0 pos-set))
351 (test (fold + 0 sparse-seq) (iset-fold + 0 sparse-set))
352 (test (iset-size neg-set) (iset-fold (lambda (_ c) (+ c 1)) 0 neg-set))
353 (test (reverse pos-seq) (iset-fold cons '() pos-set))
354 (test (reverse mixed-seq) (iset-fold cons '() mixed-set))
355
356 (test (fold + 0 pos-seq) (iset-fold-right + 0 pos-set))
357 (test (fold + 0 sparse-seq) (iset-fold-right + 0 sparse-set))
358 (test (iset-size neg-set) (iset-fold-right (lambda (_ c) (+ c 1)) 0 neg-set))
359 (test pos-seq (iset-fold-right cons '() pos-set))
360 (test mixed-seq (iset-fold-right cons '() mixed-set))
361
362 ;;; iset-map
363
364 (test-assert (iset-empty? (iset-map values (iset))))
365 (test-equal iset=? pos-set (iset-map values pos-set))
366 (test-equal iset=?
367 (list->iset (map (lambda (n) (* n 2)) mixed-seq))
368 (iset-map (lambda (n) (* n 2)) mixed-set))
369 (test-equal iset=? (iset 1) (iset-map (constantly 1) pos-set))
370
371 ;;; iset-for-each
372
373 (test (iset-size mixed-set)
374 (let ((n 0))
375 (iset-for-each (lambda (_) (set! n (+ n 1))) mixed-set)
376 n))
377 (test (fold + 0 sparse-seq)
378 (let ((sum 0))
379 (iset-for-each (lambda (n) (set! sum (+ sum n))) sparse-set)
380 sum))
381 (test (reverse mixed-seq)
382 (let ((xs '()))
383 (iset-for-each (lambda (n) (set! xs (cons n xs))) mixed-set)
384 xs))
385
386 ;;; filter, remove, & partition
387
388 (test-assert (iset-empty? (iset-filter (constantly #f) pos-set)))
389 (test-equal iset=?
390 pos-set
391 (iset-filter (constantly #t) pos-set))
392 (test-equal iset=?
393 (list->iset (filter even? mixed-seq))
394 (iset-filter even? mixed-set))
395 (test-assert (iset-empty? (iset-remove (constantly #t) pos-set)))
396 (test-equal iset=?
397 pos-set
398 (iset-remove (constantly #f) pos-set))
399 (test-equal iset=?
400 (list->iset (remove even? mixed-seq))
401 (iset-remove even? mixed-set))
402 (test-assert
403 (let-values (((in out) (iset-partition (constantly #f) pos-set)))
404 (and (iset-empty? in) (iset=? pos-set out))))
405 (test-assert
406 (let-values (((in out) (iset-partition (constantly #t) pos-set)))
407 (and (iset=? pos-set in) (iset-empty? out))))
408 (test-assert
409 (let-values (((in out) (iset-partition even? mixed-set))
410 ((lin lout) (partition even? mixed-seq)))
411 (and (iset=? in (list->iset lin))
412 (iset=? out (list->iset lout)))))
413 )
414
415 (define (check-comparison)
416 (print-header "Comparison")
417
418 (test-assert (iset<? (iset) pos-set))
419 (test-assert (iset<? pos-set pos-set+))
420 (test-not (iset<? pos-set pos-set))
421 (test-not (iset<? pos-set+ pos-set))
422 (test-assert (iset<? (iset) pos-set pos-set+))
423 (test-not (iset<? (iset) pos-set pos-set))
424 (test-assert (iset<=? (iset) pos-set))
425 (test-assert (iset<=? pos-set pos-set+))
426 (test-assert (iset<=? pos-set pos-set))
427 (test-not (iset<=? pos-set+ pos-set))
428 (test-assert (iset<=? (iset) pos-set pos-set+))
429 (test-assert (iset<=? (iset) pos-set pos-set))
430 (test-not (iset>? (iset) pos-set))
431 (test-not (iset>? pos-set pos-set+))
432 (test-not (iset>? pos-set pos-set))
433 (test-assert (iset>? pos-set+ pos-set))
434 (test-assert (iset>? pos-set+ pos-set (iset)))
435 (test-not (iset>? pos-set+ pos-set pos-set))
436 (test-not (iset>=? (iset) pos-set))
437 (test-not (iset>=? pos-set pos-set+))
438 (test-assert (iset>=? pos-set pos-set))
439 (test-assert (iset>=? pos-set+ pos-set))
440 (test-assert (iset>=? pos-set+ pos-set (iset)))
441 (test-assert (iset>=? pos-set+ pos-set pos-set))
442 )
443
444 (define (check-set-theory)
445 (print-header "Set theory")
446
447 (test-equal iset=? mixed-set (iset-union! (iset) mixed-set))
448 (test-equal iset=?
449 (list->iset (append (iota 20 100 3) (iota 20 -100 3)))
450 (iset-union pos-set neg-set))
451 (test-equal iset=? pos-set (iset-union pos-set pos-set))
452 (test-equal iset=?
453 (list->iset (iota 30 100 3))
454 (iset-union pos-set (list->iset (iota 20 130 3))))
455 (test-equal iset=?
456 (list->iset (iota 10))
457 (iset-union (iset 0 1 2) (iset 3 5 8) (iset 4 6 7 9)))
458
459 ;; iset-intersection
460 (test-assert (iset-empty? (iset-intersection (iset) mixed-set)))
461 (test-equal iset=? neg-set (iset-intersection neg-set neg-set))
462 (test-equal iset=? (iset -97) (iset-intersection (iset -97) neg-set))
463 (test-equal iset=? (iset) (iset-intersection pos-set neg-set))
464 (test-equal iset=?
465 (list->iset (drop-while negative? mixed-seq))
466 (iset-intersection mixed-set dense-set))
467 (test-equal iset=?
468 (iset 0 1)
469 (iset-intersection (iset 0 1 2) (iset 0 1 3 4) (iset 10 7 0 1)))
470
471 ;; iset-difference
472 (test-assert (iset-empty? (iset-difference neg-set neg-set)))
473 (test-equal iset=? pos-set (iset-difference pos-set neg-set))
474 (test-equal iset=? pos-set (iset-difference pos-set neg-set))
475 (test-equal iset=?
476 (iset 100)
477 (iset-difference pos-set (list->iset (cdr pos-seq))))
478 (test-equal iset=?
479 (list->iset (take-while negative? mixed-seq))
480 (iset-difference mixed-set dense-set))
481 (test-equal iset=?
482 (iset 0 1)
483 (iset-intersection (iset 0 1 2 5) (iset 0 1 3 4) (iset 10 7 0 1)))
484
485 ;; iset-xor
486 (test-equal iset=? mixed-set (iset-xor (iset) mixed-set))
487 (test-equal iset=?
488 (list->iset (append (iota 20 100 3) (iota 20 -100 3)))
489 (iset-xor pos-set neg-set))
490 (test-equal iset=? (iset) (iset-xor pos-set pos-set))
491 (test-equal iset=?
492 (list->iset '(100 103 106))
493 (iset-xor pos-set (list->iset (iota 17 109 3))))
494 )
495
496 (define (check-subsets)
497 (print-header "Subsets")
498
499 (test-assert (iset-empty? (iset-open-interval (iset) 0 10)))
500 (test-equal iset=?
501 (iset 103 106)
502 (iset-open-interval pos-set 100 109))
503 (test-assert (iset-empty? (iset-open-interval neg-set 0 50)))
504
505 (test-assert (iset-empty? (iset-closed-interval (iset) 0 10)))
506 (test-equal iset=?
507 (iset 100 103 106 109)
508 (iset-closed-interval pos-set 100 109))
509 (test-assert (iset-empty? (iset-closed-interval neg-set 0 50)))
510
511 (test-assert (iset-empty? (iset-open-closed-interval (iset) 0 10)))
512 (test-equal iset=?
513 (iset 103 106 109)
514 (iset-open-closed-interval pos-set 100 109))
515 (test-assert (iset-empty? (iset-open-closed-interval neg-set 0 50)))
516
517 (test-assert (iset-empty? (iset-closed-open-interval (iset) 0 10)))
518 (test-equal iset=?
519 (iset 100 103 106)
520 (iset-closed-open-interval pos-set 100 109))
521 (test-assert (iset-empty? (iset-closed-open-interval neg-set 0 50)))
522
523 ;;; isubset*
524
525 (test-assert (iset-empty? (isubset= pos-set 90)))
526 (test-equal iset=? (iset 100) (isubset= pos-set 100))
527
528 (test-assert (iset-empty? (isubset< (iset) 10)))
529 (test-equal iset=?
530 (iset 100 103 106)
531 (isubset< pos-set 109))
532 (test-equal iset=?
533 (iset -10 -7)
534 (isubset< mixed-set -4))
535 (test-assert (iset-empty? (isubset< mixed-set -15)))
536
537 (test-assert (iset-empty? (isubset<= (iset) 10)))
538 (test-equal iset=?
539 (iset 100 103 106 109)
540 (isubset<= pos-set 109))
541 (test-equal iset=?
542 (iset -10 -7 -4)
543 (isubset<= mixed-set -4))
544 (test-assert (iset-empty? (isubset<= mixed-set -15)))
545
546 (test-assert (iset-empty? (isubset> (iset) 10)))
547 (test-equal iset=?
548 (iset 151 154 157)
549 (isubset> pos-set 148))
550 (test-equal iset=?
551 (iset 41 44 47)
552 (isubset> mixed-set 38))
553 (test-assert (iset-empty? (isubset> mixed-set 50)))
554
555 (test-assert (iset-empty? (isubset>= (iset) 10)))
556 (test-equal iset=?
557 (iset 148 151 154 157)
558 (isubset>= pos-set 148))
559 (test-equal iset=?
560 (iset 38 41 44 47)
561 (isubset>= mixed-set 38))
562 (test-assert (iset-empty? (isubset>= mixed-set 50)))
563 )
564
565 (define (check-all)
566 (check-iset=?)
567 (check-copying-and-conversion)
568 (check-constructors)
569 (check-predicates)
570 (check-accessors)
571 (check-updaters)
572 (check-whole-set)
573 (check-iterators)
574 (check-comparison)
575 (check-set-theory)
576 (check-subsets)
577 (newline)
578 (check-report))
579
580 (check-all)