Debian Codegraph @

lib/scheme/mapping/hash.scm

raw
1 ;;;
2 ;;; scheme.mapping.hash - hashmaps (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.hash
35 (define-module scheme.mapping.hash
36 (export hashmap hashmap-unfold
37 hashmap? hashmap-contains? hashmap-empty? hashmap-disjoint?
38 hashmap-ref hashmap-ref/default
39 hashmap-key-comparator
40
41 hashmap-set hashmap-set!
42 hashmap-adjoin hashmap-adjoin!
43 hashmap-replace hashmap-replace!
44 hashmap-delete hashmap-delete!
45 hashmap-delete-all hashmap-delete-all!
46 hashmap-intern hashmap-intern!
47 hashmap-update hashmap-update!
48 hashmap-update/default hashmap-update!/default
49 hashmap-pop hashmap-pop!
50 hashmap-search hashmap-search!
51 hashmap-size hashmap-find hashmap-count
52 hashmap-any? hashmap-every?
53 hashmap-keys hashmap-values hashmap-entries
54 hashmap-map hashmap-map->list hashmap-for-each hashmap-fold
55 hashmap-filter hashmap-filter! hashmap-remove hashmap-remove!
56 hashmap-partition hashmap-partition!
57 hashmap-copy hashmap->alist alist->hashmap alist->hashmap!
58
59 hashmap=? hashmap<? hashmap>? hashmap<=? hashmap>=?
60 hashmap-union hashmap-intersection hashmap-difference hashmap-xor
61 hashmap-union! hashmap-intersection! hashmap-difference! hashmap-xor!
62 make-hashmap-comparator
63 hashmap-comparator
64
65 ;; builtin
66 comparator?))
67 (select-module scheme.mapping.hash)
68
69 ;; We provide <hash-table> as hashmap.
70 (define <hashmap> <hash-table>)
71 (define (hashmap? m) (is-a? m <hashmap>))
72
73 (define-syntax dopairs
74 (syntax-rules ()
75 [(_ [k v lis] body ...)
76 (let1 lis lis
77 (do ([xs lis (cddr xs)])
78 [(null? xs)]
79 (when (null? (cdr xs))
80 (error "mapping kv-list isn't even:" lis))
81 (let ([k (car xs)]
82 [v (cadr xs)])
83 body ...)))]))
84
85 (define (hashmap comparator . args)
86 (assume-type comparator <comparator>)
87 (rlet1 m (make-hash-table comparator)
88 (dopairs [k v args] (hash-table-adjoin! m k v))))
89
90 (define (hashmap-unfold p f g seed comparator)
91 (assume-type comparator <comparator>)
92 (rlet1 m (make-hash-table comparator)
93 (do ([seed seed (g seed)])
94 [(p seed) m]
95 (receive (k v) (f seed)
96 (hash-table-adjoin! m k v)))))
97
98 (define (hashmap-empty? m) (hash-table-empty? m))
99 (define (hashmap-contains? m key) (hash-table-exists? m key))
100 (define (hashmap-disjoint? m1 m2)
101 (assume-type m1 <hashmap>)
102 (assume-type m2 <hashmap>)
103 (hash-table-seek m1 (^[k _] (hash-table-exists? m2 k))
104 (^[] #t)
105 (^[r k v] #f)))
106
107 (define %unique (list #f))
108
109 (define (hashmap-ref m key
110 :optional
111 (failure #f)
112 (success identity))
113 (assume-type m <hashmap>)
114 (if failure
115 (let1 v (hash-table-get m key %unique)
116 (if (eq? v %unique)
117 (failure)
118 (success v)))
119 (success (hash-table-get m key)))) ;let hash-table-get handle failure
120
121 (define (hashmap-ref/default m key default)
122 (assume-type m <hashmap>)
123 (hash-table-get m key default))
124
125 (define (hashmap-key-comparator m) (hash-table-comparator m))
126
127 (define (hashmap-set m . args)
128 (if (null? args)
129 (begin
130 (assume-type m <hashmap>)
131 m) ;shortcut
132 (apply hashmap-set! (hashmap-copy m) args)))
133
134 (define (hashmap-set! m . args)
135 (assume-type m <hashmap>)
136 (dopairs [k v args] (hash-table-put! m k v))
137 m)
138
139 (define (hashmap-adjoin m . args)
140 (if (null? args)
141 (begin
142 (assume-type m <hashmap>)
143 m) ;shortcut
144 (apply hashmap-adjoin! (hash-table-copy m) args)))
145
146 (define (hashmap-adjoin! m . args)
147 (assume-type m <hashmap>)
148 (dopairs [k v args] (hash-table-adjoin! m k v))
149 m)
150
151 (define (hashmap-replace m k v)
152 (assume-type m <hashmap>)
153 (if (hash-table-exists? m k)
154 (hashmap-replace! (hash-table-copy m) k v)
155 m))
156
157 (define (hashmap-replace! m k v)
158 (assume-type m <hashmap>)
159 (hash-table-replace! m k v)
160 m)
161
162 (define (hashmap-delete m . keys) (hashmap-delete-all m keys))
163 (define (hashmap-delete! m . keys) (hashmap-delete-all! m keys))
164
165 (define (hashmap-delete-all m keys)
166 (assume-type m <hashmap>)
167 ;; We delay copy until we actually modify the map.
168 (fold (^[k t]
169 (if (hash-table-exists? t k)
170 (rlet1 t (if (eq? t m) (hash-table-copy m) t)
171 (hash-table-delete! t k))
172 t))
173 m keys))
174
175 (define (hashmap-delete-all! m keys)
176 (assume-type m <hashmap>)
177 (dolist [k keys] (hash-table-delete! m k))
178 m)
179
180 (define (hashmap-intern m k newval)
181 (assume-type m <hashmap>)
182 (let1 v (hash-table-get m k %unique)
183 (if (eq? v %unique)
184 (let ([t (hash-table-copy m)]
185 [v (newval)])
186 (hash-table-put! t k v)
187 (values t v))
188 (values m v))))
189
190 (define (hashmap-intern! m k newval)
191 (assume-type m <hashmap>)
192 (let1 v (hash-table-get m k %unique)
193 (if (eq? v %unique)
194 (let1 v (newval)
195 (hash-table-put! m k v)
196 (values m v))
197 (values m v))))
198
199 (define (hashmap-update m k updater
200 :optional
201 (failure (^[] (errorf "~s doesn't have a key ~s" m k)))
202 (success identity))
203 (assume-type m <hashmap>)
204 ;; We delay copy until we actually modify the map.
205 (let* ([v (hash-table-get m k %unique)]
206 [v1 (if (eq? v %unique)
207 (updater (failure))
208 (updater (success v)))])
209 (if (eq? v v1)
210 m ; no action needed
211 (rlet1 t (hash-table-copy m)
212 (hash-table-put! t k v1)))))
213
214 (define (hashmap-update! m k updater
215 :optional
216 (failure (^[] (errorf "~s doesn't have a key ~s" m k)))
217 (success identity))
218 (assume-type m <hashmap>)
219 (let* ([v (hash-table-get m k %unique)]
220 [v1 (if (eq? v %unique)
221 (updater (failure))
222 (updater (success v)))])
223 (hash-table-put! m k v1))
224 m)
225
226 (define (hashmap-update/default m k updater default)
227 (hashmap-update m k updater (lambda () default)))
228
229 (define (hashmap-update!/default m k updater default)
230 (hashmap-update! m k updater (lambda () default)))
231
232 (define (hashmap-pop! m
233 :optional
234 (failure (^[] (error "can't pop from an empty map"))))
235 (assume-type m <hashmap>)
236 ;; We cheat to use internal iterator to avoid traversing whole hashtable
237 (let1 iter ((with-module gauche.internal %hash-table-iter) m)
238 (receive (k v) (iter %unique)
239 (if (eq? k %unique)
240 (failure)
241 (begin
242 (hash-table-delete! m k)
243 (values m k v))))))
244
245 (define (hashmap-pop m
246 :optional
247 (failure (^[] (error "can't pop from an empty map"))))
248 (assume-type m <hashmap>)
249 (if (hash-table-empty? m)
250 (failure) ;avoid unnecessary copying
251 (hashmap-pop! (hashmap-copy m))))
252
253 (define (hashmap-search m k failure success)
254 (assume-type m <hashmap>)
255 (let1 v (hash-table-get m k %unique)
256 (if (eq? v %unique)
257 (failure (^[v o] (let1 m (hash-table-copy m) ;insert
258 (hash-table-put! m k v)
259 (values m o)))
260 (^[o] (values m o))) ;ignore
261 (success k v
262 (^[k v o] (let1 m (hash-table-copy m) ;update
263 (hash-table-put! m k v)
264 (values m o)))
265 (^[o] (let1 m (hash-table-copy m) ;remove
266 (hash-table-delete! m k)
267 (values m o)))))))
268
269 (define (hashmap-search! m k failure success)
270 (assume-type m <hashmap>)
271 (let1 v (hash-table-get m k %unique)
272 (if (eq? v %unique)
273 (failure (^[v o] (hash-table-put! m k v) (values m o)) ;insert
274 (^[o] (values m o))) ;ignore
275 (success v
276 (^[k v o] (hash-table-put! m k v) (values m o)) ;update
277 (^[o] (hash-table-delete! m k) (values m o)))))) ;remove
278
279 (define (hashmap-size m)
280 (assume-type m <hashmap>)
281 (hash-table-num-entries m))
282
283 (define (hashmap-find pred m failure)
284 (assume-type m <hashmap>)
285 (hash-table-seek m pred failure (^[r k v] (values k v))))
286
287 (define (hashmap-count pred m)
288 (assume-type m <hashmap>)
289 (hash-table-fold m (^[k v c] (if (pred k v) (+ 1 c) c)) 0))
290
291 (define (hashmap-any? pred m)
292 (assume-type m <hashmap>)
293 (hash-table-seek m pred (^[] #f) (^[r k v] #t)))
294
295 (define (hashmap-every? pred m)
296 (assume-type m <hashmap>)
297 (hash-table-seek m (^[k v] (not (pred k v))) (^[] #t) (^[r k v] #f)))
298
299 (define (hashmap-keys m) (hash-table-keys m))
300 (define (hashmap-values m) (hash-table-values m))
301
302 (define (hashmap-entries m)
303 (values (hash-table-keys m) (hash-table-values m)))
304
305 (define (hashmap-map proc cmpr m)
306 (assume-type m <hashmap>)
307 (assume-type cmpr <comparator>)
308 (rlet1 r (make-hash-table cmpr)
309 (hash-table-for-each m (^[k v] (receive [k v] (proc k v)
310 (hash-table-put! r k v))))))
311
312 (define (hashmap-for-each proc m)
313 (assume-type m <hashmap>)
314 (hash-table-for-each m proc))
315
316 (define (hashmap-fold kons knil m)
317 (assume-type m <hashmap>)
318 (hash-table-fold m kons knil))
319
320 (define (hashmap-map->list proc m)
321 (assume-type m <hashmap>)
322 (hash-table-map m proc))
323
324 (define (hashmap-filter pred m)
325 (assume-type m <hashmap>)
326 (rlet1 r (make-hash-table (hash-table-comparator m))
327 (hash-table-for-each m (^[k v] (when (pred k v)
328 (hash-table-put! r k v))))))
329
330 (define (hashmap-filter! pred m)
331 (assume-type m <hashmap>)
332 (hash-table-for-each m (^[k v] (unless (pred k v)
333 (hash-table-delete! m k)))))
334
335 (define (hashmap-remove pred m)
336 (assume-type m <hashmap>)
337 (rlet1 r (make-hash-table (hash-table-comparator m))
338 (hash-table-for-each m (^[k v] (unless (pred k v)
339 (hash-table-put! r k v))))))
340
341 (define (hashmap-remove! pred m)
342 (assume-type m <hashmap>)
343 (hash-table-for-each m (^[k v] (when (pred k v)
344 (hash-table-delete! m k)))))
345
346 (define (hashmap-partition pred m)
347 (assume-type m <hashmap>)
348 (let ([f (make-hash-table (hash-table-comparator m))]
349 [r (make-hash-table (hash-table-comparator m))])
350 (hash-table-for-each m (^[k v] (if (pred k v)
351 (hash-table-put! f k v)
352 (hash-table-put! r k v))))
353 (values f r)))
354
355 (define (hashmap-partition! pred m)
356 (assume-type m <hashmap>)
357 (let1 r (make-hash-table (hash-table-comparator m))
358 (hash-table-for-each m (^[k v] (unless (pred k v)
359 (hash-table-delete! m k)
360 (hash-table-put! r k v))))
361 (values m r)))
362
363 (define (hashmap-copy m)
364 (assume-type m <hashmap>)
365 (hash-table-copy m))
366
367 (define (hashmap->alist m)
368 (assume-type m <hashmap>)
369 (hash-table-fold m acons '()))
370
371 (define (alist->hashmap cmpr alist)
372 (assume-type cmpr <comparator>)
373 (rlet1 m (make-hash-table cmpr)
374 (dolist [p alist]
375 (hash-table-adjoin! m (car p) (cdr p)))))
376
377 (define (alist->hashmap! m alist)
378 (assume-type m <hashmap>)
379 (dolist [p alist]
380 (hash-table-adjoin! m (car p) (cdr p)))
381 m)
382
383 (define (%hashmap-cmp v=? pred ms)
384 (let loop ([ms ms])
385 (cond [(null? (cdr ms)) #t]
386 [(not (eqv? (hash-table-comparator (car ms))
387 (hash-table-comparator (cadr ms))))
388 #f]
389 [(hash-table-compare-as-sets (car ms) (cadr ms) v=? #f)
390 => (^r (and (pred r) (loop (cdr ms))))]
391 [else #f])))
392
393 (define-syntax define-hashmap-cmp
394 (syntax-rules ()
395 [(_ name op)
396 (define (name vcmp m . more)
397 (assume-type vcmp <comparator>)
398 (%hashmap-cmp (comparator-equality-predicate vcmp)
399 (^[x] (op x 0))
400 (cons m more)))]))
401
402 (define-hashmap-cmp hashmap=? =)
403 (define-hashmap-cmp hashmap<? <)
404 (define-hashmap-cmp hashmap<=? <=)
405 (define-hashmap-cmp hashmap>? >)
406 (define-hashmap-cmp hashmap>=? >=)
407
408 (define (%union-2! m1 m2)
409 (hash-table-for-each m2 (^[k v] (hash-table-adjoin! m1 k v)))
410 m1)
411
412 (define (hashmap-union! m1 . more)
413 (if (null? more)
414 m1
415 (apply hashmap-union! (%union-2! m1 (car more)) (cdr more))))
416
417 (define (hashmap-union m1 . more)
418 (apply hashmap-union! (hashmap-copy m1) more))
419
420 (define (%intersection-2! m1 m2)
421 (hash-table-for-each m1 (^[k v] (unless (hash-table-get m2 k #f)
422 (hash-table-delete! m1 k))))
423 m1)
424
425 (define (hashmap-intersection! m1 . more)
426 (if (null? more)
427 m1
428 (apply hashmap-intersection! (%intersection-2! m1 (car more)) (cdr more))))
429
430 (define (hashmap-intersection m1 . more)
431 (apply hashmap-intersection! (hashmap-copy m1) more))
432
433 (define (%difference-2! m1 m2)
434 (hash-table-for-each m2 (^[k v] (hash-table-delete! m1 k)))
435 m1)
436
437 (define (hashmap-difference! m1 . more)
438 (let loop ([m1 m1] [more more])
439 (if (null? more)
440 m1
441 (loop (%difference-2! m1 (car more)) (cdr more)))))
442
443 (define (hashmap-difference m1 . more)
444 (apply hashmap-difference! (hashmap-copy m1) more))
445
446 (define (hashmap-xor! m1 m2)
447 (hash-table-for-each m2 (^[k v] (if (hash-table-get m1 k #f)
448 (hash-table-delete! m1 k)
449 (hash-table-put! m1 k v))))
450 m1)
451
452 (define (hashmap-xor m1 m2)
453 (hashmap-xor! (hashmap-copy m1) m2))
454
455 (define (make-hashmap-comparator value-cmpr)
456 (define (hash-hash h)
457 (let1 key-cmpr (hash-table-comparator h)
458 (hash-table-fold h 0
459 (^[k v s]
460 (logxor s (combine-hash-value
461 (comparator-hash key-cmpr k)
462 (comparator-hash value-cmpr v)))))))
463 (define (hash-equal? a b)
464 (and (hash-table? a)
465 (hash-table? b)
466 (equal? (hash-table-comparator a) (hash-table-comparator b))
467 (hashmap=? value-cmpr a b)))
468 (make-comparator hashmap? hash-equal? #f hash-hash))
469
470 (define hashmap-comparator (make-hashmap-comparator default-comparator))