Debian Codegraph @

test/treemap.scm

raw
1 ;;
2 ;; test for tree-map
3 ;;
4
5 (use gauche.test)
6 (test-start "treemap")
7
8 (define %tree-map-check-consistency
9 (with-module gauche.internal %tree-map-check-consistency))
10
11 ;; Basic stuff
12 (define (do-tree-map ctor)
13 (let1 tree1 #f
14 (test* "make-tree-map" #t
15 (begin (set! tree1 (ctor)) (tree-map? tree1)))
16 (test* "tree-map-get" (test-error)
17 (tree-map-get #f 0 'foo))
18 (test* "tree-map-get" 'not-found
19 (tree-map-get tree1 0 'not-found))
20 (test* "tree-map-get" (test-error)
21 (tree-map-get tree1 0))
22 (test* "tree-map-put!" (test-error)
23 (tree-map-put! #f 0 'foo))
24 (test* "tree-map-put!" "0"
25 (begin (tree-map-put! tree1 0 "0")
26 (tree-map-get tree1 0)))
27 (test* "tree-map-put!" '("0" "1")
28 (begin (tree-map-put! tree1 1 "1")
29 (list (tree-map-get tree1 0)
30 (tree-map-get tree1 1))))
31 (test* "tree-map-put!" 'bar
32 (begin (tree-map-put! tree1 2 'foo)
33 (tree-map-put! tree1 2 'bar)
34 (tree-map-get tree1 2)))
35 (test* "tree-map-adjoin! (no overwrite)" 'bar
36 (begin (tree-map-adjoin! tree1 2 'foo)
37 (tree-map-get tree1 2)))
38 (test* "tree-map-replace! (nonexistent)" #f
39 (begin (tree-map-replace! tree1 3 'foo)
40 (tree-map-get tree1 3 #f)))
41 (test* "tree-map-adjoin! (nonexistent)" 'baz
42 (begin (tree-map-adjoin! tree1 3 'baz)
43 (tree-map-get tree1 3)))
44 (test* "tree-map-replace! (exists)" 'boo
45 (begin (tree-map-replace! tree1 3 'boo)
46 (tree-map-get tree1 3)))
47 (test* "tree-map-fold" '(3 boo 2 bar 1 "1" 0 "0")
48 (tree-map-fold tree1 list* '()))
49 (test* "tree-map-fold-right" '(0 "0" 1 "1" 2 bar 3 boo)
50 (tree-map-fold-right tree1 list* '()))
51 (test* "tree-map-delete! (exiting key)" '(#t not-found)
52 (let1 r (tree-map-delete! tree1 1)
53 (list r (tree-map-get tree1 1 'not-found))))
54 (test* "tree-map-delete! (non-existing key)" #f
55 (tree-map-delete! tree1 1))
56 (test* "tree-map-delete!" 'no-error
57 (begin (tree-map-delete! tree1 1)
58 'no-error))
59 (test* "tree-map->alist" '()
60 (tree-map->alist (ctor)))
61 (test* "tree-map->alist" '((0 . "0") (1 . "1") (2 . "2"))
62 (let1 tree (ctor)
63 (for-each (^p (tree-map-put! tree (car p) (cdr p)))
64 '((0 . "0") (1 . "1") (2 . "2")))
65 (tree-map->alist tree)))
66 (test* "alist->tree-map" '((0 . "0") (1 . "1") (2 . "2"))
67 (tree-map->alist
68 (alist->tree-map '((0 . "0") (1 . "1") (2 . "2")) = <)))
69 (test* "tree-map-empty?" #f
70 (tree-map-empty? tree1))
71 (test* "tree-map-empty?" #t
72 (tree-map-empty? (ctor)))
73 (test* "tree-map-empty?" (test-error)
74 (tree-map-empty? 'wrong-arg))
75 (test* "tree-map-exists?" '(#t #f)
76 (let1 tree (ctor)
77 (tree-map-put! tree 1 'foo)
78 (map (cut tree-map-exists? tree <>)
79 '(1 2))))
80 (test* "tree-map-num-entries" '(0 1 0)
81 (let* ((t (ctor))
82 (a (tree-map-num-entries t))
83 (b (begin (tree-map-put! t 7 7)
84 (tree-map-num-entries t)))
85 (c (begin (tree-map-delete! t 7)
86 (tree-map-num-entries t))))
87 (list a b c)))
88 (test* "tree-map-push!" '(bar foo)
89 (let1 tree (ctor)
90 (tree-map-push! tree 1 'foo)
91 (tree-map-push! tree 1 'bar)
92 (tree-map-get tree 1)))
93 (test* "tree-map-pop!" '(foo bar)
94 (let1 tree (alist->tree-map '((1 foo bar)) = <)
95 (let1 r (tree-map-pop! tree 1)
96 (list r (tree-map-pop! tree 1)))))
97 (test* "tree-map-update!" 2
98 (let1 tree (ctor)
99 (tree-map-update! tree 1 (cut + 1 <>) 0)
100 (tree-map-update! tree 1 (cut + 1 <>) 0)
101 (tree-map-get tree 1)))
102 ))
103
104 (do-tree-map (cut make-tree-map = <))
105 (do-tree-map (cut make-tree-map (^[a b] (cond [(< a b) -1][(= a b) 0][else 1]))))
106 (do-tree-map (cut make-tree-map))
107
108 ;; Min, max, iterators
109 (let ((empty (make-tree-map = <))
110 (tree2 (alist->tree-map '((1 . "1") (0 . "0") (2 . "2")) = <)))
111
112 (test* "tree-map-min" '(0 . "0") (tree-map-min tree2))
113 (test* "tree-map-max" '(2 . "2") (tree-map-max tree2))
114 (test* "tree-map-min" (test-error) (tree-map-min 'wrong-arg))
115 (test* "tree-map-max" (test-error) (tree-map-max 'wrong-arg))
116
117 (test* "tree-map-keys" '(0 1 2)
118 (tree-map-keys tree2))
119
120 (test* "tree-map-values" '("0" "1" "2")
121 (tree-map-values tree2))
122
123 (test* "tree-map-copy" #t
124 (let1 new (tree-map-copy tree2)
125 (%tree-map-check-consistency new)
126 (equal? (tree-map->alist tree2)
127 (tree-map->alist new))))
128
129 (test* "tree-map-pop-min!" '((0 . "0") (1 . "1"))
130 (let1 r (tree-map-pop-min! tree2)
131 (list r (tree-map-min tree2))))
132
133 (test* "tree-map-pop-max!" '((2 . "2") (1 . "1"))
134 (let1 r (tree-map-pop-max! tree2)
135 (list r (tree-map-max tree2))))
136 )
137
138 ;; The following test sequence is carefully assembled so that
139 ;; it goes through every path in the rbtree manipulation routine.
140 ;; The "case" numbers corresponds to BALANCE_CASE/DELETE_CASE macros
141 ;; in treemap.c.
142
143 (let1 tree (make-tree-map = <)
144 (define (i . args) (dolist (k args) (tree-map-put! tree k k)))
145 (define (d . args) (dolist (k args) (tree-map-delete! tree k)))
146 (define (c) (%tree-map-check-consistency tree))
147
148 ;; Insertion
149 ;; case 0. adding to an empty tree
150 ;; B:0
151 (test* "insertion case 0" #t (begin (i 0) (c)))
152
153 ;; case 2. adding to a black parent.
154 ;; B:0
155 ;; R:1
156 (test* "insetrion case 2" #t (begin (i 1) (c)))
157
158 ;; case 3&1. adding to a red parent, while uncle is also red.
159 ;; R:-2
160 ;; B:-1
161 ;; B:0
162 ;; B:1
163 ;; R:2
164 (test* "insertion case 3&1" #t (begin (i -1 -2 2) (c)))
165
166 ;; case 5b. adding to a red parent, while uncle is black.
167 ;; new node is on the right side of parent,
168 ;; while parent is the left side of grandparent.
169 ;; this goes through rotate_left, then rotate_right.
170 ;; R:-2 => -2
171 ;; B:-1 => -1
172 ;; B:0 => 0
173 ;; R:1 => 1
174 ;; B:1.5 => 1.5
175 ;; R:2 => 2
176 (test* "insertion case 5b" #t (begin (i 1.5) (c)))
177
178 ;; case 5a. same as 3a except left and right is swapped.
179 ;; R:-2 => -2
180 ;; B:-1.5 => -1.5
181 ;; R:-1 => -1
182 ;; B:0 => 0
183 ;; R:1 => 1
184 ;; B:1.5 => 1.5
185 ;; R:2 => 2
186 (test* "insertion case 5a" #t (begin (i -1.5) (c)))
187
188 ;; Deletion.
189 ;; case 1. deleting the leaf red node.
190 ;; R:-2 => -2
191 ;; B:-1.5 => -1.5
192 ;; R:-1 => -1
193 ;; B:0 => 0
194 ;; R:1 => 1
195 ;; B:1.5 => 1.5
196 (test* "deletion case 1" #t (begin (d 2) (c)))
197
198 ;; prepare for next test
199 ;; R:-3 => -3
200 ;; B:-2 => -2
201 ;; R:-1.5 => -1.5
202 ;; B:-1 => -1
203 ;; B:0 => 0
204 ;; B:1 => 1
205 ;; R:1.5 => 1.5
206 ;; B:2 => 2
207 ;; R:3 => 3
208 (i 2 3 -2 -3)
209
210 ;; case 8a. deleting the leaf black node.
211 ;; parent is red, sibling is black.
212 ;; R:-3 => -3
213 ;; B:-2 => -2
214 ;; R:-1.5 => -1.5
215 ;; B:-1 => -1
216 ;; B:0 => 0
217 ;; B:1.5 => 1.5
218 ;; R:2 => 2
219 ;; B:3 => 3
220 (test* "deletion case 8a" #t (begin (d 1) (c)))
221
222 ;; case 8b. same, except left/right swapped
223 ;; B:-3 => -3
224 ;; R:-2 => -2
225 ;; B:-1.5 => -1.5
226 ;; B:0 => 0
227 ;; B:1.5 => 1.5
228 ;; R:2 => 2
229 ;; B:3 => 3
230 (test* "deletion case8b" #t (begin (d -1) (c)))
231
232 ;; case 6. deleting red node w/ both children
233 ;; In our implementation, the node is first replaced by
234 ;; its previous node until we get a single-child case,
235 ;; then the balancing is applied. In this particular case
236 ;; it degenerates to the deletion of a black node whose
237 ;; parent is red and whose sibling is black.
238 ;; B:-3 => -3
239 ;; R:-2 => -2
240 ;; B:-1.5 => -1.5
241 ;; B:0 => 0
242 ;; B:1.5 => 1.5
243 ;; R:3 => 3
244 (test* "deletion case6" #t (begin (d 2) (c)))
245
246 ;; case 2. deleting black node, whose parent is black and sibing is red.
247 ;; B:-3 => -3
248 ;; R:-2 => -2
249 ;; B:-1.5 => -1.5
250 ;; B:0 => 0
251 ;; B:3 => 3
252 (test* "deletion case2" #t (begin (d 1.5) (c)))
253
254 ;; preparation
255 ;; B:-3 => -3
256 ;; B:-2 => -2
257 ;; B:-1.5 => -1.5
258 ;; B:0 => 0
259 ;; R:0.5 => 0.5
260 ;; B:1 => 1
261 ;; B:2 => 2
262 ;; B:2.5 => 2.5
263 ;; R:3 => 3
264 ;; B:3.5 => 3.5
265 ;; R:4 => 4
266 (i 2 1 .5 2.5 3.5 4)
267
268 ;; case 5. deleting black node, whose parent and sibling is black
269 ;; and sibling's both child is black.
270 ;; B:-2 => -2
271 ;; R:-1.5 => -1.5
272 ;; B:0 => 0
273 ;; R:0.5 => 0.5
274 ;; B:1 => 1
275 ;; B:2 => 2
276 ;; B:2.5 => 2.5
277 ;; B:3 => 3
278 ;; B:3.5 => 3.5
279 ;; R:4 => 4
280 (test* "deletion case5" #t (begin (d -3) (c)))
281
282 ;; preparation
283 ;; B:-2 => -2
284 ;; R:-1.5 => -1.5
285 ;; R:-1 => -1
286 ;; B:-0.5 => -0.5
287 ;; B:0 => 0
288 ;; R:0.5 => 0.5
289 ;; B:1 => 1
290 ;; B:2 => 2
291 ;; B:2.5 => 2.5
292 ;; B:3 => 3
293 ;; B:3.5 => 3.5
294 ;; R:4 => 4
295 (i -0.5 -1)
296
297 ;; case 7a deleting black node, which is a left child of its parent,
298 ;; and its sibling is black, and sibling's left child is red.
299 ;; This goes through a nested if-statement in delete_node1()
300 ;; and involves swapping sibling.
301 (test* "deletion case7a" #t (begin (d -2) (c)))
302
303 ;; case 4b. deleting black node, whose sibling is red.
304 (test* "deletion case4b" #t (begin (d 0.5 1) (c)))
305
306 ;; case 3. this goes through parent==NULL stop condition in the
307 ;; loop in delete_node1.
308 ;; B:-1.5 => -1.5
309 ;; R:-0.5 => -0.5
310 ;; B:0 => 0
311 ;; B:2.5 => 2.5
312 ;; R:3 => 3
313 ;; B:3.5 => 3.5
314 ;; R:4 => 4
315 (test* "deletion case3" #t (begin (d 2 -1) (c)))
316
317 ;; preparation
318 ;; R:-4 => -4
319 ;; B:-3 => -3
320 ;; R:-2 => -2
321 ;; R:-1 => -1
322 ;; R:-0.7 => -0.7
323 ;; B:-0.5 => -0.5
324 ;; B:0 => 0
325 ;; B:2.5 => 2.5
326 ;; R:4 => 4
327 (d 3.5 3 -1.5)
328 (i -1 -2 -3 -4 -0.7)
329
330 ;; insertion case 4a.
331 ;; R:-4 => -4
332 ;; B:-3 => -3
333 ;; R:-2 => -2
334 ;; R:-1 => -1
335 ;; R:-0.7 => -0.7
336 ;; B:-0.6 => -0.6
337 ;; R:-0.5 => -0.5
338 ;; B:0 => 0
339 ;; B:2.5 => 2.5
340 ;; R:4 => 4
341 (test* "insertion case4a" #t (begin (i -0.6) (c)))
342
343 ;; preparation
344 ;; B:-2 => -2
345 ;; B:-1 => -1
346 ;; B:-0.7 => -0.7
347 ;; R:-0.6 => -0.6
348 ;; R:-0.5 => -0.5
349 ;; B:0 => 0
350 (d 2.5 4 -3 -4)
351
352 ;; case 4a. the reverse case of 4b.
353 ;; B:-1 => -1
354 ;; R:-0.7 => -0.7
355 ;; B:-0.6 => -0.6
356 ;; R:-0.5 => -0.5
357 ;; B:0 => 0
358 (test* "deletion case4a" #t (begin (d -2) (c)))
359
360 ;; preparation
361 ;; R:-2 => -2
362 ;; B:-1 => -1
363 ;; B:-0.6 => -0.6
364 ;; B:-0.5 => -0.5
365 ;; R:-0.3 => -0.3
366 ;; R:0 => 0
367 ;; R:1 => 1
368 ;; B:2 => 2
369 ;; R:3 => 3
370 (d -0.7)
371 (i -2 2 1 3 -0.3)
372
373 ;; insertion case 4b
374 ;; R:-2 => -2
375 ;; B:-1 => -1
376 ;; B:-0.6 => -0.6
377 ;; R:-0.5 => -0.5
378 ;; B:-0.4 => -0.4
379 ;; R:-0.3 => -0.3
380 ;; R:0 => 0
381 ;; R:1 => 1
382 ;; B:2 => 2
383 ;; R:3 => 3
384 (test* "insertion case4b" #t (begin (i -0.4) (c)))
385 )
386
387 ;; deletion during traversal
388 (let ()
389 (define (make-tm) (alist->tree-map '((a . 1) (b . 2) (c . 3))
390 default-comparator))
391 (test* "deletion during traversal 1" '((b c) (a c) (a b))
392 (map (^s
393 (let1 tm (make-tm)
394 ($ tree-map-fold tm
395 (^[k v _] (when (eq? k s) (tree-map-delete! tm k)))
396 #f)
397 (sort (tree-map-keys tm))))
398 '(a b c)))
399 (test* "deletion during traversal 1 (reverse)" '((b c) (a c) (a b))
400 (map (^s
401 (let1 tm (make-tm)
402 ($ tree-map-fold-right tm
403 (^[k v _] (when (eq? k s) (tree-map-delete! tm k)))
404 #f)
405 (sort (tree-map-keys tm))))
406 '(a b c)))
407 (test* "deletion during traversal 2" '((a) (b) (c))
408 (map (^s
409 (let1 tm (make-tm)
410 ($ tree-map-fold tm
411 (^[k v _] (unless (eq? k s) (tree-map-delete! tm k)))
412 #f)
413 (sort (tree-map-keys tm))))
414 '(a b c)))
415 (test* "deletion during traversal 2 (reverse)" '((a) (b) (c))
416 (map (^s
417 (let1 tm (make-tm)
418 ($ tree-map-fold-right tm
419 (^[k v _] (unless (eq? k s) (tree-map-delete! tm k)))
420 #f)
421 (sort (tree-map-keys tm))))
422 '(a b c)))
423 (test* "deletion during traversal 3" '(() () ())
424 (map (^s
425 (let1 tm (make-tm)
426 (tree-map-fold tm (^[k v _] (tree-map-delete! tm k)) #f)
427 (sort (tree-map-keys tm))))
428 '(a b c)))
429 (test* "deletion during traversal 3 (reverse)" '(() () ())
430 (map (^s
431 (let1 tm (make-tm)
432 (tree-map-fold-right tm (^[k v _] (tree-map-delete! tm k)) #f)
433 (sort (tree-map-keys tm))))
434 '(a b c)))
435 )
436
437 ;;
438 ;; tree-map-{floor|ceiling|predecessor|successor}
439 ;;
440
441 (let* ((alist '(("ai" . "to eat")
442 ("aka" . "but")
443 ("aka`aka" . "to laugh")
444 ("alani" . "orange")
445 ("aloha" . "love")
446 ("aoao" . "page")
447 ("aumoe" . "midnight")))
448 (tree (alist->tree-map alist string=? string<?)))
449
450 (define (get-val key) (if (string? key) (cdr (assoc key alist)) key))
451
452 (define (test-key-val name key expected-key both-proc key-proc val-proc)
453 (test* #"~name (~key)" (list expected-key (get-val expected-key))
454 (receive (k v) (both-proc tree key) (list k v)))
455 (test* #"~|name|-key (~key)" expected-key
456 (key-proc tree key))
457 (test* #"~|name|-value (~key)" (get-val expected-key)
458 (val-proc tree key))
459 (unless expected-key
460 (test* #"~name (~key) / fallback" (list 0 1)
461 (receive (k v) (both-proc tree key 0 1) (list k v)))
462 (test* #"~|name|-key (~key) / fallback" 0
463 (key-proc tree key 0))
464 (test* #"~|name|-value (~key) / fallback" 0
465 (val-proc tree key 0))))
466
467 (define (tester key floor ceil pred succ)
468 (test-key-val "tree-map-floor" key floor
469 tree-map-floor tree-map-floor-key tree-map-floor-value)
470 (test-key-val "tree-map-ceiling" key ceil
471 tree-map-ceiling tree-map-ceiling-key tree-map-ceiling-value)
472 (test-key-val "tree-map-predecessor" key pred
473 tree-map-predecessor tree-map-predecessor-key tree-map-predecessor-value)
474 (test-key-val "tree-map-successor" key succ
475 tree-map-successor tree-map-successor-key tree-map-successor-value))
476
477 (tester "am" "aloha" "aoao" "aloha" "aoao")
478 (tester "aoao" "aoao" "aoao" "aloha" "aumoe")
479 (tester "av" "aumoe" #f "aumoe" #f)
480 (tester "aumoe" "aumoe" "aumoe" "aoao" #f)
481 (tester "aii" "ai" "aka" "ai" "aka")
482 (tester "ai" "ai" "ai" #f "aka")
483 (tester "aa" #f "ai" #f "ai")
484
485 (tree-map-clear! tree)
486
487 (tester "xx" #f #f #f #f)
488 )
489
490 (let1 tree (make-tree-map = <)
491 (test* "tree-map-pop-min! and num-entries" 0
492 (begin
493 (tree-map-put! tree 0 0)
494 (tree-map-pop-min! tree)
495 (tree-map-num-entries tree))))
496
497 (let* ([comparator (make-comparator/compare string? #t
498 (^[a b] (compare (string->number a)
499 (string->number b)))
500 #f)]
501 [tmap (make-tree-map comparator)])
502 (test* "custom comparator" '(("00" . a) ("1" . b) ("10" . c))
503 (begin
504 (dolist [p '(("00" . x) ("1" . t) ("10" . c) ("01" . b)
505 ("000" . y) ("0" . a))]
506 (tree-map-put! tmap (car p) (cdr p)))
507 (tree-map->alist tmap)))
508 (test* "comparator error check" (test-error)
509 (tree-map-put! tmap 3 'z))
510 )
511
512 (let* ([tm1 (alist->tree-map '((1 . "a") (2 . "b") (3 . "c"))
513 default-comparator)]
514 [tm2 (alist->tree-map '((1 . "a") (2 . "b") (3 . "c") (4 . "d"))
515 default-comparator)]
516 [tm3 (alist->tree-map '((2 . "b") (4 . "d"))
517 default-comparator)]
518 [tm4 (alist->tree-map '((3 . "c") (2 . "b") (1 . "a"))
519 default-comparator)]
520 [tm5 (alist->tree-map '((1 . "a") (2 . "b") (3 . "x"))
521 default-comparator)]
522 [tm6 (alist->tree-map '((1 . "a") (2 . "b") (3 . "c"))
523 (make-comparator integer? eqv? < #f))]
524 [tm7 (alist->tree-map '((2 . "B") (1 . "a") (3 . "C"))
525 default-comparator)])
526 (test* "compare-as-sets - same" 0 (tree-map-compare-as-sets tm1 tm1))
527 (test* "compare-as-sets - different comparator"
528 (test-error <error> #/different comparator/)
529 (tree-map-compare-as-sets tm1 tm6))
530 (test* "compare-as-sets <" -1
531 (tree-map-compare-as-sets tm1 tm2))
532 (test* "compare-as-sets >" 1
533 (tree-map-compare-as-sets tm2 tm1))
534 (test* "compare-as-sets <" -1
535 (tree-map-compare-as-sets tm3 tm2))
536 (test* "compare-as-sets >" 1
537 (tree-map-compare-as-sets tm2 tm3))
538 (test* "compare-as-sets =" 0
539 (tree-map-compare-as-sets tm1 tm4))
540 (test* "compare-as-sets - unorderable" (test-error <error> #/can't be ordered/)
541 (tree-map-compare-as-sets tm1 tm5))
542 (test* "compare-as-sets - unorderable, fallback" #f
543 (tree-map-compare-as-sets tm1 tm5 equal? #f))
544 (test* "compare-as-sets - custom value=?" #f
545 (tree-map-compare-as-sets tm1 tm7 string=? #f))
546 (test* "compare-as-sets - custom value=?" 0
547 (tree-map-compare-as-sets tm1 tm7 string-ci=?))
548
549 (test* "compare-as-sequences - same" 0
550 (tree-map-compare-as-sequences tm1 tm1))
551 (test* "compare-as-sequences - different comparator"
552 (test-error <error> #/different comparator/)
553 (tree-map-compare-as-sequences tm1 tm6))
554 (test* "compare-as-sequences tm1 < tm2" -1
555 (tree-map-compare-as-sequences tm1 tm2))
556 (test* "compare-as-sequences tm2 > tm1" 1
557 (tree-map-compare-as-sequences tm2 tm1))
558 (test* "compare-as-sequences tm1 < tm3" -1
559 (tree-map-compare-as-sequences tm1 tm3))
560 (test* "compare-as-sequences tm4 = tm1" 0
561 (tree-map-compare-as-sequences tm4 tm1))
562 (test* "compare-as-sequences tm1 < tm5" -1
563 (tree-map-compare-as-sequences tm1 tm5))
564 (test* "compare-as-sequences tm1 > tm7" 1
565 (tree-map-compare-as-sequences tm1 tm7))
566 (test* "compare-as-sequences tm1 = tm7" 0
567 (tree-map-compare-as-sequences tm1 tm7 string-ci-comparator))
568 )
569
570 ;; key range generator
571 (let ((tm (alist->tree-map '((0 . a) (1 . b) (2 . c) (3 . d) (4 . e)
572 (5 . f))
573 default-comparator)))
574 ;; avoid depending on gauche.generator
575 (define (->list gen)
576 (let loop ((r '()))
577 (let1 v (gen)
578 (if (eof-object? v)
579 (reverse r)
580 (loop (cons v r))))))
581
582 (test* "key-range generator (no limits)"
583 '((0 . a) (1 . b) (2 . c) (3 . d) (4 . e) (5 . f))
584 (->list (tree-map->generator/key-range tm)))
585 (test* "key-range generator (no limits, reverse)"
586 '((5 . f) (4 . e) (3 . d) (2 . c) (1 . b) (0 . a))
587 (->list (tree-map->generator/key-range tm :descending #t)))
588 (test* "key-range generator (> 1)"
589 '((2 . c) (3 . d) (4 . e) (5 . f))
590 (->list (tree-map->generator/key-range tm :> 1)))
591 (test* "key-range generator (> 1, reverse)"
592 '((5 . f) (4 . e) (3 . d) (2 . c))
593 (->list (tree-map->generator/key-range tm :> 1 :descending #t)))
594 (test* "key-range generator (>= 1)"
595 '((1 . b) (2 . c) (3 . d) (4 . e) (5 . f))
596 (->list (tree-map->generator/key-range tm :>= 1)))
597 (test* "key-range generator (>= 1, reverse)"
598 '((5 . f) (4 . e) (3 . d) (2 . c) (1 . b))
599 (->list (tree-map->generator/key-range tm :>= 1 :descending #t)))
600 (test* "key-range generator (< 4)"
601 '((0 . a) (1 . b) (2 . c) (3 . d))
602 (->list (tree-map->generator/key-range tm :< 4)))
603 (test* "key-range generator (< 4, reverse)"
604 '((3 . d) (2 . c) (1 . b) (0 . a))
605 (->list (tree-map->generator/key-range tm :< 4 :descending #t)))
606 (test* "key-range generator (<= 4)"
607 '((0 . a) (1 . b) (2 . c) (3 . d) (4 . e))
608 (->list (tree-map->generator/key-range tm :<= 4)))
609 (test* "key-range generator (<= 4, reverse)"
610 '((4 . e) (3 . d) (2 . c) (1 . b) (0 . a))
611 (->list (tree-map->generator/key-range tm :<= 4 :descending #t)))
612 (test* "key-range generator (> 1, <= 4)"
613 '((2 . c) (3 . d) (4 . e))
614 (->list (tree-map->generator/key-range tm :<= 4 :> 1)))
615 (test* "key-range generator (> 1, <= 4, reverse)"
616 '((4 . e) (3 . d) (2 . c))
617 (->list (tree-map->generator/key-range tm :<= 4 :> 1 :descending #t)))
618 (test* "key-range generator (>= 1, < 4)"
619 '((1 . b) (2 . c) (3 . d))
620 (->list (tree-map->generator/key-range tm :< 4 :>= 1)))
621 (test* "key-range generator (>= 1, < 4, reverse)"
622 '((3 . d) (2 . c) (1 . b))
623 (->list (tree-map->generator/key-range tm :< 4 :>= 1 :descending #t)))
624 (test* "key-range generator (> 5)"
625 '()
626 (->list (tree-map->generator/key-range tm :> 5)))
627 (test* "key-range generator (> 5, descending)"
628 '()
629 (->list (tree-map->generator/key-range tm :> 5 :descending #t)))
630 (test* "key-range generator (< 0)"
631 '()
632 (->list (tree-map->generator/key-range tm :< 0)))
633 (test* "key-range generator (< 0, descending)"
634 '()
635 (->list (tree-map->generator/key-range tm :< 0 :descending #t)))
636 (test* "key-range generator (> 4, < 4)"
637 '()
638 (->list (tree-map->generator/key-range tm :< 4 :> 4)))
639 )
640
641 (test-end)