Debian Codegraph @

test/include/srfi-196-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 (import (scheme write))
24 (import (srfi 1))
25 (import (srfi 196))
26
27 (cond-expand
28 ((library (srfi 78))
29 (import (srfi 78)))
30 (else
31 (begin
32 (define *tests-failed* 0)
33 (define-syntax check
34 (syntax-rules (=>)
35 ((check expr => expected)
36 (if (equal? expr expected)
37 (begin
38 (display 'expr)
39 (display " => ")
40 (display expected)
41 (display " ; correct")
42 (newline))
43 (begin
44 (set! *tests-failed* (+ *tests-failed* 1))
45 (display "FAILED: for ")
46 (display 'expr)
47 (display " expected ")
48 (display expected)
49 (display " but got ")
50 (display expr)
51 (newline))))))
52 (define (check-report)
53 (if (zero? *tests-failed*)
54 (begin
55 (display "All tests passed.")
56 (newline))
57 (begin
58 (display "TESTS FAILED: ")
59 (display *tests-failed*)
60 (newline)))))))
61
62 (cond-expand
63 ((library (srfi 158))
64 (import (only (srfi 158) generator->list)))
65 (else
66 (begin
67 (define (generator->list g)
68 (let ((v (g)))
69 (if (eof-object? v)
70 '()
71 (cons v (generator->list g))))))))
72
73 ;;;; Utility
74
75 (define (identity x) x)
76
77 (define (print-header message)
78 (newline)
79 (display ";;; ")
80 (display message)
81 (newline))
82
83 (define-syntax constantly
84 (syntax-rules ()
85 ((_ obj) (lambda _ obj))))
86
87 (define always (constantly #t))
88 (define never (constantly #f))
89
90 (define (range=/eqv? ra rb)
91 (range=? eqv? ra rb))
92
93 (define (%range-empty? r) (zero? (range-length r)))
94
95 ;;;; Test ranges
96
97 (define test-num-range (numeric-range 10 30))
98
99 (define test-num-seq (iota 20 10))
100
101 (define test-empty-range (numeric-range 0 0))
102
103 ;; Produces the range {#f, #t}.
104 (define test-bool-range
105 (range 2 (lambda (n) (not (zero? n)))))
106
107 ;;;; Conversion
108
109 (define (check-conversion)
110 (print-header "Running conversion tests...")
111
112 (check (range->list test-empty-range) => '())
113 (check (range->list test-bool-range) => '(#f #t))
114 (check (range->list test-num-range) => test-num-seq)
115
116 (check (generator->list (range->generator test-num-range))
117 => test-num-seq)
118
119 (check (vector->list (range->vector test-num-range)) => test-num-seq)
120
121 (check (range->string test-empty-range) => "")
122 (let ((s "0123456789"))
123 (check (range->string (string-range s)) => s))
124
125 (let* ((vec (vector 1 3 5 7 9))
126 (vrange (vector->range vec)))
127 (check (range-length vrange) => (vector-length vec))
128 (check (range-first vrange) => (vector-ref vec 0))
129 (check (range-last vrange) => (vector-ref vec 4))
130 (check (range->vector vrange) => vec)
131 (check (range->list (begin (vector-set! vec 0 0) vrange))
132 => '(1 3 5 7 9)))
133 )
134
135 (define (check-constructors)
136 (print-header "Running constructor tests...")
137
138 (check (%range-empty? (numeric-range 1 1)) => #t)
139 (check (range->list (numeric-range -5 -1)) => (iota 4 -5))
140 (check (range->list (numeric-range 1 -5 -1)) => (iota 6 1 -1))
141 (check (range->list (numeric-range 4/3 16/3)) => (iota 4 4/3))
142 (check (range->list (numeric-range 0 9 4)) => (iota 3 0 4))
143 (check (%range-empty? (numeric-range 0 10 -1)) => #t)
144 (check (%range-empty? (numeric-range 0 -10)) => #t)
145 (check (range->list (numeric-range 5 1 -1)) => (iota 4 5 -1))
146 (check (range->list (numeric-range -2 2)) => (iota 4 -2))
147 (check (range->list (numeric-range 2 -2 -1)) => (iota 4 2 -1))
148 (check (range->list (numeric-range -4 -8 -1)) => (iota 4 -4 -1))
149 (check (range->list (numeric-range -1 -4 -2/3)) => (iota 5 -1 -2/3))
150
151 (check (range=/eqv? (iota-range 10 0 0)
152 (range 10 (lambda (_) 0)))
153 => #t)
154 (check (%range-empty? (iota-range 0)) => #t)
155 (check (range->list (iota-range 10)) => (iota 10))
156 (check (range->list (iota-range 10 0)) => (iota 10))
157 (check (range->list (iota-range 10 0 1)) => (iota 10))
158 (check (range->list (iota-range 10 10 2)) => (iota 10 10 2))
159 (check (range->list (iota-range 10 0 -1)) => (iota 10 0 -1))
160 (check (range->list (iota-range 10 5 -2)) => (iota 10 5 -2))
161 (check (range->list (iota-range 10 1/2)) => (iota 10 1/2))
162
163 (let ((vec (vector 1 3 5 7 9)))
164 (check (range-length (vector-range vec)) => (vector-length vec))
165 (check (range-first (vector-range vec)) => (vector-ref vec 0))
166 (check (range-last (vector-range vec)) => (vector-ref vec 4))
167 (check (range->vector (vector-range vec)) => vec))
168
169 (let* ((s "0123456789") (srange (string-range s)))
170 (check (range-length srange) => (string-length s))
171 (check (range-first srange) => (string-ref s 0))
172 (check (range-last srange) => (string-ref s 9))
173 (check (range->list srange) => (string->list s)))
174 )
175
176 ;;;; Predicates
177
178 (define (check-predicates)
179 (print-header "Running predicate tests...")
180
181 (check (range=? eqv? (numeric-range 0 0) (numeric-range 5 5)) => #t)
182 (check (range=? eqv? (numeric-range 0 0) test-num-range) => #f)
183 (check (range=? eqv? test-num-range test-num-range) => #t)
184 (check (range=? eqv? test-num-range (numeric-range 10 30)) => #t)
185 (check (range=? eqv? test-num-range (numeric-range 10 20)) => #f)
186 (check (range=? eqv? test-bool-range (vector-range #(#f #t))) => #t)
187 (check (range=? eqv? test-bool-range (vector-range #(#t #f))) => #f)
188 (check (range=? eqv?
189 test-num-range
190 (numeric-range 10 30)
191 (subrange (numeric-range 0 50) 10 30))
192 => #t)
193 (check (range=? eqv?
194 test-bool-range
195 (numeric-range 10 30)
196 (subrange (numeric-range 0 50) 10 30))
197 => #f)
198 (check (range=? eqv?
199 test-num-range
200 (numeric-range 11 31)
201 (subrange (numeric-range 0 50) 10 30))
202 => #f)
203 )
204
205 ;;;; Accessors
206
207 (define (check-accessors)
208 (print-header "Running accessor tests...")
209
210 (check (range-ref test-num-range 0) => 10)
211 (check (range-ref test-bool-range 1) => #t)
212 )
213
214 ;;;; Iteration
215
216 (define (check-iteration)
217 (print-header "Running iteration tests...")
218
219 ;; Check lengths of ranges returned by range-split-at.
220 (let ((n 10))
221 (check (let-values (((ra rb) (range-split-at test-num-range n)))
222 (list (range-length ra) (range-length rb)))
223 => (list n (- (range-length test-num-range) n))))
224
225 ;; Joining the two ranges returned by range-split-at gives the
226 ;; original range.
227 (check (let-values (((ra rb) (range-split-at test-bool-range 1)))
228 (range=/eqv? (range-append ra rb) test-bool-range))
229 => #t)
230
231 (check (range=/eqv?
232 (subrange test-bool-range 0 (range-length test-bool-range))
233 test-bool-range)
234 => #t)
235 (let ((a 5) (b 10))
236 (check (= (range-length (subrange test-num-range a b)) (- b a))
237 => #t)
238 (check (range=/eqv? (subrange test-num-range a b)
239 (range-take (range-drop test-num-range a) (- b a)))
240 => #t)
241 (check (range=/eqv? (subrange test-num-range 0 b)
242 (range-take test-num-range b))
243 => #t)
244 (check (range=/eqv?
245 (subrange test-num-range a (range-length test-num-range))
246 (range-drop test-num-range a))
247 => #t))
248
249 ;; range-take r n returns a range of length n.
250 (check (range-length (range-take test-num-range 10)) => 10)
251 (check (range-length
252 (range-take test-num-range (range-length test-num-range)))
253 => (range-length test-num-range))
254 (check (range->list (range-take test-num-range 5))
255 => (take test-num-seq 5))
256
257 ;; range-take-right r n returns a range of length n.
258 (check (range-length (range-take-right test-num-range 10)) => 10)
259 (check (range-length
260 (range-take-right test-num-range (range-length test-num-range)))
261 => (range-length test-num-range))
262 (check (range->list (range-take-right test-num-range 5))
263 => (drop test-num-seq 15))
264
265 ;; range-drop r n returns a range of length (range-length r) - n.
266 (check (range-length (range-drop test-num-range 10))
267 => (- (range-length test-num-range) 10))
268 (check (range-length
269 (range-drop test-num-range (range-length test-num-range)))
270 => 0)
271 (check (range->list (range-drop test-num-range 15))
272 => (drop test-num-seq 15))
273
274 ;; range-drop-right r n returns a range of length (range-length r) - n.
275 (check (range-length (range-drop-right test-num-range 10))
276 => (- (range-length test-num-range) 10))
277 (check (range-length
278 (range-drop-right test-num-range (range-length test-num-range)))
279 => 0)
280 (check (range->list (range-drop-right test-num-range 15))
281 => (take test-num-seq 5))
282
283 (check (range=/eqv? (car (range-segment test-num-range 5))
284 (range-take test-num-range 5))
285 => #t)
286 (check (range=/eqv? (apply range-append
287 (cdr (range-segment test-num-range 5)))
288 (range-drop test-num-range 5))
289 => #t)
290 (check (range=/eqv? (apply range-append (range-segment test-num-range 5))
291 test-num-range)
292 => #t)
293 (check (fold + 0 (map range-length (range-segment test-num-range 5)))
294 => (range-length test-num-range))
295 (check (fold + 0 (map range-length (range-segment test-num-range 7)))
296 => (range-length test-num-range))
297
298 (check (range-count always test-num-range) => (range-length test-num-range))
299 (check (range-count never test-num-range) => 0)
300 (check (range-count even? test-num-range) => (count even? test-num-seq))
301 (check (range-count (lambda (x y) y) test-num-range test-bool-range)
302 => 1)
303 (check (range-count (lambda (x y) (zero? (+ x y)))
304 test-num-range
305 (range-map - test-num-range))
306 => (range-length test-num-range))
307
308 (check (range-any even? test-num-range) => #t)
309 (check (range-any never test-num-range) => #f)
310 (check (range-any (lambda (x y) y) test-num-range test-bool-range)
311 => #t)
312 (check (range-any (lambda (x y) (zero? (+ x y)))
313 test-num-range
314 test-num-range)
315 => #f)
316
317 (check (range-every number? test-num-range) => #t)
318 (check (range-every even? test-num-range) => #f)
319 (check (range-every (lambda (x y) y) test-num-range test-bool-range)
320 => #f)
321 (check (range-every (lambda (x y) (zero? (+ x y)))
322 test-num-range
323 (range-map - test-num-range))
324 => #t)
325
326 ;;; map, filter-map, & for-each
327
328 (check (range=/eqv? (range-map (lambda (x) (+ 1 x)) test-num-range)
329 (numeric-range 11 31))
330 => #t)
331 (check (equal? (range->list (range-map square test-num-range))
332 (map square test-num-seq))
333 => #t)
334 (check (range=/eqv? (range-map + test-num-range test-num-range)
335 (numeric-range 20 60 2))
336 => #t)
337 ;; range-map over ranges with unequal lengths terminates when
338 ;; the shortest range is exhausted.
339 (check (range=/eqv?
340 (range-map (lambda (x _) x) test-num-range test-bool-range)
341 (range-take test-num-range (range-length test-bool-range)))
342 => #t)
343
344 ;; (range-map->list f r) = (map f (range->list r))
345 (check (equal? (range-map->list not test-bool-range)
346 (map not (range->list test-bool-range)))
347 => #t)
348 (check (equal? (range-map->list + test-num-range test-num-range)
349 (map + test-num-seq test-num-seq))
350 => #t)
351
352 ;; (range-map->vector f r) = (map f (range->vector r))
353 (check (equal? (range-map->vector not test-bool-range)
354 (vector-map not (range->vector test-bool-range)))
355 => #t)
356 (let ((num-vec (list->vector test-num-seq)))
357 (check (equal? (range-map->vector + test-num-range test-num-range)
358 (vector-map + num-vec num-vec))
359 => #t))
360
361 (check (%range-empty? (range-filter-map never test-bool-range)) => #t)
362 (check (range=/eqv? (range-filter-map values test-num-range)
363 test-num-range)
364 => #t)
365 (check (equal?
366 (range->list (range-filter-map (lambda (x) (and (even? x) x))
367 test-num-range))
368 (filter-map (lambda (x) (and (even? x) x)) test-num-seq))
369 => #t)
370 (let ((proc (lambda (x y) (and (even? x) (even? y) (+ x y)))))
371 (check (range=/eqv? (range-filter-map proc test-num-range test-num-range)
372 (numeric-range 20 60 4))
373 => #t))
374
375 (check (range-filter-map->list never test-bool-range) => '())
376 (check (equal? (range-filter-map->list values test-num-range)
377 test-num-seq)
378 => #t)
379 (check (equal?
380 (range-filter-map->list (lambda (x) (and (even? x) x))
381 test-num-range)
382 (filter-map (lambda (x) (and (even? x) x)) test-num-seq))
383 => #t)
384 (let ((proc (lambda (x y) (and (even? x) (even? y) (+ x y)))))
385 (check (equal? (range-filter-map->list proc
386 test-num-range
387 test-num-range)
388 (filter-map proc test-num-seq test-num-seq))
389 => #t))
390
391 (check (let ((v #f))
392 (range-for-each (lambda (x) (set! v x)) test-bool-range)
393 v)
394 => #t)
395 (check (let ((v #f))
396 (range-for-each (lambda (x y) (when y (set! v x)))
397 test-num-range
398 test-bool-range)
399 v)
400 => 11)
401
402 ;;; filter & remove
403
404 (check (range=/eqv? (range-filter always test-bool-range)
405 test-bool-range)
406 => #t)
407 (check (%range-empty? (range-filter never test-bool-range)) => #t)
408 (check (equal? (range->list (range-filter even? test-num-range))
409 (filter even? test-num-seq))
410 => #t)
411
412 (check (range-filter->list always test-bool-range) => '(#f #t))
413
414 (check (null? (range-filter->list never test-bool-range)) => #t)
415
416 ;; (range-filter->list pred r) = (filter pred (range->list r))
417 (check (equal? (range-filter->list even? test-num-range)
418 (filter even? test-num-seq))
419 => #t)
420
421 (check (range=/eqv? (range-remove never test-bool-range)
422 test-bool-range)
423 => #t)
424 (check (%range-empty? (range-remove always test-bool-range))
425 => #t)
426 (check (equal? (range->list (range-remove even? test-num-range))
427 (remove even? test-num-seq))
428 => #t)
429
430 (check (equal? (range-remove->list never test-bool-range)
431 (range->list test-bool-range))
432 => #t)
433
434 (check (null? (range-remove->list always test-bool-range)) => #t)
435
436 ;; (range-remove->list pred r) = (remove pred (range->list r))
437 (check (equal? (range-remove->list even? test-num-range)
438 (remove even? test-num-seq))
439 => #t)
440
441 ;; (range-fold (lambda (b) (+ 1 b)) 0 r) = (range-length r)
442 (check (= (range-fold (lambda (b _) (+ b 1)) 0 test-num-range)
443 (range-length test-num-range))
444 => #t)
445
446 ;; (range-fold proc nil r) = (fold proc nil (range->list r))
447 (check (equal? (range-fold + 0 test-num-range)
448 (fold + 0 test-num-seq))
449 => #t)
450
451 (check (= (range-fold + 0 test-num-range test-num-range)
452 (fold + 0 test-num-seq test-num-seq))
453 => #t)
454
455 ;; range-fold over ranges with unequal lengths terminates when
456 ;; the shortest range is exhausted.
457 (check (= (range-fold (lambda (s x _) (+ s x))
458 0
459 test-num-range
460 test-bool-range)
461 (range-fold + 0 (range-take test-num-range
462 (range-length test-bool-range))))
463 => #t)
464
465 ;; (range-fold-right (lambda (b) (+ 1 b)) 0 r) = (range-length r)
466 (check (= (range-fold-right (lambda (b _) (+ b 1)) 0 test-num-range)
467 (range-length test-num-range))
468 => #t)
469
470 ;; (range-fold-right r proc nil) = (fold-right proc nil (range->list r))
471 (check (equal? (range-fold-right + 0 test-num-range)
472 (fold-right + 0 test-num-seq))
473 => #t)
474
475 (check (= (range-fold-right + 0 test-num-range test-num-range)
476 (fold-right + 0 test-num-seq test-num-seq))
477 => #t)
478
479 ;; range-fold-right over ranges with unequal lengths terminates when
480 ;; the shortest range is exhausted.
481 (check (= (range-fold-right (lambda (s x _) (+ s x))
482 0
483 test-num-range
484 test-bool-range)
485 (range-fold-right + 0 (range-take test-num-range
486 (range-length
487 test-bool-range))))
488 => #t)
489
490 (check (eqv? (range-first (range-reverse test-bool-range))
491 (range-last test-bool-range))
492 => #t)
493
494 (check (eqv? (range-last (range-reverse test-bool-range))
495 (range-first test-bool-range))
496 => #t)
497
498 (check (equal? (range->list (range-reverse test-num-range))
499 (reverse test-num-seq))
500 => #t)
501
502 (check (%range-empty? (range-append)) => #t)
503 (check (range->list (range-append test-bool-range)) => '(#f #t))
504 (check (range=/eqv? (range-append (numeric-range 10 20)
505 (numeric-range 20 30))
506 test-num-range)
507 => #t)
508 (check (range=/eqv? (range-append (numeric-range 10 15)
509 (numeric-range 15 20)
510 (numeric-range 20 25)
511 (numeric-range 25 30))
512 test-num-range)
513 => #t)
514 )
515
516 ;;;; Searching
517
518 (define (check-searching)
519 (print-header "Running search tests...")
520
521 (check (range-index always test-num-range) => 0)
522 (check (range-index never test-num-range) => #f)
523 (check (range-index values test-bool-range) => 1)
524 (check (range-index (lambda (x y) (and (odd? x) y))
525 test-num-range
526 test-bool-range)
527 => 1)
528
529 (check (eqv? (range-index-right always test-num-range)
530 (- (range-length test-num-range) 1))
531 => #t)
532 (check (range-index-right never test-num-range) => #f)
533 (check (range-index-right values test-bool-range) => 1)
534 (check (range-index-right (lambda (x y) (< (+ x y) 30))
535 test-num-range
536 test-num-range)
537 => 4)
538
539 ;; range-index and range-index-right produce the same index if pred
540 ;; is only satisfied by the element at that index.
541 (let ((fifteen? (lambda (n) (= n 15))))
542 (check (= (range-index fifteen? test-num-range)
543 (range-index-right fifteen? test-num-range)
544 (list-index fifteen? test-num-seq))
545 => #t))
546
547 ;; (range-take-while always r) = r
548 (check (range=/eqv? (range-take-while always test-bool-range)
549 test-bool-range)
550 => #t)
551
552 ;; (range-take-while never r) = [empty range]
553 (check (%range-empty? (range-take-while never test-bool-range)) => #t)
554
555 (let ((pred (lambda (n) (< n 15))))
556 (check (range->list (range-take-while pred test-num-range))
557 => (take-while pred test-num-seq)))
558
559 ;; (range-drop-while always r) = [empty range]
560 (check (%range-empty? (range-drop-while always test-bool-range)) => #t)
561
562 ;; (range-drop-while never r) = r
563 (check (range=/eqv? (range-drop-while never test-bool-range)
564 test-bool-range)
565 => #t)
566
567 (let ((pred (lambda (n) (< n 15))))
568 (check (range->list (range-drop-while pred test-num-range))
569 => (drop-while pred test-num-seq)))
570
571 ;; (range-append (range-take-while p r) (range-drop-while p r)) = r
572 (let ((pred (lambda (n) (< n 10))))
573 (check (range=/eqv?
574 (range-append (range-take-while pred test-num-range)
575 (range-drop-while pred test-num-range))
576 test-num-range)
577 => #t))
578
579 ;; (range-take-while-right always r) = r
580 (check (range=/eqv? (range-take-while-right always test-bool-range)
581 test-bool-range)
582 => #t)
583
584 ;; (range-take-while-right never r) = [empty range]
585 (check (%range-empty? (range-take-while-right never test-bool-range)) => #t)
586
587 (let ((pred (lambda (n) (>= n 15))))
588 (check (range->list (range-take-while-right pred test-num-range))
589 => (iota 15 15)))
590
591 ;; (range-drop-while-right always r) = [empty range]
592 (check (%range-empty? (range-drop-while-right always test-bool-range)) => #t)
593
594 ;; (range-drop-while-right never r) = r
595 (check (range=/eqv? (range-drop-while-right never test-bool-range)
596 test-bool-range)
597 => #t)
598
599 (let ((pred (lambda (n) (>= n 15))))
600 (check (range->list (range-drop-while-right pred test-num-range))
601 => (take test-num-seq 5)))
602
603 ;; (range-append (range-drop-while-right p r)
604 ;; (range-take-while-right p r)) = r
605 (let ((pred (lambda (n) (< n 10))))
606 (check (range=/eqv?
607 (range-append (range-drop-while-right pred test-num-range)
608 (range-take-while-right pred test-num-range))
609 test-num-range)
610 => #t))
611 )
612
613 (define (check-all)
614 (check-predicates)
615 (check-conversion)
616 (check-constructors)
617 (check-accessors)
618 (check-iteration)
619 (check-searching)
620
621 (newline)
622 (check-report))
623
624 (check-all)