Integer sets (Gauche Users’ Reference)

11.45 `srfi-217` - Integer sets

Module: srfi-217

This srfi defines a set whose element is limited to fixnums.

Although general sets are provided by scheme.set (see R7RS sets), this module may take advantage of limited-type elements to optimize storage and operations.

It also provides range-based operations, which aren’t available in the general sets.

Constructors

Function: iset element …

[SRFI-217] {srfi-217} Each element must be a fixnum.

Returns a fresh iset contains element ….

Function: iset-unfold p f g seed

[SRFI-217] {srfi-217} Constructs an iset whose element is computed procedurally.

The p argument is called with a current seed value. If it returns #t, the iteration ends.

The f argument is called with a current seed value, and returns a fixnum to be included into the set.

The g argument is called with a current seed value, and returns the next seed value.

The seed argument gives the initial seed.

(iset->list
 (iset-unfold (cut > <> 10) (cut * <> 2) (cut + <> 1) 0))
 ⇒ (0 2 4 6 8 10 12 14 16 18 20)

Function: make-range-iset start end :optional step

[SRFI-217] {srfi-217} Creates an iset that contains each fixnum in (numeric-range start end step). See Range, for the details of ranges.

(iset->list (make-range-iset 0 5))
 ⇒ (0 1 2 3 4)

Predicates

Function: iset? obj: [SRFI-217] {srfi-217} Returns #t iff obj is an iset.

Function: iset-contains? iset element: [SRFI-217] {srfi-217} Returns #t iff iset contains element.

Function: iset-empty? iset: [SRFI-217] {srfi-217} Returns #t iff iset is empty. An error is thrown if an object other than an iset is passed.

Function: iset-disjoint? iset1 iset2: [SRFI-217] {srfi-217} Both arguments must be an iset. Returns #t iff no element belongs to both isets.

Accessors

Function: iset-member iset element default: [SRFI-217] {srfi-217} Returns element if it is contained in iset, otherwise default.

Function: iset-min iset
Function: iset-max iset: [SRFI-217] {srfi-217} Returns the minimum and the maximum element in iset. If iset is empty, returns #f.

Updaters

Function: iset-adjoin iset elt1 elt2 …

Function: iset-adjoin! iset elt1 elt2 …

[SRFI-217] {srfi-217} Returns an iset that includes all the elements in iset, plus elt1 elt2 ….

The linear update version iset-adjoin! may reuse iset to store the result, but the caller must always use its return value.

Function: iset-delete iset elt1 elt2 …

Function: iset-delete! iset elt1 elt2 …

[SRFI-217] {srfi-217} Returns an iset that includes the elements in iset except the ones matching one of elt1 elt2 ….

The linear update version iset-delete! may reuse iset to store the result, but the caller must always use its return value.

Function: iset-delete-all iset elt-list

Function: iset-delete-all! iset elt-list

[SRFI-217] {srfi-217} The elt-list argument must be a list of fixnums. Returns an iset that includes the elements in iset except the ones in elt-list.

The linear update version iset-delete-all! may reuse iset to store the result, but the caller must always use its return value.

Function: iset-delete-min iset

Function: iset-delete-min! iset

Function: iset-delete-max iset

Function: iset-delete-max! iset

[SRFI-217] {srfi-217} Returns two values: The minimum or the maximum element in iset, and a new iset taht contains elements in iset except the minimum/maximum element. An error is thrown if iset is empty.

The linear update version iset-delete-min!/iset-delete-max! may reuse iset to store the result, but the caller must always use its return value.

Function: iset-search iset element failure success

Function: iset-search! iset element failure success

[SRFI-217] {srfi-217} Search iset for matching element from lowest to highest value. They return two values, a (possibly updated) iset, and auxiliary value as explained below.

If element is found, the success procedure is called with three arguments: the matching element of iset, a procedure update, and a procedure remove. The update procedure can be invoked with two arguments, new-element and obj; if called, new-element replaces element in iset, and iset-search returns the new iset and obj. The remove procedure can be invoked with one argument, obj. It removes the matching element from iset and iset-search returns the new iset and obj.

If element is not found, the failure procedure is called with two arguments, insert and ignore, both procedures. The insert procedure can be called with one argument, obj. It causes iset-search to return a new iset that contains all the elements from iset plus element, and obj. The ignore procedure can be called with one argument, obj. It causes iset-search to return the original iset and obj.

The linear update version, iset-search!, may reuse iset for the updated iset.

The whole iset

