Debian Codegraph @

test/data.scm

raw
1 ;; testing data.*
2
3 ;; data.* depends on quite a few modules, so we run this after
4 ;; tests of extension modules are done.
5
6 (use gauche.test)
7 (test-start "data.* modules")
8
9 ;;;========================================================================
10 (test-section "data.cache")
11 (use data.cache)
12 (test-module 'data.cache)
13
14 ;; FIFO cache
15 (let* ([c (make-fifo-cache 4)])
16 (test* "FIFO empty" 'none (cache-lookup! c 'a 'none))
17 (test* "FIFO fill" '((a . 4) (b . 2) (c . 3) (d . 5))
18 (begin
19 (cache-write! c 'a 1)
20 (cache-write! c 'b 2)
21 (cache-write! c 'c 3)
22 (cache-write! c 'a 4)
23 (cache-write! c 'd 5)
24 (list (cache-check! c 'a)
25 (cache-check! c 'b)
26 (cache-check! c 'c)
27 (cache-check! c 'd))))
28 (test* "FIFO non-spill" '((a . 6) (b . 7) (c . 3) (d . 5))
29 (begin
30 (cache-write! c 'a 6)
31 (cache-write! c 'b 7)
32 (list (cache-check! c 'a)
33 (cache-check! c 'b)
34 (cache-check! c 'c)
35 (cache-check! c 'd))))
36 (test* "FIFO spill" '((a . 6) (b . 7) #f #f (e . 8) (f . 9))
37 (begin
38 (cache-write! c 'e 8)
39 (cache-write! c 'f 9)
40 (list (cache-check! c 'a)
41 (cache-check! c 'b)
42 (cache-check! c 'c)
43 (cache-check! c 'd)
44 (cache-check! c 'e)
45 (cache-check! c 'f))))
46 (test* "FIFO evict" '(#f (b . 7) #f (d . 10) (e . 8) (f . 9))
47 (begin
48 (cache-evict! c 'a)
49 (cache-write! c 'd 10)
50 (list (cache-check! c 'a)
51 (cache-check! c 'b)
52 (cache-check! c 'c)
53 (cache-check! c 'd)
54 (cache-check! c 'e)
55 (cache-check! c 'f))))
56 ;; To test renumber, we forcibly change the counter value - do not do this
57 ;; in the actual code!
58 (set! (~ c'counter) (- (greatest-fixnum) 1))
59 (test* "FIFO renumber" '((a . 11) #f (c . 13) (d . 12) #f (f . 9))
60 (begin
61 (cache-write! c 'a '11)
62 (cache-write! c 'd '12)
63 (cache-write! c 'c '13)
64 (list (cache-check! c 'a)
65 (cache-check! c 'b)
66 (cache-check! c 'c)
67 (cache-check! c 'd)
68 (cache-check! c 'e)
69 (cache-check! c 'f))))
70 )
71
72 ;; LRU cache
73 (let* ([c (make-lru-cache 4)])
74 (test* "LRU empty" 'none (cache-lookup! c 'a 'none))
75 (test* "LRU fill" '((a . 4) (b . 2) (c . 3) (d . 5))
76 (begin
77 (cache-write! c 'a 1)
78 (cache-write! c 'b 2)
79 (cache-write! c 'c 3)
80 (cache-write! c 'a 4)
81 (cache-write! c 'd 5)
82 (list (cache-check! c 'a)
83 (cache-check! c 'b)
84 (cache-check! c 'c)
85 (cache-check! c 'd))))
86 (test* "LRU spill" '((a . 4) #f #f (d . 5) (e . 8) (f . 9))
87 (begin
88 (cache-check! c 'a)
89 (cache-check! c 'd)
90 (cache-write! c 'e 8)
91 (cache-write! c 'f 9)
92 (list (cache-check! c 'a)
93 (cache-check! c 'b)
94 (cache-check! c 'c)
95 (cache-check! c 'd)
96 (cache-check! c 'e)
97 (cache-check! c 'f))))
98 (test* "LRU evict" '(#f #f #f (d . 5) (e . 8) (f . 9))
99 (begin
100 (cache-evict! c 'a)
101 (list (cache-check! c 'a)
102 (cache-check! c 'b)
103 (cache-check! c 'c)
104 (cache-check! c 'd)
105 (cache-check! c 'e)
106 (cache-check! c 'f))))
107 ;; To test renumber, we forcibly change the counter value - do not do this
108 ;; in the actual code!
109 (set! (~ c'counter) (- (greatest-fixnum) 1))
110 (test* "LRU renumber" '((a . 11) #f (c . 13) (d . 12) #f (f . 9))
111 (begin
112 (cache-write! c 'a '11)
113 (cache-write! c 'd '12)
114 (cache-write! c 'c '13)
115 (list (cache-check! c 'a)
116 (cache-check! c 'b)
117 (cache-check! c 'c)
118 (cache-check! c 'd)
119 (cache-check! c 'e)
120 (cache-check! c 'f))))
121 )
122
123 ;; TTL cache tester
124 ;; Avoid tests from depending on timing, we mock timestamper.
125 (let* ([t 0]
126 [c0 (make-ttl-cache 10 :timestamper (^[] t))])
127 (test* "TTL empty" 'none (cache-lookup! c0 'a 'none))
128 (test* "TTL fill" '((a . 1) (b . 2) (c . 3) #f)
129 (begin
130 (cache-register! c0 'a 1)
131 (inc! t)
132 (cache-register! c0 'b 2)
133 (inc! t)
134 (cache-register! c0 'c 3)
135 (list (cache-check! c0 'a)
136 (cache-check! c0 'b)
137 (cache-check! c0 'c)
138 (cache-check! c0 'd))))
139 (test* "TTL lookup" '(1 2 3 #f)
140 (let* ([a (cache-lookup! c0 'a)]
141 [b (begin (inc! t) (cache-lookup! c0 'b))]
142 [c (begin (inc! t) (cache-lookup! c0 'c))]
143 [d (cache-lookup! c0 'd #f)])
144 (list a b c d)))
145 ;; content and timestamp
146 ;; a -> 1 : 0
147 ;; b -> 2 : 1
148 ;; c -> 3 : 2
149 (test* "TTL timeout" '(#f 2 3)
150 (begin (set! t 11) ; expire 'a'
151 (list
152 (cache-lookup! c0 'a #f)
153 (cache-lookup! c0 'b #f)
154 (cache-lookup! c0 'c #f))))
155 ;; content and timestamp
156 ;; b -> 2 : 1
157 ;; c -> 3 : 2
158 (test* "TTL through, register" '(6 7 8 9)
159 (let* ([a1 (cache-through! c0 'a (^_ 6))]
160 [b1 (begin (set! t 12) (cache-through! c0 'b (^_ 7)))]
161 [a2 (begin (cache-register! c0 'a 8)
162 (cache-lookup! c0 'a))]
163 [b2 (begin (set! t 13)
164 (cache-register! c0 'b 9)
165 (cache-lookup! c0 'b))])
166 (list a1 b1 a2 b2)))
167 ;; content and timestamp
168 ;; a -> 8 : 12
169 ;; b -> 9 : 13
170 (test* "TTL multiple timestamps" '(#f 14)
171 (begin
172 (set! t 14)
173 (cache-write! c0 'b 10)
174 (cache-write! c0 'c 11)
175 (set! t 15)
176 (cache-write! c0 'b 12)
177 (cache-write! c0 'c 13)
178 (set! t 16)
179 (cache-write! c0 'c 14)
180 (set! t 26) ; expire b but not c
181 (list (cache-lookup! c0 'b #f)
182 (cache-lookup! c0 'c #f))))
183 ;; content and timestamp
184 ;; c -> 14 : 16
185 (test* "TTL evict" #f
186 (begin
187 (cache-evict! c0 'c)
188 (cache-lookup! c0 'c #f)))
189 )
190
191 ;; TTLR cache tester
192 ;; Avoid tests from depending on timing, we mock timestamper.
193 (let* ([t 0]
194 [c0 (make-ttlr-cache 10 :timestamper (^[] t))])
195 (test* "TTLR empty" 'none (cache-lookup! c0 'a 'none))
196 (test* "TTLR fill" '((a . 1) (b . 2) (c . 3) #f)
197 (begin
198 (cache-register! c0 'a 1)
199 (cache-register! c0 'b 2)
200 (cache-register! c0 'c 3)
201 (list (cache-check! c0 'a)
202 (cache-check! c0 'b)
203 (cache-check! c0 'c)
204 (cache-check! c0 'd))))
205 (test* "TTLR lookup" '(1 2 3 #f)
206 (let* ([a (cache-lookup! c0 'a)]
207 [b (begin (inc! t) (cache-lookup! c0 'b))]
208 [c (begin (inc! t) (cache-lookup! c0 'c))]
209 [d (cache-lookup! c0 'd #f)])
210 (list a b c d)))
211 ;; content and timestamp
212 ;; a -> 1 : 0
213 ;; b -> 2 : 1
214 ;; c -> 3 : 2
215 (test* "TTLR timeout" '(#f 2 3)
216 (begin (set! t 11)
217 (list
218 (cache-lookup! c0 'a #f)
219 (cache-lookup! c0 'b #f)
220 (cache-lookup! c0 'c #f))))
221 ;; content and timestamp
222 ;; b -> 2 : 11
223 ;; c -> 3 : 11
224 (test* "TTLR through, register" '(6 2 8 9)
225 (let* ([a1 (cache-through! c0 'a (^_ 6))]
226 [b1 (begin (set! t 12) (cache-through! c0 'b (^_ 7)))]
227 [a2 (begin (cache-register! c0 'a 8)
228 (cache-lookup! c0 'a))]
229 [b2 (begin (set! t 13)
230 (cache-register! c0 'b 9)
231 (cache-lookup! c0 'b))])
232 (list a1 b1 a2 b2)))
233 ;; content ant timestamp
234 ;; a -> 8 : 12
235 ;; b -> 9 : 13
236 ;; c -> 3 : 11
237 (test* "TTLR multiple" '(8 9 #f)
238 (begin
239 (set! t 22) ; expires c
240 (list (cache-lookup! c0 'a #f)
241 (cache-lookup! c0 'b #f)
242 (cache-lookup! c0 'c #f))))
243 ;; content and timestamp
244 ;; a -> 8 : 22
245 ;; b -> 9 : 22
246 (test* "TTLR multiple - evict" '(8 #f #f)
247 ;; evict an entry that has multiple timestamps
248 (begin
249 (cache-evict! c0 'b)
250 (list (cache-lookup! c0 'a #f)
251 (cache-lookup! c0 'b #f)
252 (cache-lookup! c0 'c #f))))
253 ;; content and timestamp
254 ;; a -> 8 : 22
255 (test* "TTLR multiple - expire" '(#f #f #f)
256 ;; expiring an entry with multiple timestamps
257 (begin
258 (set! t 33)
259 (list (cache-lookup! c0 'a #f)
260 (cache-lookup! c0 'b #f)
261 (cache-lookup! c0 'c #f))))
262 )
263
264 ;; counting cache
265 (let ([c (make-counting-cache (make-fifo-cache 4))])
266 (test* "Counting cache, initial" '(:hits 0 :misses 0)
267 (cache-stats c))
268 (test* "Counting cache" '(:hits 3 :misses 6)
269 (begin
270 (cache-through! c 'a symbol->string) ; miss
271 (cache-through! c 'b symbol->string) ; miss
272 (cache-through! c 'c symbol->string) ; miss
273 (cache-through! c 'd symbol->string) ; miss
274 (cache-through! c 'e symbol->string) ; miss, spills a
275 (cache-through! c 'd symbol->string) ; hit
276 (cache-through! c 'c symbol->string) ; hit
277 (cache-through! c 'b symbol->string) ; hit
278 (cache-through! c 'a symbol->string) ; miss, spills b
279 (cache-stats c)))
280 (test* "Counting cache" '(:hits 8 :misses 9)
281 (begin
282 (cache-through! c 'a symbol->string) ; hit
283 (cache-through! c 'b symbol->string) ; miss, spills c
284 (cache-through! c 'c symbol->string) ; miss, spills d
285 (cache-through! c 'd symbol->string) ; miss, spills e
286 (cache-through! c 'a symbol->string) ; hit
287 (cache-through! c 'b symbol->string) ; hit
288 (cache-through! c 'c symbol->string) ; hit
289 (cache-through! c 'd symbol->string) ; hit
290 (cache-stats c))))
291
292 ;;;========================================================================
293 (test-section "data.ideque")
294 (use data.ideque)
295 (use gauche.generator)
296 (test-module 'data.ideque)
297 (use compat.chibi-test)
298
299 (chibi-test
300 (include "include/ideque-tests"))
301
302 ;; non-SRFI-134 api
303 (test* "make-ideque" '(a a a a a)
304 (ideque->list (make-ideque 5 'a)))
305
306
307 ;;;========================================================================
308 (test-section "data.imap")
309 (use data.imap)
310 (use gauche.sequence)
311 (use gauche.dictionary)
312 (test-module 'data.imap)
313
314 (let* ([z (make-imap)]
315 [z (begin (test* "empty" #t (imap-empty? z))
316 (do ([i 0 (+ i 1)]
317 [z z (let1 n (modulo (* i 61) 128)
318 (imap-put z n (integer->char n)))])
319 [(= i 128) z]
320 ))]
321 [z (begin (test* "exists?" #t
322 (every (cut imap-exists? z <>) (iota 128)))
323 (test* "exists?" #f
324 (imap-exists? z -1))
325 (test* "get" #t
326 (every (^n (eqv? (imap-get z n)
327 (integer->char n)))
328 (iota 128)))
329 (test* "get" (test-error) (imap-get z -1))
330 (test* "get" 'z (imap-get z -1 'z))
331 (test* "collection"
332 (map (^n (cons n (integer->char n))) (iota 128))
333 (map identity z))
334 (test* "dictionary"
335 (reverse (map (^n (cons n (integer->char n))) (iota 128)))
336 (dict-fold z acons '()))
337 (test* "dictionary"
338 (map (^n (cons n (integer->char n))) (iota 128))
339 (dict-fold-right z acons '()))
340 (imap-put z 0 'meow))])
341 (test* "replace" 'meow (imap-get z 0))
342 (test* "min/max" `((0 . meow) (127 . ,(integer->char 127)))
343 (list (imap-min z)
344 (imap-max z)))
345 (test* "min/max" `(#f #f)
346 (let1 z (make-imap)
347 (list (imap-min z)
348 (imap-max z))))
349 (let ()
350 ;; If we give p which is coprime to 128, the series
351 ;; (modulo (* k p) 128) where k = [0..127] will walk all the
352 ;; numbers between [0..127]. We delete the elements in that order
353 ;; and check if it works.
354 (define (delete-test p)
355 (test* #"imap-delete (~p)"
356 ;; result is a list of
357 ;; (index num-elements exists-before-delete exists-after-delete)
358 (map (^k (list k (- 127 k) #t #f)) (iota 128))
359 (let loop ([ns (iota 128)] [z z] [r '()])
360 (if (null? ns)
361 (reverse r)
362 (let* ([k (modulo (* (car ns) p) 128)]
363 [b (imap-exists? z k)]
364 [z (imap-delete z k)])
365 (loop (cdr ns)
366 z
367 (cons (list (car ns)
368 (dict-fold z (^[k v c](+ c 1)) 0)
369 b
370 (imap-exists? z k))
371 r)))))))
372 (delete-test 1) ; in-order deletion
373 (delete-test 13)
374 (delete-test 31)
375 (delete-test 61)
376 (delete-test 127) ; (almost) reverse-order deletion
377 )
378
379 (let1 data (map (^[i] (cons (integer->char i) i)) (iota 128))
380 (test* #"imap and alist conversions"
381 data
382 (dict->alist (alist->imap data char-comparator))))
383 )
384
385 ;;;========================================================================
386
387 ;; data.random is tested in ext/data, for it depends on math.mt-random
388
389 ;;;========================================================================
390
391 ;; data.heap is tested in ext/data, for its test depends on math.mt-random.
392
393 ;;;========================================================================
394 (test-section "data.priority-map")
395 (use data.priority-map)
396 (test-module 'data.priority-map)
397
398 (use scheme.list)
399
400 (let* ([data '((a . 5) (b . 2) (c . 9) (d . -1) (e . -59) (f . 0) (g . 9))])
401 (define (make-populated)
402 (rlet1 m (make-priority-map)
403 (dolist [p data] (dict-put! m (car p) (cdr p)))))
404 (define (compare-minmax-result a b)
405 (and (lset= eq? (car a) (car b))
406 (= (cdr a) (cdr b))))
407 (define (stabilize seq)
408 ;; if there's consecutive items in seq whose cdr is the same,
409 ;; sort them with their cars' order. don't change other items orders.
410 ($ apply append
411 $ map (^[items] (sort-by items car))
412 $ group-sequence seq :key cdr))
413
414 (let1 m (make-populated)
415 (test* "get" (map cdr data)
416 (map (^p (dict-get m (car p))) data))
417 (test* "min" '((e) . -59)
418 (priority-map-min-all m)
419 compare-minmax-result)
420 (test* "min" '(e . -59)
421 (priority-map-min m))
422 (test* "max" '((c g) . 9)
423 (priority-map-max-all m)
424 compare-minmax-result)
425 (test* "max" (test-one-of '(g . 9) '(c . 9))
426 (priority-map-max m))
427 (test* "delete" (remove (^p (eq? (car p) 'c)) data)
428 (begin (dict-delete! m 'c)
429 (sort-by (dict->alist m) car))))
430
431 (let1 m (make-populated)
432 (test* "pop, increasing" (stabilize (sort-by data cdr))
433 (stabilize ((rec (pop m)
434 (if (zero? (size-of m))
435 '()
436 (let1 z (priority-map-pop-min! m)
437 (cons z (pop m)))))
438 m))))
439 (let1 m (make-populated)
440 (test* "pop, decreasing" (stabilize (sort-by data cdr >))
441 (stabilize ((rec (pop m)
442 (if (zero? (size-of m))
443 '()
444 (let1 z (priority-map-pop-max! m)
445 (cons z (pop m)))))
446 m))))
447
448 (let ([tm (alist->tree-map data)])
449 (test* "alist->priority-map" data
450 (sort (dict->alist (alist->priority-map data))))
451 (test* "dict->priority-map" data
452 (sort (dict->alist (dict->priority-map tm)))))
453 )
454
455 ;;;========================================================================
456 ;; range
457 (test-section "data.range")
458 (use data.range)
459 (test-module 'data.range)
460
461 ;; SRFI-196 is a subset of data.range, and we test it here.
462
463 (define-module srfi-196-tests
464 (use gauche.test)
465 (test-include-r7 "include/srfi-196-test"))
466
467 ;; gauche extensions
468
469 (test* "range-ref out of range" (test-error <error> #/Index out of range/)
470 (range-ref (iota-range 10) 11))
471 (test* "range-ref fallback" 'oops
472 (range-ref (iota-range 10) 11 'oops))
473 (test* "range-ref fallback" 'oops
474 (range-ref (iota-range 10) -1 'oops))
475 (test* "range-first fallback" 'wow
476 (range-first (iota-range 0) 'wow))
477 (test* "range-last fallback" 'boo
478 (range-last (iota-range 0) 'boo))
479
480 ;; https://github.com/shirok/Gauche/pull/1004
481 (test* "range-append" '(0 1 2 3 4 10 11 12 13 14)
482 (range->list (range-append (numeric-range 0 5) (numeric-range 10 15))))
483
484 (test* "range-reverse start/end" '(5 4 3)
485 (range->list (range-reverse (iota-range 7) 3 6)))
486 (test* "range-reverse start/end nested" '(5 4 3)
487 (range->list (range-reverse (subrange (iota-range 10) 1 9) 2 5)))
488 (test* "range-reverse start/end nested" '(6 5 4)
489 (range->list (range-reverse
490 (subrange (subrange (iota-range 10) 1 9) 1 6)
491 2 5)))
492
493 (test* "vector-range start/end" '(c d e f g)
494 (range->list (vector-range '#(a b c d e f g) 2)))
495 (test* "vector-range start/end" '(c d e)
496 (range->list (vector-range '#(a b c d e f g) 2 5)))
497 (test* "uvector-range" '(0 1 2 3 4)
498 (range->list (uvector-range '#u8(0 1 2 3 4))))
499 (test* "uvector-range start/end" '(1 2 3 4)
500 (range->list (uvector-range '#u8(0 1 2 3 4 5) 1 5)))
501 (test* "string-range start/end" '(#\c #\d #\e #\f #\g)
502 (range->list (string-range "abcdefg" 2)))
503 (test* "string-range start/end" '(#\c #\d #\e)
504 (range->list (string-range "abcdefg" 2 5)))
505 (test* "bitvector/bool-range" '(#t #f #t #t)
506 (range->list (bitvector/bool-range #*0101100 1 5)))
507 (test* "bitvector/int-range" '(0 1 1 0 0)
508 (range->list (bitvector/int-range #*0101100 2)))
509
510 ;; sequence protocol
511 (test* "range as a sequence (ref)" 3 (~ (numeric-range 1 6) 2))
512 (test* "range as a sequence (iterate)" '(1 2 3 4 5)
513 (coerce-to <list> (numeric-range 1 6)))
514 (test* "range as a sequence (build from list)" '(a b c d e)
515 (range->list (coerce-to <range> '(a b c d e))))
516 (test* "range as a sequence (build from vector)" '(a b c d e)
517 (range->list (coerce-to <range> '#(a b c d e))))
518 (test* "range as a sequence (subseq)" '(3 4 5 6 7)
519 (range->list (subseq (numeric-range 0 10) 3 8)))
520
521 ;; SRFI-42 extension
522 (define-module range-srfi-42-test
523 (use gauche.test)
524 (use data.range)
525 (use srfi.42)
526 (test* "SRFI-42 :range" '((a 0) (b 1) (c 2) (d 3) (e 4))
527 (list-ec (: v (index k) (vector-range '#(a b c d e)))
528 (list v k)))
529 )
530
531 ;;;========================================================================
532 ;; skew-list
533 (test-section "data.skew-list")
534 (use data.skew-list)
535 (use gauche.sequence)
536 (use gauche.generator)
537 (test-module 'data.skew-list)
538
539 (test* "skew-list?" #f (skew-list? '()))
540 (test* "skew-list?" #f (skew-list? '(a b)))
541 (test* "skew-list?" #t (skew-list? (list->skew-list '(a b))))
542
543 (dotimes [n 30]
544 (let1 data (iota n)
545 (test* "list -> skew-list ->list" data
546 (skew-list->list (list->skew-list data)))))
547
548 (test* "skew-list-cons" 'a
549 (skew-list-car (skew-list-cons 'a skew-list-null)))
550 (test* "skew-list-cons/car/cdr" '((z a b c d e) a (b c d e))
551 (let1 sl (list->skew-list '(a b c d e))
552 (list (skew-list->list (skew-list-cons 'z sl))
553 (skew-list-car sl)
554 (skew-list->list (skew-list-cdr sl)))))
555 (test* "skew-list-cons (error)" (test-error)
556 (skew-list-cons 'a 'b))
557 (test* "skew-list-car (error)" (test-error)
558 (skew-list-car skew-list-null))
559 (test* "skew-list-cdr (error)" (test-error)
560 (skew-list-cdr skew-list-null))
561
562 (dotimes [n 20]
563 (test* #"skew-list-length ~n" n
564 (skew-list-length (list->skew-list (make-list n)))))
565
566 (let ([series '(0 1 2 3 5 8 13 21)])
567 (dolist [x series]
568 (dolist [y series]
569 (test* #"skew-list-length<=? ~x ~y" (<= x y)
570 (skew-list-length<=? (list->skew-list (iota x)) y)))))
571
572 (let* ([data '(a b c d e f g h i j k l m n o p q r s t u v w x y z)]
573 [sl (list->skew-list data)])
574 (test* "skew-list-ref" data
575 (map-with-index (^[i _] (skew-list-ref sl i)) data))
576 (test* "skew-list-ref (out of range)" (test-error)
577 (skew-list-ref sl (length data)))
578 (test* "skew-list-ref fallback" 'oops
579 (skew-list-ref sl (length data) 'oops))
580 (dotimes [n (length data)]
581 (test* #"skew-list-set ~n"
582 (rlet1 seq (list-copy data)
583 (list-set! seq n 'z))
584 (skew-list->list (skew-list-set sl n 'z)))))
585
586 ;; mapping
587 (let1 sl (list->skew-list (iota 22))
588 (define (f x) (+ (* 2 x) 1))
589 (test* "skew-list-map" (map f (skew-list->list sl))
590 (skew-list->list (skew-list-map sl f))))
591
592 ;; generator & lseq
593 (let* ([data '(a b c d e f g h i j k l m n o p q r s t u v w x y z)]
594 [sl (list->skew-list data)])
595 (define (t-gen . args)
596 (test* #"skew-list->generator ~args"
597 (apply subseq data args)
598 (generator->list (apply skew-list->generator sl args)))
599 (test* #"skew-list->lseq ~args"
600 (apply subseq data args)
601 (apply skew-list->lseq sl args)))
602 (t-gen)
603 (t-gen 5)
604 (t-gen 9 17)
605 (t-gen 20 20)
606 (t-gen 25 26))
607
608 ;; take
609 (let ()
610 (define (t-take orig-len take-len)
611 (let1 input (iota orig-len)
612 (test* #"skew-list-take ~|take-len| from ~|orig-len|"
613 (take input take-len)
614 (skew-list->list
615 (skew-list-take (list->skew-list input) take-len)))
616 (test* #"skew-list-drop ~|take-len| from ~|orig-len|"
617 (drop input take-len)
618 (skew-list->list
619 (skew-list-drop (list->skew-list input) take-len)))
620 (test* #"skew-list-split-at ~|take-len| from ~|orig-len|"
621 (values->list (split-at input take-len))
622 (receive (a b)
623 (skew-list-split-at (list->skew-list input) take-len)
624 (list (skew-list->list a)
625 (skew-list->list b))))
626 ))
627 ;; We cover all the cases
628 ;; edge case
629 (t-take 0 0)
630 (t-take 10 0)
631 ;; trivial prefix
632 (t-take 26 1) ; 26 = [1 3 7 15]
633 (t-take 26 4)
634 (t-take 26 11)
635 (t-take 26 26)
636 (t-take 29 7) ; 29 = [7 7 15]
637 (t-take 29 14) ; 29 = [7 7 15]
638 (t-take 29 29) ; 29 = [7 7 15]
639 ;; [1 n ...] case
640 (t-take 8 2) ; 8 = [1 7]
641 (t-take 8 5) ; 8 = [1 7]
642 ;; [n ...] (n > 3) case
643 (t-take 14 1) ; 14 = [7 7]
644 (t-take 14 2)
645 (t-take 14 4)
646 (t-take 15 1) ; 15 = [15]
647 (t-take 15 2)
648 (t-take 15 5)
649 (t-take 15 8)
650 ;; [3 ...] case
651 (t-take 6 1) ; 6 = [3 3]
652 (t-take 6 2)
653 ;; general case
654 (t-take 6 3)
655 (t-take 6 4)
656 (t-take 6 5)
657 (t-take 26 2)
658 (t-take 26 3)
659 (t-take 26 5)
660 (t-take 26 10)
661 (t-take 26 15)
662 )
663
664 ;; append
665 (let ()
666 (define (t-append i j)
667 (let ([x (iota i)]
668 [y (iota j)])
669 (test* "skew-list-append" (append x y)
670 (skew-list->list (skew-list-append (list->skew-list x)
671 (list->skew-list y))))))
672 (t-append 0 0)
673 (t-append 0 1)
674 (t-append 1 0)
675 (t-append 1 1)
676 (t-append 1 2)
677 (t-append 1 3)
678 (t-append 1 4)
679 (t-append 1 5)
680 (t-append 2 1)
681 (t-append 2 2)
682 (t-append 2 3)
683 (t-append 2 6)
684 (t-append 3 1)
685 (t-append 3 2)
686 (t-append 3 3)
687 (t-append 3 4)
688 (t-append 3 6)
689 (t-append 3 7)
690 (t-append 3 10)
691 (t-append 5 10)
692 )
693
694 ;; sequence protocol
695 (test* "skew-list size-of" 5
696 (size-of (list->skew-list '(a b c d e))))
697 (test* "skew-list iterator" '(a b c d e f g h i j k l m n o p q)
698 (coerce-to <list> (list->skew-list '(a b c d e f g h i j k l m n o p q))))
699 (test* "skew-list fold" '(e d c b a)
700 (fold cons '() (list->skew-list '(a b c d e))))
701 (test* "skew-list ref" '(a b c d e)
702 (map (cute ref (list->skew-list '(a b c d e)) <>) (iota 5)))
703
704 ;;;========================================================================
705 ;; ulid
706 (test-section "data.ulid")
707 (use data.ulid)
708 (test-module 'data.ulid)
709
710 (define-module ulid-test
711 (use gauche.test)
712 (use data.ulid)
713 (test-include-r7 "include/ulid-test" (exclude (ulid))))
714
715 (test-end)