[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: ADT Sets?
> Date: Sun, 09 Aug 1998 04:45:59 -0400
> From: Michael Griebling <mgriebling@inspired.to>
>
> Michael van Acken wrote:
>
> > 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.
> >
>
> It would be a nice thing to have.
Any volunteers to put together a draft?
> In my opinion they are also missing a convenience function to build
> up a set, perhaps based on an array of integers where each integer
> represents a set element. Strictly speaking this isn't necessary
> since Incl can be called repeatedly; but it would be a convenient
> thing to have.
How would this function look like? Maybe
PROCEDURE InitFromArray (VAR s: ARRAY OF SET;
VAR src: ARRAY OF LONGINT; sizeSrc: LONGINT)
IMO this would be too specialized. It is pretty unlikely that the
input elements are available in such a convenient format.
> > CONST size* = 32;
> >
>
> Is this useful information? Why would anyone care how the sets are
> implemented (ie. that they are made up of pieces of 32-bit SETs)?
In this case one does care, because one has to allocate memory for the
sets manually. The module has no mechanism to allocate memory for
sets.
I have attached the revised module. Changes:
Added type "Set* = ARRAY OF SET".
Replaced all INTEGER with LONGINT.
Renamed
Different -> EmptyIntersection
Unite -> Union
Differ -> Difference
Interset -> Intersection
Print -> Write
size -> baseSize
Made `Intersection' a 2 operand operation, instead of 3.
Changes `Elements' to avoid an undefined `lastElem' for empty sets.
Added `Copy' and `Complement'.
Added comment addressing some general caveats.
-- mva
------------------------------------------------------------------------
(* $Id: StSetsInt.Mod,v 1.1 1998/08/09 12:34:28 acken Exp $ *)
MODULE StSetsInt;
(*
Module derived from the ETH Oberon System's Sets modules. Original sources
are believed to be in the public domain.
About this module:
- the user is expected to allocate variables of appropriate size to store
the set; the size of the sets is bounded by the initial allocation
- all procedures that take two sets as input arguments implicitly assume
that the length of the second argument is greater or equal to the size
of the first
- the procedures assume that all valid array indices are also valid set
elements; in particular, `Fill' and `Complement' will always work on the
range [0..LEN(s)*baseSize-1]
*)
(*
$Log: StSetsInt.Mod,v $
Revision 1.1 1998/08/09 12:34:28 acken
Initial revision
*)
IMPORT
TextRider;
CONST
baseSize* = MAX (SET)+1;
TYPE
Set* = ARRAY OF SET;
(* Constructors
======================================================================== *)
PROCEDURE Clear* (VAR s: Set);
VAR
i: LONGINT;
BEGIN
i := 0;
WHILE i < LEN(s) DO
s[i] := {}; INC(i)
END
END Clear;
PROCEDURE Fill* (VAR s: Set);
VAR
i: LONGINT;
BEGIN
i := 0;
WHILE i < LEN(s) DO
s[i] := -{}; INC(i)
END
END Fill;
PROCEDURE Copy* (VAR s1, s2: Set);
(* s1 := s2 *)
VAR
i: LONGINT;
BEGIN
i := 0;
WHILE i < LEN(s1) DO
s1[i] := s2[i]; INC(i)
END
END Copy;
PROCEDURE Incl* (VAR s: Set; x: LONGINT);
BEGIN
INCL(s[x DIV baseSize], x MOD baseSize)
END Incl;
PROCEDURE Excl* (VAR s: Set; x: LONGINT);
BEGIN
EXCL(s[x DIV baseSize], x MOD baseSize)
END Excl;
(* Predicates and Functions
======================================================================== *)
PROCEDURE In* (VAR s: Set; x: LONGINT): BOOLEAN;
BEGIN
RETURN (x MOD baseSize) IN s[x DIV baseSize]
END In;
PROCEDURE Includes* (VAR s1, s2: Set): BOOLEAN;
(* TRUE iff s2 is a subset of s1 *)
VAR
i: LONGINT;
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: Set; VAR lastElem: LONGINT): LONGINT;
VAR
i, n, max: LONGINT;
BEGIN
lastElem := -1;
i := 0; n := 0; max := SHORT(LEN(s)) * baseSize;
WHILE i < max DO
IF (i MOD baseSize) IN s[i DIV baseSize] THEN INC(n); lastElem := i END;
INC(i)
END;
RETURN n
END Elements;
PROCEDURE Empty* (VAR s: Set): BOOLEAN;
VAR
i: LONGINT;
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: Set): BOOLEAN;
VAR
i: LONGINT;
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 EmptyIntersection* (VAR s1, s2: Set): BOOLEAN;
VAR i: LONGINT;
BEGIN
i := 0;
WHILE i < LEN(s1) DO
IF s1[i] * s2[i] # {} THEN RETURN FALSE END;
INC(i)
END;
RETURN TRUE
END EmptyIntersection;
(* Operators
======================================================================== *)
PROCEDURE Union* (VAR s1, s2: Set);
VAR
i: LONGINT; s: SET;
BEGIN
i := 0;
WHILE i < LEN(s1) DO
s := s1[i] + s2[i]; s1[i] := s; INC(i)
END
END Union;
PROCEDURE Difference* (VAR s1, s2: Set);
VAR
i: LONGINT; s: SET;
BEGIN
i := 0;
WHILE i < LEN(s1) DO
s := s1[i] - s2[i]; s1[i] := s; INC(i)
END
END Difference;
PROCEDURE Intersection* (VAR s1, s2: Set);
VAR
i: LONGINT; s: SET;
BEGIN
i := 0;
WHILE i < LEN(s1) DO
s := s1[i] * s2[i]; s1[i] := s; INC(i)
END
END Intersection;
PROCEDURE Complement* (VAR s1: Set);
VAR
i: LONGINT; s: SET;
BEGIN
i := 0;
WHILE i < LEN(s1) DO
s := -s1[i]; s1[i] := s; INC(i)
END
END Complement;
(* Misc
======================================================================== *)
PROCEDURE Print* (VAR w: TextRider.Writer; VAR s: Set;
width, indent: LONGINT);
VAR
col, i, max: LONGINT;
BEGIN
i := 0; col := indent; max := SHORT(LEN(s)) * baseSize;
w.WriteChar("{");
WHILE i < max DO
IF In(s, i) THEN
IF col + 4 > width THEN
w.WriteLn();
col := 0;
WHILE col < indent DO
w.WriteChar(" "); INC(col)
END
END;
w.WriteLInt(i, 3); w.WriteChar(",");
INC(col, 4)
END;
INC(i)
END;
w.WriteChar("}")
END Print;
END StSetsInt.