#

**integer-set.ss**: Integer Sets

**integer-set.ss**

To load: `(require (lib "integer-set.ss"))`

The ` integer-set.ss` module provides functions for working with
finite sets of integers. This module is designed for sets that are
compactly represented as groups of intervals, even when their
cardinality is large. For example, the set of integers from

`-`1000000 to 1000000 except for 0, can be represented as {[

`-`1000000,

`-`1], [1, 1000000]}. This data structure would not be a good choice for the set of all odd integers between 0 and 1000000 (which would be {[1, 1], [3, 3],

`...`[999999, 999999]}).

In addition to the `integer-set`

abstract type, we define a
`well-formed-set`

to be a list of pairs of exact integers, where
each pair represents a closed range of integers, and the entire set
is the union of the ranges. The ranges must be disjoint and
increasing. Further, adjacent ranges must have at least one integer
between them. For example: `'((-1 . 2) (4 . 10))`

is a
well-formed-set as is `'((1 . 1) (3 . 3))`

, but ```
'((1
. 5) (6 . 7))
```

, `'((1 . 5) (-3 . -1))`

, `'((5 . 1))`

,
and `'((1 . 5) (3 . 6))`

are not.

`(make-integer-set`

` ``well-formed-set`

`)`

PROCEDURE

Creates an integer set from a well-formed set.

`(integer-set-contents`

` ``integer-set`

`)`

PROCEDURE

Produces a well-formed set from an integer set.

`(set-integer-set-contents!`

` ``integer-set well-formed-set`

`)`

PROCEDURE

Mutates an integer set.

Returns `#t`

if `v`

is an integer set, `#f`

otherwise.

make-range/empty

Produces an empty integer set.

Produces an integer set containing only `k`

.

`(make-range`

` ``start-k end-k`

`)`

PROCEDURE

Produces an integer set containing the integers from
`start-k`

to `end-k`

inclusive, where
`start-k`

`<=`

`end-k`

.

`(intersect`

` ``x-integer-set y-integer-set`

`)`

PROCEDURE

Returns the intersection of the given sets.

`(difference`

` ``x-integer-set y-integer-set`

`)`

PROCEDURE

Returns the difference of the given sets (i.e., elements in
`x-integer-set`

that are not in `y-integer-set`

).

`(union`

` ``x-integer-set y-integer-set`

`)`

PROCEDURE

Returns the union of the given sets.

`(split`

` ``x-integer-set y-integer-set`

`)`

PROCEDURE

Produces three values: the first is the intersection of
`x-integer-set`

and `y-integer-set`

, the second is the
difference `x-integer-set`

remove `y-integer-set`

, and the
third is the difference `y-integer-set`

remove
`x-integer-set`

.

`(complement`

` ``integer-set start-k end-k`

`)`

PROCEDURE

Returns the a set containing the elements between
`start-k`

to `end-k`

inclusive that are not
in `integer-set`

, where `start-k`

`<=`

`end-k`

.

`(xor`

` ``x-integer-set y-integer-set`

`)`

PROCEDURE

Returns an integer set containing every member of `x-integer-set`

and `y-integer-set`

that is not in both sets.

`(member?`

` ``k integer-set`

`)`

PROCEDURE

Returns `#t`

if `k`

is in `integer-set`

, `#f`

otherwise.

`(get-integer`

` ``integer-set`

`)`

PROCEDURE

Returns a member of `integer-set`

, or `#f`

if
`integer-set`

is empty.

`(foldr`

` ``proc base-v integer-set`

`)`

PROCEDURE

Applies `proc`

to each member of `integer-set`

in ascending
order, where the first argument to `proc`

is the set member, and
the second argument is the fold result starting with
`base-v`

. For example, `(foldr cons null `

returns
a list of all the integers in `x`

)`x`

, sorted in increasing order.

`(partition`

` ``integer-set-list`

`)`

PROCEDURE

Returns the coarsest refinement of the sets in `integer-set-list`

such that the sets in the result list are pairwise disjoint. For
example, partitioning the sets that represent ```
'((1 . 2) (5
. 10))
```

and `'((2 . 2) (6 . 6) (12 . 12))`

produces the a list
containing the sets for `'((1 . 1) (5 . 5) (7 . 10))`

`'((2 . 2) (6 . 6))`

, and `'((12 . 12))`

.

Returns the number of integers in the given integer set.

`(subset?`

` ``x-integer-set y-integer-set`

`)`

PROCEDURE

Returns true if every integer in `x-integer-set`

is also in
`y-integer-set`

, otherwise `#f`

.