Debian Codegraph @

lib/scheme/mapping.scm

raw
1 ;;;
2 ;;; scheme.mapping - mappings (R7RS Tangerine)
3 ;;;
4 ;;; Copyright (c) 2017-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 ;; Originally SRFI-146
35 (define-module scheme.mapping
36 (export mapping mapping-unfold mapping/ordered mapping-unfold/ordered
37 mapping? mapping-contains? mapping-empty? mapping-disjoint?
38 mapping-ref mapping-ref/default
39 mapping-key-comparator
40
41 mapping-set mapping-set!
42 mapping-adjoin mapping-adjoin!
43 mapping-replace mapping-replace!
44 mapping-delete mapping-delete!
45 mapping-delete-all mapping-delete-all!
46 mapping-intern mapping-intern!
47 mapping-update mapping-update!
48 mapping-update/default mapping-update!/default
49 mapping-pop mapping-pop!
50 mapping-search mapping-search!
51 mapping-size mapping-find mapping-count
52 mapping-any? mapping-every?
53 mapping-keys mapping-values mapping-entries
54 mapping-map mapping-map->list mapping-for-each mapping-fold
55 mapping-filter mapping-filter! mapping-remove mapping-remove!
56 mapping-partition mapping-partition!
57 mapping-copy mapping->alist alist->mapping alist->mapping!
58 alist->mapping/ordered alist->mapping/ordered!
59
60 mapping=? mapping<? mapping>? mapping<=? mapping>=?
61 mapping-union mapping-intersection mapping-difference mapping-xor
62 mapping-union! mapping-intersection! mapping-difference! mapping-xor!
63 make-mapping-comparator
64 mapping-comparator
65 mapping-min-key mapping-max-key
66 mapping-min-value mapping-max-value
67 mapping-key-predecessor mapping-key-successor
68 mapping-range= mapping-range< mapping-range>
69 mapping-range<= mapping-range>=
70 mapping-range=! mapping-range<! mapping-range>!
71 mapping-range<=! mapping-range>=!
72 mapping-split
73 mapping-catenate mapping-catenate!
74 mapping-map/monotone mapping-map/monotone!
75 mapping-fold/reverse
76
77 ;; builtin
78 comparator?))
79 (select-module scheme.mapping)
80
81 ;; We provide <tree-map> as mapping.
82 (define <mapping> <tree-map>)
83 (define (mapping? m) (is-a? m <mapping>))
84
85 (define-syntax dopairs
86 (syntax-rules ()
87 [(_ [k v lis] body ...)
88 (let1 lis lis
89 (do ([xs lis (cddr xs)])
90 [(null? xs)]
91 (when (null? (cdr xs))
92 (error "mapping kv-list isn't even:" lis))
93 (let ([k (car xs)]
94 [v (cadr xs)])
95 body ...)))]))
96
97 (define (mapping comparator . args)
98 (assume-type comparator <comparator>)
99 (rlet1 m (make-tree-map comparator)
100 (dopairs [k v args] (tree-map-adjoin! m k v))))
101
102 (define (mapping-unfold p f g seed comparator)
103 (assume-type comparator <comparator>)
104 (rlet1 m (make-tree-map comparator)
105 (do ([seed seed (g seed)])
106 [(p seed) m]
107 (receive (k v) (f seed)
108 (tree-map-adjoin! m k v)))))
109
110 ;; We don't take advantage of, neither check, the ordered keys.
111 (define mapping/ordered mapping)
112 (define mapping-unfold/ordered mapping-unfold)
113
114 (define (mapping-empty? m) (tree-map-empty? m))
115 (define (mapping-contains? m key) (tree-map-exists? m key))
116 (define (mapping-disjoint? m1 m2)
117 (assume-type m1 <mapping>)
118 (assume-type m2 <mapping>)
119 (tree-map-seek m1 (^[k _] (tree-map-exists? m2 k))
120 (^[] #t)
121 (^[r k v] #f)))
122
123 (define %unique (list #f))
124
125 (define (mapping-ref m key
126 :optional
127 (failure #f)
128 (success identity))
129 (assume-type m <mapping>)
130 (if failure
131 (let1 v (tree-map-get m key %unique)
132 (if (eq? v %unique)
133 (failure)
134 (success v)))
135 (success (tree-map-get m key)))) ;let tree-map-get handle failure
136
137 (define (mapping-ref/default m key default)
138 (assume-type m <mapping>)
139 (tree-map-get m key default))
140
141 (define (mapping-key-comparator m) (tree-map-comparator m))
142
143 (define (mapping-set m . args)
144 (if (null? args)
145 (begin
146 (assume-type m <mapping>)
147 m) ;shortcut
148 (apply mapping-set! (mapping-copy m) args)))
149
150 (define (mapping-set! m . args)
151 (assume-type m <mapping>)
152 (dopairs [k v args] (tree-map-put! m k v))
153 m)
154
155 (define (mapping-adjoin m . args)
156 (if (null? args)
157 (begin
158 (assume-type m <mapping>)
159 m) ;shortcut
160 (apply mapping-adjoin! (tree-map-copy m) args)))
161
162 (define (mapping-adjoin! m . args)
163 (assume-type m <mapping>)
164 (dopairs [k v args] (tree-map-adjoin! m k v))
165 m)
166
167 (define (mapping-replace m k v)
168 (assume-type m <mapping>)
169 (if (tree-map-exists? m k)
170 (mapping-replace! (tree-map-copy m) k v)
171 m))
172
173 (define (mapping-replace! m k v)
174 (assume-type m <mapping>)
175 (tree-map-replace! m k v)
176 m)
177
178 (define (mapping-delete m . keys) (mapping-delete-all m keys))
179 (define (mapping-delete! m . keys) (mapping-delete-all! m keys))
180
181 (define (mapping-delete-all m keys)
182 (assume-type m <mapping>)
183 ;; We delay copy until we actually modify the map.
184 (fold (^[k t]
185 (if (tree-map-exists? t k)
186 (rlet1 t (if (eq? t m) (tree-map-copy m) t)
187 (tree-map-delete! t k))
188 t))
189 m keys))
190
191 (define (mapping-delete-all! m keys)
192 (assume-type m <mapping>)
193 (dolist [k keys] (tree-map-delete! m k))
194 m)
195
196 (define (mapping-intern m k newval)
197 (assume-type m <mapping>)
198 (let1 v (tree-map-get m k %unique)
199 (if (eq? v %unique)
200 (let ([t (tree-map-copy m)]
201 [v (newval)])
202 (tree-map-put! t k v)
203 (values t v))
204 (values m v))))
205
206 (define (mapping-intern! m k newval)
207 (assume-type m <mapping>)
208 (let1 v (tree-map-get m k %unique)
209 (if (eq? v %unique)
210 (let1 v (newval)
211 (tree-map-put! m k v)
212 (values m v))
213 (values m v))))
214
215 (define (mapping-update m k updater
216 :optional
217 (failure (^[] (errorf "~s doesn't have a key ~s" m k)))
218 (success identity))
219 (assume-type m <mapping>)
220 ;; We delay copy until we actually modify the map.
221 (let* ([v (tree-map-get m k %unique)]
222 [v1 (if (eq? v %unique)
223 (updater (failure))
224 (updater (success v)))])
225 (if (eq? v v1)
226 m ; no action needed
227 (rlet1 t (tree-map-copy m)
228 (tree-map-put! t k v1)))))
229
230 (define (mapping-update! m k updater
231 :optional
232 (failure (^[] (errorf "~s doesn't have a key ~s" m k)))
233 (success identity))
234 (assume-type m <mapping>)
235 (let* ([v (tree-map-get m k %unique)]
236 [v1 (if (eq? v %unique)
237 (updater (failure))
238 (updater (success v)))])
239 (tree-map-put! m k v1))
240 m)
241
242 (define (mapping-update/default m k updater default)
243 (mapping-update m k updater (lambda () default)))
244
245 (define (mapping-update!/default m k updater default)
246 (mapping-update! m k updater (lambda () default)))
247
248 (define (mapping-pop! m
249 :optional
250 (failure (^[] (error "can't pop from an empty map"))))
251 (assume-type m <mapping>)
252 (if-let1 p (tree-map-pop-min! m)
253 (values m (car p) (cdr p))
254 (failure)))
255
256 (define (mapping-pop m
257 :optional
258 (failure (^[] (error "can't pop from an empty map"))))
259 (assume-type m <mapping>)
260 (if (tree-map-empty? m)
261 (failure) ;avoid unnecessary copying
262 (mapping-pop! (mapping-copy m))))
263
264 (define (mapping-search m k failure success)
265 (assume-type m <mapping>)
266 (let1 v (tree-map-get m k %unique)
267 (if (eq? v %unique)
268 (failure (^[v o] (let1 m (tree-map-copy m) ;insert
269 (tree-map-put! m k v)
270 (values m o)))
271 (^[o] (values m o))) ;ignore
272 (success k v
273 (^[k v o] (let1 m (tree-map-copy m) ;update
274 (tree-map-put! m k v)
275 (values m o)))
276 (^[o] (let1 m (tree-map-copy m) ;remove
277 (tree-map-delete! m k)
278 (values m o)))))))
279
280 (define (mapping-search! m k failure success)
281 (assume-type m <mapping>)
282 (let1 v (tree-map-get m k %unique)
283 (if (eq? v %unique)
284 (failure (^[v o] (tree-map-put! m k v) (values m o)) ;insert
285 (^[o] (values m o))) ;ignore
286 (success v
287 (^[k v o] (tree-map-put! m k v) (values m o)) ;update
288 (^[o] (tree-map-delete! m k) (values m o)))))) ;remove
289
290 (define (mapping-size m)
291 (assume-type m <mapping>)
292 (tree-map-num-entries m))
293
294 (define (mapping-find pred m failure)
295 (assume-type m <mapping>)
296 (tree-map-seek m pred failure (^[r k v] (values k v))))
297
298 (define (mapping-count pred m)
299 (assume-type m <mapping>)
300 (tree-map-fold m (^[k v c] (if (pred k v) (+ 1 c) c)) 0))
301
302 (define (mapping-any? pred m)
303 (assume-type m <mapping>)
304 (tree-map-seek m pred (^[] #f) (^[r k v] #t)))
305
306 (define (mapping-every? pred m)
307 (assume-type m <mapping>)
308 (tree-map-seek m (^[k v] (not (pred k v))) (^[] #t) (^[r k v] #f)))
309
310 (define (mapping-keys m) (tree-map-keys m))
311 (define (mapping-values m) (tree-map-values m))
312
313 (define (mapping-entries m)
314 (values (tree-map-keys m) (tree-map-values m)))
315
316 (define (mapping-map proc cmpr m)
317 (assume-type m <mapping>)
318 (assume-type cmpr <comparator>)
319 (rlet1 r (make-tree-map cmpr)
320 (tree-map-for-each m (^[k v] (receive [k v] (proc k v)
321 (tree-map-put! r k v))))))
322
323 (define (mapping-for-each proc m)
324 (assume-type m <mapping>)
325 (tree-map-for-each m proc))
326
327 (define (mapping-fold kons knil m)
328 (assume-type m <mapping>)
329 (tree-map-fold m kons knil))
330
331 (define (mapping-map->list proc m)
332 (assume-type m <mapping>)
333 (tree-map-map m proc))
334
335 (define (mapping-filter pred m)
336 (assume-type m <mapping>)
337 (rlet1 r (make-tree-map (tree-map-comparator m))
338 (tree-map-for-each m (^[k v] (when (pred k v)
339 (tree-map-put! r k v))))))
340
341 (define (mapping-filter! pred m)
342 (assume-type m <mapping>)
343 (tree-map-for-each m (^[k v] (unless (pred k v)
344 (tree-map-delete! m k)))))
345
346 (define (mapping-remove pred m)
347 (assume-type m <mapping>)
348 (rlet1 r (make-tree-map (tree-map-comparator m))
349 (tree-map-for-each m (^[k v] (unless (pred k v)
350 (tree-map-put! r k v))))))
351
352 (define (mapping-remove! pred m)
353 (assume-type m <mapping>)
354 (tree-map-for-each m (^[k v] (when (pred k v)
355 (tree-map-delete! m k)))))
356
357 (define (mapping-partition pred m)
358 (assume-type m <mapping>)
359 (let ([f (make-tree-map (tree-map-comparator m))]
360 [r (make-tree-map (tree-map-comparator m))])
361 (tree-map-for-each m (^[k v] (if (pred k v)
362 (tree-map-put! f k v)
363 (tree-map-put! r k v))))
364 (values f r)))
365
366 (define (mapping-partition! pred m)
367 (assume-type m <mapping>)
368 (let1 r (make-tree-map (tree-map-comparator m))
369 (tree-map-for-each m (^[k v] (unless (pred k v)
370 (tree-map-delete! m k)
371 (tree-map-put! r k v))))
372 (values m r)))
373
374 (define (mapping-copy m)
375 (assume-type m <mapping>)
376 (tree-map-copy m))
377
378 (define (mapping->alist m)
379 (assume-type m <mapping>)
380 (tree-map-fold-right m acons '()))
381
382 (define (alist->mapping cmpr alist)
383 (assume-type cmpr <comparator>)
384 (rlet1 m (make-tree-map cmpr)
385 (dolist [p alist]
386 (tree-map-adjoin! m (car p) (cdr p)))))
387
388 (define (alist->mapping! m alist)
389 (assume-type m <mapping>)
390 (dolist [p alist]
391 (tree-map-adjoin! m (car p) (cdr p)))
392 m)
393
394 ;; we don't take advantage of, neither check, ordered keys
395 (define alist->mapping/ordered alist->mapping)
396 (define alist->mapping/ordered! alist->mapping!)
397
398 (define (%mapping-cmp v=? pred ms)
399 (let loop ([ms ms])
400 (cond [(null? (cdr ms)) #t]
401 [(not (eqv? (tree-map-comparator (car ms))
402 (tree-map-comparator (cadr ms))))
403 #f]
404 [(tree-map-compare-as-sets (car ms) (cadr ms) v=? #f)
405 => (^r (and (pred r) (loop (cdr ms))))]
406 [else #f])))
407
408 (define-syntax define-mapping-cmp
409 (syntax-rules ()
410 [(_ name op)
411 (define (name vcmp m . more)
412 (assume-type vcmp <comparator>)
413 (%mapping-cmp (comparator-equality-predicate vcmp)
414 (^[x] (op x 0))
415 (cons m more)))]))
416
417 (define-mapping-cmp mapping=? =)
418 (define-mapping-cmp mapping<? <)
419 (define-mapping-cmp mapping<=? <=)
420 (define-mapping-cmp mapping>? >)
421 (define-mapping-cmp mapping>=? >=)
422
423 (define (%union-2! m1 m2)
424 (tree-map-for-each m2 (^[k v] (tree-map-adjoin! m1 k v)))
425 m1)
426
427 (define (mapping-union! m1 . more)
428 (if (null? more)
429 m1
430 (apply mapping-union! (%union-2! m1 (car more)) (cdr more))))
431
432 (define (mapping-union m1 . more)
433 (apply mapping-union! (mapping-copy m1) more))
434
435 (define (%intersection-2! m1 m2)
436 (tree-map-for-each m1 (^[k v] (unless (tree-map-get m2 k #f)
437 (tree-map-delete! m1 k))))
438 m1)
439
440 (define (mapping-intersection! m1 . more)
441 (if (null? more)
442 m1
443 (apply mapping-intersection! (%intersection-2! m1 (car more)) (cdr more))))
444
445 (define (mapping-intersection m1 . more)
446 (apply mapping-intersection! (mapping-copy m1) more))
447
448 (define (%difference-2! m1 m2)
449 (tree-map-for-each m2 (^[k v] (tree-map-delete! m1 k)))
450 m1)
451
452 (define (mapping-difference! m1 . more)
453 (let loop ([m1 m1] [more more])
454 (if (null? more)
455 m1
456 (loop (%difference-2! m1 (car more)) (cdr more)))))
457
458 (define (mapping-difference m1 . more)
459 (apply mapping-difference! (mapping-copy m1) more))
460
461 (define (mapping-xor! m1 m2)
462 (tree-map-for-each m2 (^[k v] (if (tree-map-get m1 k #f)
463 (tree-map-delete! m1 k)
464 (tree-map-put! m1 k v))))
465 m1)
466
467 (define (mapping-xor m1 m2)
468 (mapping-xor! (mapping-copy m1) m2))
469
470 (define (mapping-min-key m)
471 (assume-type m <mapping>)
472 (if-let1 p (tree-map-min m)
473 (car p)
474 (error "Can't get min key from an empty map:" m)))
475
476 (define (mapping-max-key m)
477 (assume-type m <mapping>)
478 (if-let1 p (tree-map-max m)
479 (car p)
480 (error "Can't get min key from an empty map:" m)))
481
482 (define (mapping-min-value m)
483 (assume-type m <mapping>)
484 (if-let1 p (tree-map-min m)
485 (cdr p)
486 (error "Can't get min key from an empty map:" m)))
487
488 (define (mapping-max-value m)
489 (assume-type m <mapping>)
490 (if-let1 p (tree-map-max m)
491 (cdr p)
492 (error "Can't get min key from an empty map:" m)))
493
494 (define (mapping-key-predecessor m probe failure)
495 (assume-type m <mapping>)
496 (receive [k v] (tree-map-predecessor m probe %unique)
497 (if (eq? k %unique)
498 (failure)
499 k)))
500
501 (define (mapping-key-successor m probe failure)
502 (assume-type m <mapping>)
503 (receive [k v] (tree-map-successor m probe %unique)
504 (if (eq? k %unique)
505 (failure)
506 k)))
507
508 (define-syntax define-mapping-range
509 (syntax-rules ()
510 [(_ name! name op)
511 (begin
512 (define (name! m probe)
513 (assume-type m <mapping>)
514 (let1 cmpr (tree-map-comparator m)
515 ($ tree-map-for-each m
516 (^[k v] (unless (op (comparator-compare cmpr k probe) 0)
517 (tree-map-delete! m k)))))
518 m)
519 (define (name m probe)
520 (name! (mapping-copy m) probe)))]))
521
522 (define-mapping-range mapping-range=! mapping-range= =)
523 (define-mapping-range mapping-range<! mapping-range< <)
524 (define-mapping-range mapping-range<=! mapping-range<= <=)
525 (define-mapping-range mapping-range>! mapping-range> >)
526 (define-mapping-range mapping-range>=! mapping-range>= >=)
527
528 (define (mapping-split m probe)
529 (assume-type m <mapping>)
530 ;; no more efficient than calling each one
531 (values (mapping-range< m probe)
532 (mapping-range<= m probe)
533 (mapping-range= m probe)
534 (mapping-range>= m probe)
535 (mapping-range> m probe)))
536
537 (define (%mapping-catenate! cmpr m1 key val m2 reuse?)
538 (define (too-small key m)
539 (errorf "Catenating key ~s is too small for ~s" key m))
540 (define (too-large key m)
541 (errorf "Catenating key ~s is too large for ~s" key m))
542 (cond [(and reuse? (equal? cmpr (tree-map-comparator m1)))
543 ;; Reuse m1
544 (when (and (not (tree-map-empty? m1))
545 (>= (comparator-compare cmpr (car (tree-map-max m1)) key) 0))
546 (too-small key m1))
547 (tree-map-put! m1 key val)
548 ($ tree-map-for-each m2
549 (^[k v]
550 (when (<= (comparator-compare cmpr k key) 0)
551 (too-large key m2))
552 (tree-map-put! m1 k v)))
553 m1]
554 [(and reuse? (equal? cmpr (tree-map-comparator m2)))
555 ;; Reuse m2
556 (when (and (not (tree-map-empty? m2))
557 (<= (comparator-compare cmpr (car (tree-map-max m2)) key) 0))
558 (too-large key m2))
559 (tree-map-put! m2 key val)
560 ($ tree-map-for-each m1
561 (^[k v]
562 (when (>= (comparator-compare cmpr k key) 0)
563 (too-small key m1))
564 (tree-map-put! m2 k v)))
565 m2]
566 [else
567 (rlet1 m (make-tree-map cmpr)
568 (tree-map-put! m key val)
569 ($ tree-map-for-each m1
570 (^[k v]
571 (when (>= (comparator-compare cmpr k key) 0)
572 (too-small key m1))
573 (tree-map-put! m k v)))
574 ($ tree-map-for-each m2
575 (^[k v]
576 (when (<= (comparator-compare cmpr k key) 0)
577 (too-large key m2))
578 (tree-map-put! m k v))))]))
579
580 (define (mapping-catenate cmpr m1 key val m2)
581 (%mapping-catenate! cmpr m1 key val m2 #f))
582 (define (mapping-catenate! cmpr m1 key val m2)
583 (%mapping-catenate! cmpr m1 key val m2 #t))
584
585 ;; We don't take advantage of monotone
586 (define (mapping-map/monotone! proc cmpr m)
587 (mapping-map proc cmpr m))
588 (define (mapping-map/monotone proc cmpr m)
589 (mapping-map proc cmpr m))
590
591 (define (mapping-fold/reverse kons knil m)
592 (tree-map-fold-right m kons knil))
593
594 (define (make-mapping-comparator value-cmpr)
595 (define (compare a b)
596 (tree-map-compare-as-sequences a b value-cmpr))
597 (make-comparator/compare mapping? #t compare #f))
598
599 (define mapping-comparator (make-mapping-comparator default-comparator))