Function: iset-size iset: [SRFI-217] {srfi-217} Returns the number of elements in iset.

Function: iset-find pred iset failure: [SRFI-217] {srfi-217} Returns the smallest element of iset that satisfies pred. If no element satisfies pred, failure is called with no arguments, and its result is returned from iset-find.

Function: iset-count pred iset: [SRFI-217] {srfi-217} Returns the number of elements in iset that satisfy pred.

Function: iset-any? pred iset: [SRFI-217] {srfi-217} Returns #t if any element in iset satisfies pred, #f otherwise.

Function: iset-every? pred iset: [SRFI-217] {srfi-217} Returns #t if every element in iset satisfies pred, #f otherwise.

Mapping and folding

Function: iset-map proc iset

[SRFI-217] {srfi-217} Creates and returns a new iset whose elements consist of the result of proc applied to each element of the given iset. An error is signaled if proc doesn’t return an exact integer.

Note that the size of the result set may be smaller than the input, if proc isn’t injective.

The order of proc’s application is unspecified.

Function: iset-for-each proc iset: [SRFI-217] {srfi-217} Applies proc to each element in iset in increasing order. The result of proc is discarded. Returns unspecified result.

Function: iset-fold kons knil iset
Function: iset-fold-right kons knil iset: [SRFI-217] {srfi-217} Like fold/fold-right, apply kons on each element in iset, passing the result to the next kons.

Function: iset-filter pred iset
Function: iset-filter! pred iset: [SRFI-217] {srfi-217} Returns an iset that contains the elements in iset that satisfy pred. The linear-update version iset-filter! may reuse given iset to store the result.

Function: iset-remove pred iset
Function: iset-remove! pred iset: [SRFI-217] {srfi-217} Returns an iset that contains the elements in iset that do not satisfy pred. The linear-update version iset-remove! may reuse given iset to store the result.

Function: iset-partition pred iset
Function: iset-partition! pred iset: [SRFI-217] {srfi-217} Returns two isets, first one consisting of the elements in iset that satisfy pred, and the second one consisting of the elements that don’t. The linear-update version iset-partition! may reuse given iset to store one of the results.

Copying and conversion

Function: iset-copy iset: [SRFI-217] {srfi-217} Returns a copy of iset.

Function: iset->list iset: [SRFI-217] {srfi-217} Returns a list of elements in iset, in increasing order.

Function: list->iset list: [SRFI-217] {srfi-217} Returns an iset that contains elements in list. The elements in list must be exact integers. Duplicate elements are omitted.

Function: list->iset! iset list: [SRFI-217] {srfi-217} Returns an iset consists of the elements from iset and list. It may reuse the given iset to store the result.

Subsets

Function: iset=? iset1 iset2 iset3 …: [SRFI-217] {srfi-217} Returns #t iff given isets are equal to each other as sets.

Function: iset<? iset1 iset2 iset3 …

Function: iset<=? iset1 iset2 iset3 …

Function: iset>? iset1 iset2 iset3 …

Function: iset>=? iset1 iset2 iset3 …

[SRFI-217] {srfi-217} These compares subset relationships between isets. (iset<=? iset1 iset2) is #t iff every element of iset1 is contained in iset2, and so on.

Note that (iset<? a b) does not imply (iset>=? a b).

Set theory operations

Function: iset-union iset1 iset2 iset3 …
Function: iset-union! iset1 iset2 iset3 …: [SRFI-217] {srfi-217}

Function: iset-intersection iset1 iset2 iset3 …
Function: iset-intersection! iset1 iset2 iset3 …: [SRFI-217] {srfi-217}

Function: iset-difference iset1 iset2 iset3 …
Function: iset-difference! iset1 iset2 iset3 …: [SRFI-217] {srfi-217}

Function: iset-xor iset1 iset2 iset3 …
Function: iset-xor! iset1 iset2 iset3 …: [SRFI-217] {srfi-217}

Intervals and ranges

Function: iset-open-interval iset low high
Function: iset-closed-interval iset low high
Function: iset-open-closed-interval iset low high
Function: iset-closed-open-interval iset low high: [SRFI-217] {srfi-217}

Function: isubset= iset k
Function: isubset< iset k
Function: isubset<= iset k
Function: isubset> iset k
Function: isubset>= iset k: [SRFI-217] {srfi-217} Returns a subset of iset whose elements are equal to, less than, less than or equal to, greater than, and greater than or equal to, k.

11.45 srfi-217 - Integer sets