(*-------------------------------------------------------------------------*)
(*                                                                         *)
(*  Amiga Oberon Interface Module: BigSets            Date: 02-Nov-92      *)
(*                                                                         *)
(*   © 1992 by Fridtjof Siebert                                            *)
(*                                                                         *)
(*-------------------------------------------------------------------------*)

MODULE BigSets;

IMPORT BasicTypes;

TYPE
  BigSet * = POINTER TO BigSetDesc;
  BigSetDesc * = RECORD (BasicTypes.ANYDesc)
    nbElements - : LONGINT;
    bits         : POINTER TO ARRAY OF SET;
  END;

CONST
  SetSize = MAX(SET) + 1;


PROCEDURE Create * (nbElements: LONGINT): BigSet;
(*
 * Create empty Set with numElements Elements of the range 0..n-1
 *
 * require
 *   0 <= numElements
 *
 * ensure
 *   Result.numElements = numElements;
 *   0 <= x < numElementes IMPLIES ~ Result.In(x)
 *
 *)

VAR
  new: BigSet;

BEGIN
  NEW(new);
  NEW(new.bits,(nbElements + MAX(SET)) DIV SetSize);
  new.nbElements := nbElements;
  RETURN new;
END Create;


PROCEDURE (b: BigSet) Copy * (): BigSet;
(*
 * Create a 1 : 1 copy of b.
 *
 * ensure
 *   Result.numElements = b.numElements;
 *     b.In(x) IMPLIES   Result.In(x)
 *   ~ b.In(x) IMPLIES ~ Result.In(x)
 *
 *)

VAR
  copy: BigSet;
  i: LONGINT;
BEGIN
  copy := Create(b.nbElements);
  FOR i:=0 TO LEN(b.bits^)-1 DO
    copy.bits[i] := b.bits[i];
  END;
  RETURN copy;
END Copy;


PROCEDURE (b: BigSet) Incl * (e: LONGINT);
(*
 * require
 *   0 <= e < b.numElements;
 *
 * ensure
 *   b.In(e);
 *
 *)

BEGIN
  INCL(b.bits[e DIV SetSize],e MOD SetSize);
END Incl;


PROCEDURE (b: BigSet) Excl * (e: LONGINT);
(*
 * require
 *   0 <= e < b.numElements;
 *
 * ensure
 *   ~ b.In(e);
 *
 *)

BEGIN
  EXCL(b.bits[e DIV SetSize],e MOD SetSize);
END Excl;


PROCEDURE (b: BigSet) In * (e: LONGINT): BOOLEAN;
(*
 * require
 *   0 <= e < b.numElements;
 *
 *)

BEGIN
  RETURN (e MOD SetSize) IN b.bits[e DIV SetSize];
END In;


PROCEDURE (b: BigSet) Complement * (): BigSet;
(*
 * ensure
 *   Result.numElements = b.numElements;
 *     Result.In(x) IMPLIES ~ b.In(x);
 *   ~ Result.In(x) IMPLIES   b.In(x)
 *)

VAR
  n: LONGINT;
  result: BigSet;

BEGIN
  result := Create(b.nbElements);
  FOR n := 0 TO LEN(b.bits^)-1 DO
    result.bits[n] := - b.bits[n];
  END;
  RETURN result;
END Complement;


PROCEDURE NewMax(a,b: BigSet): BigSet;
(*
 * allocates new Set. Result.nbElements = MAX(a.nbElements,b.nbElements);
 *)
VAR
  c: BigSet;
BEGIN
  IF b.nbElements > a.nbElements THEN
    a := b;
  END;
  c := Create(a.nbElements);
  RETURN c;
END NewMax;


PROCEDURE Min(a,b: BigSet): LONGINT;
(*
 * Result is MIN(a.bits^,b.bits^)-1
 *)
BEGIN
  IF LEN(b.bits^) < LEN(a.bits^) THEN
    RETURN LEN(b.bits^)-1;
  ELSE
    RETURN LEN(a.bits^)-1;
  END;
END Min;


PROCEDURE (b: BigSet) Difference * (c: BigSet): BigSet;
(*
 * require
 *   c # NIL;
 *
 * ensure
 *   Result.numElements = b.numElements;
 *     Result.In(x) IMPLIES   b.In(x) &  ~ c.In(x);
 *   ~ Result.In(x) IMPLIES ~ b.In(x) OR   c.In(x);
 *)

VAR
  n: LONGINT;
  result: BigSet;

BEGIN
  result := NewMax(b,c);
  FOR n := 0              TO Min(b,c)       DO result.bits[n] := b.bits[n] - c.bits[n] END;
  FOR n := LEN(b.bits^)-1 TO LEN(c.bits^)-1 DO result.bits[n] := b.bits[n]             END;
  RETURN result;
END Difference;


PROCEDURE (b: BigSet) Intersection * (c: BigSet): BigSet;
(*
 * require
 *   c # NIL;
 *
 * ensure
 *   Result.numElements = b.numElements;
 *     Result.In(x) IMPLIES   b.In(x) &    c.In(x);
 *   ~ Result.In(x) IMPLIES ~ b.In(x) OR ~ c.In(x);
 *)

VAR
  n: LONGINT;
  result: BigSet;

BEGIN
  result := NewMax(b,c);
  FOR n := 0              TO Min(b,c)       DO result.bits[n] := b.bits[n] * c.bits[n] END;
  RETURN result;
END Intersection;


PROCEDURE (b: BigSet) SymmetricDifference * (c: BigSet): BigSet;
(*
 * require
 *   c # NIL;
 *
 * ensure
 *   Result.numElements = b.numElements;
 *     Result.In(x) IMPLIES b.In(x) # c.In(x);
 *   ~ Result.In(x) IMPLIES b.In(x) = c.In(x);
 *)

VAR
  n: LONGINT;
  result: BigSet;

BEGIN
  result := NewMax(b,c);
  FOR n := 0              TO Min(b,c)       DO result.bits[n] := b.bits[n] / c.bits[n] END;
  FOR n := LEN(b.bits^)-1 TO LEN(c.bits^)-1 DO result.bits[n] := b.bits[n]             END;
  FOR n := LEN(c.bits^)-1 TO LEN(b.bits^)-1 DO result.bits[n] :=             c.bits[n] END;
  RETURN result;
END SymmetricDifference;


PROCEDURE (b: BigSet) Union * (c: BigSet): BigSet;
(*
 * require
 *   c # NIL;
 *
 * ensure
 *   Result.numElements = b.numElements;
 *     Result.In(x) IMPLIES   b.In(x) OR   c.In(x);
 *   ~ Result.In(x) IMPLIES ~ b.In(x) &  ~ c.In(x);
 *)

VAR
  n: LONGINT;
  result: BigSet;

BEGIN
  result := NewMax(b,c);
  FOR n := 0              TO Min(b,c)       DO result.bits[n] := b.bits[n] + c.bits[n] END;
  FOR n := LEN(b.bits^)-1 TO LEN(c.bits^)-1 DO result.bits[n] := b.bits[n]             END;
  FOR n := LEN(c.bits^)-1 TO LEN(b.bits^)-1 DO result.bits[n] := c.bits[n]             END;
  RETURN result;
END Union;


END BigSets.