SETS(2)SETS(2)NAME
Sets - sets of non-negative integers
SYNOPSIS
include "sets.m";
OR 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;
};
};
DESCRIPTION
The Sets module provides routines for manipulating sets of small non-
negative integers. There are currently two implementations available:
the implementation declared in sets32.m stores sets of numbers from 0
to 31 inclusive; the implementation in 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.
Init must be called first, to allow Sets to initialise its internal
state. Set returns a new set, containing nothing. Str2set converts a
string to a new set; the string should have been created with
Set.str(). Bytes2set converts an array of bytes, d, as returned by
Set.bytes(), to a new set.
Note that all set operations are copy operations; none change an exist‐
ing set.
s1.X(op, s2)
Returns a new set, the result of combining s1 and s2 accord‐
ing to boolean operator op. Op can be any bitwise boolean
combination of the two constants A and B, defined in the mod‐
ule. 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 corre‐
sponding bit in s1 and s2, X sets a corresponding bit in the
returned set according to the calculation s1 op s2.
s.add(n) Returns the set s with n added.
s.addlist(ns)
Addlist is the same as calling add on each member of the list
ns, but somewhat more efficient.
s.del(n) Returns s with n removed.
s.invert()
Invert returns a set holding all non-negative integers other
than those already in s. Hence set().invert() holds all non-
negative integers.
s1.eq(s2) Returns non-zero if s1 is identical to s2.
s.holds(n)
Returns non-zero if s holds n as a member.
s.isempty()
Returns non-zero if s holds no members.
s.msb() Returns the "most significant bit": the membership status of
all members that have not been explicitly set. For example,
set().msb() is 0; set().invert().msb() is 1.
s.limit() If s.msb() is zero, s.limit() returns one more than the
largest member contained in s, otherwise it returns one more
than the largest member not contained in s. Thus
set().limit() yields 0, and set().invert().del(5).limit()
yields 6.
s.str() Returns a string corresponding to s. The format is hexdig‐
its:msb, where hexdigits give the least significant members
of the set, most significant on the left, in hexadecimal for‐
mat; msb gives the padding bit that fills the rest of the
set. Note that this format is compatible between the two
implementations.
s.bytes(n)
Returns a packed byte representaton of 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 n bytes.
EXAMPLES
Given two sets, s1 and s2, s1.X(A&B, s2) gives their intersection;
s1.X(A|B, s2) their union; s1.X(A&~B, s2) gives the set of all members
of s1 that aren't in s2; s1.X(~(A|B), s2) gives the set of all integers
in neither s1 nor s2.
sys->print("%s\n", set().addlist(1::2::5::nil)
.invert().X(A|B, set().add(2)).str());
produces the string ``dd:1'', corresponding to the set of all non-nega‐
tive integers except 1 and 5.
SETS(2)