Integer sets (Gauche Users’ Reference)

11.53 `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 scheme.set - 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} Returns a fresh iset contains element …. Each element must be a fixnum.

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 data.range - 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.

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 …. An error is thrown if elt1 elt2 … include other than fixnums.

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 that 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. The failure and success arguments are both procedures.

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 success procedure can either return or tail call one of either update or 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. When those procedures are tail-called from success, those values become the return values of iset-search.

If element is not found, the failure procedure is called with two arguments, insert and ignore, both procedures and failure is expected to tail-call one of them.

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 a fixnum.

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, increasing or decreasing order, passing the result to the previous kons, or knil for the first iteration. Returns the last result of kons. If iset is empty, kons is never called and knil is returned as is.

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

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 fixnums. Duplicate elements are consolidated.

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

Subsets

Function: iset=? iset1 iset2 iset3 … ¶: [SRFI-217]{srfi.217} Returns #t iff all given isets contains the same elements.

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.

Set theory operations

Function: iset-union iset1 iset2 iset3 … ¶
Function: iset-union! iset1 iset2 iset3 … ¶: [SRFI-217]{srfi.217} Returns an iset that is a union of given isets. Functional version iset-union always returns a fresh iset. Linear update version iset-union! may reuse iset1 to produce the result.

Function: iset-intersection iset1 iset2 iset3 … ¶
Function: iset-intersection! iset1 iset2 iset3 … ¶: [SRFI-217]{srfi.217} Returns an iset that is an intersction of the given iset. Functional version iset-intersection always returns a fresh iset. Linear update version iset-intersection! may reuse iset1 to produce the result.

Function: iset-difference iset1 iset2 iset3 … ¶
Function: iset-difference! iset1 iset2 iset3 … ¶: [SRFI-217]{srfi.217} Returns an iset that has elements in iset1 but not in iset2 iset3 …. Functional version iset-difference always returns a fresh iset. Linear update version iset-difference! may reuse iset1 to produce the result.

Function: iset-xor iset1 iset2 ¶
Function: iset-xor! iset1 iset2 ¶: [SRFI-217]{srfi.217} Returns an iset that has elements, each of which is either in iset1 or iset2 but not in both. Functional version iset-xor always returns a fresh iset. Linear update version iset-xor! may reuse iset1 to produce the result.

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} Extract elements in iset that are in the range specified by low and high, which must be real numbers. The ‘open’ and ‘close’ in the name indicates whether the boundary is included; iset-open-interval doesn’t include both boundary, iset-close-interval includes both boundary, iset-open-closed-interval includes high but not low set-closed-open-interval inclues low but not high.

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

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, which must be a real number.

11.53 srfi.217 - Integer sets