Artifact
6df590667d079315dec8d1e1ccc134fd9a17134b:
- File
srfi/s113/sets.sls
— part of check-in
[07be5132aa]
at
2017-01-11 16:37:00
on branch trunk
— added srfi 113 sets&bags, srfi 128 comparators
(user:
aldo
size: 1842)
0000: 28 6c 69 62 72 61 72 79 20 28 73 72 66 69 20 73 (library (srfi s
0010: 31 31 33 20 73 65 74 73 29 0a 20 20 28 65 78 70 113 sets). (exp
0020: 6f 72 74 20 73 65 74 20 73 65 74 2d 75 6e 66 6f ort set set-unfo
0030: 6c 64 0a 09 20 20 73 65 74 3f 20 73 65 74 2d 63 ld.. set? set-c
0040: 6f 6e 74 61 69 6e 73 3f 20 73 65 74 2d 65 6d 70 ontains? set-emp
0050: 74 79 3f 20 73 65 74 2d 64 69 73 6a 6f 69 6e 74 ty? set-disjoint
0060: 3f 0a 09 20 20 65 78 70 6f 72 74 20 73 65 74 2d ?.. export set-
0070: 6d 65 6d 62 65 72 20 73 65 74 2d 65 6c 65 6d 65 member set-eleme
0080: 6e 74 2d 63 6f 6d 70 61 72 61 74 6f 72 0a 09 20 nt-comparator..
0090: 20 73 65 74 2d 61 64 6a 6f 69 6e 20 73 65 74 2d set-adjoin set-
00a0: 61 64 6a 6f 69 6e 21 20 73 65 74 2d 72 65 70 6c adjoin! set-repl
00b0: 61 63 65 20 73 65 74 2d 72 65 70 6c 61 63 65 21 ace set-replace!
00c0: 0a 09 20 20 73 65 74 2d 64 65 6c 65 74 65 20 73 .. set-delete s
00d0: 65 74 2d 64 65 6c 65 74 65 21 20 73 65 74 2d 64 et-delete! set-d
00e0: 65 6c 65 74 65 2d 61 6c 6c 20 73 65 74 2d 64 65 elete-all set-de
00f0: 6c 65 74 65 2d 61 6c 6c 21 20 73 65 74 2d 73 65 lete-all! set-se
0100: 61 72 63 68 21 0a 09 20 20 73 65 74 2d 73 69 7a arch!.. set-siz
0110: 65 20 73 65 74 2d 66 69 6e 64 20 73 65 74 2d 63 e set-find set-c
0120: 6f 75 6e 74 20 73 65 74 2d 61 6e 79 3f 20 73 65 ount set-any? se
0130: 74 2d 65 76 65 72 79 3f 0a 09 20 20 73 65 74 2d t-every?.. set-
0140: 6d 61 70 20 73 65 74 2d 66 6f 72 2d 65 61 63 68 map set-for-each
0150: 20 73 65 74 2d 66 6f 6c 64 0a 09 20 20 73 65 74 set-fold.. set
0160: 2d 66 69 6c 74 65 72 20 73 65 74 2d 72 65 6d 6f -filter set-remo
0170: 76 65 20 73 65 74 2d 72 65 6d 6f 76 65 20 73 65 ve set-remove se
0180: 74 2d 70 61 72 74 69 74 69 6f 6e 0a 09 20 20 73 t-partition.. s
0190: 65 74 2d 66 69 6c 74 65 72 21 20 73 65 74 2d 72 et-filter! set-r
01a0: 65 6d 6f 76 65 21 20 73 65 74 2d 70 61 72 74 69 emove! set-parti
01b0: 74 69 6f 6e 21 0a 09 20 20 73 65 74 2d 63 6f 70 tion!.. set-cop
01c0: 79 20 73 65 74 2d 3e 6c 69 73 74 20 6c 69 73 74 y set->list list
01d0: 2d 3e 73 65 74 20 6c 69 73 74 2d 3e 73 65 74 21 ->set list->set!
01e0: 0a 09 20 20 73 65 74 3d 3f 20 73 65 74 3c 3f 20 .. set=? set<?
01f0: 73 65 74 3e 3f 20 73 65 74 3c 3d 3f 20 73 65 74 set>? set<=? set
0200: 3e 3d 3f 0a 09 20 20 73 65 74 2d 75 6e 69 6f 6e >=?.. set-union
0210: 20 73 65 74 2d 69 6e 74 65 72 73 65 63 74 69 6f set-intersectio
0220: 6e 20 73 65 74 2d 64 69 66 66 65 72 65 6e 63 65 n set-difference
0230: 20 73 65 74 2d 78 6f 72 0a 09 20 20 73 65 74 2d set-xor.. set-
0240: 75 6e 69 6f 6e 21 20 73 65 74 2d 69 6e 74 65 72 union! set-inter
0250: 73 65 63 74 69 6f 6e 21 20 73 65 74 2d 64 69 66 section! set-dif
0260: 66 65 72 65 6e 63 65 21 20 73 65 74 2d 78 6f 72 ference! set-xor
0270: 21 0a 09 20 20 73 65 74 2d 63 6f 6d 70 61 72 61 !.. set-compara
0280: 74 6f 72 0a 09 20 20 0a 09 20 20 62 61 67 20 62 tor.. .. bag b
0290: 61 67 2d 75 6e 66 6f 6c 64 0a 09 20 20 62 61 67 ag-unfold.. bag
02a0: 3f 20 62 61 67 2d 63 6f 6e 74 61 69 6e 73 3f 20 ? bag-contains?
02b0: 62 61 67 2d 65 6d 70 74 79 3f 20 62 61 67 2d 64 bag-empty? bag-d
02c0: 69 73 6a 6f 69 6e 74 3f 0a 09 20 20 62 61 67 2d isjoint?.. bag-
02d0: 6d 65 6d 62 65 72 20 62 61 67 2d 65 6c 65 6d 65 member bag-eleme
02e0: 6e 74 2d 63 6f 6d 70 61 72 61 74 6f 72 0a 09 20 nt-comparator..
02f0: 20 62 61 67 2d 61 64 6a 6f 69 6e 20 62 61 67 2d bag-adjoin bag-
0300: 61 64 6a 6f 69 6e 21 20 62 61 67 2d 72 65 70 6c adjoin! bag-repl
0310: 61 63 65 20 62 61 67 2d 72 65 70 6c 61 63 65 21 ace bag-replace!
0320: 0a 09 20 20 62 61 67 2d 64 65 6c 65 74 65 20 62 .. bag-delete b
0330: 61 67 2d 64 65 6c 65 74 65 21 20 62 61 67 2d 64 ag-delete! bag-d
0340: 65 6c 65 74 65 2d 61 6c 6c 20 62 61 67 2d 64 65 elete-all bag-de
0350: 6c 65 74 65 2d 61 6c 6c 21 20 62 61 67 2d 73 65 lete-all! bag-se
0360: 61 72 63 68 21 0a 09 20 20 62 61 67 2d 73 69 7a arch!.. bag-siz
0370: 65 20 62 61 67 2d 66 69 6e 64 20 62 61 67 2d 63 e bag-find bag-c
0380: 6f 75 6e 74 20 62 61 67 2d 61 6e 79 3f 20 62 61 ount bag-any? ba
0390: 67 2d 65 76 65 72 79 3f 0a 09 20 20 62 61 67 2d g-every?.. bag-
03a0: 6d 61 70 20 62 61 67 2d 66 6f 72 2d 65 61 63 68 map bag-for-each
03b0: 20 62 61 67 2d 66 6f 6c 64 0a 09 20 20 62 61 67 bag-fold.. bag
03c0: 2d 66 69 6c 74 65 72 20 62 61 67 2d 72 65 6d 6f -filter bag-remo
03d0: 76 65 20 62 61 67 2d 70 61 72 74 69 74 69 6f 6e ve bag-partition
03e0: 0a 09 20 20 62 61 67 2d 66 69 6c 74 65 72 21 20 .. bag-filter!
03f0: 62 61 67 2d 72 65 6d 6f 76 65 21 20 62 61 67 2d bag-remove! bag-
0400: 70 61 72 74 69 74 69 6f 6e 21 0a 09 20 20 62 61 partition!.. ba
0410: 67 2d 63 6f 70 79 20 62 61 67 2d 3e 6c 69 73 74 g-copy bag->list
0420: 20 6c 69 73 74 2d 3e 62 61 67 20 6c 69 73 74 2d list->bag list-
0430: 3e 62 61 67 21 0a 09 20 20 62 61 67 3d 3f 20 62 >bag!.. bag=? b
0440: 61 67 3c 3f 20 62 61 67 3e 3f 20 62 61 67 3c 3d ag<? bag>? bag<=
0450: 3f 20 62 61 67 3e 3d 3f 0a 09 20 20 62 61 67 2d ? bag>=?.. bag-
0460: 75 6e 69 6f 6e 20 62 61 67 2d 69 6e 74 65 72 73 union bag-inters
0470: 65 63 74 69 6f 6e 20 62 61 67 2d 64 69 66 66 65 ection bag-diffe
0480: 72 65 6e 63 65 20 62 61 67 2d 78 6f 72 0a 09 20 rence bag-xor..
0490: 20 62 61 67 2d 75 6e 69 6f 6e 21 20 62 61 67 2d bag-union! bag-
04a0: 69 6e 74 65 72 73 65 63 74 69 6f 6e 21 20 62 61 intersection! ba
04b0: 67 2d 64 69 66 66 65 72 65 6e 63 65 21 20 62 61 g-difference! ba
04c0: 67 2d 78 6f 72 21 0a 09 20 20 62 61 67 2d 63 6f g-xor!.. bag-co
04d0: 6d 70 61 72 61 74 6f 72 0a 09 20 20 62 61 67 2d mparator.. bag-
04e0: 73 75 6d 20 62 61 67 2d 73 75 6d 21 20 62 61 67 sum bag-sum! bag
04f0: 2d 70 72 6f 64 75 63 74 20 62 61 67 2d 70 72 6f -product bag-pro
0500: 64 75 63 74 21 0a 09 20 20 62 61 67 2d 75 6e 69 duct!.. bag-uni
0510: 71 75 65 2d 73 69 7a 65 20 62 61 67 2d 65 6c 65 que-size bag-ele
0520: 6d 65 6e 74 2d 63 6f 75 6e 74 20 62 61 67 2d 66 ment-count bag-f
0530: 6f 72 2d 65 61 63 68 2d 75 6e 69 71 75 65 20 62 or-each-unique b
0540: 61 67 2d 66 6f 6c 64 2d 75 6e 69 71 75 65 0a 09 ag-fold-unique..
0550: 20 20 62 61 67 2d 69 6e 63 72 65 6d 65 6e 74 21 bag-increment!
0560: 20 62 61 67 2d 64 65 63 72 65 6d 65 6e 74 21 20 bag-decrement!
0570: 62 61 67 2d 3e 73 65 74 20 73 65 74 2d 3e 62 61 bag->set set->ba
0580: 67 20 73 65 74 2d 3e 62 61 67 21 0a 09 20 20 62 g set->bag!.. b
0590: 61 67 2d 3e 61 6c 69 73 74 20 61 6c 69 73 74 2d ag->alist alist-
05a0: 3e 62 61 67 29 0a 0a 20 20 28 69 6d 70 6f 72 74 >bag).. (import
05b0: 20 28 65 78 63 65 70 74 20 28 63 68 65 7a 73 63 (except (chezsc
05c0: 68 65 6d 65 29 20 6d 61 6b 65 2d 68 61 73 68 2d heme) make-hash-
05d0: 74 61 62 6c 65 20 64 65 66 69 6e 65 2d 72 65 63 table define-rec
05e0: 6f 72 64 2d 74 79 70 65 20 68 61 73 68 2d 74 61 ord-type hash-ta
05f0: 62 6c 65 2d 66 6f 72 2d 65 61 63 68 29 0a 09 20 ble-for-each)..
0600: 20 28 6f 6e 6c 79 20 28 73 72 66 69 20 73 39 20 (only (srfi s9
0610: 72 65 63 6f 72 64 73 29 20 64 65 66 69 6e 65 2d records) define-
0620: 72 65 63 6f 72 64 2d 74 79 70 65 29 29 0a 20 20 record-type)).
0630: 28 69 6d 70 6f 72 74 20 28 73 72 66 69 20 73 30 (import (srfi s0
0640: 20 63 6f 6e 64 2d 65 78 70 61 6e 64 29 29 0a 20 cond-expand)).
0650: 20 28 69 6d 70 6f 72 74 20 28 73 72 66 69 20 70 (import (srfi p
0660: 72 69 76 61 74 65 20 69 6e 63 6c 75 64 65 29 29 rivate include))
0670: 0a 20 20 28 69 6d 70 6f 72 74 20 28 65 78 63 65 . (import (exce
0680: 70 74 20 28 73 72 66 69 20 73 36 39 20 62 61 73 pt (srfi s69 bas
0690: 69 63 2d 68 61 73 68 2d 74 61 62 6c 65 73 29 0a ic-hash-tables).
06a0: 09 09 20 20 68 61 73 68 2d 74 61 62 6c 65 3f 20 .. hash-table?
06b0: 73 74 72 69 6e 67 2d 68 61 73 68 20 73 74 72 69 string-hash stri
06c0: 6e 67 2d 63 69 2d 68 61 73 68 29 29 0a 20 20 28 ng-ci-hash)). (
06d0: 69 6d 70 6f 72 74 20 28 73 72 66 69 20 73 31 32 import (srfi s12
06e0: 38 20 63 6f 6d 70 61 72 61 74 6f 72 73 29 29 0a 8 comparators)).
06f0: 20 20 28 69 6e 63 6c 75 64 65 2f 72 65 73 6f 6c (include/resol
0700: 76 65 20 28 22 73 72 66 69 22 20 22 73 31 31 33 ve ("srfi" "s113
0710: 22 29 20 22 73 65 74 73 2d 69 6d 70 6c 2e 73 63 ") "sets-impl.sc
0720: 6d 22 29 0a 29 20 3b 20 6c 69 62 72 61 72 79 0a m").) ; library.
0730: 0a 0a ..