integer-set.ss: Integer Sets
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.