srfi-217 | chickadee

SRFI-217: Integer Sets

Integer sets, or isets, are unordered collections of fixnums. This egg provides the SRFI 217 sample implementation of integer sets.

SRFI Description

This page includes excerpts from the 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

iset element …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)) ⇒ ()

iset-unfold stop? mapper successor seedprocedure

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)

make-range-iset start end #!optional stepprocedure

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

iset? objprocedure: Returns #t if obj is a iset, and #f otherwise.

iset-contains? iset elementprocedure

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

iset-empty? isetprocedure

Returns #t if iset has no elements and #f otherwise.

Examples:

   (iset-empty? (iset 2 3 5 7 11)) ⇒ #f
   (iset-empty? (iset)) ⇒ #t

iset-disjoint? iset1 iset2procedure

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

iset-member iset element defaultprocedure

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

iset-min isetprocedure

iset-max isetprocedure

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

iset-adjoin iset element1 element2 …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)

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.

iset-delete iset element1 element2 …procedure

iset-delete! iset element1 element2 …procedure

iset-delete-all iset element-listprocedure

iset-delete-all! iset element-listprocedure

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)

iset-delete-min isetprocedure

iset-delete-min! isetprocedure

iset-delete-max isetprocedure

iset-delete-max! isetprocedure

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

iset-search iset element failure successprocedure

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.

iset-search! iset element failure successprocedure: 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

iset-size isetprocedure

Returns the number of elements in iset as an exact integer.

Example:

   (iset-size (iset 1 3 5)) ⇒ 3

iset-find predicate iset failureprocedure

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

iset-count predicate isetprocedure

Returns the number of elements of iset that satisfy predicate as an exact integer.

Example:

   (iset-count positive? (iset -2 -1 1 2)) ⇒ 2

iset-any? predicate isetprocedure

Returns #t if any 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-any? positive? (iset -2 -1 1 2)) ⇒ #t
   (iset-any? zero? (iset -2 -1 1 2)) ⇒ #f

iset-every? predicate isetprocedure

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

iset-map proc isetprocedure

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)

iset-for-each proc isetprocedure

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

iset-fold proc nil isetprocedure

iset-fold-right proc nil isetprocedure

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)

iset-filter predicate isetprocedure

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)

iset-filter! predicate isetprocedure: A linear update procedure that returns a iset containing just the elements of iset that satisfy predicate.

iset-remove predicate isetprocedure

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)

iset-remove! predicate isetprocedure: A linear update procedure that returns a iset containing just the elements of iset that do not satisfy predicate.

iset-partition predicate isetprocedure

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

iset-partition! predicate isetprocedure: 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

iset-copy isetprocedure: Returns a newly allocated iset containing the elements of iset.

iset->list isetprocedure

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)

list->iset listprocedure

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)

list->iset! iset listprocedure

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.

iset=? iset1 iset2 iset3 …procedure: Returns #t if each iset contains the same elements.

iset<? iset1 iset2 iset3 …procedure: Returns #t if each iset other than the last is a proper subset of the following iset, and #f otherwise.

iset>? iset1 iset2 iset3 …procedure: Returns #t if each iset other than the last is a proper superset of the following iset, and #f otherwise.

iset<=? iset1 iset2 iset3 …procedure: Returns #t if each iset other than the last is a subset of the following iset, and #f otherwise.

iset>=? iset1 iset2 iset3 …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

iset-union iset1 iset2 iset3 …procedure

iset-intersection iset1 iset2 iset3 …procedure

iset-difference iset1 iset2 iset3 …procedure

iset-xor iset1 iset2procedure

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)

iset-union! iset1 iset2 iset3 …procedure

iset-intersection! iset1 iset2 iset3 …procedure

iset-difference! iset1 iset2 iset3 …procedure

iset-xor! iset1 iset2procedure: Linear update procedures returning an iset that is the union, intersection, asymmetric difference, or symmetric difference of the isets.

Intervals and ranges

iset-open-interval iset low highprocedure

iset-closed-interval iset low highprocedure

iset-open-closed-interval iset low highprocedure

iset-closed-open-interval iset low highprocedure

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)

isubset= iset kprocedure

isubset< iset kprocedure

isubset<= iset kprocedure

isubset> iset kprocedure

isubset>= iset kprocedure

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:

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

GitHub

Version History

0.1: Initial release.
0.2: Add types, remove buggy optimization of make-range-iset.

Copyright

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.

chickadee » srfi-217

Identifier search

SRFI-217: Integer Sets

TOC »

SRFI Description

(srfi 217) vs. iset

Specification

Linear update

Constructors

Predicates

Accessors

Updaters

The whole iset

Mapping and folding

Copying and conversion

Subsets

Set theory operations

Intervals and ranges

About This Egg

Dependencies

Authors

Maintainer

Repository

Version History

Copyright

Contents »