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;
              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;
                  empty:      fn(s: self Set): int;
                  msb:        fn(s: self Set): int;
                  limit:      fn(s: self Set): int;

                  str:        fn(s: self Set): string;
              };
          };

     DESCRIPTION
          The Sets module provides routines for manipulating sets of
          small non-negative integers. There are currently two imple-
          mentations 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().

          Note that all set operations are copy operations; none
          change an existing set.

     Page 1                       Plan 9            (printed 12/29/24)

     SETS(2)                                                   SETS(2)

          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 corre-
                    sponding 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.empty() 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 explic-
                    itly 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 sig-
                    nificant 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.

     EXAMPLES

     Page 2                       Plan 9            (printed 12/29/24)

     SETS(2)                                                   SETS(2)

          Given two sets, s1 and s2, s1.X(A&B, s2) gives their inter-
          section; 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-negative integers except 1 and 5.

     Page 3                       Plan 9            (printed 12/29/24)