1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
#lang scribble/manual
@(require scribble/eval
(for-label data/integer-set
racket/contract
(except-in racket/base
foldr)))
@(define (racket-tech pre)
(tech #:doc '(lib "scribblings/reference/reference.scrbl") pre))
@title[#:tag "integer-set"]{Integer Sets}
@(define the-eval (make-base-eval))
@(the-eval '(require data/integer-set))
@defmodule[data/integer-set]
This library 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
@math{-1000000} to @math{1000000} except for @math{0}, can be represented as
@math{{[-1000000, -1], [1, 1000000]}}. This data structure would not be
a good choice for the set of all odd integers between @math{0} and
@math{1000000}, which would be @math{{[1, 1], [3, 3], ... [999999,
999999]}}.
In addition to the @defterm{integer set} abstract type, a
@defterm{well-formed set} is 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: @racket['((-1 . 2) (4 . 10))] is a well-formed-set as is
@racket['((1 . 1) (3 . 3))], but @racket['((1 . 5) (6 . 7))],
@racket['((1 . 5) (-3 . -1))], @racket['((5 . 1))], and @racket['((1
. 5) (3 . 6))] are not.
An integer set implements the @racket-tech{stream} and
@racket-tech{sequence} generic interfaces.
@examples[#:eval the-eval
(for/list ([i (make-integer-set '((2 . 3)
(5 . 6)
(10 . 15)))])
i)]
@defproc[(make-integer-set [wfs well-formed-set?]) integer-set?]{
Creates an integer set from a well-formed set.}
@defproc[(integer-set-contents [s integer-set?]) well-formed-set?]{
Produces a well-formed set from an integer set.}
@defproc[(set-integer-set-contents! [s integer-set?][wfs well-formed-set?]) void?]{
Mutates an integer set.}
@defproc[(integer-set? [v any/c]) boolean?]{
Returns @racket[#t] if @racket[v] is an integer set, @racket[#f]
otherwise.}
@defproc[(well-formed-set? [v any/c]) boolean?]{
Recognizes @racket[(listof (cons/c exact-integer? exact-integer?))],
where the result of @racket[(flatten v)] is sorted by
@racket[<=], the elements of the pairs in the list
are distinct (and thus strictly increasing), and the
second element in a pair is at least one less than the
first element of the subsequent pair.
@examples[#:eval the-eval
(well-formed-set? '((-1 . 2) (4 . 10)))
(well-formed-set? '((1 . 1) (3 . 3)))
(well-formed-set? '((1 . 5) (6 . 7)))
(well-formed-set? '((1 . 5) (-3 . -1)))
(well-formed-set? '((5 . 1)))
(well-formed-set? '((1 . 5) (3 . 6)))]
}
@defproc*[([(make-range) integer-set?]
[(make-range [elem exact-integer?]) integer-set?]
[(make-range [start exact-integer?]
[end exact-integer?]) integer-set?])]{
Produces, respectively, an empty integer set, an integer set
containing only @racket[elem], or an integer set containing the
integers from @racket[start] to @racket[end] inclusive, where
@racket[(start . <= . end)].}
@defproc[(intersect [x integer-set?][y integer-set?]) integer-set?]{
Returns the intersection of the given sets.}
@defproc[(subtract [x integer-set?][y integer-set?]) integer-set?]{
Returns the difference of the given sets (i.e., elements in @racket[x]
that are not in @racket[y]).}
@defproc[(union [x integer-set?][y integer-set?]) integer-set?]{
Returns the union of the given sets.}
@defproc[(split [x integer-set?][y integer-set?])
(values integer-set? integer-set? integer-set?)]{
Produces three values: the first is the intersection of @racket[x] and
@racket[y], the second is the difference @racket[x] remove @racket[y],
and the third is the difference @racket[y] remove @racket[x].}
@defproc[(complement [s integer-set?]
[start exact-integer?]
[end exact-integer?]) integer-set?]{
Returns a set containing the elements between @racket[start] to
@racket[end] inclusive that are not in @racket[s], where
@racket[(start-k . <= . end-k)].}
@defproc[(symmetric-difference [x integer-set?][y integer-set?]) integer-set?]{
Returns an integer set containing every member of @racket[x]
and @racket[y] that is not in both sets.}
@defproc[(member? [k exact-integer?][s integer-set?]) boolean?]{
Returns @racket[#t] if @racket[k] is in @racket[s], @racket[#f]
otherwise.}
@defproc[(get-integer [set integer-set?]) (or/c exact-integer? #f)]{
Returns a member of @racket[set], or @racket[#f] if @racket[set] is empty.}
@defproc[(foldr [proc (exact-integer? any/c . -> . any/c)]
[base-v any/c]
[s integer-set?])
any/c]{
Applies @racket[proc] to each member of @racket[s] in ascending order,
where the first argument to @racket[proc] is the set member, and the
second argument is the fold result starting with @racket[base-v]. For
example, @racket[(foldr cons null s)] returns a list of all the
integers in @racket[s], sorted in increasing order.}
@defproc[(partition [s (listof integer-set?)]) (listof integer-set?)]{
Returns the coarsest refinement of the sets in @racket[s] such that
the sets in the result list are pairwise disjoint. For example,
partitioning the sets that represent @racket['((1 . 2) (5 . 10))] and
@racket['((2 . 2) (6 . 6) (12 . 12))] produces the a list containing
the sets for @racket['((1 . 1) (5 . 5) (7 . 10))] @racket['((2 . 2) (6
. 6))], and @racket['((12 . 12))].}
@defproc[(count [s integer-set?]) exact-nonnegative-integer?]{
Returns the number of integers in the given integer set.}
@defproc[(subset? [x integer-set?][y integer-set?]) boolean?]{
Returns true if every integer in @racket[x] is also in
@racket[y], otherwise @racket[#f].}
@close-eval[the-eval]
|
