| 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)) |