Debian Codegraph @

lib/scheme/set.scm

raw
1 ;;
2 ;; Copyright (C) John Cowan 2013. All Rights Reserved.
3 ;;
4 ;; Permission is hereby granted, free of charge, to any person obtaining
5 ;; a copy of this software and associated documentation
6 ;; files (the "Software"), to deal in the Software without restriction,
7 ;; including without limitation the rights to use, copy, modify, merge,
8 ;; publish, distribute, sublicense, and/or sell copies of the Software,
9 ;; and to permit persons to whom the Software is furnished to do so,
10 ;; subject to the following conditions:
11 ;;
12 ;; The above copyright notice and this permission notice shall be
13 ;; included in all copies or substantial portions of the Software.
14 ;;
15 ;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 ;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 ;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 ;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
19 ;; LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
20 ;; OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
21 ;; WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22
23 ;; Apapted to Gauche by Shiro Kawai
24
25 ;;;; Implementation of general sets and bags for SRFI 113
26
27 ;;; A "sob" object is the representation of both sets and bags.
28 ;;; This allows each set-* and bag-* procedure to be implemented
29 ;;; using the same code, without having to deal in ugly indirections
30 ;;; over the field accessors. There are three fields, "sob-multi?",
31 ;;; "sob-hash-table", and "sob-comparator."
32
33 ;;; The value of "sob-multi?" is #t for bags and #f for sets.
34 ;;; "Sob-hash-table" maps the elements of the sob to the number of times
35 ;;; the element appears, which is always 1 for a set, any positive value
36 ;;; for a bag. "Sob-comparator" is the comparator for the elements of
37 ;;; the set.
38
39 ;;; Note that sob-* procedures do not do type checking or (typically) the
40 ;;; copying required for supporting pure functional update. These things
41 ;;; are done by the set-* and bag-* procedures, which are externally
42 ;;; exposed (but trivial and mostly uncommented below).
43
44
45 ;;; Shim to convert from SRFI 69 to the future "intermediate hash tables"
46 ;;; SRFI. Unfortunately, hash-table-fold is incompatible between the two
47 ;;; and so is not usable.
48
49 ;; Originally SRFI-113
50 (define-module scheme.set
51 (use srfi.114)
52 (use gauche.collection)
53 (use gauche.generator)
54 (export set set-unfold
55 set? set-contains? set-empty? set-disjoint?
56 set-member set-element-comparator
57 set-adjoin set-adjoin! set-replace set-replace!
58 set-delete set-delete! set-delete-all set-delete-all! set-search!
59 set-size set-find set-count set-any? set-every?
60 set-map set-for-each set-fold
61 set-filter set-remove set-remove set-partition
62 set-filter! set-remove! set-partition!
63 set-copy set->list list->set list->set!
64 set=? set<? set>? set<=? set>=?
65 set-union set-intersection set-difference set-xor
66 set-union! set-intersection! set-difference! set-xor!
67 set-comparator
68
69 bag bag-unfold
70 bag? bag-contains? bag-empty? bag-disjoint?
71 bag-member bag-element-comparator
72 bag-adjoin bag-adjoin! bag-replace bag-replace!
73 bag-delete bag-delete! bag-delete-all bag-delete-all! bag-search!
74 bag-size bag-find bag-count bag-any? bag-every?
75 bag-map bag-for-each bag-fold
76 bag-filter bag-remove bag-partition
77 bag-filter! bag-remove! bag-partition!
78 bag-copy bag->list list->bag list->bag!
79 bag=? bag<? bag>? bag<=? bag>=?
80 bag-union bag-intersection bag-difference bag-xor
81 bag-union! bag-intersection! bag-difference! bag-xor!
82 bag-comparator
83
84 bag-sum bag-sum! bag-product bag-product!
85 bag-unique-size bag-element-count bag-for-each-unique bag-fold-unique
86 bag-increment! bag-decrement! bag->set set->bag set->bag!
87 bag->alist alist->bag
88 ))
89 (select-module scheme.set)
90
91 ;; Gauche adaptation
92
93 (define hash-table-contains? hash-table-exists?)
94 (define (hash-table-for-each proc hash-table) ; argument order reversed
95 ((with-module gauche hash-table-for-each) hash-table proc))
96 (define make-hash-table/comparator make-hash-table)
97 (define hash-table-size hash-table-num-entries)
98 (define hash-table-ref/default hash-table-get)
99 (define hash-table-set! hash-table-put!)
100 (define hash-table-update!/default hash-table-update!)
101
102 (define-class <sob> (<collection>)
103 ((table :init-keyword :table)))
104 (define-class <set> (<sob>) ())
105 (define-class <bag> (<sob>) ())
106
107 (define (raw-make-sob hash-table comparator multi?)
108 (if multi?
109 (make <bag> :table hash-table)
110 (make <set> :table hash-table)))
111
112 (define (set? obj) (is-a? obj <set>))
113 (define (bag? obj) (is-a? obj <bag>))
114
115 ;; we assume sob is either <set> or <bag>
116 (define (sob-hash-table sob) (slot-ref sob 'table))
117 (define (sob-comparator sob) (hash-table-comparator (slot-ref sob'table)))
118 (define (sob-multi? sob) (is-a? sob <bag>))
119
120 (define-method object-hash ((obj <sob>)) (sob-hash obj))
121 (define-method object-equal? ((a <set>) (b <set>)) (sob=? a b))
122 (define-method object-equal? ((a <bag>) (b <bag>)) (sob=? a b))
123
124 (define-method write-object ((obj <set>) out)
125 (format out "#<set ~a ~aitems>" (debug-label obj)
126 (hash-table-num-entries (sob-hash-table obj))))
127 (define-method write-object ((obj <bag>) out)
128 (format out "#<bag ~a ~akinds, ~aitems>" (debug-label obj)
129 (hash-table-num-entries (sob-hash-table obj))
130 (apply + (hash-table-values (sob-hash-table obj)))))
131
132 (define-method call-with-iterator ((obj <sob>) proc :allow-other-keys)
133 ($ call-with-iterator (sob-hash-table obj)
134 (^[end? next]
135 (define current (if (end?) #f (next))) ; (<item> . <count>)
136 (define (over?) (or (not current) (and (end?) (zero? (cdr current)))))
137 (define (get) (and (pair? current)
138 (if (zero? (cdr current))
139 (and (not (end?))
140 (begin (set! current (next))
141 (dec! (cdr current))
142 (car current)))
143 (begin (dec! (cdr current))
144 (car current)))))
145 (proc over? get))))
146
147 ;; TODO: To impelment call-with-builder, we need some way to specify
148 ;; comparator argument for the constructor.
149
150 ;; The following code is mostly intact from the reference implementation
151 ;; I commented out some irrelevant definitions, and rewrote early break
152 ;; pattern (by call/cc) with hash-table-find.
153
154 ;;; Record definition and core typing/checking procedures
155
156 ;; (define-record-type sob
157 ;; (raw-make-sob hash-table comparator multi?)
158 ;; sob?
159 ;; (hash-table sob-hash-table)
160 ;; (comparator sob-comparator)
161 ;; (multi? sob-multi?))
162
163 ;; (define (set? obj) (and (sob? obj) (not (sob-multi? obj))))
164
165 ;; (define (bag? obj) (and (sob? obj) (sob-multi? obj)))
166
167 (define (check-set obj) (if (not (set? obj)) (error "not a set" obj)))
168
169 (define (check-bag obj) (if (not (bag? obj)) (error "not a bag" obj)))
170
171 ;; These procedures verify that not only are their arguments all sets
172 ;; or all bags as the case may be, but also share the same comparator.
173
174 (define (check-all-sets list)
175 (for-each (lambda (obj) (check-set obj)) list)
176 (sob-check-comparators list))
177
178 (define (check-all-bags list)
179 (for-each (lambda (obj) (check-bag obj)) list)
180 (sob-check-comparators list))
181
182 (define (sob-check-comparators list)
183 (if (not (null? list))
184 (for-each
185 (lambda (sob)
186 (check-same-comparator (car list) sob))
187 (cdr list))))
188
189 ;; This procedure is used directly when there are exactly two arguments.
190 ;; [SK] Gauche's equal? is more permissive than eq? when comparing comparators.
191 (define (check-same-comparator a b)
192 (if (not (equal? (sob-comparator a) (sob-comparator b)))
193 (error "different comparators" a b)))
194
195 ;; This procedure defends against inserting an element
196 ;; into a sob that violates its constructor, since
197 ;; typical hash-table implementations don't check for us.
198
199 (define (check-element sob element)
200 (comparator-check-type (sob-comparator sob) element))
201
202 ;;; Constructors
203
204 ;; Construct an arbitrary empty sob out of nothing.
205
206 (define (make-sob comparator multi?)
207 (raw-make-sob (make-hash-table/comparator comparator) comparator multi?))
208
209 ;; Copy a sob, sharing the constructor.
210
211 (define (sob-copy sob)
212 (raw-make-sob (hash-table-copy (sob-hash-table sob))
213 (sob-comparator sob)
214 (sob-multi? sob)))
215
216 (define (set-copy set)
217 (check-set set)
218 (sob-copy set))
219
220 (define (bag-copy bag)
221 (check-bag bag)
222 (sob-copy bag))
223
224 ;; Construct an empty sob that shares the constructor of an existing sob.
225
226 (define (sob-empty-copy sob)
227 (make-sob (sob-comparator sob) (sob-multi? sob)))
228
229 ;; Construct a set or a bag and insert elements into it. These are the
230 ;; simplest external constructors.
231
232 (define (set comparator . elements)
233 (let ((result (make-sob comparator #f)))
234 (for-each (lambda (x) (sob-increment! result x 1)) elements)
235 result))
236
237 (define (bag comparator . elements)
238 (let ((result (make-sob comparator #t)))
239 (for-each (lambda (x) (sob-increment! result x 1)) elements)
240 result))
241
242 ;; The fundamental (as opposed to simplest) constructor: unfold the
243 ;; results of iterating a function as a set. In line with SRFI 1,
244 ;; we provide an opportunity to map the sequence of seeds through a
245 ;; mapper function.
246
247 (define (sob-unfold stop? mapper successor seed comparator multi?)
248 (let ((result (make-sob comparator multi?)))
249 (let loop ((seed seed))
250 (if (stop? seed)
251 result
252 (begin
253 (sob-increment! result (mapper seed) 1)
254 (loop (successor seed)))))))
255
256 (define (set-unfold continue? mapper successor seed comparator)
257 (sob-unfold continue? mapper successor seed comparator #f))
258
259 (define (bag-unfold continue? mapper successor seed comparator)
260 (sob-unfold continue? mapper successor seed comparator #t))
261
262 ;;; Predicates
263
264 ;; Just a wrapper of hash-table-contains?.
265
266 (define (sob-contains? sob member)
267 (hash-table-contains? (sob-hash-table sob) member))
268
269 (define (set-contains? set member)
270 (check-set set)
271 (sob-contains? set member))
272
273 (define (bag-contains? bag member)
274 (check-bag bag)
275 (sob-contains? bag member))
276
277 ;; A sob is empty if its size is 0.
278
279 (define (sob-empty? sob)
280 (= 0 (hash-table-size (sob-hash-table sob))))
281
282 (define (set-empty? set)
283 (check-set set)
284 (sob-empty? set))
285
286 (define (bag-empty? bag)
287 (check-bag bag)
288 (sob-empty? bag))
289
290 ;; Two sobs are disjoint if, when looping through one, we can't find
291 ;; any of its elements in the other. We have to try both ways:
292 ;; sob-half-disjoint checks just one direction for simplicity.
293
294 (define (sob-half-disjoint? a b)
295 (let ((ha (sob-hash-table a))
296 (hb (sob-hash-table b)))
297 (not (hash-table-find ha (^[k _] (hash-table-contains? hb k))))))
298
299 (define (set-disjoint? a b)
300 (check-set a)
301 (check-set b)
302 (check-same-comparator a b)
303 (and (sob-half-disjoint? a b) (sob-half-disjoint? b a)))
304
305 (define (bag-disjoint? a b)
306 (check-bag a)
307 (check-bag b)
308 (check-same-comparator a b)
309 (and (sob-half-disjoint? a b) (sob-half-disjoint? b a)))
310
311 ;; Accessors
312
313 ;; If two objects are indistinguishable by the comparator's
314 ;; equality procedure, only one of them will be represented in the sob.
315 ;; This procedure lets us find out which one it is; it will return
316 ;; the value stored in the sob that is equal to the element.
317 ;; Note that we have to search the whole hash table item by item.
318 ;; The default is returned if there is no such element.
319
320 (define (sob-member sob element default)
321 (define (same? a b) (=? (sob-comparator sob) a b))
322 (let1 r (hash-table-find (sob-hash-table sob)
323 (^[k v] (and (same? k element) (list k))))
324 (if (pair? r) (car r) default)))
325
326 (define (set-member set element default)
327 (check-set set)
328 (sob-member set element default))
329
330 (define (bag-member bag element default)
331 (check-bag bag)
332 (sob-member bag element default))
333
334 ;; Retrieve the comparator.
335
336 (define (set-element-comparator set)
337 (check-set set)
338 (sob-comparator set))
339
340 (define (bag-element-comparator bag)
341 (check-bag bag)
342 (sob-comparator bag))
343
344
345 ;; Updaters (pure functional and linear update)
346
347 ;; The primitive operation for adding an element to a sob.
348 ;; There are a few cases where we bypass this for efficiency.
349
350 (define (sob-increment! sob element count)
351 (check-element sob element)
352 (hash-table-update!/default
353 (sob-hash-table sob)
354 element
355 (if (sob-multi? sob)
356 (lambda (value) (+ value count))
357 (lambda (value) 1))
358 0))
359
360 ;; The primitive operation for removing an element from a sob. Note this
361 ;; procedure is incomplete: it allows the count of an element to drop below 1.
362 ;; Therefore, whenever it is used it is necessary to call sob-cleanup!
363 ;; to fix things up. This is done because it is unsafe to remove an
364 ;; object from a hash table while iterating through it.
365
366 (define (sob-decrement! sob element count)
367 (hash-table-update!/default
368 (sob-hash-table sob)
369 element
370 (lambda (value) (- value count))
371 0))
372
373 ;; This is the cleanup procedure, which happens in two passes: it
374 ;; iterates through the sob, deciding which elements to remove (those
375 ;; with non-positive counts), and collecting them in a list. When the
376 ;; iteration is done, it is safe to remove the elements using the list,
377 ;; because we are no longer iterating over the hash table. It returns
378 ;; its argument, because it is often tail-called at the end of some
379 ;; procedure that wants to return the clean sob.
380
381 (define (sob-cleanup! sob)
382 (let ((ht (sob-hash-table sob)))
383 (for-each (lambda (key) (hash-table-delete! ht key))
384 (nonpositive-keys ht))
385 sob))
386
387 (define (nonpositive-keys ht)
388 (let ((result '()))
389 (hash-table-for-each
390 (lambda (key value)
391 (when (<= value 0)
392 (set! result (cons key result))))
393 ht)
394 result))
395
396 ;; We expose these for bags but not sets.
397
398 (define (bag-increment! bag element count)
399 (check-bag bag)
400 (sob-increment! bag element count)
401 bag)
402
403 (define (bag-decrement! bag element count)
404 (check-bag bag)
405 (sob-decrement! bag element count)
406 (sob-cleanup! bag)
407 bag)
408
409 ;; The primitive operation to add elements from a list. We expose
410 ;; this two ways: with a list argument and with multiple arguments.
411
412 (define (sob-adjoin-all! sob elements)
413 (for-each
414 (lambda (elem)
415 (sob-increment! sob elem 1))
416 elements))
417
418 (define (set-adjoin! set . elements)
419 (check-set set)
420 (sob-adjoin-all! set elements)
421 set)
422
423 (define (bag-adjoin! bag . elements)
424 (check-bag bag)
425 (sob-adjoin-all! bag elements)
426 bag)
427
428
429 ;; These versions copy the set or bag before adjoining.
430
431 (define (set-adjoin set . elements)
432 (check-set set)
433 (let ((result (sob-copy set)))
434 (sob-adjoin-all! result elements)
435 result))
436
437 (define (bag-adjoin bag . elements)
438 (check-bag bag)
439 (let ((result (sob-copy bag)))
440 (sob-adjoin-all! result elements)
441 result))
442
443 ;; Given an element which resides in a set, this makes sure that the
444 ;; specified element is represented by the form given. Thus if a
445 ;; sob contains 2 and the equality predicate is =, then calling
446 ;; (sob-replace! sob 2.0) will replace the 2 with 2.0. Does nothing
447 ;; if there is no such element in the sob.
448
449 (define (sob-replace! sob element)
450 (let* ((comparator (sob-comparator sob))
451 (= (comparator-equality-predicate comparator))
452 (ht (sob-hash-table sob)))
453 (comparator-check-type comparator element)
454 (or (hash-table-find ht
455 (^[k v]
456 (and (= k element)
457 (begin
458 (hash-table-delete! ht k)
459 (hash-table-set! ht element v)
460 sob))))
461 sob)))
462
463 (define (set-replace! set element)
464 (check-set set)
465 (sob-replace! set element)
466 set)
467
468 (define (bag-replace! bag element)
469 (check-bag bag)
470 (sob-replace! bag element)
471 bag)
472
473 ;; Non-destructive versions that copy the set first. Yes, a little
474 ;; bit inefficient because it copies the element to be replaced before
475 ;; actually replacing it.
476
477 (define (set-replace set element)
478 (check-set set)
479 (let ((result (sob-copy set)))
480 (sob-replace! result element)
481 result))
482
483 (define (bag-replace bag element)
484 (check-bag bag)
485 (let ((result (sob-copy bag)))
486 (sob-replace! result element)
487 result))
488
489 ;; The primitive operation to delete elemnets from a list.
490 ;; Like sob-adjoin-all!, this is exposed two ways. It calls
491 ;; sob-cleanup! itself, so its callers don't need to (though it is safe
492 ;; to do so.)
493
494 (define (sob-delete-all! sob elements)
495 (for-each (lambda (element) (sob-decrement! sob element 1)) elements)
496 (sob-cleanup! sob)
497 sob)
498
499 (define (set-delete! set . elements)
500 (check-set set)
501 (sob-delete-all! set elements))
502
503 (define (bag-delete! bag . elements)
504 (check-bag bag)
505 (sob-delete-all! bag elements))
506
507 (define (set-delete-all! set elements)
508 (check-set set)
509 (sob-delete-all! set elements))
510
511 (define (bag-delete-all! bag elements)
512 (check-bag bag)
513 (sob-delete-all! bag elements))
514
515 ;; Non-destructive version copy first; this is inefficient.
516
517 (define (set-delete set . elements)
518 (check-set set)
519 (sob-delete-all! (sob-copy set) elements))
520
521 (define (bag-delete bag . elements)
522 (check-bag bag)
523 (sob-delete-all! (sob-copy bag) elements))
524
525 (define (set-delete-all set elements)
526 (check-set set)
527 (sob-delete-all! (sob-copy set) elements))
528
529 (define (bag-delete-all bag elements)
530 (check-bag bag)
531 (sob-delete-all! (sob-copy bag) elements))
532
533 ;; Flag used by sob-search! to represent a missing object.
534
535 (define missing (string-copy "missing"))
536
537 ;; Searches and then dispatches to user-defined procedures on failure
538 ;; and success, which in turn should reinvoke a procedure to take some
539 ;; action on the set (insert, ignore, replace, or remove).
540
541 (define (sob-search! sob element failure success)
542 (define (insert obj)
543 (sob-increment! sob element 1)
544 (values sob obj))
545 (define (ignore obj)
546 (values sob obj))
547 (define (update new-elem obj)
548 (sob-decrement! sob element 1)
549 (sob-increment! sob new-elem 1)
550 (values (sob-cleanup! sob) obj))
551 (define (remove obj)
552 (sob-decrement! sob element 1)
553 (values (sob-cleanup! sob) obj))
554 (let ((true-element (sob-member sob element missing)))
555 (if (eq? true-element missing)
556 (failure insert ignore)
557 (success true-element update remove))))
558
559 (define (set-search! set element failure success)
560 (check-set set)
561 (sob-search! set element failure success))
562
563 (define (bag-search! bag element failure success)
564 (check-bag bag)
565 (sob-search! bag element failure success))
566
567 ;; Return the size of a sob. If it's a set, we can just use the
568 ;; number of associations in the hash table, but if it's a bag, we
569 ;; have to add up the counts.
570
571 (define (sob-size sob)
572 (if (sob-multi? sob)
573 (let ((result 0))
574 (hash-table-for-each
575 (lambda (elem count) (set! result (+ count result)))
576 (sob-hash-table sob))
577 result)
578 (hash-table-size (sob-hash-table sob))))
579
580 (define (set-size set)
581 (check-set set)
582 (sob-size set))
583
584 (define (bag-size bag)
585 (check-bag bag)
586 (sob-size bag))
587
588 ;; Search a sob to find something that matches a predicate. You don't
589 ;; know which element you will get, so this is not as useful as finding
590 ;; an element in a list or other ordered container. If it's not there,
591 ;; call the failure thunk.
592
593 (define (sob-find pred sob failure)
594 (let1 r (hash-table-find (sob-hash-table sob)
595 (^[k _] (and (pred k) (list k))))
596 (if (pair? r) (car r) (failure))))
597
598 (define (set-find pred set failure)
599 (check-set set)
600 (sob-find pred set failure))
601
602 (define (bag-find pred bag failure)
603 (check-bag bag)
604 (sob-find pred bag failure))
605
606 ;; Count the number of elements in the sob that satisfy the predicate.
607 ;; This is a special case of folding.
608
609 (define (sob-count pred sob)
610 (sob-fold
611 (lambda (elem total) (if (pred elem) (+ total 1) total))
612 0
613 sob))
614
615 (define (set-count pred set)
616 (check-set set)
617 (sob-count pred set))
618
619 (define (bag-count pred bag)
620 (check-bag bag)
621 (sob-count pred bag))
622
623 ;; Check if any of the elements in a sob satisfy a predicate. Breaks out
624 ;; early (with call/cc) if a success is found.
625
626 (define (sob-any? pred sob)
627 (hash-table-find (sob-hash-table sob) (^[k _] (boolean (pred k)))))
628
629 (define (set-any? pred set)
630 (check-set set)
631 (sob-any? pred set))
632
633 (define (bag-any? pred bag)
634 (check-bag bag)
635 (sob-any? pred bag))
636
637 ;; Analogous to set-any?. Breaks out early if a failure is found.
638
639 (define (sob-every? pred sob)
640 (not (hash-table-find (sob-hash-table sob) (^[k _] (not (pred k))))))
641
642 (define (set-every? pred set)
643 (check-set set)
644 (sob-every? pred set))
645
646 (define (bag-every? pred bag)
647 (check-bag bag)
648 (sob-every? pred bag))
649
650
651 ;;; Mapping and folding
652
653 ;; A utility for iterating a command n times. This is used by sob-for-each
654 ;; to execute a procedure over the repeated elements in a bag. Because
655 ;; of the representation of sets, it works for them too.
656
657 (define (do-n-times cmd n)
658 (let loop ((n n))
659 (when (> n 0)
660 (cmd)
661 (loop (- n 1)))))
662
663 ;; Basic iterator over a sob.
664
665 (define (sob-for-each proc sob)
666 (hash-table-for-each
667 (lambda (key value) (do-n-times (lambda () (proc key)) value))
668 (sob-hash-table sob)))
669
670 (define (set-for-each proc set)
671 (check-set set)
672 (sob-for-each proc set))
673
674 (define (bag-for-each proc bag)
675 (check-bag bag)
676 (sob-for-each proc bag))
677
678 ;; Fundamental mapping operator. We map over the associations directly,
679 ;; because each instance of an element in a bag will be treated identically
680 ;; anyway; we insert them all at once with sob-increment!.
681
682 (define (sob-map comparator proc sob)
683 (let ((result (make-sob comparator (sob-multi? sob))))
684 (hash-table-for-each
685 (lambda (key value) (sob-increment! result (proc key) value))
686 (sob-hash-table sob))
687 result))
688
689 (define (set-map comparator proc set)
690 (check-set set)
691 (sob-map comparator proc set))
692
693 (define (bag-map comparator proc bag)
694 (check-bag bag)
695 (sob-map comparator proc bag))
696
697 ;; The fundamental deconstructor. Note that there are no left vs. right
698 ;; folds because there is no order. Each element in a bag is fed into
699 ;; the fold separately.
700
701 (define (sob-fold proc nil sob)
702 (let ((result nil))
703 (sob-for-each
704 (lambda (elem) (set! result (proc elem result)))
705 sob)
706 result))
707
708 (define (set-fold proc nil set)
709 (check-set set)
710 (sob-fold proc nil set))
711
712 (define (bag-fold proc nil bag)
713 (check-bag bag)
714 (sob-fold proc nil bag))
715
716 ;; Process every element and copy the ones that satisfy the predicate.
717 ;; Identical elements are processed all at once. This is used for both
718 ;; filter and remove.
719
720 (define (sob-filter pred sob)
721 (let ((result (sob-empty-copy sob)))
722 (hash-table-for-each
723 (lambda (key value)
724 (if (pred key) (sob-increment! result key value)))
725 (sob-hash-table sob))
726 result))
727
728 (define (set-filter pred set)
729 (check-set set)
730 (sob-filter pred set))
731
732 (define (bag-filter pred bag)
733 (check-bag bag)
734 (sob-filter pred bag))
735
736 (define (set-remove pred set)
737 (check-set set)
738 (sob-filter (lambda (x) (not (pred x))) set))
739
740 (define (bag-remove pred bag)
741 (check-bag bag)
742 (sob-filter (lambda (x) (not (pred x))) bag))
743
744 ;; Process each element and remove those that don't satisfy the filter.
745 ;; This does its own cleanup, and is used for both filter! and remove!.
746
747 (define (sob-filter! pred sob)
748 (hash-table-for-each
749 (lambda (key value)
750 (if (not (pred key)) (sob-decrement! sob key value)))
751 (sob-hash-table sob))
752 (sob-cleanup! sob))
753
754 (define (set-filter! pred set)
755 (check-set set)
756 (sob-filter! pred set))
757
758 (define (bag-filter! pred bag)
759 (check-bag bag)
760 (sob-filter! pred bag))
761
762 (define (set-remove! pred set)
763 (check-set set)
764 (sob-filter! (lambda (x) (not (pred x))) set))
765
766 (define (bag-remove! pred bag)
767 (check-bag bag)
768 (sob-filter! (lambda (x) (not (pred x))) bag))
769
770 ;; Create two sobs and copy the elements that satisfy the predicate into
771 ;; one of them, all others into the other. This is more efficient than
772 ;; filtering and removing separately.
773
774 (define (sob-partition pred sob)
775 (let ((res1 (sob-empty-copy sob))
776 (res2 (sob-empty-copy sob)))
777 (hash-table-for-each
778 (lambda (key value)
779 (if (pred key)
780 (sob-increment! res1 key value)
781 (sob-increment! res2 key value)))
782 (sob-hash-table sob))
783 (values res1 res2)))
784
785 (define (set-partition pred set)
786 (check-set set)
787 (sob-partition pred set))
788
789 (define (bag-partition pred bag)
790 (check-bag bag)
791 (sob-partition pred bag))
792
793 ;; Create a sob and iterate through the given sob. Anything that satisfies
794 ;; the predicate is left alone; anything that doesn't is removed from the
795 ;; given sob and added to the new sob.
796
797 (define (sob-partition! pred sob)
798 (let ((result (sob-empty-copy sob)))
799 (hash-table-for-each
800 (lambda (key value)
801 (if (not (pred key))
802 (begin
803 (sob-decrement! sob key value)
804 (sob-increment! result key value))))
805 (sob-hash-table sob))
806 (values (sob-cleanup! sob) result)))
807
808 (define (set-partition! pred set)
809 (check-set set)
810 (sob-partition! pred set))
811
812 (define (bag-partition! pred bag)
813 (check-bag bag)
814 (sob-partition! pred bag))
815
816
817 ;;; Copying and conversion
818
819 ;;; Convert a sob to a list; a special case of sob-fold.
820
821 (define (sob->list sob)
822 (sob-fold (lambda (elem list) (cons elem list)) '() sob))
823
824 (define (set->list set)
825 (check-set set)
826 (sob->list set))
827
828 (define (bag->list bag)
829 (check-bag bag)
830 (sob->list bag))
831
832 ;; Convert a list to a sob. Probably could be done using unfold, but
833 ;; since sobs are mutable anyway, it's just as easy to add the elements
834 ;; by side effect.
835
836 (define (list->sob! sob list)
837 (for-each (lambda (elem) (sob-increment! sob elem 1)) list)
838 sob)
839
840 (define (list->set comparator list)
841 (list->sob! (make-sob comparator #f) list))
842
843 (define (list->bag comparator list)
844 (list->sob! (make-sob comparator #t) list))
845
846 (define (list->set! set list)
847 (check-set set)
848 (list->sob! set list))
849
850 (define (list->bag! bag list)
851 (check-bag bag)
852 (list->sob! bag list))
853
854
855 ;;; Subsets
856
857 ;; All of these procedures follow the same pattern. The
858 ;; sob<op>? procedures are case-lambdas that reduce the multi-argument
859 ;; case to the two-argument case. As usual, the set<op>? and
860 ;; bag<op>? procedures are trivial layers over the sob<op>? procedure.
861 ;; The dyadic-sob<op>? procedures are where it gets interesting, so see
862 ;; the comments on them.
863
864 (define sob=?
865 (case-lambda
866 ((sob) #t)
867 ((sob1 sob2) (dyadic-sob=? sob1 sob2))
868 ((sob1 sob2 . sobs)
869 (and (dyadic-sob=? sob1 sob2)
870 (apply sob=? sob2 sobs)))))
871
872 (define (set=? . sets)
873 (check-all-sets sets)
874 (apply sob=? sets))
875
876 (define (bag=? . bags)
877 (check-all-bags bags)
878 (apply sob=? bags))
879
880 ;; First we check that there are the same number of entries in the
881 ;; hashtables of the two sobs; if that's not true, they can't be equal.
882 ;; Then we check that for each key, the values are the same (where
883 ;; being absent counts as a value of 0). If any values aren't equal,
884 ;; again they can't be equal.
885
886 (define (sob-table-compare op ht1 ht2)
887 (and (op (hash-table-size ht1) (hash-table-size ht2))
888 (not ($ hash-table-find ht1
889 (^[k v] (not (op v (hash-table-ref/default ht2 k 0))))))))
890
891 (define (dyadic-sob=? sob1 sob2)
892 (sob-table-compare = (sob-hash-table sob1) (sob-hash-table sob2)))
893
894 (define sob<=?
895 (case-lambda
896 ((sob) #t)
897 ((sob1 sob2) (dyadic-sob<=? sob1 sob2))
898 ((sob1 sob2 . sobs)
899 (and (dyadic-sob<=? sob1 sob2)
900 (apply sob<=? sob2 sobs)))))
901
902 (define (set<=? . sets)
903 (check-all-sets sets)
904 (apply sob<=? sets))
905
906 (define (bag<=? . bags)
907 (check-all-bags bags)
908 (apply sob<=? bags))
909
910 ;; This is analogous to dyadic-sob=?, except that we have to check
911 ;; both sobs to make sure each value is <= in order to be sure
912 ;; that we've traversed all the elements in either sob.
913
914 (define (dyadic-sob<=? sob1 sob2)
915 (sob-table-compare <= (sob-hash-table sob1) (sob-hash-table sob2)))
916
917 (define sob<?
918 (case-lambda
919 ((sob) #t)
920 ((sob1 sob2) (dyadic-sob<? sob1 sob2))
921 ((sob1 sob2 . sobs)
922 (and (dyadic-sob<? sob1 sob2)
923 (apply sob<? sob2 sobs)))))
924
925 (define (set<? . sets)
926 (check-all-sets sets)
927 (apply sob<? sets))
928
929 (define (bag<? . bags)
930 (check-all-bags bags)
931 (apply sob<? bags))
932
933
934 ;; < is a bit complicated - we can't just negate >=, since subset relationship
935 ;; is partial order. Neither does it follow the same pattern as = and <=,
936
937 (define (dyadic-sob<? sob1 sob2)
938 (let ([ht1 (sob-hash-table sob1)]
939 [ht2 (sob-hash-table sob2)])
940 (and-let* ([small-count
941 (cond [(= (hash-table-size ht1) (hash-table-size ht2)) 0]
942 [(< (hash-table-size ht1) (hash-table-size ht2)) 1]
943 [else #f])]
944 [(not ($ hash-table-find ht1
945 (^[k v]
946 (let1 v2 (hash-table-ref/default ht2 k 0)
947 (cond [(< v v2) (inc! small-count) #f]
948 [(> v v2) #t]
949 [else #f])))))])
950 (positive? small-count))))
951
952 (define sob>?
953 (case-lambda
954 ((sob) #t)
955 ((sob1 sob2) (dyadic-sob>? sob1 sob2))
956 ((sob1 sob2 . sobs)
957 (and (dyadic-sob>? sob1 sob2)
958 (apply sob>? sob2 sobs)))))
959
960 (define (set>? . sets)
961 (check-all-sets sets)
962 (apply sob>? sets))
963
964 (define (bag>? . bags)
965 (check-all-bags bags)
966 (apply sob>? bags))
967
968 ;; > is the inverse of <. this is only true dyadically.
969
970 (define (dyadic-sob>? sob1 sob2)
971 (dyadic-sob<? sob2 sob1))
972
973 (define sob>=?
974 (case-lambda
975 ((sob) #t)
976 ((sob1 sob2) (dyadic-sob>=? sob1 sob2))
977 ((sob1 sob2 . sobs)
978 (and (dyadic-sob>=? sob1 sob2)
979 (apply sob>=? sob2 sobs)))))
980
981 (define (set>=? . sets)
982 (check-all-sets sets)
983 (apply sob>=? sets))
984
985 (define (bag>=? . bags)
986 (check-all-bags bags)
987 (apply sob>=? bags))
988
989 ;; Finally, >= is the inverse of <=.
990
991 (define (dyadic-sob>=? sob1 sob2)
992 (dyadic-sob<=? sob2 sob1))
993
994
995 ;;; Set theory operations
996
997 ;; A trivial helper function which upper-bounds n by one if multi? is false.
998
999 (define (max-one n multi?)
1000 (if multi? n (if (> n 1) 1 n)))
1001
1002 ;; The logic of union, intersection, difference, and sum is the same: the
1003 ;; sob-* and sob-*! procedures do the reduction to the dyadic-sob-*!
1004 ;; procedures. The difference is that the sob-* procedures allocate
1005 ;; an empty copy of the first sob to accumulate the results in, whereas
1006 ;; the sob-*! procedures work directly in the first sob.
1007
1008 ;; Note that there is no set-sum, as it is the same as set-union.
1009
1010 (define (sob-union sob1 . sobs)
1011 (if (null? sobs)
1012 sob1
1013 (let ((result (sob-empty-copy sob1)))
1014 (dyadic-sob-union! result sob1 (car sobs))
1015 (for-each
1016 (lambda (sob) (dyadic-sob-union! result result sob))
1017 (cdr sobs))
1018 result)))
1019
1020 ;; For union, we take the max of the counts of each element found
1021 ;; in either sob and put that in the result. On the pass through
1022 ;; sob2, we know that the intersection is already accounted for,
1023 ;; so we just copy over things that aren't in sob1.
1024
1025 (define (dyadic-sob-union! result sob1 sob2)
1026 (let ((sob1-ht (sob-hash-table sob1))
1027 (sob2-ht (sob-hash-table sob2))
1028 (result-ht (sob-hash-table result)))
1029 (hash-table-for-each
1030 (lambda (key value1)
1031 (let ((value2 (hash-table-ref/default sob2-ht key 0)))
1032 (hash-table-set! result-ht key (max value1 value2))))
1033 sob1-ht)
1034 (hash-table-for-each
1035 (lambda (key value2)
1036 (let ((value1 (hash-table-ref/default sob1-ht key 0)))
1037 (if (= value1 0)
1038 (hash-table-set! result-ht key value2))))
1039 sob2-ht)))
1040
1041 (define (set-union . sets)
1042 (check-all-sets sets)
1043 (apply sob-union sets))
1044
1045 (define (bag-union . bags)
1046 (check-all-bags bags)
1047 (apply sob-union bags))
1048
1049 (define (sob-union! sob1 . sobs)
1050 (for-each
1051 (lambda (sob) (dyadic-sob-union! sob1 sob1 sob))
1052 sobs)
1053 sob1)
1054
1055 (define (set-union! . sets)
1056 (check-all-sets sets)
1057 (apply sob-union! sets))
1058
1059 (define (bag-union! . bags)
1060 (check-all-bags bags)
1061 (apply sob-union! bags))
1062
1063 (define (sob-intersection sob1 . sobs)
1064 (if (null? sobs)
1065 sob1
1066 (let ((result (sob-empty-copy sob1)))
1067 (dyadic-sob-intersection! result sob1 (car sobs))
1068 (for-each
1069 (lambda (sob) (dyadic-sob-intersection! result result sob))
1070 (cdr sobs))
1071 (sob-cleanup! result))))
1072
1073 ;; For intersection, we compute the min of the counts of each element.
1074 ;; We only have to scan sob1. We clean up the result when we are
1075 ;; done, in case it is the same as sob1.
1076
1077 (define (dyadic-sob-intersection! result sob1 sob2)
1078 (let ((sob1-ht (sob-hash-table sob1))
1079 (sob2-ht (sob-hash-table sob2))
1080 (result-ht (sob-hash-table result)))
1081 (hash-table-for-each
1082 (lambda (key value1)
1083 (let ((value2 (hash-table-ref/default sob2-ht key 0)))
1084 (hash-table-set! result-ht key (min value1 value2))))
1085 sob1-ht)))
1086
1087 (define (set-intersection . sets)
1088 (check-all-sets sets)
1089 (apply sob-intersection sets))
1090
1091 (define (bag-intersection . bags)
1092 (check-all-bags bags)
1093 (apply sob-intersection bags))
1094
1095 (define (sob-intersection! sob1 . sobs)
1096 (for-each
1097 (lambda (sob) (dyadic-sob-intersection! sob1 sob1 sob))
1098 sobs)
1099 (sob-cleanup! sob1))
1100
1101 (define (set-intersection! . sets)
1102 (check-all-sets sets)
1103 (apply sob-intersection! sets))
1104
1105 (define (bag-intersection! . bags)
1106 (check-all-bags bags)
1107 (apply sob-intersection! bags))
1108
1109 (define (sob-difference sob1 . sobs)
1110 (if (null? sobs)
1111 sob1
1112 (let ((result (sob-empty-copy sob1)))
1113 (dyadic-sob-difference! result sob1 (car sobs))
1114 (for-each
1115 (lambda (sob) (dyadic-sob-difference! result result sob))
1116 (cdr sobs))
1117 (sob-cleanup! result))))
1118
1119 ;; For difference, we use (big surprise) the numeric difference, bounded
1120 ;; by zero. We only need to scan sob1, but we clean up the result in
1121 ;; case it is the same as sob1.
1122
1123 (define (dyadic-sob-difference! result sob1 sob2)
1124 (let ((sob1-ht (sob-hash-table sob1))
1125 (sob2-ht (sob-hash-table sob2))
1126 (result-ht (sob-hash-table result)))
1127 (hash-table-for-each
1128 (lambda (key value1)
1129 (let ((value2 (hash-table-ref/default sob2-ht key 0)))
1130 (hash-table-set! result-ht key (- value1 value2))))
1131 sob1-ht)))
1132
1133 (define (set-difference . sets)
1134 (check-all-sets sets)
1135 (apply sob-difference sets))
1136
1137 (define (bag-difference . bags)
1138 (check-all-bags bags)
1139 (apply sob-difference bags))
1140
1141 (define (sob-difference! sob1 . sobs)
1142 (for-each
1143 (lambda (sob) (dyadic-sob-difference! sob1 sob1 sob))
1144 sobs)
1145 (sob-cleanup! sob1))
1146
1147 (define (set-difference! . sets)
1148 (check-all-sets sets)
1149 (apply sob-difference! sets))
1150
1151 (define (bag-difference! . bags)
1152 (check-all-bags bags)
1153 (apply sob-difference! bags))
1154
1155 (define (sob-sum sob1 . sobs)
1156 (if (null? sobs)
1157 sob1
1158 (let ((result (sob-empty-copy sob1)))
1159 (dyadic-sob-sum! result sob1 (car sobs))
1160 (for-each
1161 (lambda (sob) (dyadic-sob-sum! result result sob))
1162 (cdr sobs))
1163 result)))
1164
1165 ;; Sum is just like union, except that we take the sum rather than the max.
1166
1167 (define (dyadic-sob-sum! result sob1 sob2)
1168 (let ((sob1-ht (sob-hash-table sob1))
1169 (sob2-ht (sob-hash-table sob2))
1170 (result-ht (sob-hash-table result)))
1171 (hash-table-for-each
1172 (lambda (key value1)
1173 (let ((value2 (hash-table-ref/default sob2-ht key 0)))
1174 (hash-table-set! result-ht key (+ value1 value2))))
1175 sob1-ht)
1176 (hash-table-for-each
1177 (lambda (key value2)
1178 (let ((value1 (hash-table-ref/default sob1-ht key 0)))
1179 (if (= value1 0)
1180 (hash-table-set! result-ht key value2))))
1181 sob2-ht)))
1182
1183
1184 ;; Sum is defined for bags only; for sets, it is the same as union.
1185
1186 (define (bag-sum . bags)
1187 (check-all-bags bags)
1188 (apply sob-sum bags))
1189
1190 (define (sob-sum! sob1 . sobs)
1191 (for-each
1192 (lambda (sob) (dyadic-sob-sum! sob1 sob1 sob))
1193 sobs)
1194 sob1)
1195
1196 (define (bag-sum! . bags)
1197 (check-all-bags bags)
1198 (apply sob-sum! bags))
1199
1200 ;; For xor exactly two arguments are required, so the above structures are
1201 ;; not necessary. This version accepts a result sob and computes the
1202 ;; absolute difference between the counts in the first sob and the
1203 ;; corresponding counts in the second.
1204
1205 ;; We start by copying the entries in the second sob but not the first
1206 ;; into the first. Then we scan the first sob, computing the absolute
1207 ;; difference of the values and writing them back into the first sob.
1208 ;; It's essential to scan the second sob first, as we are not going to
1209 ;; damage it in the process. (Hat tip: Sam Tobin-Hochstadt.)
1210
1211 (define (sob-xor! result sob1 sob2)
1212 (let ((sob1-ht (sob-hash-table sob1))
1213 (sob2-ht (sob-hash-table sob2))
1214 (result-ht (sob-hash-table result)))
1215 (hash-table-for-each
1216 (lambda (key value2)
1217 (let ((value1 (hash-table-ref/default sob1-ht key 0)))
1218 (if (= value1 0)
1219 (hash-table-set! result-ht key value2))))
1220 sob2-ht)
1221 (hash-table-for-each
1222 (lambda (key value1)
1223 (let ((value2 (hash-table-ref/default sob2-ht key 0)))
1224 (hash-table-set! result-ht key (abs (- value1 value2)))))
1225 sob1-ht)
1226 (sob-cleanup! result)))
1227
1228 (define (set-xor set1 set2)
1229 (check-set set1)
1230 (check-set set2)
1231 (check-same-comparator set1 set2)
1232 (sob-xor! (sob-empty-copy set1) set1 set2))
1233
1234 (define (bag-xor bag1 bag2)
1235 (check-bag bag1)
1236 (check-bag bag2)
1237 (check-same-comparator bag1 bag2)
1238 (sob-xor! (sob-empty-copy bag1) bag1 bag2))
1239
1240 (define (set-xor! set1 set2)
1241 (check-set set1)
1242 (check-set set2)
1243 (check-same-comparator set1 set2)
1244 (sob-xor! set1 set1 set2))
1245
1246 (define (bag-xor! bag1 bag2)
1247 (check-bag bag1)
1248 (check-bag bag2)
1249 (check-same-comparator bag1 bag2)
1250 (sob-xor! bag1 bag1 bag2))
1251
1252
1253 ;;; A few bag-specific procedures
1254
1255 (define (sob-product! n result sob)
1256 (let ((rht (sob-hash-table result)))
1257 (hash-table-for-each
1258 (lambda (elem count) (hash-table-set! rht elem (* count n)))
1259 (sob-hash-table sob))
1260 result))
1261
1262 (define (valid-n n)
1263 (and (integer? n) (exact? n) (positive? n)))
1264
1265 (define (bag-product n bag)
1266 (check-bag bag)
1267 (valid-n n)
1268 (sob-product! n (sob-empty-copy bag) bag))
1269
1270 (define (bag-product! n bag)
1271 (check-bag bag)
1272 (valid-n n)
1273 (sob-product! n bag bag))
1274
1275 (define (bag-unique-size bag)
1276 (check-bag bag)
1277 (hash-table-size (sob-hash-table bag)))
1278
1279 (define (bag-element-count bag elem)
1280 (check-bag bag)
1281 (hash-table-ref/default (sob-hash-table bag) elem 0))
1282
1283 (define (bag-for-each-unique proc bag)
1284 (check-bag bag)
1285 (hash-table-for-each
1286 (lambda (key value) (proc key value))
1287 (sob-hash-table bag)))
1288
1289 (define (bag-fold-unique proc nil bag)
1290 (check-bag bag)
1291 (let ((result nil))
1292 (hash-table-for-each
1293 (lambda (elem count) (set! result (proc elem count result)))
1294 (sob-hash-table bag))
1295 result))
1296
1297 (define (bag->set bag)
1298 (check-bag bag)
1299 (let ((result (make-sob (sob-comparator bag) #f)))
1300 (hash-table-for-each
1301 (lambda (key value) (sob-increment! result key value))
1302 (sob-hash-table bag))
1303 result))
1304
1305 (define (set->bag set)
1306 (check-set set)
1307 (let ((result (make-sob (sob-comparator set) #t)))
1308 (hash-table-for-each
1309 (lambda (key value) (sob-increment! result key value))
1310 (sob-hash-table set))
1311 result))
1312
1313 (define (set->bag! bag set)
1314 (check-bag bag)
1315 (check-set set)
1316 (check-same-comparator set bag)
1317 (hash-table-for-each
1318 (lambda (key value) (sob-increment! bag key value))
1319 (sob-hash-table set))
1320 bag)
1321
1322 (define (bag->alist bag)
1323 (check-bag bag)
1324 (bag-fold-unique
1325 (lambda (elem count list) (cons (cons elem count) list))
1326 '()
1327 bag))
1328
1329 (define (alist->bag comparator alist)
1330 (let* ((result (bag comparator))
1331 (ht (sob-hash-table result)))
1332 (for-each
1333 (lambda (assoc)
1334 (let ((element (car assoc)))
1335 (if (not (hash-table-contains? ht element))
1336 (sob-increment! result element (cdr assoc)))))
1337 alist)
1338 result))
1339
1340 ;;; Comparators
1341
1342 ;; Hash over sobs
1343 (define (sob-hash sob)
1344 (let ((hash (comparator-hash-function (sob-comparator sob))))
1345 (sob-fold
1346 (lambda (element result) (logxor (hash element) result))
1347 5381
1348 sob)))
1349
1350 ;; Set and bag comparator
1351
1352 (define set-comparator (make-comparator set? set=? #f sob-hash 'set-comparator))
1353
1354 (define bag-comparator (make-comparator bag? bag=? #f sob-hash 'bag-comparator))
1355
1356 ;;; Register above comparators for use by default-comparator
1357 ;; (comparator-register-default! set-comparator)
1358 ;; (comparator-register-default! bag-comparator)
1359
1360 ;;; Set/bag printer (for debugging)
1361
1362 ;; (define (sob-print sob port)
1363 ;; (display (if (sob-multi? sob) "&bag[" "&set[") port)
1364 ;; (sob-for-each
1365 ;; (lambda (elem) (display " " port) (write elem port))
1366 ;; sob)
1367 ;; (display " ]" port))
1368
1369 ;; ;; Chicken-specific
1370 ;; (cond-expand
1371 ;; (chicken
1372 ;; (define-record-printer sob sob-print))
1373 ;; (else))