ADT Sets?

[Michael van Acken <KK120y2@mail.lvr.de>]

Mike Griebling send me another candidate module for the ADT library
(see attached source code).  This is a "port" of the Oberon System
"Sets" module.  

As it is, the module make perfect sense in a "simple type library"
that concentrates on compactness and efficiency, but it does not fit
into the current framework of classes.  Maybe this is a good time to  
start thinking about such separate "simply type" library: if we rename
the module, e.g. to "StSetsInt" for "simple type, sets, integer based
implementation", we have the first module of the ST library.

Is anyone in favor of an analogous implementation of a "true" sets
(of integers) class, derived from Container or Object?  This would
include things like riders and persistence.


As for the procedure naming of the module below: "Unite", "Differ",
and "Intersect" seem a little bit awkward to me, and I would rename
them to "Union", "Difference", and "Intersection".  YMMV.

There is no complement function.

The function "Different" is _not_ equivalent to "~Equal":
Different(a,b)=TRUE iff a*b={}.  Does anyone have a better name for
this?

-- mva


MODULE Sets;

IMPORT Texts := TextRider;

CONST size* = 32;

PROCEDURE Clear*(VAR s: ARRAY OF SET);
  VAR i: INTEGER;
BEGIN
  i := 0; WHILE i < LEN(s) DO s[i] := {}; INC(i) END
END Clear;

PROCEDURE Fill*(VAR s: ARRAY OF SET);
  VAR i: INTEGER;
BEGIN
  i := 0; WHILE i < LEN(s) DO s[i] := {0 .. size-1}; INC(i) END
END Fill;

PROCEDURE Incl*(VAR s: ARRAY OF SET; x: INTEGER);
BEGIN INCL(s[x DIV size], x MOD size)
END Incl;

PROCEDURE Excl*(VAR s: ARRAY OF SET; x: INTEGER);
BEGIN EXCL(s[x DIV size], x MOD size)
END Excl;

PROCEDURE In*(VAR s: ARRAY OF SET; x: INTEGER): BOOLEAN;
BEGIN RETURN x MOD size IN s[x DIV size]
END In;

PROCEDURE Includes*(VAR s1, s2: ARRAY OF SET): BOOLEAN;
  VAR i: INTEGER;
BEGIN
  i := 0;
  WHILE i < LEN(s1) DO
    IF s1[i] + s2[i] # s1[i] THEN RETURN FALSE END;
    INC(i)
  END;
  RETURN TRUE;
END Includes;

PROCEDURE Elements*(VAR s: ARRAY OF SET; VAR lastElem: INTEGER): INTEGER;
  VAR i, n, max: INTEGER;
BEGIN
  i := 0; n := 0; max := SHORT(LEN(s)) * size;
  WHILE i < max DO
    IF (i MOD size) IN s[i DIV size] THEN INC(n); lastElem := i END;
    INC(i)
  END;
  RETURN n
END Elements;

PROCEDURE Empty*(VAR s: ARRAY OF SET): BOOLEAN;
  VAR i: INTEGER;
BEGIN
  i := 0;
  WHILE i < LEN(s) DO
    IF s[i] # {} THEN RETURN FALSE END;
    INC(i)
  END;
  RETURN TRUE
END Empty;

PROCEDURE Equal*(VAR s1, s2: ARRAY OF SET): BOOLEAN;
  VAR i: INTEGER;
BEGIN
  i := 0;
  WHILE i < LEN(s1) DO
    IF s1[i] # s2[i] THEN RETURN FALSE END;
    INC(i)
  END;
  RETURN TRUE
END Equal;

PROCEDURE Different*(VAR s1, s2: ARRAY OF SET): BOOLEAN;
  VAR i: INTEGER;
BEGIN
  i := 0;
  WHILE i < LEN(s1) DO
    IF s1[i] * s2[i] # {} THEN RETURN FALSE END;
    INC(i)
  END;
  RETURN TRUE
END Different;

PROCEDURE Unite*(VAR s1, s2: ARRAY OF SET);
  VAR i: INTEGER; s: SET;
BEGIN
  i := 0; WHILE i < LEN(s1) DO s := s1[i] + s2[i]; s1[i] := s; INC(i) END
END Unite;

PROCEDURE Differ*(VAR s1, s2: ARRAY OF SET);
  VAR i: INTEGER; s: SET;
BEGIN
  i := 0; WHILE i < LEN(s1) DO s := s1[i] - s2[i]; s1[i] := s; INC(i) END
END Differ;

PROCEDURE Intersect*(VAR s1, s2, s3: ARRAY OF SET);
  VAR i: INTEGER; s: SET;
BEGIN
  i := 0; WHILE i < LEN(s1) DO s := s1[i] * s2[i]; s3[i] := s; INC(i) END
END Intersect;

PROCEDURE Print*(VAR f: Texts.Writer; s: ARRAY OF SET; w, indent: INTEGER);
  VAR col, i, max: INTEGER;
BEGIN
  i := 0; col := indent; max := SHORT(LEN(s)) * size;
  f.WriteChar("{");
  WHILE i < max DO
    IF In(s, i) THEN
      IF col + 4 > w THEN
        f.WriteLn(); 
        col := 0; WHILE col < indent DO f.WriteChar(" "); INC(col) END
      END;
      f.WriteInt(i, 3); f.WriteChar(",");
      INC(col, 4)
    END;
    INC(i)
  END;
  f.WriteChar("}")
END Print;

END Sets.