Sets - sets of non-negative integers .EX 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; }; };

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 existing set.

10 s1 .X(op, s2) Returns a new set, the result of combining s1 and s2 according to boolean operator op . Op can be any bitwise boolean combination of the two constants A and 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 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 hexdigits : msb, where hexdigits give the least significant members of the set, most significant on the left, in hexadecimal format; 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.

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 .

.EX sys->print("%s\en", 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-negative integers except 1 and 5.