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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
|
.TH SETS 2
.SH NAME
Sets \-
sets of non-negative integers
.SH SYNOPSIS
.EX
include "sets.m";
\fIOR\fP include "sets32.m";
sets := load Sets Sets->PATH;
A, B: import Sets;
Sets: adt {
init: fn();
set: fn(): Set;
str2set: fn(str: string): Set;
bytes2set: fn(d: array of byte): Set;
Set: adt {
# opaque data
X: fn(s1: self Set, op: int, s2: Set): Set;
add: fn(s: self Set, n: int): Set;
addlist: fn(s: self Set, ns: list of int): Set;
del: fn(s: self Set, n: int): Set;
invert: fn(s: self Set): Set;
eq: fn(s1: self Set, s2: Set): int;
holds: fn(s: self Set, n: int): int;
isempty: fn(s: self Set): int;
msb: fn(s: self Set): int;
limit: fn(s: self Set): int;
str: fn(s: self Set): string;
bytes: fn(s: self Set, n: int): array of byte;
};
};
.EE
.SH DESCRIPTION
.PP
The
.B Sets
module provides routines for manipulating sets
of small non-negative integers. There are currently
two implementations available:
the implementation declared in
.B sets32.m
stores sets of numbers from 0 to 31 inclusive;
the implementation in
.B sets.m
stores arbitrary sets of non-negative integers.
The description given is for the more general
implementation; behaviour of the other is undefined
if an integer higher than 31 is used.
.PP
.B Init
must be called first, to allow
.B Sets
to initialise its internal state.
.B Set
returns a new set, containing nothing.
.B Str2set
converts a string to a new set; the string
should have been created with
.BR Set.str() .
.B Bytes2set
converts an array of bytes,
.IR d ,
as returned by
.BR Set.bytes() ,
to a new set.
.PP
Note that all set operations are copy operations;
none change an existing set.
.TP 10
.IB s1 .X(\fIop\fP,\ \fIs2\fP)
Returns a new set, the result of combining
.I s1
and
.I s2
according to boolean operator
.IR op .
.I Op
can be any bitwise boolean combination of the
two constants
.B A
and
.BR B ,
defined in the module. Notionally, each
set is an infinitely long string of bits, each
bit representing a non-negative integer:
zero if the integer is present, and one if absent.
For each corresponding bit in
.I s1
and
.IR s2 ,
.B X
sets a corresponding bit in the returned set
according to the calculation
.IR "s1 op s2" .
.TP
.IB s .add(\fIn\fP)
Returns the set
.I s
with
.I n
added.
.TP
.IB s .addlist(\fIns\fP)
.B Addlist
is the same as calling
.B add
on each member of the list
.IR ns ,
but somewhat more efficient.
.TP
.IB s .del(\fIn\fP)
Returns
.I s
with
.I n
removed.
.TP
.IB s .invert()
.B Invert
returns a set holding all non-negative integers
other than those already in
.IR s .
Hence
.B set().invert()
holds all non-negative integers.
.TP
.IB s1 .eq(\fIs2\fP)
Returns non-zero if
.I s1
is identical to
.IR s2 .
.TP
.IB s .holds(\fIn\fP)
Returns non-zero if
.I s
holds
.I n
as a member.
.TP
.IB s .isempty()
Returns non-zero if
.I s
holds no members.
.TP
.IB s .msb()
Returns the "most significant bit": the membership
status of all members that have not been explicitly
set. For example,
.B set().msb()
is 0;
.B set().invert().msb()
is 1.
.TP
.IB s .limit()
If
.IB s .msb()
is zero,
.IB s .limit()
returns one more than the largest member contained in
.IR s ,
otherwise it returns one more than the largest member
.I not
contained in
.IR s .
Thus
.B set().limit()
yields 0,
and
.B set().invert().del(5).limit()
yields 6.
.TP
.IB s .str()
Returns a string corresponding to
.IR s .
The format is
.IB hexdigits : msb\fR,\fP
where
.I hexdigits
give the least significant members of the set,
most significant on the left, in hexadecimal format;
.I msb
gives the padding bit that fills the rest of the set.
Note that this format is compatible between the
two implementations.
.TP
.IB s .bytes(\fIn\fP)
Returns a packed byte representaton of
.I s .
The array is held in little-endian order,
with the topmost bit of the top byte
holding the msb of the set.
The array returned will contain at least
.I n
bytes.
.SH EXAMPLES
Given two sets,
.I s1
and
.IR s2 ,
.IB s1 ".X(A&B," " s2" )
gives their intersection;
.IB s1 ".X(A|B," " s2" )
their union;
.IB s1 ".X(A&~B," " s2" )
gives the set of all members of
.I s1
that aren't in
.IR s2 ;
.IB s1 ".X(~(A|B), " s2 )
gives the set of all integers in neither
.I s1
nor
.IR s2 .
.PP
.EX
sys->print("%s\en", set().addlist(1::2::5::nil)
.invert().X(A|B, set().add(2)).str());
.EE
produces the string
.RB `` dd:1 '',
corresponding to the set of all non-negative
integers except 1 and 5.
|
