Debian Codegraph @

lib/srfi/217.scm

raw
1 ;;;
2 ;;; SRFI-217 - Integer sets
3 ;;;
4 ;;; Copyright (c) 2021-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (define-module srfi.217
35 (use gauche.record)
36 (use gauche.sequence)
37 (use gauche.generator)
38 (use scheme.list)
39 (use util.match)
40 (use srfi.42)
41 (export iset iset-unfold make-range-iset
42 iset? iset-contains? iset-empty? iset-disjoint?
43 iset-member iset-min iset-max
44 iset-adjoin iset-adjoin! iset-delete iset-delete!
45 iset-delete-all iset-delete-all! iset-search iset-search!
46 iset-delete-min iset-delete-min! iset-delete-max iset-delete-max!
47 iset-size iset-find iset-count iset-any? iset-every?
48 iset-map iset-for-each iset-fold iset-fold-right
49 iset-filter iset-filter! iset-remove iset-remove!
50 iset-partition iset-partition!
51 iset-copy iset->list list->iset list->iset!
52 iset=? iset<? iset>? iset<=? iset>=?
53 iset-union iset-intersection iset-difference iset-xor
54 iset-union! iset-intersection! iset-difference! iset-xor!
55 iset-open-interval iset-closed-interval
56 iset-open-closed-interval iset-closed-open-interval
57 isubset= isubset< isubset<= isubset> isubset>=)
58 )
59 (select-module srfi.217)
60
61 ;; Internally, <iset> has a persistent/transient distinction. Persistent
62 ;; iset is an ordinary functional structure. Transient iset can be passed
63 ;; to linear-updating procedures, given that the caller will never share the
64 ;; reference to it elsewhere, and the linear-updating procedure may mutate it.
65 ;;
66 ;; If a functional procedure receives a transient iset, or a linear-updating
67 ;; procedure gets a persistent iset, the structure is always copied.
68 ;; Cf. http://blog.practical-scheme.net/gauche/20210531-functional-and-linear-update
69 ;;
70 ;; A functional procedure always returns a persistent iset. A linear-updating
71 ;; procedure returns a transient iset, except when it is an alias of
72 ;; functional version.
73 ;;
74 ;; The distinction is purely internal; the users don't need to worry about it,
75 ;; and they can treat functional version as if it always return a copy, so
76 ;; that it is safe to pass it to the linear updating version as long as
77 ;; she don't keep explicit reference to it.
78
79 (define-record-type <iset> %make-iset-int iset?
80 (transient? %iset-transient? %iset-transient?-set!)
81 (size %iset-size %iset-size-set!) ;; this is lazily computed
82 (tmap iset-tmap))
83
84 (define (%make-iset :optional (transient? #t) (tmap #f))
85 (%make-iset-int transient?
86 #f ;; size to be computed lazily
87 (or tmap (make-tree-map = <))))
88
89 ;; If you modify internal tree map, call this to invalidate size cache.
90 ;; returns iset itself.
91 (define (%iset-touch! iset)
92 (%iset-size-set! iset #f)
93 iset)
94
95 (define-method write-object ((iset <iset>) port)
96 (format port "#<iset ~a entrie(s)>" (iset-size iset)))
97
98 (define (%iset->persistent iset)
99 (if (%iset-transient? iset)
100 (%make-iset #f (tree-map-copy (iset-tmap iset)))
101 iset))
102
103 (define (%iset->transient iset)
104 (if (%iset-transient? iset)
105 iset
106 (%make-iset #t (tree-map-copy (iset-tmap iset)))))
107
108 (define (%iset-make-persistent! iset) ; only used in constructors
109 (%iset-transient?-set! iset #f))
110
111 ;;;
112 ;;; Constructors
113 ;;;
114
115 (define (iset . args) (list->iset args))
116
117 (define (list->iset args)
118 (let1 tmap (make-tree-map = <)
119 (let loop ([p (group-contiguous-sequence (sort args <) :squeeze #t)])
120 (match p
121 [() (%make-iset #f tmap)]
122 [((s e) . rest) (tree-map-put! tmap s e) (loop rest)]
123 [((v) . rest) (tree-map-put! tmap v v) (loop rest)]))))
124
125 (define (iset-unfold p f g seed)
126 (list->iset (unfold p f g seed)))
127
128 (define (make-range-iset start end :optional (step 1))
129 (if (= step 1)
130 (%make-iset #f (alist->tree-map `((,start . ,(- end 1))) = <))
131 (list->iset (lrange start end step))))
132
133 ;;;
134 ;;; Predicates
135 ;;;
136
137 ;; iset? - above
138
139 (define (%tmap-contains? tmap k)
140 (receive (s e) (tree-map-floor tmap k)
141 (and s (<= k e))))
142
143 (define (iset-contains? iset k)
144 (assume-type iset <iset>)
145 (%tmap-contains? (iset-tmap iset) k))
146
147 (define (iset-empty? iset) (tree-map-empty? (iset-tmap iset)))
148
149 (define (iset-disjoint? iset1 iset2)
150 (assume-type iset1 <iset>)
151 (assume-type iset2 <iset>)
152 (let ([g1 (x->generator (iset-tmap iset1))]
153 [g2 (x->generator (iset-tmap iset2))])
154 (let loop ([p1 (g1)] [p2 (g2)])
155 (cond [(eof-object? p1)]
156 [(eof-object? p2)]
157 [(<= (car p1) (car p2))
158 (if (< (cdr p1) (car p2))
159 (loop (g1) p2)
160 #f)]
161 [(< (car p2) (car p1))
162 (if (< (cdr p2) (car p1))
163 (loop p1 (g2))
164 #f)]))))
165
166 ;;;
167 ;;; Accessors
168 ;;;
169
170 (define (iset-member iset k fallback)
171 (if (iset-contains? iset k)
172 k
173 fallback))
174
175 (define (iset-min iset)
176 (assume-type iset <iset>)
177 (match (tree-map-min (iset-tmap iset))
178 [#f #f]
179 [(s . _) s]))
180
181 (define (iset-max iset)
182 (assume-type iset <iset>)
183 (match (tree-map-max (iset-tmap iset))
184 [#f #f]
185 [(_ . e) e]))
186
187 ;;;
188 ;;; Updaters
189 ;;;
190
191 ;; The 'noclobber' thing is to avoid unecessary copying of persistent iset.
192
193 (define (%adjoin-1! k tmap maybe-copy)
194 (receive (s e) (tree-map-floor tmap k)
195 (cond [(not s) (rlet1 tmap2 (maybe-copy tmap)
196 (tree-map-put! tmap2 k k))]
197 [(<= k e) tmap] ; subsumed
198 [else (receive (s2 e2) (tree-map-floor tmap (+ k 1))
199 (rlet1 tmap2 (maybe-copy tmap)
200 (if (or (not s2) (= s s2))
201 (if (= (+ e 1) k)
202 (tree-map-put! tmap2 s k) ; extend
203 (tree-map-put! tmap2 k k)) ; lone
204 (if (= (+ e 1) k)
205 (begin ; k connects two spans
206 (tree-map-delete! tmap2 s2)
207 (tree-map-put! tmap2 s e2))
208 (tree-map-put! tmap2 k k)))))])))
209
210 (define (iset-adjoin iset k . ks)
211 (define (noclobber tmap)
212 (if (eq? tmap (iset-tmap iset))
213 (tree-map-copy tmap)
214 tmap))
215 (let* ([input (%iset->persistent iset)]
216 [tm (if (null? ks)
217 (%adjoin-1! k (iset-tmap input) noclobber)
218 (fold (cut %adjoin-1! <> <> noclobber)
219 (%adjoin-1! k (iset-tmap input) noclobber) ks))])
220 (if (eq? tm (iset-tmap iset))
221 iset
222 (%make-iset #f tm))))
223
224 (define (iset-adjoin! iset k . ks)
225 (let1 input (%iset->transient iset)
226 (%adjoin-1! k (iset-tmap input) identity)
227 (dolist [k ks] (%adjoin-1! k (iset-tmap input) identity))
228 (%iset-touch! input)))
229
230 (define (%delete-1! k tmap maybe-copy)
231 (receive (s e) (tree-map-floor tmap k)
232 (if s
233 (cond [(= k s) (rlet1 tmap2 (maybe-copy tmap)
234 (tree-map-delete! tmap2 k)
235 (unless (= k e) (tree-map-put! tmap2 (+ s 1) e)))]
236 [(< k e) (rlet1 tmap2 (maybe-copy tmap)
237 (tree-map-put! tmap2 s (- k 1))
238 (tree-map-put! tmap2 (+ k 1) e))]
239 [(= k e) (rlet1 tmap2 (maybe-copy tmap)
240 (tree-map-put! tmap2 s (- k 1)))]
241 [else tmap])
242 tmap)))
243
244 (define (iset-delete iset k . ks)
245 (define (noclobber tmap)
246 (if (eq? tmap (iset-tmap iset))
247 (tree-map-copy tmap)
248 tmap))
249 (let* ([input (%iset->persistent iset)]
250 [tm (let loop ([tm (%delete-1! k (iset-tmap input) noclobber)]
251 [ks ks])
252 (if (null? ks)
253 tm
254 (loop (%delete-1! (car ks) tm noclobber) (cdr ks))))])
255 (if (eq? tm (iset-tmap iset))
256 iset
257 (%make-iset #f tm))))
258
259 (define (iset-delete! iset k . ks)
260 (let1 input (%iset->transient iset)
261 (%delete-1! k (iset-tmap input) identity)
262 (dolist [k ks] (%delete-1! k (iset-tmap input) identity))
263 (%iset-touch! input)))
264
265 (define (iset-delete-all iset ks)
266 (if (null? ks)
267 (%iset->persistent iset)
268 (apply iset-delete iset ks)))
269
270 (define (iset-delete-all! iset ks)
271 (if (null? ks)
272 (%iset->transient iset)
273 (apply iset-delete! iset ks)))
274
275 (define (iset-delete-min iset)
276 (match (tree-map-min (iset-tmap iset))
277 [#f (error "iset is empty:" iset)]
278 [(s . e)
279 ;; we copy the tree anyway, so it doesn't matter if input is transient
280 ;; or persistent.
281 (let1 tmap (tree-map-copy (iset-tmap iset))
282 (tree-map-delete! tmap s)
283 (when (< s e)
284 (tree-map-put! tmap (+ s 1) e))
285 (values s (%make-iset #f tmap)))]))
286
287 (define (iset-delete-min! iset)
288 (match (tree-map-min (iset-tmap iset))
289 [#f (error "iset is empty:" iset)]
290 [(s . e) (let* ([input (%iset->transient iset)]
291 [tmap (iset-tmap input)])
292 (tree-map-delete! tmap s)
293 (when (< s e)
294 (tree-map-put! tmap (+ s 1) e))
295 (values s (%iset-touch! input)))]))
296
297 (define (iset-delete-max iset)
298 (match (tree-map-max (iset-tmap iset))
299 [#f (error "iset is empty:" iset)]
300 [(s . e)
301 ;; we copy the tree anyway, so it doesn't matter if input is transient
302 ;; or persistent.
303 (let1 tmap (tree-map-copy (iset-tmap iset))
304 (if (= s e)
305 (tree-map-delete! tmap s)
306 (tree-map-put! tmap s (- e 1)))
307 (values e (%make-iset #f tmap)))]))
308
309 (define (iset-delete-max! iset)
310 (match (tree-map-max (iset-tmap iset))
311 [#f (error "iset is empty:" iset)]
312 [(s . e) (let* ([input (%iset->transient iset)]
313 [tmap (iset-tmap input)])
314 (if (= s e)
315 (tree-map-delete! tmap s)
316 (tree-map-put! tmap s (- e 1)))
317 (values e (%iset-touch! iset)))]))
318
319 (define (%iset-search iset k failure success update remove insert)
320 (receive (s e) (tree-map-floor (iset-tmap iset) k)
321 (if (and s (<= k e))
322 (success k update remove)
323 (failure insert (^[result] (values iset result))))))
324
325 (define (iset-search iset k failure success)
326 (define (update new-k result)
327 (values (iset-adjoin! (iset-delete iset k) new-k) result))
328 (define (remove result)
329 (values (iset-delete iset k) result))
330 (define (insert result)
331 (values (iset-adjoin iset k) result))
332 (%iset-search iset k failure success update remove insert))
333
334 (define (iset-search! iset k failure success)
335 (define (update new-k result)
336 (values (iset-adjoin! (iset-delete! iset k) new-k) result))
337 (define (remove result)
338 (values (iset-delete! iset k) result))
339 (define (insert result)
340 (values (iset-adjoin! iset k) result))
341 (%iset-search iset k failure success update remove insert))
342
343 ;;;
344 ;;; The whole set
345 ;;;
346
347 (define (iset-size iset)
348 (or (%iset-size iset)
349 (rlet1 s (tree-map-fold (iset-tmap iset)
350 (^[s e count] (+ 1 (- e s) count))
351 0)
352 (%iset-size-set! iset s))))
353
354 (define (iset-find pred iset failure)
355 (let/cc return
356 (tree-map-for-each (iset-tmap iset)
357 (^[s e]
358 (do-ec (: k s (+ e 1))
359 (when (pred k) (return k)))))
360 (failure)))
361
362 (define (iset-count pred iset)
363 (rlet1 cnt 0
364 (tree-map-for-each (iset-tmap iset)
365 (^[s e]
366 (do-ec (: k s (+ e 1))
367 (when (pred k) (inc! cnt)))))))
368
369 (define (iset-any? pred iset)
370 (boolean (iset-find pred iset (constantly #f))))
371
372 (define (iset-every? pred iset)
373 (not (iset-find (complement pred) iset (constantly #f))))
374
375 ;;;
376 ;;; Mapping and folding
377 ;;;
378
379 (define (iset-map proc iset)
380 (rlet1 r (%make-iset)
381 (tree-map-for-each (iset-tmap iset)
382 (^[s e]
383 (do-ec (: k s (+ e 1))
384 (set! r (iset-adjoin! r (proc k))))))
385 (%iset-make-persistent! r)))
386
387 (define (iset-for-each proc iset)
388 (tree-map-for-each (iset-tmap iset)
389 (^[s e]
390 (do-ec (: k s (+ e 1))
391 (proc k)))))
392
393 (define (iset-fold kons knil iset)
394 (tree-map-fold (iset-tmap iset)
395 (^[s e seed]
396 (fold-ec seed (: k s (+ e 1)) k kons))
397 knil))
398
399 (define (iset-fold-right kons knil iset)
400 (tree-map-fold-right (iset-tmap iset)
401 (^[s e seed]
402 (fold-ec seed (: k e (- s 1) -1) k kons))
403 knil))
404
405 (define (iset-filter pred iset)
406 (rlet1 r (%make-iset)
407 (iset-for-each (^k (when (pred k) (set! r (iset-adjoin! r k))))
408 iset)
409 (%iset-make-persistent! r)))
410
411 ;; we don't have an efficient way to modify the internal map in-place.
412 (define (iset-filter! pred iset) (iset-filter pred iset))
413
414 (define (iset-remove pred iset)
415 (rlet1 r (%make-iset)
416 (iset-for-each (^k (unless (pred k) (set! r (iset-adjoin! r k))))
417 iset)
418 (%iset-make-persistent! r)))
419
420 (define (iset-remove! pred iset) (iset-remove pred iset))
421
422 (define (iset-partition pred iset)
423 (let ([in (%make-iset)]
424 [out (%make-iset)])
425 (iset-for-each (^k (if (pred k)
426 (set! in (iset-adjoin! in k))
427 (set! out (iset-adjoin! out k))))
428 iset)
429 (%iset-make-persistent! in)
430 (%iset-make-persistent! out)
431 (values in out)))
432
433 (define (iset-partition! pred iset) (iset-partition pred iset))
434
435 ;;;
436 ;;; Copying and conversion
437 ;;;
438
439 (define (iset-copy iset)
440 (%make-iset (%iset-transient? iset) (tree-map-copy (iset-tmap iset))))
441
442 (define (iset->list iset)
443 (iset-fold-right cons '() iset))
444
445 (define (list->iset! iset ks)
446 (fold (^[k iset] (iset-adjoin! iset k)) iset ks))
447
448 ;;;
449 ;;; Subsets
450 ;;;
451
452 (define (iset=? iset1 iset2 . isets)
453 (and (equal? (iset-tmap iset1) (iset-tmap iset2))
454 (or (null? isets)
455 (apply iset=? iset2 isets))))
456
457 (define (iset<? iset1 iset2 . isets)
458 (and (< (iset-size iset1) (iset-size iset2))
459 (iset-every? (cut iset-contains? iset2 <>) iset1)
460 (or (null? isets)
461 (apply iset<? iset2 isets))))
462
463 (define (iset>? iset1 iset2 . isets)
464 (and (> (iset-size iset1) (iset-size iset2))
465 (iset-every? (cut iset-contains? iset1 <>) iset2)
466 (or (null? isets)
467 (apply iset>? iset2 isets))))
468
469 (define (iset<=? iset1 iset2 . isets)
470 (and (iset-every? (cut iset-contains? iset2 <>) iset1)
471 (or (null? isets)
472 (apply iset<=? iset2 isets))))
473
474 (define (iset>=? iset1 iset2 . isets)
475 (and (iset-every? (cut iset-contains? iset1 <>) iset2)
476 (or (null? isets)
477 (apply iset>=? iset2 isets))))
478
479 ;;;
480 ;;; Set theory operations
481 ;;;
482
483 (define (%union-2! tmap1 tmap2 maybe-copy)
484 (tree-map-fold tmap2
485 (^[s e rtmap]
486 (do-ec [: k s (+ e 1)]
487 (set! rtmap (%adjoin-1! k rtmap maybe-copy)))
488 rtmap)
489 tmap1))
490
491 (define (iset-union iset1 iset2 . isets)
492 (define (noclobber tmap)
493 (if (eq? tmap (iset-tmap iset1))
494 (tree-map-copy tmap)
495 tmap))
496 (define input (%iset->persistent iset1))
497 (let loop ([tmap (%union-2! (iset-tmap input) (iset-tmap iset2) noclobber)]
498 [isets isets])
499 (if (null? isets)
500 (if (eq? tmap (iset-tmap iset1))
501 iset1
502 (%make-iset #f tmap))
503 (loop (%union-2! tmap (iset-tmap (car isets)) noclobber)
504 (cdr isets)))))
505
506 (define (iset-union! iset1 iset2 . isets)
507 (define input (%iset->transient iset1))
508 (let loop ([tmap (%union-2! (iset-tmap input) (iset-tmap iset2) identity)]
509 [isets isets])
510 (if (null? isets)
511 (%iset-touch! input)
512 (loop (%union-2! tmap (iset-tmap (car isets)) identity)
513 (cdr isets)))))
514
515 (define (%diff-2! tmap1 tmap2 maybe-copy)
516 (tree-map-fold tmap2
517 (^[s e rtmap]
518 (do-ec [: k s (+ e 1)]
519 (set! rtmap (%delete-1! k rtmap maybe-copy)))
520 rtmap)
521 tmap1))
522
523 (define (iset-difference iset1 iset2 . isets)
524 (define (noclobber tmap)
525 (if (eq? tmap (iset-tmap iset1))
526 (tree-map-copy tmap)
527 tmap))
528 (define input (%iset->persistent iset1))
529 (let loop ([tmap (%diff-2! (iset-tmap input) (iset-tmap iset2) noclobber)]
530 [isets isets])
531 (if (null? isets)
532 (if (eq? tmap (iset-tmap iset1))
533 iset1
534 (%make-iset #f tmap))
535 (loop (%diff-2! tmap (iset-tmap (car isets)) noclobber)
536 (cdr isets)))))
537
538 (define (iset-difference! iset1 iset2 . isets)
539 (define input (%iset->transient iset1))
540 (let loop ([tmap (%diff-2! (iset-tmap input) (iset-tmap iset2) identity)]
541 [isets isets])
542 (if (null? isets)
543 (%iset-touch! input)
544 (loop (%diff-2! tmap (iset-tmap (car isets)) identity)
545 (cdr isets)))))
546
547 ;; For xor and intersect, it's easier to build a new imap.
548 ;; We might be able to do better when operating on more than two sets.
549
550 (define (%xor-2 tmap1 tmap2)
551 (rlet1 rmap (tree-map-copy tmap1)
552 (tree-map-for-each tmap2
553 (^[s e]
554 (do-ec (: k s (+ e 1))
555 (if (%tmap-contains? tmap1 k)
556 (%delete-1! k rmap identity)
557 (%adjoin-1! k rmap identity)))))))
558
559 (define (%xor-n transient? iset1 iset2 . isets)
560 (let loop ([tmap (%xor-2 (iset-tmap iset1) (iset-tmap iset2))]
561 [isets isets])
562 (if (null? isets)
563 (%make-iset transient? tmap)
564 (loop (%xor-2 tmap (iset-tmap (car isets))) (cdr isets)))))
565
566 (define (iset-xor iset1 iset2 . isets)
567 (apply %xor-n #f iset1 iset2 isets))
568
569 (define (iset-xor! iset1 iset2 . isets)
570 (apply %xor-n #t iset1 iset2 isets))
571
572 (define (%intersect-2 tmap1 tmap2)
573 (rlet1 rmap (make-tree-map = <)
574 (tree-map-for-each tmap2
575 (^[s e]
576 (do-ec (: k s (+ e 1))
577 (when (%tmap-contains? tmap1 k)
578 (%adjoin-1! k rmap identity)))))))
579
580 (define (%intersect-n transient? iset1 iset2 . isets)
581 (let loop ([tmap (%intersect-2 (iset-tmap iset1) (iset-tmap iset2))]
582 [isets isets])
583 (if (null? isets)
584 (%make-iset transient? tmap)
585 (loop (%intersect-2 tmap (iset-tmap (car isets))) (cdr isets)))))
586
587 (define (iset-intersection iset1 iset2 . isets)
588 (apply %intersect-n #f iset1 iset2 isets))
589
590 (define (iset-intersection! iset1 iset2 . isets)
591 (apply %intersect-n #t iset1 iset2 isets))
592
593 (define (isubset= iset0 k)
594 (if (iset-contains? iset0 k)
595 (if (= (iset-size iset0) 1)
596 (%iset->persistent iset0)
597 (iset k))
598 (iset)))
599
600 (define (isubset< iset0 k)
601 (let1 tmap (iset-tmap iset0)
602 (match (tree-map-max tmap)
603 [#f (%iset->persistent iset0)] ;empty set
604 [(s . e)
605 (if (<= e k)
606 (%iset->persistent iset0) ;no change
607 (let ([rmap (make-tree-map = <)]
608 [g (x->generator tmap)])
609 (let loop ()
610 (match-let1 (s . e) (g)
611 (cond
612 [(< e k) (tree-map-put! rmap s e) (loop)]
613 [(<= k s) (%make-iset #f rmap)]
614 [else (tree-map-put! rmap s (- k 1))
615 (%make-iset #f rmap)])))))])))
616
617 (define (isubset<= iset0 k) (isubset< iset0 (+ k 1)))
618
619 (define (isubset>= iset0 k)
620 (let1 tmap (iset-tmap iset0)
621 (match (tree-map-min tmap)
622 [#f (%iset->persistent iset0)] ;empty set
623 [(s . e)
624 (if (<= k s)
625 (%iset->persistent iset0) ;no change
626 (let ([rmap (make-tree-map = <)]
627 [g (x->generator tmap)])
628 (let loop ()
629 (match (g)
630 [(s . e)
631 (cond
632 [(< e k) (loop)]
633 [(<= k s) (tree-map-put! rmap s e) (loop)]
634 [else (tree-map-put! rmap k e) (loop)])]
635 [else (%make-iset #f rmap)]))))])))
636
637 (define (isubset> iset0 k) (isubset>= iset0 (+ k 1)))
638
639
640 (define (iset-closed-interval iset0 lo hi)
641 (let1 tmap (iset-tmap iset0)
642 (match (tree-map-min tmap)
643 [#f (%iset->persistent iset0)]
644 [(s . e)
645 (if (< hi s)
646 (iset) ;empty
647 (match-let1 (sz . ez) (tree-map-max tmap)
648 (if (< ez lo)
649 (iset) ;empty
650 (let ([rmap (make-tree-map = <)]
651 [g (x->generator tmap)])
652 (let loop ()
653 (match (g)
654 [(s . e)
655 (cond
656 [(< e lo) (loop)] ;non overwrapping
657 [(< hi s) (%make-iset #f rmap)] ;past range
658 [(< lo s) (if (< e hi)
659 (begin (tree-map-put! rmap s e) (loop))
660 (begin (tree-map-put! rmap s hi)
661 (%make-iset #f rmap)))]
662 [else (if (< e hi)
663 (begin (tree-map-put! rmap lo e) (loop))
664 (begin (tree-map-put! rmap lo hi)
665 (%make-iset #f rmap)))])]))))))])))
666
667 (define (iset-open-closed-interval iset0 lo hi)
668 (iset-closed-interval iset0 (+ lo 1) hi))
669 (define (iset-closed-open-interval iset0 lo hi)
670 (iset-closed-interval iset0 lo (- hi 1)))
671 (define (iset-open-interval iset0 lo hi)
672 (iset-closed-interval iset0 (+ lo 1) (- hi 1)))