You can edit this page using wiki syntax for markup.

Article contents:== SRFI-217: Integer Sets Integer sets, or ''isets'', are unordered collections of fixnums. This egg provides the SRFI 217 sample implementation of integer sets. [[toc:]] == SRFI Description This page includes excerpts from the [[https://srfi.schemers.org/srfi-217/srfi-217.html|SRFI 217 document]], but is primarily intended to document the forms exported by the egg. See the original document for a full description of the SRFI. == (srfi 217) vs. iset This egg provides a larger interface than the [[iset]] egg, and has substantial differences in implementation. The representation of integer sets used by this egg is by big-endian radix trees, as described by Chris Okasaki and Andrew Gill. These trees are self-balancing and provide fast lookup, insertion, and (especially) set-theoretical operations. To increase space efficiency, bitmap compression of leaves is used. This implementation approach is identical to that used by Haskell's IntMap library. In contrast, the iset egg uses a space-optimized binary tree representation which requires manual balancing to maintain consistent time efficiency. This may be preferable when space efficiency is crucial, or when insertion and set theory operations are expected to be rare. == Specification Isets are disjoint from other types of Scheme objects. === Linear update This egg provides the linear-update forms of SRFI 217 (indicated by the {{!}} suffix), but they are identical to their "normal" variants. === Constructors <procedure>(iset element … ) → iset</procedure> Returns a newly allocated iset. The ''elements'' are used to initialize the iset. Example: (iset->list (iset 2 3 5 7 11)) ⇒ (2 3 5 7 11) (iset->list (iset)) ⇒ () <procedure>(iset-unfold stop? mapper successor seed) → iset</procedure> Create a newly allocated iset as if by {{iset}}. If the result of applying the predicate ''stop?'' to ''seed'' is true, return the iset. Otherwise, apply the procedure ''mapper'' to ''seed''. The value that ''mapper'' returns is added to the iset. Then get a new seed by applying the procedure ''successor'' to ''seed'', and repeat this algorithm. Examples: (iset->list (iset-unfold (lambda (n) (> n 64)) values (lambda (n) (* n 2)) 2)) ⇒ (2 4 8 16 32 64) <procedure>(make-range-iset start end [step]) → iset</procedure> Returns a newly allocated iset specified by an inclusive lower bound ''start'', an exclusive upper bound ''end'', and a ''step'' value (default 1), all of which are exact integers. This constructor produces an iset containing the sequence start, (+ start step), (+ start (* 2 step)), …, (+ start (* n step)) where ''n'' is the greatest integer such that {{(+ start (* n step))}} < ''end'' if ''step'' is positive, or such that {{(+ start (* n step))}} > ''end'' if ''step'' is negative. It is an error if ''step'' is zero. Examples: (iset->list (make-range-iset 25 30)) ⇒ (25 26 27 28 29) (iset->list (make-range-iset -10 10 6)) ⇒ (-10 -4 2 8) === Predicates <procedure>(iset? obj) → boolean</procedure> Returns {{#t}} if ''obj'' is a iset, and {{#f}} otherwise. <procedure>(iset-contains? iset element) → boolean</procedure> Returns {{#t}} if ''element'' is a member of ''iset'' and {{#f}} otherwise. Examples: (iset-contains? (iset 2 3 5 7 11) 5) ⇒ #t (iset-contains? (iset 2 3 5 7 11) 4) ⇒ #f <procedure>(iset-empty? iset) → boolean</procedure> Returns {{#t}} if ''iset'' has no elements and {{#f}} otherwise. Examples: (iset-empty? (iset 2 3 5 7 11)) ⇒ #f (iset-empty? (iset)) ⇒ #t <procedure>(iset-disjoint? iset1 iset2) → boolean</procedure> Returns {{#t}} if ''iset1'' and ''iset2'' have no elements in common and {{#f}} otherwise. Examples: (iset-disjoint? (iset 1 3 5) (iset 0 2 4)) ⇒ #t (iset-disjoint? (iset 1 3 5) (iset 2 3 4)) ⇒ #f === Accessors <procedure>(iset-member iset element default) → integer-or-#f</procedure> Returns the element of ''iset'' that is equal to ''element''. If ''element'' is not a member of ''iset'', ''default'' is returned. Examples: (iset-member (iset 2 3 5 7 11) 7 #f) ⇒ 7 (iset-member (iset 2 3 5 7 11) 4 'failure) ⇒ failure <procedure>(iset-min iset) → integer-or-#f</procedure> <procedure>(iset-max iset) → integer-or-#f</procedure> Returns the smallest or largest integer in ''iset'', or {{#f}} if there is none. Examples: (iset-min (iset 2 3 5 7 11)) ⇒ 2 (iset-max (iset 2 3 5 7 11)) ⇒ 11 (iset-max (iset)) ⇒ #f === Updaters <procedure>(iset-adjoin iset element1 element2 …) → iset</procedure> The `iset-adjoin` procedure returns a newly allocated iset that contains all the values of ''iset'', and in addition each ''element'' unless it is already equal to one of the existing or newly added members. Examples: (iset->list (iset-adjoin (iset 1 3 5) 0)) ⇒ (0 1 3 5) <procedure>(iset-adjoin! iset element1 element2 …)</procedure> The `iset-adjoin!` procedure is the same as `iset-adjoin`, except that it is permitted to mutate and return the ''iset'' argument rather than allocating a new iset. <procedure>(iset-delete iset element1 element2 …) → iset</procedure> <procedure>(iset-delete! iset element1 element2 …) → iset</procedure> <procedure>(iset-delete-all iset element-list) → iset</procedure> <procedure>(iset-delete-all! iset element-list) → iset</procedure> The {{iset-delete}} procedure returns a newly allocated iset containing all the values of ''iset'' except for any that are equal to one or more of the ''elements''. Any ''element'' that is not equal to some member of the iset is ignored. The {{iset-delete!}} procedure is the same as {{iset-delete}}, except that it is permitted to mutate and return the ''iset'' argument rather than allocating a new iset. The {{iset-delete-all}} and {{iset-delete-all!}} procedures are the same as {{iset-delete}} and {{iset-delete!}}, except that they accept a single argument which is a list of elements to be deleted. Examples: (iset->list (iset-delete (iset 1 3 5) 3)) ⇒ (1 5) (iset->list (iset-delete-all (iset 2 3 5 7 11) '(3 4 5))) ⇒ (2 7 11) <procedure>(iset-delete-min iset) → [integer, iset]</procedure> <procedure>(iset-delete-min! iset) → [integer, iset]</procedure> <procedure>(iset-delete-max iset) → [integer, iset]</procedure> <procedure>(iset-delete-max! iset) → [integer, iset]</procedure> Returns two values: the smallest/largest integer ''n'' in ''iset'' and a newly-allocated iset that contains all elements of ''iset'' except for ''n''. It is an error if ''iset'' is empty. The {{iset-delete-min!}} and {{iset-delete-max!}} procedures are the same as {{iset-delete-min}} and {{iset-delete-max}}, respectively, except that they are permitted to mutate and return the ''iset'' argument instead of allocating a new iset. Examples: (let-values (((n set) (iset-delete-min (iset 2 3 5 7 11)))) (list n (iset->list set))) ⇒ (2 (3 5 7 11)) (let-values (((n set) (iset-delete-max (iset 2 3 5 7 11)))) (list n (iset->list set))) ⇒ (11 (2 3 5 7)) <procedure>(iset-search iset element failure success) → iset</procedure> The ''iset'' is searched from lowest to highest value for ''element''. If it is not found, then the ''failure'' procedure is tail-called with two continuation arguments, ''insert'' and ''ignore'', and is expected to tail-call one of them. If ''element'' is found, then the ''success'' procedure is tail-called with the matching element of ''iset'' and two continuations, ''update'' and ''remove'', and is expected to tail-call one of them. The effects of the continuations are as follows (where ''obj'' is any Scheme object): * Invoking {{(insert obj)}} causes ''element'' to be inserted into ''iset''. * Invoking {{(ignore obj)}} causes ''iset'' to remain unchanged. * Invoking {{(update new-element obj)}} causes ''new-element'' to be inserted into ''iset'' in place of ''element''. * Invoking {{(remove obj)}} causes the matching element of ''iset'' to be removed from it. In all cases, two values are returned: a newly allocated iset and ''obj''. <procedure>(iset-search! iset element failure success) → iset</procedure> The `iset-search!` procedure is the same as `iset-search`, except that it is permitted to mutate and return the ''iset'' argument rather than allocating a new iset. === The whole iset <procedure>(iset-size iset) → integer</procedure> Returns the number of elements in ''iset'' as an exact integer. Example: (iset-size (iset 1 3 5)) ⇒ 3 <procedure>(iset-find predicate iset failure) → integer-or-*</procedure> Returns the smallest element of ''iset'' that satisfies ''predicate'', or the result of invoking ''failure'' with no arguments if there is none. Examples: (iset-find positive? (iset -1 1) (lambda () #f)) ⇒ 1 (iset-find zero? (iset -1 1) (lambda () #f)) ⇒ #f <procedure>(iset-count predicate iset) → integer</procedure> Returns the number of elements of ''iset'' that satisfy ''predicate'' as an exact integer. Example: (iset-count positive? (iset -2 -1 1 2)) ⇒ 2 <procedure>(iset-any? predicate iset) → boolean</procedure> Returns {{#t}} if any element of ''iset'' satisfies ''predicate'', or {{#f}} otherwise. Note that this differs from the [[https://srfi.schemers.org/srfi-1/srfi-1.html|SRFI 1]] analogue because it does not return an element of the iset. Examples: (iset-any? positive? (iset -2 -1 1 2)) ⇒ #t (iset-any? zero? (iset -2 -1 1 2)) ⇒ #f <procedure>(iset-every? predicate iset) → boolean</procedure> Returns {{#t}} if every element of ''iset'' satisfies ''predicate'', or {{#f}} otherwise. Note that this differs from the SRFI 1 analogue because it does not return an element of the iset. Examples: (iset-every? (lambda (x) (< x 5)) (iset -2 -1 1 2)) ⇒ #t (iset-every? positive? (iset -2 -1 1 2)) ⇒ #f === Mapping and folding <procedure>(iset-map proc iset) → iset</procedure> ''proc'' must be an argument of type {{exact-integer → exact-integer}}. Applies ''proc'' to each element of ''iset'' in arbitrary order and returns a newly allocated iset, created as if by {{iset}}, which contains the results of the applications. Examples: (iset-map (lambda (x) (* 10 x)) (iset 1 11 21)) ⇒ (iset 10 110 210) (iset-map (lambda (x) (quotient x 2)) (iset 1 2 3 4 5)) ⇒ (iset 0 1 2) <procedure>(iset-for-each proc iset) → unspecified</procedure> Applies ''proc'' to ''iset'' in increasing numerical order, discarding the returned values. Example: (let ((sum 0)) (iset-for-each (lambda (x) (set! sum (+ sum x))) (iset 2 3 5 7 11)) sum) ⇒ 28 <procedure>(iset-fold proc nil iset) → *</procedure> <procedure>(iset-fold-right proc nil iset) → *</procedure> Invokes ''proc'' on each member of ''iset'' in increasing/decreasing numerical order, passing the result of the previous invocation as a second argument. For the first invocation, ''nil'' is used as the second argument. Returns the result of the last invocation, or ''nil'' if there was no invocation. Examples: (iset-fold + 0 (iset 2 3 5 7 11)) ⇒ 28 (iset-fold cons '() (iset 2 3 5 7 11)) ⇒ (11 7 5 3 2) (iset-fold-right cons '() (iset 2 3 5 7 11)) ⇒ (2 3 5 7 11) <procedure>(iset-filter predicate iset) → iset</procedure> Returns a newly allocated iset containing just the elements of ''iset'' that satisfy ''predicate''. Example: (iset->list (iset-filter (lambda (x) (< x 6)) (iset 2 3 5 7 11))) ⇒ (2 3 5) <procedure>(iset-filter! predicate iset) → iset</procedure> A linear update procedure that returns a iset containing just the elements of ''iset'' that satisfy ''predicate''. <procedure>(iset-remove predicate iset) → iset</procedure> Returns a newly allocated iset containing just the elements of ''iset'' that do not satisfy ''predicate''. Example: (iset->list (iset-remove (lambda (x) (< x 6)) (iset 2 3 5 7 11))) ⇒ (7 11) <procedure>(iset-remove! predicate iset) → iset</procedure> A linear update procedure that returns a iset containing just the elements of ''iset'' that do not satisfy ''predicate''. <procedure>(iset-partition predicate iset) → [iset, iset]</procedure> Returns two values: a newly allocated iset that contains just the elements of ''iset'' that satisfy ''predicate'' and another newly allocated iset that contains just the elements of ''iset'' that do not satisfy ''predicate''. Example: (let-values (((low high) (iset-partition (lambda (x) (< x 6)) (iset 2 3 5 7 11)))) (list (iset->list low) (iset->list high))) ⇒ ((2 3 5) (7 11)) <procedure>(iset-partition! predicate iset) → [iset, iset]</procedure> A linear update procedure that returns two isets containing the elements of ''iset'' that do and do not, respectively, not satisfy ''predicate''. === Copying and conversion <procedure>(iset-copy iset) → iset</procedure> Returns a newly allocated iset containing the elements of ''iset''. <procedure>(iset->list iset) → list[integer]</procedure> Returns a newly allocated list containing the members of ''iset'' in increasing numerical order. Example: (iset->list (iset 2 3 5 7 11)) ⇒ (2 3 5 7 11) <procedure>(list->iset list) → iset</procedure> Returns a newly allocated iset, created as if by {{iset}}, that contains the elements of ''list''. Duplicate elements are omitted. Example: (list->iset '(-3 -1 0 2)) = (iset -3 -1 0 2) <procedure>(list->iset! iset list) → iset</procedure> Returns a iset that contains the elements of both ''iset'' and ''list''. Duplicate elements are omitted. {{list->iset!}} may mutate ''iset'' rather than allocating a new iset. Example: (iset->list (list->iset! (iset 2 3 5) '(-3 -1 0))) ⇒ (-3 -1 0 2 3 5) === Subsets Note: None of these predicates produces a total order on isets. In particular, {{iset=?}}, {{iset<?}}, and {{iset>?}} do not obey the trichotomy law. <procedure>(iset=? iset1 iset2 iset3 …) → boolean</procedure> Returns {{#t}} if each ''iset'' contains the same elements. <procedure>(iset<? iset1 iset2 iset3 …) → boolean</procedure> Returns {{#t}} if each ''iset'' other than the last is a proper subset of the following ''iset'', and {{#f}} otherwise. <procedure>(iset>? iset1 iset2 iset3 …) → boolean</procedure> Returns {{#t}} if each ''iset'' other than the last is a proper superset of the following ''iset'', and {{#f}} otherwise. <procedure>(iset<=? iset1 iset2 iset3 …) → boolean</procedure> Returns {{#t}} if each ''iset'' other than the last is a subset of the following ''iset'', and {{#f}} otherwise. <procedure>(iset>=? iset1 iset2 iset3 …) → boolean</procedure> Returns {{#t}} if each ''iset'' other than the last is a superset of the following ''iset'', and {{#f}} otherwise. Examples: (iset=? (iset 1 2 3) (iset 3 1 2)) ⇒ #t (iset<? (iset 3 1 2) (iset 4 2 1 3)) ⇒ #t (iset>=? (iset 3 0 1) (iset 0 1) (iset 0 1)) ⇒ #t === Set theory operations <procedure>(iset-union iset1 iset2 iset3 …) → iset</procedure> <procedure>(iset-intersection iset1 iset2 iset3 …) → iset</procedure> <procedure>(iset-difference iset1 iset2 iset3 …) → iset</procedure> <procedure>(iset-xor iset1 iset2) → iset</procedure> Return a newly allocated iset that is the union, intersection, asymmetric difference, or symmetric difference of the ''isets''. Asymmetric difference is extended to more than two isets by taking the difference between the first iset and the union of the others. Symmetric difference is not extended beyond two isets. Elements in the result iset are drawn from the first iset in which they appear. Examples: (iset->list (iset-union (iset 0 1 3) (iset 0 2 4))) ⇒ (0 1 2 3 4) (iset->list (iset-intersection (iset 0 1 3 4) (iset 0 2 4))) ⇒ (0 4) (iset->list (iset-difference (iset 0 1 3 4) (iset 0 2) (iset 0 4))) ⇒ (1 3) (iset->list (iset-xor (iset 0 1 3) (iset 0 2 4))) ⇒ (1 2 3 4) <procedure>(iset-union! iset1 iset2 iset3 …) → iset</procedure> <procedure>(iset-intersection! iset1 iset2 iset3 …) → iset</procedure> <procedure>(iset-difference! iset1 iset2 iset3 …) → iset</procedure> <procedure>(iset-xor! iset1 iset2) → iset</procedure> Linear update procedures returning an ''iset'' that is the union, intersection, asymmetric difference, or symmetric difference of the ''iset''s. === Intervals and ranges <procedure>(iset-open-interval iset low high) → iset</procedure> <procedure>(iset-closed-interval iset low high) → iset</procedure> <procedure>(iset-open-closed-interval iset low high) → iset</procedure> <procedure>(iset-closed-open-interval iset low high) → iset</procedure> Procedures that return a subset of ''iset'' contained in the interval from ''low'' to ''high''. The interval may be open, closed, open below and closed above, or open above and closed below. Examples: (iset->list (iset-open-interval (iset 2 3 5 7 11) 2 7)) ⇒ (3 5) (iset->list (iset-closed-interval (iset 2 3 5 7 11) 2 7)) ⇒ (2 3 5 7) (iset->list (iset-open-closed-interval (iset 2 3 5 7 11) 2 7)) ⇒ (3 5 7) (iset->list (iset-closed-open-interval (iset 2 3 5 7 11) 2 7)) ⇒ (2 3 5) <procedure>(isubset= iset k) → iset</procedure> <procedure>(isubset< iset k) → iset</procedure> <procedure>(isubset<= iset k) → iset</procedure> <procedure>(isubset> iset k) → iset</procedure> <procedure>(isubset>= iset k) → iset</procedure> Procedures that return an integer set containing the elements of ''iset'' that are equal to, less than, less than or equal to, greater than, or greater than or equal to ''k''. Note that the result of {{isubset=}} contains at most one element. Examples: (iset->list (isubset= (iset 2 3 5 7 11) 7)) ⇒ (7) (iset->list (isubset< (iset 2 3 5 7 11) 7)) ⇒ (2 3 5) (iset->list (isubset>= (iset 2 3 5 7 11) 7)) ⇒ (7 11) == About This Egg === Dependencies The following eggs are required: * [[srfi-1]] * [[srfi-143]] * [[srfi-145]] The [[test]] egg is additionally required to run the included tests. === Authors John Cowan and Wolfgang Corcoran-Mathe === Maintainer Wolfgang Corcoran-Mathe Contact: {{<wcm at sigwinch dot xyzzy minus the zy>}} === Repository [[https://github.com/Zipheir/srfi-217-chicken|GitHub]] === Version History ; 0.1 : Initial release. ; 0.2 : Add types, remove buggy optimization of {{make-range-iset}}. === Copyright (C) 2020 John Cowan, Wolfgang Corcoran-Mathe. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. Description of your changes:

I would like to authenticate

Spam control

What do you get when you add 21 to 9?