Debian Codegraph @

test/util.scm

raw
1 ;;
2 ;; test util modules
3 ;;
4
5 (use gauche.test)
6 (test-start "util")
7
8 (use scheme.list)
9
10 ;;-----------------------------------------------
11 (test-section "util.match")
12 (use util.match)
13 (test-module 'util.match)
14 (test* "match (quasiquote + empty-vector)"
15 #t
16 (match '#() (`#() #t) (_ #f)))
17 (test* "match (quasi-pattern + vector)"
18 '(3 1 2)
19 (match '#(1 2 3) (`#(,a ,b ,c) (list c a b)) (_ #f)))
20 (test* "match (quasi-pattern + ellipsis + vector)"
21 '(1 2 3)
22 (match '#(1 2 3) (`#(,a ...) a) (_ #f)))
23
24 ;;-----------------------------------------------
25 (test-section "util.combinations")
26 (use util.combinations)
27 (test-module 'util.combinations)
28
29 (test* "permutations (boundary)" '(())
30 (permutations '()))
31 (test* "permutations (boundary)" '((a))
32 (permutations '(a)))
33 (test* "permutations" '((a b) (b a))
34 (permutations '(a b)))
35 (test* "permutations" '((a a) (a a))
36 (permutations '(a a)))
37 (test* "permutations" '((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
38 (permutations '(a b c)))
39 (test* "permutations" '((a b c d) (a b d c) (a c b d) (a c d b)
40 (a d b c) (a d c b) (b a c d) (b a d c)
41 (b c a d) (b c d a) (b d a c) (b d c a)
42 (c a b d) (c a d b) (c b a d) (c b d a)
43 (c d a b) (c d b a) (d a b c) (d a c b)
44 (d b a c) (d b c a) (d c a b) (d c b a))
45 (permutations '(a b c d)))
46
47 (test* "permutations* (boundary)" '(())
48 (permutations* '()))
49 (test* "permutations* (boundary)" '((a))
50 (permutations* '(a)))
51 (test* "permutations*" '((a b) (b a))
52 (permutations* '(a b)))
53 (test* "permutations*" '((a a))
54 (permutations* '(a a)))
55 (test* "permutations*" '((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
56 (permutations* '(a b c)))
57 (test* "permutations*" '((a a b) (a b a) (b a a))
58 (permutations* '(a a b)))
59 (test* "permutations*" '((a b a) (a a b) (b a a))
60 (permutations* '(a b a)))
61 (test* "permutations*" '((b a a) (a b a) (a a b))
62 (permutations* '(b a a)))
63 (test* "permutations*" '((a a a))
64 (permutations* '(a a a)))
65 (test* "permutations*" '((a b c d) (a b d c) (a c b d) (a c d b)
66 (a d b c) (a d c b) (b a c d) (b a d c)
67 (b c a d) (b c d a) (b d a c) (b d c a)
68 (c a b d) (c a d b) (c b a d) (c b d a)
69 (c d a b) (c d b a) (d a b c) (d a c b)
70 (d b a c) (d b c a) (d c a b) (d c b a))
71 (permutations* '(a b c d)))
72 (test* "permutations*" '((a a b c) (a a c b) (a b a c) (a b c a)
73 (a c a b) (a c b a) (b a a c) (b a c a)
74 (b c a a) (c a a b) (c a b a) (c b a a))
75 (permutations* '(a a b c)))
76 (test* "permutations*" '((a b a c) (a b c a) (a a b c) (a a c b)
77 (a c b a) (a c a b) (b a a c) (b a c a)
78 (b c a a) (c a b a) (c a a b) (c b a a))
79 (permutations* '(a b a c)))
80 (test* "permutations*" '((a b c a) (a b a c) (a c b a) (a c a b)
81 (a a b c) (a a c b) (b a c a) (b a a c)
82 (b c a a) (c a b a) (c a a b) (c b a a))
83 (permutations* '(a b c a)))
84 (test* "permutations*" '((a b a b) (a b b a) (a a b b)
85 (b a a b) (b a b a) (b b a a))
86 (permutations* '(a b a b)))
87 (test* "permutations*" '((a a a b) (a a b a) (a b a a) (b a a a))
88 (permutations* '(a a a b)))
89 (test* "permutations*" '((a b a a) (a a b a) (a a a b) (b a a a))
90 (permutations* '(a b a a)))
91 (test* "permutations*" '((a a a a))
92 (permutations* '(a a a a)))
93
94 (test* "permutations*" '(("a" "b" "b" "a") ("a" "b" "a" "b") ("a" "a" "b" "b")
95 ("b" "a" "b" "a") ("b" "a" "a" "b") ("b" "b" "a" "a"))
96 (permutations* '("a" "b" "b" "a") string=?))
97
98 (test* "permutations-for-each"
99 '()
100 (let1 r '()
101 (permutations-for-each (^p (push! r p)) '())
102 (reverse r)))
103 (test* "permutations-for-each"
104 '((a))
105 (let1 r '()
106 (permutations-for-each (^p (push! r p)) '(a))
107 (reverse r)))
108 (test* "permutations-for-each"
109 '((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
110 (let1 r '()
111 (permutations-for-each (^p (push! r p)) '(a b c))
112 (reverse r)))
113 (test* "permutations*-for-each"
114 '()
115 (let1 r '()
116 (permutations*-for-each (^p (push! r p)) '())
117 (reverse r)))
118 (test* "permutations*-for-each"
119 '((a))
120 (let1 r '()
121 (permutations*-for-each (^p (push! r p)) '(a))
122 (reverse r)))
123 (test* "permutations*-for-each"
124 '((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
125 (let1 r '()
126 (permutations*-for-each (^p (push! r p)) '(a b c))
127 (reverse r)))
128 (test* "permutations*-for-each"
129 '((a a b) (a b a) (b a a))
130 (let1 r '()
131 (permutations*-for-each (^p (push! r p)) '(a a b))
132 (reverse r)))
133 (test* "permutations*-for-each"
134 '((a a a))
135 (let1 r '()
136 (permutations*-for-each (^p (push! r p)) '(a a a))
137 (reverse r)))
138 (test* "permutations*-for-each"
139 '(("a" "a" "b") ("a" "b" "a") ("b" "a" "a"))
140 (let1 r '()
141 (permutations*-for-each (^p (push! r p)) '("a" "a" "b")
142 string=?)
143 (reverse r)))
144
145 (test* "combinations" '(())
146 (combinations '() 0))
147 (test* "combinations" '((a))
148 (combinations '(a) 1))
149 (test* "combinations" '((a) (b) (c) (d))
150 (combinations '(a b c d) 1))
151 (test* "combinations" '((a b) (a c) (b c))
152 (combinations '(a b c) 2))
153 (test* "combinations" '((a b c))
154 (combinations '(a b c) 3))
155 (test* "combinations" '((a b c) (a b d) (a c d) (b c d))
156 (combinations '(a b c d) 3))
157
158 (test* "combinations*" '(())
159 (combinations* '() 0))
160 (test* "combinations*" '((a))
161 (combinations* '(a) 1))
162 (test* "combinations*" '((a) (b) (c) (d))
163 (combinations* '(a b c d) 1))
164 (test* "combinations*" '((a b) (a c) (b c))
165 (combinations* '(a b c) 2))
166 (test* "combinations*" '((a b c))
167 (combinations* '(a b c) 3))
168 (test* "combinations*" '((a b c) (a b d) (a c d) (b c d))
169 (combinations* '(a b c d) 3))
170 (test* "combinations*" '((a) (b))
171 (combinations* '(a a b) 1))
172 (test* "combinations*" '((a a) (a b))
173 (combinations* '(a a b) 2))
174 (test* "combinations*" '((a a b))
175 (combinations* '(a a b) 3))
176 (test* "combinations*" '((a b) (a a))
177 (combinations* '(a b a a) 2))
178 (test* "combinations*" '((a b a) (a a a))
179 (combinations* '(a b a a) 3))
180 (test* "combinations*" '((a b b) (a b a))
181 (combinations* '(a b b a) 3))
182 (test* "combinations*" '(("a" "b" "b") ("a" "b" "a"))
183 (combinations* '("a" "b" "b" "a") 3 string=?))
184
185 (test* "combinations-for-each" '(())
186 (let1 r '()
187 (combinations-for-each (^c (push! r c)) '() 0)
188 (reverse! r)))
189 (test* "combinations-for-each" '((a))
190 (let1 r '()
191 (combinations-for-each (^c (push! r c)) '(a) 1)
192 (reverse! r)))
193 (test* "combinations-for-each" '((a) (b) (c) (d))
194 (let1 r '()
195 (combinations-for-each (^c (push! r c)) '(a b c d) 1)
196 (reverse! r)))
197 (test* "combinations-for-each" '((a b) (a c) (b c))
198 (let1 r '()
199 (combinations-for-each (^c (push! r c)) '(a b c) 2)
200 (reverse! r)))
201 (test* "combinations-for-each" '((a b c))
202 (let1 r '()
203 (combinations-for-each (^c (push! r c)) '(a b c) 3)
204 (reverse! r)))
205 (test* "combinations-for-each" '((a b c) (a b d) (a c d) (b c d))
206 (let1 r '()
207 (combinations-for-each (^c (push! r c)) '(a b c d) 3)
208 (reverse! r)))
209
210 (test* "combinations*-for-each" '(())
211 (let1 r '()
212 (combinations*-for-each (^c (push! r c)) '() 0)
213 (reverse! r)))
214 (test* "combinations*-for-each" '((a))
215 (let1 r '()
216 (combinations*-for-each (^c (push! r c)) '(a) 1)
217 (reverse! r)))
218 (test* "combinations*-for-each" '((a) (b) (c) (d))
219 (let1 r '()
220 (combinations*-for-each (^c (push! r c)) '(a b c d) 1)
221 (reverse! r)))
222 (test* "combinations*-for-each" '((a b) (a c) (b c))
223 (let1 r '()
224 (combinations*-for-each (^c (push! r c)) '(a b c) 2)
225 (reverse! r)))
226 (test* "combinations*-for-each" '((a b c))
227 (let1 r '()
228 (combinations*-for-each (^c (push! r c)) '(a b c) 3)
229 (reverse! r)))
230 (test* "combinations*-for-each" '((a b c) (a b d) (a c d) (b c d))
231 (let1 r '()
232 (combinations*-for-each (^c (push! r c)) '(a b c d) 3)
233 (reverse! r)))
234 (test* "combinations*-for-each" '((a) (b))
235 (let1 r '()
236 (combinations*-for-each (^c (push! r c)) '(a a b) 1)
237 (reverse! r)))
238 (test* "combinations*-for-each" '((a a) (a b))
239 (let1 r '()
240 (combinations*-for-each (^c (push! r c)) '(a a b) 2)
241 (reverse! r)))
242 (test* "combinations*-for-each" '((a a b))
243 (let1 r '()
244 (combinations*-for-each (^c (push! r c)) '(a a b) 3)
245 (reverse! r)))
246 (test* "combinations*-for-each" '((a b) (a a))
247 (let1 r '()
248 (combinations*-for-each (^c (push! r c)) '(a b a a) 2)
249 (reverse! r)))
250 (test* "combinations*-for-each" '((a b a) (a a a))
251 (let1 r '()
252 (combinations*-for-each (^c (push! r c)) '(a b a a) 3)
253 (reverse! r)))
254 (test* "combinations*-for-each" '((a b b) (a b a))
255 (let1 r '()
256 (combinations*-for-each (^c (push! r c)) '(a b b a) 3)
257 (reverse! r)))
258 (test* "combinations*-for-each" '(("a" "b" "b") ("a" "b" "a"))
259 (let1 r '()
260 (combinations*-for-each (^c (push! r c)) '("a" "b" "b" "a") 3
261 string=?)
262 (reverse! r)))
263
264 (test* "power-set-binary" '(())
265 (power-set-binary '()))
266 (test* "power-set-binary" '(() (a))
267 (power-set-binary '(a)))
268 (test* "power-set-binary" '(() (c) (b) (b c) (a) (a c) (a b) (a b c))
269 (power-set-binary '(a b c)))
270
271 (test* "power-set" '(())
272 (power-set '()))
273 (test* "power-set" '(() (a))
274 (power-set '(a)))
275 (test* "power-set" '(() (a) (b) (c) (a b) (a c) (b c) (a b c))
276 (power-set '(a b c)))
277
278 (test* "power-set*" '(())
279 (power-set* '()))
280 (test* "power-set*" '(() (a))
281 (power-set* '(a)))
282 (test* "power-set*" '(() (a) (b) (a a) (a b) (a a b))
283 (power-set* '(a a b)))
284 (test* "power-set*" '(() ("a") ("b") ("a" "a") ("a" "b") ("a" "a" "b"))
285 (power-set* '("a" "a" "b") string=?))
286
287 (test* "power-set-for-each" '(())
288 (let1 r '()
289 (power-set-for-each (^s (push! r s)) '())
290 (reverse! r)))
291 (test* "power-set-for-each" '(() (a))
292 (let1 r '()
293 (power-set-for-each (^s (push! r s)) '(a))
294 (reverse! r)))
295 (test* "power-set-for-each" '(() (a) (b) (c) (a b) (a c) (b c) (a b c))
296 (let1 r '()
297 (power-set-for-each (^s (push! r s)) '(a b c))
298 (reverse! r)))
299
300 (test* "power-set*-for-each" '(())
301 (let1 r '()
302 (power-set*-for-each (^s (push! r s)) '())
303 (reverse! r)))
304 (test* "power-set*-for-each" '(() (a))
305 (let1 r '()
306 (power-set*-for-each (^s (push! r s)) '(a))
307 (reverse! r)))
308 (test* "power-set*-for-each" '(() (a) (b) (a a) (a b) (a a b))
309 (let1 r '()
310 (power-set*-for-each (^s (push! r s)) '(a a b))
311 (reverse! r)))
312 (test* "power-set*-for-each" '(() ("a") ("b") ("a" "a") ("a" "b") ("a" "a" "b"))
313 (let1 r '()
314 (power-set*-for-each (^s (push! r s)) '("a" "a" "b")
315 string=?)
316 (reverse! r)))
317
318 (test* "cartesian-product" '((a 0) (a 1) (b 0) (b 1) (c 0) (c 1))
319 (cartesian-product '((a b c) (0 1))))
320 (test* "cartesian-product" '((a 0 0) (a 0 1) (a 1 0) (a 1 1)
321 (b 0 0) (b 0 1) (b 1 0) (b 1 1))
322 (cartesian-product '((a b) (0 1) (0 1))))
323 (test* "cartesian-product-right" '((a 0) (b 0) (c 0) (a 1) (b 1) (c 1))
324 (cartesian-product-right '((a b c) (0 1))))
325 (test* "cartesian-product-right" '((a 0 0) (b 0 0) (a 1 0) (b 1 0)
326 (a 0 1) (b 0 1) (a 1 1) (b 1 1))
327 (cartesian-product-right '((a b) (0 1) (0 1))))
328
329 ;;-----------------------------------------------
330 (test-section "util.dominator")
331 (use util.dominator)
332 (test-module 'util.dominator)
333
334 (let ((graph1 '((a b c)
335 (b d)
336 (c d)
337 (d e f)
338 (e h)
339 (f g)
340 (g d h)
341 (h j k)
342 (i h)
343 (j l)
344 (k l))))
345 (test* "dominators"
346 '((l h) (j h) (k h) (h d) (e d) (g f) (f d) (d a) (b a) (c a))
347 ($ calculate-dominators 'a
348 (^n (filter-map (^g (and (memq n (cdr g)) (car g))) graph1))
349 (^n (assoc-ref graph1 n '()))
350 eq-comparator)))
351
352 ;;-----------------------------------------------
353 (test-section "util.identifier-syntax")
354
355 (define-module test-identifier-syntax
356 (use gauche.test)
357 (use util.identifier-syntax)
358 (test-module 'util.identifier-syntax)
359
360 (define p (cons 4 5))
361 (define-syntax p.car (identifier-syntax (car p)))
362 (test* "identifier-syntax form 1" 4 p.car)
363
364 (test* "identifier-syntax form 1 no set!"
365 (test-error <error> #/id macro can't be used with set!/i)
366 (eval '(set! p.car 99) (current-module)))
367
368 (let ((p (cons 6 7)))
369 (test* "identifier-syntax hygiene" 4 p.car))
370
371 (define-syntax p.cdr (identifier-syntax
372 [_ (cdr p)]
373 [(set! _ expr) (set-cdr! p expr)]))
374 (test* "identifier-sytnax form 2" 5 p.cdr)
375 (test* "identidier-syntax set!" '(4 . 99)
376 (begin
377 (set! p.cdr 99)
378 p))
379 (let ((p (cons 6 7)))
380 (set! p.cdr 101)
381 (test* "identifier-syntax hygiene" 101 p.cdr))
382
383 (let ((p (cons 8 9)))
384 (let-syntax ([p.cdr (identifier-syntax
385 [_ (cdr p)]
386 [(set! _ expr) (set-cdr! p (+ 1 expr))])])
387 (let ((p (cons 0 1)))
388 (set! p.cdr 9999)
389 (test* "local identifier syntax hygine" '(0 . 1) p)
390 (test* "local identifier syntax hygine" 10000 p.cdr))
391 (test* "local identifier syntax hygine" '(8 . 10000) p)))
392 (test* "local identifier syntax hygine" '(4 . 101) p)
393 )
394
395 ;;-----------------------------------------------
396 (test-section "util.isomorph")
397 (use util.isomorph)
398 (test-module 'util.isomorph)
399
400 (define-class <isomorph-test> ()
401 ((a :init-keyword :a)
402 (b :init-keyword :b)))
403
404 (define-method object-isomorphic? ((x <isomorph-test>)
405 (y <isomorph-test>)
406 context)
407 (and (isomorphic? (ref x 'a) (ref y 'a) context)
408 (isomorphic? (ref x 'b) (ref y 'b) context)))
409
410 (define (make-data type)
411 (let* ((z (vector #f #f #f #f))
412 (x (circular-list "a" 'b 4 9845938427094857239485 #\z 8+5i z))
413 (y (circular-list "a" 'b 4 9845938427094857239485 #\z 8+5i z))
414 (w (make <isomorph-test> :a z)))
415 (vector-set! z 0 x)
416 (vector-set! z 1 y)
417 (vector-set! z 2 w)
418 (slot-set! w 'b w)
419 (if type (vector-set! z 3 x) (vector-set! z 3 y))
420 z))
421
422 (test* "isomorphic?" #t
423 (isomorphic? (make-data #f) (make-data #f)))
424 (test* "isomorphic?" #f
425 (isomorphic? (make-data #t) (make-data #f)))
426
427 ;;-----------------------------------------------
428 (test-section "util.lcs")
429 (use util.lcs)
430 (test-module 'util.lcs)
431
432 (test* "lcs skip" '(a c)
433 (lcs '(a b c) '(a c)))
434
435 (test* "lcs head" '(a b)
436 (lcs '(a b c) '(a b)))
437
438 (test* "lcs tail" '(b c)
439 (lcs '(a b c) '(b c)))
440
441 (test* "lcs same" '(a b c)
442 (lcs '(a b c) '(a b c)))
443
444 (test* "lcs no common" '()
445 (lcs '(a b c) '(x y z)))
446
447 (test* "lcs empty" '()
448 (lcs '(a b c) '()))
449
450 (test* "lcs mislead" '(a x b y c z)
451 (lcs '(a x b y c z p d q) '(a b c a x b y c z)))
452
453 (test* "lcs mislead count"
454 '(6 ((a 0 0) (x 1 4) (b 2 5) (y 3 6) (c 4 7) (z 5 8)))
455 (lcs-with-positions '(a x b y c z p d q) '(a b c a x b y c z)))
456
457 (let1 z (iota 200)
458 (test* "lcs (long, same)" #t (equal? z (lcs z z)))
459 (test* "lcs (long, none)" '(199) (lcs (reverse z) z))
460 (test* "lcs (long)" '(0 1 2 3 4 5 6 7 8 9)
461 (lcs z (apply append (make-list 10 (iota 10)))))
462 (test* "lcs (long)" '(0 1 2 3 4 5 6 7 8 9)
463 (lcs z (apply append (make-list 10 (iota 10 9 -1)))))
464 )
465
466 (test* "lcs edit-list"
467 '(((- 0 a))
468 ((+ 2 d))
469 ((- 4 h) (+ 4 f))
470 ((+ 6 k))
471 ((- 8 n) (- 9 p) (+ 9 r) (+ 10 s) (+ 11 t)))
472 (lcs-edit-list '(a b c e h j l m n p)
473 '(b c d e f j k l m r s t)))
474
475 (test* "lcs edit-list"
476 '(((- 0 a) (- 1 b) (- 2 c) (- 3 d) (+ 0 e) (+ 1 f) (+ 2 g) (+ 3 h)))
477 (lcs-edit-list '(a b c d) '(e f g h)))
478
479 (test* "lcs edit-list"
480 '()
481 (lcs-edit-list '(a b c d) '(a b c d)))
482
483 (test* "lcs edit-list"
484 '(((- 0 a) (- 1 b) (- 2 c) (- 3 d)))
485 (lcs-edit-list '(a b c d) '()))
486
487 (test* "lcs edit-list"
488 '(((+ 0 a) (+ 1 b) (+ 2 c) (+ 3 d)))
489 (lcs-edit-list '() '(a b c d)))
490
491 (test* "lcs edit-list"
492 '(((+ 0 b)) ((- 1 b)))
493 (lcs-edit-list '(a b) '(b a)))
494
495 (test* "lcs edit-list"
496 '(((- 1 b)))
497 (lcs-edit-list '(a b) '(a)))
498
499 (test* "lcs edit-list"
500 '(((+ 1 b)))
501 (lcs-edit-list '(a) '(a b)))
502
503 (test* "lcs edit-list/context (no diff)"
504 '()
505 (lcs-edit-list/context '(a b c) '(a b c)))
506
507 (test* "lcs edit-list/context (a empty)"
508 '(#((0 0) (0 3 (+ a) (+ b) (+ c))))
509 (lcs-edit-list/context '() '(a b c)))
510
511 (test* "lcs edit-list/context (b empty)"
512 '(#((0 3 (- a) (- b) (- c)) (0 0)))
513 (lcs-edit-list/context '(a b c) '()))
514
515 (test* "lcs edit-list/context (deletion)"
516 '(#((0 4 (= a) (- b) (= c) (= d))
517 (0 3 (= a) (= c) (= d))))
518 (lcs-edit-list/context '(a b c d) '(a c d)))
519
520 (test* "lcs edit-list/context (addition)"
521 '(#((0 4 (= a) (= b) (= c) (= d))
522 (0 5 (= a) (= b) (+ z) (= c) (= d))))
523 (lcs-edit-list/context '(a b c d) '(a b z c d)))
524
525 (test* "lcs edit-list/context (change)"
526 '(#((0 3 (= a) (! b) (= c)) (0 3 (= a) (! d) (= c))))
527 (lcs-edit-list/context '(a b c) '(a d c)))
528
529 (test* "lcs edit-list/context size"
530 '(#((3 12 (= d) (= e) (= f) (! g) (! h) (! i) (= j) (= k) (= l))
531 (3 12 (= d) (= e) (= f) (! x) (! y) (! z) (= j) (= k) (= l))))
532 (lcs-edit-list/context '(a b c d e f g h i j k l m n)
533 '(a b c d e f x y z j k l m n)))
534
535 (test* "lcs edit-list/context size"
536 '(#((5 10 (= f) (! g) (! h) (! i) (= j))
537 (5 10 (= f) (! x) (! y) (! z) (= j))))
538 (lcs-edit-list/context '(a b c d e f g h i j k l m n)
539 '(a b c d e f x y z j k l m n)
540 eq? :context-size 1))
541
542 (test* "lcs edit-list/context multiple hunks"
543 '(#((1 4 (= b) (! c) (= d))
544 (1 5 (= b) (! C) (! C) (= d)))
545 #((9 13 (= j) (- k) (- l) (= m))
546 (10 12 (= j) (= m))))
547 (lcs-edit-list/context '(a b c d e f g h i j k l m n)
548 '(a b C C d e f g h i j m n)
549 eq? :context-size 1))
550
551 (test* "lcs edit-list/context hunk merging"
552 '(#((0 11 (= a) (! b) (! c) (= d) (= e) (= f) (= g) (! h) (! i) (= j) (= k))
553 (0 11 (= a) (! B) (! C) (= d) (= e) (= f) (= g) (! H) (! I) (= j) (= k)))
554 #((12 17 (= m) (= n) (! o) (! p) (= q))
555 (12 17 (= m) (= n) (! O) (! P) (= q))))
556 (lcs-edit-list/context '(a b c d e f g h i j k l m n o p q)
557 '(a B C d e f g H I j k l m n O P q)
558 eq? :context-size 2))
559
560 (test* "lcs edit-list/context boundary condition 1"
561 '(#((0 5 (- a) (- b) (= c) (= d) (= e))
562 (0 3 (= c) (= d) (= e)))
563 #((8 11 (= i) (= j) (= k))
564 (6 11 (= i) (= j) (= k) (+ l) (+ m))))
565 (lcs-edit-list/context '(a b c d e f g h i j k)
566 '(c d e f g h i j k l m)))
567
568 (test* "lcs edit-list/context boundary condition"
569 '(#((0 5 (! a) (! b) (= c) (= d) (= e))
570 (0 4 (! B) (= c) (= d) (= e)))
571 #((8 12 (= i) (= j) (= k) (! L))
572 (7 12 (= i) (= j) (= k) (! l) (! m))))
573 (lcs-edit-list/context '(a b c d e f g h i j k L)
574 '(B c d e f g h i j k l m)))
575
576 (test* "lcs edit-list/unified (no diff)"
577 '()
578 (lcs-edit-list/unified '(a b c) '(a b c)))
579
580 (test* "lcs edit-list/unified (a empty)"
581 '(#(0 0 0 3 ((+ a) (+ b) (+ c))))
582 (lcs-edit-list/unified '() '(a b c)))
583
584 (test* "lcs edit-list/unified (b empty)"
585 '(#(0 3 0 0 ((- a) (- b) (- c))))
586 (lcs-edit-list/unified '(a b c) '()))
587
588 (test* "lcs edit-list/unified (deletion)"
589 '(#(0 4 0 3 ((= a) (- b) (= c) (= d))))
590 (lcs-edit-list/unified '(a b c d) '(a c d)))
591
592 (test* "lcs edit-list/unified (addition)"
593 '(#(0 4 0 5 ((= a) (= b) (+ z) (= c) (= d))))
594 (lcs-edit-list/unified '(a b c d) '(a b z c d)))
595
596 (test* "lcs edit-list/unified (change)"
597 '(#(0 3 0 3 ((= a) (- b) (+ d) (= c))))
598 (lcs-edit-list/unified '(a b c) '(a d c)))
599
600 (test* "lcs edit-list/unified size"
601 '(#(3 9 3 9 ((= d) (= e) (= f) (- g) (- h) (- i)
602 (+ x) (+ y) (+ z) (= j) (= k) (= l))))
603 (lcs-edit-list/unified '(a b c d e f g h i j k l m n)
604 '(a b c d e f x y z j k l m n)))
605
606 (test* "lcs edit-list/unified size"
607 '(#(5 5 5 5 ((= f) (- g) (- h) (- i)
608 (+ x) (+ y) (+ z) (= j))))
609 (lcs-edit-list/unified '(a b c d e f g h i j k l m n)
610 '(a b c d e f x y z j k l m n)
611 eq? :context-size 1))
612
613 (test* "lcs edit-list/unified multiple hunks"
614 '(#(1 3 1 4 ((= b) (- c) (+ C) (+ C) (= d)))
615 #(9 4 10 2 ((= j) (- k) (- l) (= m))))
616 (lcs-edit-list/unified '(a b c d e f g h i j k l m n)
617 '(a b C C d e f g h i j m n)
618 eq? :context-size 1))
619
620 (test* "lcs edit-list/unified hunk merging"
621 '(#(0 11 0 11 ((= a) (- b) (- c) (+ B) (+ C) (= d) (= e) (= f) (= g)
622 (- h) (- i) (+ H) (+ I) (= j) (= k)))
623 #(12 5 12 5 ((= m) (= n) (- o) (- p) (+ O) (+ P) (= q))))
624 (lcs-edit-list/unified '(a b c d e f g h i j k l m n o p q)
625 '(a B C d e f g H I j k l m n O P q)
626 eq? :context-size 2))
627
628 (test* "lcs edit-list/unified boundary condition 1"
629 '(#(0 5 0 3 ((- a) (- b) (= c) (= d) (= e)))
630 #(8 3 6 5 ((= i) (= j) (= k) (+ l) (+ m))))
631 (lcs-edit-list/unified '(a b c d e f g h i j k)
632 '(c d e f g h i j k l m)))
633
634 (test* "lcs edit-list/unified boundary condition"
635 '(#(0 5 0 4 ((- a) (- b) (+ B) (= c) (= d) (= e)))
636 #(8 4 7 5 ((= i) (= j) (= k) (- L) (+ l) (+ m))))
637 (lcs-edit-list/unified '(a b c d e f g h i j k L)
638 '(B c d e f g h i j k l m)))
639
640 ;;-----------------------------------------------
641 (test-section "util.rbtree")
642 (use util.rbtree)
643 (use gauche.sequence)
644 (use srfi.27)
645 (test-module 'util.rbtree)
646
647 (define rbtree-check
648 (with-module util.rbtree rbtree-check))
649
650 (let1 tree1 #f
651 (test* "make-rbtree" #t
652 (begin (set! tree1 (make-rbtree = <))
653 (rbtree? tree1)))
654 (test* "rbtree-get" (test-error)
655 (rbtree-get #f 0 'foo))
656 (test* "rbtree-get" 'not-found
657 (rbtree-get tree1 0 'not-found))
658 (test* "rbtree-get" (test-error)
659 (rbtree-get tree1 0))
660 (test* "rbtree-put!" (test-error)
661 (rbtree-put! #f 0 'foo))
662 (test* "rbtree-put!" "0"
663 (begin (rbtree-put! tree1 0 "0")
664 (rbtree-get tree1 0)))
665 (test* "rbtree-put!" '("0" "1")
666 (begin (rbtree-put! tree1 1 "1")
667 (list (rbtree-get tree1 0)
668 (rbtree-get tree1 1))))
669 (test* "rbtree-put!" 'bar
670 (begin (rbtree-put! tree1 2 'foo)
671 (rbtree-put! tree1 2 'bar)
672 (rbtree-get tree1 2)))
673 (test* "rbtree-check" #t
674 (rbtree-check tree1))
675 (test* "rbtree-fold" '(2 bar 1 "1" 0 "0")
676 (rbtree-fold tree1 list* '()))
677 (test* "rbtree-fold-right" '(0 "0" 1 "1" 2 bar)
678 (rbtree-fold-right tree1 list* '()))
679 (test* "rbtree-delete! (exiting key)" '(#t not-found)
680 (let1 r (rbtree-delete! tree1 1)
681 (list r (rbtree-get tree1 1 'not-found))))
682 (test* "rbtree-delete! (non-existing key)" #f
683 (rbtree-delete! tree1 1))
684 (test* "rbtree-delete!" 'no-error
685 (begin (rbtree-delete! tree1 1)
686 'no-error))
687 (test* "rbtree->alist" '()
688 (rbtree->alist (make-rbtree = <)))
689 (test* "rbtree->alist" '((0 . "0") (1 . "1") (2 . "2"))
690 (let1 tree (make-rbtree = <)
691 (for-each (^p (rbtree-put! tree (car p) (cdr p)))
692 '((0 . "0") (1 . "1") (2 . "2")))
693 (rbtree->alist tree)))
694 (test* "alist->rbtree" '((0 . "0") (1 . "1") (2 . "2"))
695 (rbtree->alist
696 (alist->rbtree '((0 . "0") (1 . "1") (2 . "2")) = <)))
697 (test* "rbtree-empty?" #f
698 (rbtree-empty? tree1))
699 (test* "rbtree-empty?" #t
700 (rbtree-empty? (make-rbtree < =)))
701 (test* "rbtree-empty?" (test-error)
702 (rbtree-empty? 'wrong-arg))
703 (test* "rbtree-exists?" '(#t #f)
704 (let1 tree (make-rbtree = <)
705 (rbtree-put! tree 1 'foo)
706 (map (cut rbtree-exists? tree <>)
707 '(1 2))))
708 (test* "rbtree-num-entries" '(0 1 0)
709 (let* ((t (make-rbtree = <))
710 (a (rbtree-num-entries t))
711 (b (begin (rbtree-put! t 7 7)
712 (rbtree-num-entries t)))
713 (c (begin (rbtree-delete! t 7)
714 (rbtree-num-entries t))))
715 (list a b c)))
716 (test* "rbtree-push!" '(bar foo)
717 (let1 tree (make-rbtree = <)
718 (rbtree-push! tree 1 'foo)
719 (rbtree-push! tree 1 'bar)
720 (rbtree-get tree 1)))
721 (test* "rbtree-pop!" '(foo bar)
722 (let1 tree (alist->rbtree '((1 foo bar)) = <)
723 (let1 r (rbtree-pop! tree 1)
724 (list r (rbtree-pop! tree 1)))))
725 (test* "rbtree-update!" 2
726 (let1 tree (make-rbtree = <)
727 (rbtree-update! tree 1 (cut + 1 <>) 0)
728 (rbtree-update! tree 1 (cut + 1 <>) 0)
729 (rbtree-get tree 1)))
730 )
731
732 ;; iterators
733 (let ((empty (make-rbtree = <))
734 (tree2 (alist->rbtree '((1 . "1") (0 . "0") (2 . "2")) = <)))
735
736 (test* "rbtree-min" '(0 . "0") (rbtree-min tree2))
737 (test* "rbtree-max" '(2 . "2") (rbtree-max tree2))
738 (test* "rbtree-min" (test-error) (rbtree-min 'wrong-arg))
739 (test* "rbtree-min" (test-error) (rbtree-min 'wrong-arg))
740 (test* "rbtree-min" 'default (rbtree-min empty 'default))
741 (test* "rbtree-max" 'default (rbtree-max empty 'default))
742
743 (test* "rbtree-keys" '(0 1 2)
744 (rbtree-keys tree2))
745
746 (test* "rbtree-values" '("0" "1" "2")
747 (rbtree-values tree2))
748
749 (test* "rbtree-copy" #t
750 (let1 new (rbtree-copy tree2)
751 (rbtree-check new)
752 (equal? (rbtree->alist tree2)
753 (rbtree->alist new))))
754
755 (test* "for-each" (rbtree->alist tree2)
756 (let1 r '()
757 (for-each (^e (push! r e)) tree2)
758 (reverse! r)))
759
760 (test* "map" (rbtree->alist tree2)
761 (map values tree2))
762
763 (test* "fold" (rbtree->alist tree2)
764 (reverse! (fold cons '() tree2)))
765
766 (test* "fold-right" (rbtree->alist tree2)
767 (fold-right cons '() tree2))
768
769 (test* "ref" '("0" "1" "2")
770 (map (cut ref tree2 <>) '(0 1 2)))
771
772 (test* "rbtree-extract-min!" '((0 . "0") (1 . "1"))
773 (let1 r (rbtree-extract-min! tree2)
774 (list r (rbtree-min tree2))))
775
776 (test* "rbtree-extract-max!" '((2 . "2") (1 . "1"))
777 (let1 r (rbtree-extract-max! tree2)
778 (list r (rbtree-max tree2))))
779 )
780
781 ;; collection interface
782 (let1 tree4 (alist->rbtree '(("0" . 0) ("1" . 1) ("2" . 1))
783 string=? string<?)
784 (test* "map" '(("0" . 0) ("1" . 1) ("2" . 1))
785 (map values tree4))
786
787 (test* "call-with-builder" '(("0" . 0) ("1" . 1) ("2" . 1))
788 (call-with-builder <rbtree>
789 (lambda (add! get)
790 (for-each add! '(("0" . 0) ("1" . 1) ("2" . 1)))
791 (rbtree->alist (get)))
792 :key=? string=? :key<? string<?))
793 )
794
795 ;; random insertion/deletion
796
797 (let1 tree4 (make-rbtree = <)
798 (random-source-randomize! default-random-source)
799
800 (test* "random insertion/deletion" 'done
801 (begin (dotimes (_ 5)
802 (dotimes (_ 30)
803 (let1 i (random-integer 30)
804 (rbtree-put! tree4 i i)
805 (rbtree-check tree4)))
806 (dotimes (_ 30)
807 (let1 i (random-integer 30)
808 (rbtree-delete! tree4 i)
809 (rbtree-check tree4))))
810 'done))
811 )
812
813
814 ;;-----------------------------------------------
815 (test-section "util.record")
816 (use util.record)
817 (test-module 'util.record)
818
819 (define record:1 (make-record-type "record:1" '(a b c)))
820
821 (test* "make-record-type" #t
822 (is-a? record:1 <class>))
823
824 (test* "make-record-type (error)" (test-error)
825 (make-record-type "record:1" '((x 2) y)))
826
827 (test* "make-record-type (error)" (test-error)
828 (make-record-type "record:1" '(a b a)))
829
830 (test* "record-constructor" #t
831 (is-a? ((record-constructor record:1)) <record>))
832
833 (test* "record-constructor" '(7 8 9)
834 (let ((obj ((record-constructor record:1 '(c b a)) 9 8 7)))
835 (map (cut slot-ref obj <>) '(a b c))))
836
837 (test* "record-predicate" #t
838 (let ((obj ((record-constructor record:1))))
839 ((record-predicate record:1) obj)))
840
841 (test* "record-predicate" #f
842 (let ((obj ((record-constructor record:1))))
843 ((record-predicate record:1) (make <record>))))
844
845 (test* "record-accessor" 1
846 (let ((obj ((record-constructor record:1 '(b)) 1))
847 (acc (record-accessor record:1 'b)))
848 (acc obj)))
849
850 (test* "record-modifier" 2
851 (let ((obj ((record-constructor record:1 '(c)) 3))
852 (acc (record-accessor record:1 'c))
853 (mod (record-modifier record:1 'c)))
854 (mod obj 2)
855 (acc obj)))
856
857 ;;-----------------------------------------------
858 (test-section "util.relation")
859 (use util.relation)
860 (test-module 'util.relation)
861 (use gauche.sequence)
862
863 (let ((r #f))
864 (test* "simple-relation" '<simple-relation>
865 (begin
866 (set! r (make <simple-relation>
867 :columns '(a b c d e)
868 :rows (list
869 (vector 0 1 2 3 4)
870 (vector 5 6 7 8 9)
871 (vector 10 11 12 13 14)
872 (vector 15 16 17 18 19))))
873 (class-name (class-of r))))
874
875 (test* "simple-relation (relation-ref)" '(0 5 10 15)
876 (map (cut relation-ref r <> 'a) r))
877
878 (test* "simple-relation (relation-accessor)" '(1 6 11 16)
879 (let1 ref (relation-accessor r)
880 (map (cut ref <> 'b) r)))
881
882 (test* "simple-relation (relation-column-getter)" '(2 7 12 17)
883 (let1 getter (relation-column-getter r 'c)
884 (map getter r)))
885
886 (test* "simple-relation (relation-set!)" '(100 105 110 115)
887 (begin
888 (for-each (lambda (row)
889 (relation-set! r row 'a
890 (+ (relation-ref r row 'a) 100)))
891 r)
892 (map (cut relation-ref r <> 'a) r)))
893
894 (test* "simple-relation (relation-modifier)" '(201 206 211 216)
895 (let ((set (relation-modifier r))
896 (ref (relation-accessor r)))
897 (for-each (lambda (row)
898 (set row 'b (+ (ref row 'b) 200)))
899 r)
900 (map (cut ref <> 'b) r)))
901
902 (test* "simple-relation (relation-column-setter)" '(304 309 314 319)
903 (let ((getter (relation-column-getter r 'e))
904 (setter (relation-column-setter r 'e)))
905 (for-each (lambda (row) (setter row (+ (getter row) 300))) r)
906 (map getter r)))
907
908 (test* "simple-relation (relation-fold)" 1264
909 (relation-fold r + 0 'a 'b))
910
911 )
912
913 (define-class <object-set-test> ()
914 ((a :init-value 0 :init-keyword :a)
915 (b :init-value 1 :init-keyword :b)
916 (c :init-value 2 :init-keyword :c)))
917
918 (let ((r #f))
919 (test* "object-set-relation" '<object-set-relation>
920 (begin
921 (set! r (make <object-set-relation>
922 :class <object-set-test>
923 :rows (list
924 (make <object-set-test> :a 0 :b 1 :c 2)
925 (make <object-set-test> :a 3 :b 4 :c 5)
926 (make <object-set-test> :a 6 :b 7 :c 8)
927 (make <object-set-test> :a 9 :b 10 :c 11))))
928 (class-name (class-of r))))
929
930 (test* "object-set-relation (relation-ref)" '(0 3 6 9)
931 (map (cut relation-ref r <> 'a) r))
932
933 (test* "object-set-relation (relation-accessor)" '(1 4 7 10)
934 (let1 ref (relation-accessor r)
935 (map (cut ref <> 'b) r)))
936
937 (test* "object-set-relation (relation-column-getter)" '(2 5 8 11)
938 (let1 getter (relation-column-getter r 'c)
939 (map getter r)))
940
941 (test* "object-set-relation (relation-set!)" '(100 103 106 109)
942 (begin
943 (for-each (lambda (row)
944 (relation-set! r row 'a
945 (+ (relation-ref r row 'a) 100)))
946 r)
947 (map (cut relation-ref r <> 'a) r)))
948
949 (test* "object-set-relation (relation-modifier)" '(201 204 207 210)
950 (let ((set (relation-modifier r))
951 (ref (relation-accessor r)))
952 (for-each (lambda (row)
953 (set row 'b (+ (ref row 'b) 200)))
954 r)
955 (map (cut ref <> 'b) r)))
956
957 (test* "object-set-relation (relation-column-setter)" '(302 305 308 311)
958 (let ((getter (relation-column-getter r 'c))
959 (setter (relation-column-setter r 'c)))
960 (for-each (lambda (row) (setter row (+ (getter row) 300))) r)
961 (map getter r)))
962
963 (test* "simple-relation (relation-fold)" 1644
964 (relation-fold r + 0 'a 'c))
965 )
966 ;;-----------------------------------------------
967 (test-section "util.stream")
968 (use util.stream)
969 (test-module 'util.stream)
970
971 (test* "stream?" #t
972 (stream? (stream-cons 'a stream-null)))
973
974 (test* "stream-cons/car/cdr" '(1 1 1)
975 (letrec ((s (stream-cons 1 s)))
976 (list (stream-car s)
977 (stream-cadr s)
978 (stream-caddr s))))
979
980 (test* "stream-delay" #t
981 (stream? (stream-delay (error "Boo"))))
982
983 (test* "stream-lambda/stream-take" '(1 3 5 7 9)
984 (letrec ([iter (stream-lambda (f x)
985 (stream-cons x (iter f (f x))))])
986 (stream->list (stream-take (iter (pa$ + 2) 1) 5))))
987
988 (test* "define-stream/stream-take" '(0 2 4 6 8)
989 (let ()
990 (define-stream (iter f x)
991 (stream-cons x (iter f (f x))))
992 (stream->list (stream-take (iter (pa$ + 2) 0) 5))))
993
994 (test* "stream-unfold" '(0 1 4 9 16 25 36 49 64 81)
995 (stream->list 10
996 (stream-unfold (cut expt <> 2)
997 (^_ #t)
998 (cut + <> 1)
999 0)))
1000
1001 (test* "stream-unfoldn" '((0 2 4 6) (1 3 5 7))
1002 (receive (s0 s1)
1003 (stream-unfoldn (lambda (s)
1004 (values (+ s 2)
1005 (list s)
1006 (list (+ s 1))))
1007 0 2)
1008 (map (lambda (s)
1009 (list (stream-first s)
1010 (stream-second s)
1011 (stream-third s)
1012 (stream-fourth s)))
1013 (list s0 s1))))
1014
1015 (test* "stream-unfolds" '((1 3 5 7) (0 2 4 6))
1016 (receive (s0 s1)
1017 (stream-unfolds (^s (if (stream-null? s)
1018 (values s '() '())
1019 (if (odd? (stream-car s))
1020 (values (stream-cdr s)
1021 (list (stream-car s))
1022 #f)
1023 (values (stream-cdr s)
1024 #f
1025 (list (stream-car s))))))
1026 (stream-iota 10))
1027 (map (lambda (s)
1028 (list (stream-first s)
1029 (stream-second s)
1030 (stream-third s)
1031 (stream-fourth s)))
1032 (list s0 s1))))
1033
1034 (test* "stream-map/stream-ref" '(2 4 6 8)
1035 (let1 s
1036 (stream-map (cut * 2 <>)
1037 (stream-unfoldn (^s (values (+ s 1) (list s)))
1038 0 1))
1039 (map (cut stream-ref s <>) '(1 2 3 4))))
1040
1041 (test* "stream-for-each/stream-iota" '(1 3 5 7)
1042 (let1 r '()
1043 (stream-for-each (lambda (x y)
1044 (push! r (+ x y)))
1045 (stream-iota 4)
1046 (stream-iota -1 1))
1047 (reverse r)))
1048
1049 (test* "stream-iota" '(1.0 1.5 2.0 2.5 3.0)
1050 (stream->list (stream-iota 5 1 0.5)))
1051
1052 (test* "stream-iota" '(1.0 1.0+1.0i 1.0+2.0i 1.0+3.0i)
1053 (stream->list (stream-iota 4 1 +i)))
1054
1055 (test* "stream-filter/take/drop" '(12 15 18 21)
1056 (let1 s (stream-filter (^x (zero? (modulo x 3)))
1057 (stream-iota))
1058 (stream->list (stream-take (stream-drop s 4) 4))))
1059
1060 (test* "stream-range" '(10 9 8 7)
1061 (stream->list (stream-range 10 6)))
1062
1063 (test* "stream-range" '(10.0 9.0 8.0 7.0)
1064 (stream->list (stream-range 10 6.0)))
1065
1066 (test* "stream-range" (lrange 0 1 0.1)
1067 (stream->list (stream-range 0 1 0.1)))
1068
1069 (test* "stream-drop-while/stream-range" '(5 6 7 8 9)
1070 (stream->list 5 (stream-drop-while (cut < <> 5)
1071 (stream-range 0))))
1072
1073 (test* "stream-take-while/stream-range" '(0 1 2 3 4)
1074 (stream->list (stream-take-while (cut < <> 5)
1075 (stream-range 0))))
1076
1077 (test* "stream-fold" '(4 3 2 1 0)
1078 (stream-fold xcons '() (stream-iota 5)))
1079
1080 (test* "stream-from" '(0 1 2 3 4)
1081 (stream->list 5 (stream-from 0)))
1082
1083 (test* "stream-from" '(1 3 5 7 9)
1084 (stream->list 5 (stream-from 1 2)))
1085
1086 (test* "stream-from" '(1 3/2 2 5/2 3)
1087 (stream->list 5 (stream-from 1 1/2)))
1088
1089 (test* "stream-from" '(1.0 1.1 1.2 1.3 1.4)
1090 (stream->list 5 (stream-from 1 0.1)))
1091
1092 (test* "stream-iterate" '(10 11 12 13 14)
1093 (stream->list 5 (stream-iterate (cut + <> 1) 10)))
1094
1095 (test* "stream-iterate" '(1 2 4 8 16)
1096 (stream->list 5 (stream-iterate (cut * <> 2) 1)))
1097
1098 (test* "stream-length" 6 (stream-length (stream 0 1 2 3 4 5)))
1099 (test* "stream-length" 0 (stream-length (stream)))
1100
1101 (test* "stream-match" 5
1102 (let ()
1103 (define (len s)
1104 (stream-match s
1105 [() 0]
1106 [(head . tail) (+ 1 (len tail))]))
1107 (len (stream 0 1 2 3 4))))
1108
1109 (test* "stream-match" 'ok
1110 (stream-match (stream 1 1 2)
1111 [(x y . _) (equal? x y) 'ok]
1112 [else 'ng]))
1113
1114 (test* "stream-match" 'ng
1115 (stream-match (stream 1 2 1)
1116 [(x y . _) (equal? x y) 'ok]
1117 [else 'ng]))
1118
1119 (test* "stream-of" '(0 4 16 36 64)
1120 (stream->list
1121 (stream-of (* x x)
1122 (x in (stream-range 0 10))
1123 (even? x))))
1124
1125 (test* "stream-of" '((1 1) (1 2) (2 1) (2 2) (3 1) (3 2))
1126 (stream->list
1127 (stream-of (list a b)
1128 (a in (stream-range 1 4))
1129 (b in (stream-range 1 3)))))
1130
1131 (test* "stream-of" '((3 4 5) (5 12 13) (6 8 10))
1132 (stream->list
1133 (stream-of (list a b c)
1134 (a in (stream-range 1 14))
1135 (b in (stream-range a 14))
1136 (c in (stream-range b 14))
1137 (d is (+ (* a a) (* b b)))
1138 (= (* c c) d))))
1139
1140 (test* "stream-reverse" '(5 4 3 2 1)
1141 (stream->list (stream-reverse (stream 1 2 3 4 5))))
1142 (test* "stream-reverse" '()
1143 (stream->list (stream-reverse stream-null)))
1144
1145 (test* "stream-scan" '(0 1 3 6 10 15)
1146 (stream->list 6 (stream-scan + 0 (stream-from 1))))
1147 (test* "stream-scan" '(1 1 2 3 5 8 13 21 34 55)
1148 (letrec ((fibs (stream-scan + 1 (stream-cons 0 fibs))))
1149 (stream->list 10 fibs)))
1150 (test* "stream-scan" '(() (a) (b a) (c b a) (d c b a) (e d c b a))
1151 (stream->list (stream-scan xcons '() (stream 'a 'b 'c 'd 'e))))
1152
1153 (test* "stream-zip" '((0 a) (1 b) (2 c))
1154 (stream->list
1155 (stream-zip (stream 0 1 2) (stream 'a 'b 'c))))
1156
1157 (test* "stream-zip" '(0 3 5 7 10)
1158 (let ()
1159 (define-stream (stream-finds eq obj s)
1160 (stream-of (car x)
1161 (x in (stream-zip (stream-from 0) s))
1162 (eq obj (cadr x))))
1163 (stream->list
1164 (stream-finds char=? #\a
1165 (string->stream "abracadabra")))))
1166
1167 (test* "stream-remove" '(0 2 4 6)
1168 (stream->list (stream-remove odd? (stream-iota 8))))
1169
1170 (test* "port->stream" '(#\a #\b #\c)
1171 (let1 p (open-input-string "abc")
1172 (stream->list (port->stream p))))
1173
1174 (test* "stream+" '(1 1/2 1/3)
1175 (stream->list (stream-take (stream+ 1 (/ 1 2) (/ 1 3) (/ 1 0)) 3)))
1176
1177 (test* "stream-append" '(1 2 3 4 a b c d A B C D)
1178 (stream->list
1179 (stream-append (stream 1 2 3 4)
1180 (stream 'a 'b 'c 'd)
1181 (stream 'A 'B 'C 'D))))
1182
1183 (test* "stream-constant" '(1 2 3 1 2 3 1 2)
1184 (stream->list 8
1185 (stream-constant 1 2 3)))
1186
1187 (test* "stream-count" 4
1188 (stream-count odd? (stream-iota 8)))
1189
1190 (test* "stream-any" #f
1191 (stream-any even? stream-null))
1192
1193 (test* "stream-any" #f
1194 (stream-any even? (list->stream '(1 3))))
1195
1196 (test* "stream-any" #t
1197 (stream-any even? (list->stream '(1 2))))
1198
1199 (test* "stream-any" 1
1200 (stream-any string->number (list->stream '("1" "a"))))
1201
1202 (test* "stream-any" 1
1203 (stream-any string->number (list->stream '("1" "2"))))
1204
1205 (test* "stream-any" 1
1206 (stream-any string->number
1207 (list->stream '("1" "2"))
1208 (list->stream '(10 10))))
1209
1210 (test* "stream-any" 1
1211 (stream-any string->number
1212 (list->stream '("1" "2"))
1213 (list->stream '(10))))
1214
1215 (test* "stream-any" #f
1216 (stream-any string->number
1217 (list->stream '("1" "2"))
1218 (list->stream '())))
1219
1220 (test* "stream-every" #t
1221 (stream-every odd? stream-null))
1222
1223 (test* "stream-every" #t
1224 (stream-every odd? (list->stream '(1 3))))
1225
1226 (test* "stream-every" #f
1227 (stream-every odd? (list->stream '(1 2))))
1228
1229 (test* "stream-every" #f
1230 (stream-every string->number (list->stream '("1" "a"))))
1231
1232 (test* "stream-every" 2
1233 (stream-every string->number (list->stream '("1" "2"))))
1234
1235 (test* "stream-every" 2
1236 (stream-every string->number
1237 (list->stream '("1" "2"))
1238 (list->stream '(10 10))))
1239
1240 (test* "stream-every" 1
1241 (stream-every string->number
1242 (list->stream '("1" "2"))
1243 (list->stream '(10))))
1244
1245 (test* "stream-every" #t
1246 (stream-every string->number
1247 (list->stream '("1" "2"))
1248 (list->stream '())))
1249
1250 (test* "stream-intersperse" '(1 0 2 0 3)
1251 (stream->list (stream-intersperse (stream 1 2 3) 0)))
1252 (test* "stream-intersperse" '()
1253 (stream->list (stream-intersperse (stream) 0)))
1254
1255 (test* "stream-split" '((1 3) (5 7 9) () (1))
1256 (stream->list
1257 (stream-map stream->list
1258 (stream-split (stream 1 3 2 5 7 9 6 8 1) even?))))
1259
1260 (test* "stream-last" 3
1261 (stream-last (stream 1 2 3)))
1262 (test* "stream-last" (test-error)
1263 (stream-last (stream)))
1264
1265 (test* "stream-last-n" '(3 4 5)
1266 (stream->list (stream-last-n (stream 1 2 3 4 5) 3)))
1267 (test* "stream-last-n" '(1 2)
1268 (stream->list (stream-last-n (stream 1 2) 3)))
1269 (test* "stream-last" '()
1270 (stream->list (stream-last-n (stream) 3)))
1271
1272 ;;-----------------------------------------------
1273 (test-section "util.temporal-relation")
1274 (use util.temporal-relation)
1275 (test-module 'util.temporal-relation)
1276
1277 (define-module temporal-relation-test
1278 (use gauche.test)
1279 (use util.temporal-relation :prefix tr:)
1280 (use util.match)
1281
1282 (define (interval a b) (cons a b))
1283 (define p tr:pair-interval-protocol)
1284 (define data
1285 `([,(interval 0 5) ,(interval 6 9) before]
1286 [,(interval 0 5) ,(interval 5 9) meets]
1287 [,(interval 0 6) ,(interval 5 9) overlaps]
1288 [,(interval 0 9) ,(interval 5 9) finished-by]
1289 [,(interval 0 9) ,(interval 3 8) contains]
1290 [,(interval 3 8) ,(interval 3 9) starts]
1291 [,(interval 3 9) ,(interval 3 9) equal]
1292 [,(interval 3 9) ,(interval 3 8) started-by]
1293 [,(interval 4 8) ,(interval 0 9) during]
1294 [,(interval 4 9) ,(interval 0 9) finishes]
1295 [,(interval 4 9) ,(interval 0 8) overlapped-by]
1296 [,(interval 5 9) ,(interval 0 5) met-by]
1297 [,(interval 6 9) ,(interval 0 4) after]))
1298 (define point-data
1299 `([,(interval 0 5) 9 before]
1300 [,(interval 0 8) 8 finished-by]
1301 [,(interval 0 8) 7 contains]
1302 [,(interval 5 9) 5 started-by]
1303 [,(interval 5 9) 0 after]))
1304
1305 (dolist [d data]
1306 (match-let1 [x y rel] d
1307 (test* #"relation? ~rel" #t (tr:relation? rel))
1308 (test* #"relate ~x ~y" rel (tr:relate p x y))
1309 (test* #"relate ~y ~x" rel (tr:inverse (tr:relate p y x)))))
1310
1311 (dolist [d point-data]
1312 (match-let1 [x y rel] d
1313 (test* #"relate ~x ~y" rel (tr:relate-point p x y))))
1314 )
1315
1316 ;;-----------------------------------------------
1317 (test-section "util.toposort")
1318 (use util.toposort)
1319 (test-module 'util.toposort)
1320
1321
1322 ;; using famous socks example (Corman)
1323 (let ([sorted '(socks undershorts watch shirt tie pants belt jacket shoes)]
1324 [input '((shirt tie belt)
1325 (tie jacket)
1326 (belt jacket)
1327 (watch)
1328 (pants shoes belt)
1329 (undershorts pants shoes)
1330 (socks shoes))])
1331
1332 (test* "topological-sort, default" sorted
1333 (topological-sort input))
1334
1335 (test* "topological-sort, eq?" sorted
1336 (topological-sort input eq?))
1337
1338 (test* "topological-sort, string=?"
1339 (map symbol->string sorted)
1340 (topological-sort (map (cut map symbol->string <>) input) string=?))
1341 )
1342
1343 ;; cycle
1344 (test* "topological-sort: error" (test-error)
1345 (topological-sort '((watch tie)
1346 (tie watch))))
1347 (test* "topological-sort: error" (test-error)
1348 (topological-sort '((shirt watch)
1349 (watch tie)
1350 (tie watch))))
1351
1352
1353 ;;-----------------------------------------------
1354 (test-section "util.unification")
1355 (use util.unification)
1356 (test-module 'util.unification)
1357 (use util.match)
1358
1359 (let ([data
1360 ;; (a b merged)
1361 '((1 1 1)
1362 (1 2 #f)
1363 (a 1 1)
1364 (a (1 2) (1 2))
1365 (a (1 b) (1 b))
1366 (a (1 a) #f)
1367 ((a b) (b 1) (1 1))
1368 ((a b (c 3)) (2 c (3 b)) (2 3 (3 3)))
1369 ((a b (c 3)) (2 c (4 b)) #f)
1370 ((a b (c 3)) (2 c b) #f)
1371 ((a b (c 3)) (2 d (3 b)) (2 3 (3 3)))
1372 ((a b c) (2 c (3 d)) (2 (3 d) (3 d)))
1373 ((a b c) (2 c (3 a)) (2 (3 2) (3 2)))
1374 ((a b c) (2 c (3 b)) #f))])
1375
1376 (define var (make-comparator symbol? eq? #f eq-hash))
1377 (define val (make-comparator number? eqv? #f #f))
1378 (define (node proto args) args)
1379
1380 (dolist [d data]
1381 (match-let1 (a b m) d
1382 (test* #"unify-merge ~a ~b => ~m" m (unify-merge a b var val fold node))
1383 (test* #"unify-merge ~b ~a => ~m" m (unify-merge b a var val fold node))))
1384 )
1385
1386 (test-end)