IMPLEMENTATION MODULE BitMap; 

IMPORT SYSTEM;

  --------------------------------------
  -- The BitMap class represents arrays ot booleans
  -- in an extremely flexible, and efficient way.
  -- It is initialized with a given size; may be
  -- resized automatically by some of its attached methods.
  --
  -- Querying a positive index greater than the BitMap's
  -- size returns FALSE.
  --------------------------------------

  CLASS BitMap;
    INHERITS HashElement;
  
    CONST
      IntSize = SYSTEM.BitsPerInt;
  
    VAR
      Arr: ARRAY OF INTEGER;
      TheSize: INTEGER;
      
    METHOD ArraySize (Size: INTEGER): INTEGER;
      BEGIN
      RESULT := (Size + IntSize - 1) / IntSize;
      END ArraySize;

    REDEFINE METHOD CREATE (Size: INTEGER);
      BEGIN
      TheSize := Size;
      ASSERT Size > 0;
      Arr.CREATE (ArraySize (Size));
      END CREATE;
      
    METHOD Size: INTEGER;
      BEGIN
      RESULT := TheSize;
      END Size;
      
    METHOD Get(Index: INTEGER): BOOLEAN;
      BEGIN
      IF Index < TheSize THEN
        RESULT := SYSTEM.TestBit (Value := Arr[Index / IntSize], 
                                  BitNr := Index MOD IntSize);
        END;
      END Get;
      
    METHOD Set(Index: INTEGER);
      VAR
        i: INTEGER;
      BEGIN
      i := Index / IntSize;
      Arr[i] := SYSTEM.SetBit (Value := Arr[i],
                               BitNr := Index MOD IntSize);
      END Set;
      
    METHOD Clear(Index: INTEGER);
      VAR
        i: INTEGER;
      BEGIN
      i := Index / IntSize;
      Arr[i] := SYSTEM.UnSetBit (Value := Arr[i],
                                 BitNr := Index MOD IntSize);
      END Clear;
      
    METHOD SetValue(Index: INTEGER;
                    Value: BOOLEAN);
      BEGIN
      IF Value THEN
        Set(Index);
       ELSE
        Clear(Index);
        END;
      END SetValue;                    
      
    METHOD Resize (NewSize: INTEGER);
      VAR
        Complement: ARRAY OF INTEGER;
      BEGIN
      IF NewSize < TheSize THEN
        TheSize := NewSize;
        Arr := Arr.SLICE (0, ArraySize(NewSize));
       ELSIF NewSize > TheSize THEN  
        IF ArraySize(NewSize) <> Arr.SIZE THEN
          Complement.CREATE (ArraySize(NewSize) - Arr.SIZE);
          Arr := Arr + Complement;
          TheSize := NewSize;
          END;
        END;
      END Resize;
      
    METHOD Zap;
      BEGIN
      FOR i := 0 TO Arr.SIZE - 1 DO
        Arr[i] := 0;
        END;
      END Zap;
      
    METHOD Or (Other: BitMap);
      BEGIN
      IF Other <> VOID THEN
        IF Other.Size > TheSize THEN
          Resize (Other.Size);
          ASSERT Other.Arr.SIZE = Arr.SIZE;
          END;
        FOR i := 0 TO Other.Arr.SIZE - 1 DO
          Arr[i] := SYSTEM.BitOr (Arr[i], Other.Arr[i]);
	  END;
        END;
      END Or;
      
    METHOD And (Other: BitMap);
      VAR
        Last: INTEGER;
      BEGIN
      IF Other.Size < TheSize THEN
        Last := Other.Arr.SIZE;
       ELSE
        Last := Arr.SIZE;
        END;
      FOR i := 0 TO Last - 1 DO
        Arr[i] := SYSTEM.BitAnd (Arr[i], Other.Arr[i]);
        END;
      FOR i := Last TO Arr.SIZE - 1 DO
        Arr[i] := 0;
        END;
      END And;
      
    METHOD Xor (Other: BitMap);
      VAR
        Last: INTEGER;
      BEGIN
      IF Other.Size < TheSize THEN
        Last := Other.Arr.SIZE;
       ELSE
        Last := Arr.SIZE;
        END;
      FOR i := 0 TO Last - 1 DO
        Arr[i] := SYSTEM.BitXor (Arr[i], Other.Arr[i]);
        END;
      END Xor;
      
    METHOD Copy (Other: BitMap);
      BEGIN
      TheSize := Other.Size;
      Arr := Other.Arr.CLONE;
      END Copy;
      
    REDEFINE METHOD CLONE(Other: BitMap);
      BEGIN
      Other.Arr := Arr.CLONE;
      END CLONE;
      
    ------------------------------------
    -- The Negate method is restricted to the
    -- BitMap's current size.
    ------------------------------------
    METHOD Negate;
      BEGIN
      FOR i := 0 TO Arr.SIZE - 1 DO
        Arr[i] := SYSTEM.BitNegate (Arr[i]);
        END;
      END Negate;
      
    ------------------------------------
    -- The RowMethod is extremely inefficient,
    -- since it introduces an overhead by a factor
    -- 16 or 32 in terms of the amount of memory 
    -- which is used by the BitMap.
    --
    -- It should be restricted to desperate conditions
    -- where no other solution seems to be applicable.
    ------------------------------------
    METHOD Row: ARRAY OF BOOLEAN;
      BEGIN
      RESULT.CREATE (TheSize);
      FOR i := 0 TO RESULT.SIZE - 1 DO
        RESULT[i] := Get(i);
        END;
      END Row;
      
    METHOD IsEqual (Other: BitMap): BOOLEAN;
      BEGIN     
      ASSERT Other <> VOID;
      IF TheSize = Other.TheSize THEN
        RESULT := TRUE;
        FOR i := 0 TO Arr.SIZE - 1 WHILE RESULT DO
          RESULT := Arr[i] = Other.Arr[i];
          END;
        END;
      END IsEqual;
      
    REDEFINE METHOD HashValue: INTEGER;
      BEGIN
      RESULT := 179821;
      FOR i := 0 TO Arr.SIZE - 1 DO
        RESULT := SYSTEM.BitXor (RESULT+i, Arr[i]);
        END;
      END HashValue;

    METHOD BitsInInt (Val: INTEGER): INTEGER;
      POST
        NO_CHANGE;
      VAR
        j: INTEGER;
      BEGIN
      IF Val <> 0 THEN
 	 j := Val;
        FOR k := 0 TO IntSize - 1 WHILE j <> 0 DO
          IF SYSTEM.TestBit(j, k) THEN
            RESULT := RESULT + 1;
            j := SYSTEM.UnSetBit (j, k);
            END;
          END;
        END;
      END BitsInInt;
      
    METHOD UsedBits: INTEGER;
      BEGIN
      FOR i := 0 TO Arr.SIZE - 1 DO
        RESULT := RESULT + BitsInInt (Arr[i]);
        END;
      END UsedBits;

    METHOD Includes (Other: BitMap): BOOLEAN;
      VAR
         j: INTEGER;
      BEGIN
      RESULT := TRUE;
      FOR i := 0 TO Other.Arr.SIZE - 1 WHILE RESULT DO
        j := Other.Arr[i];
        IF j <> 0 THEN
          IF i < Arr.SIZE THEN
            RESULT := SYSTEM.BitOr (Arr[i], j) = Arr[i];
           ELSE
            RESULT := FALSE;
            END;
          END;
        END;
      END Includes;

    ------------------------------------
    -- The Intersects method indicates whether THIS
    -- has a non-empty intersection with another bit map
    ------------------------------------
    METHOD Intersects (Other: BitMap): BOOLEAN;
      BEGIN
      IF Other <> VOID THEN
	FOR i := 0 TO SYSTEM.MIN (Arr.SIZE, Other.Arr.SIZE) - 1 
               WHILE NOT RESULT DO
	  RESULT := (SYSTEM.BitAnd (Arr[i], Other.Arr[i]) <> 0);
          END;
        END;
      END Intersects;

    METHOD Distance (Other: BitMap): INTEGER;
      VAR
	LongArr, ShortArr: ARRAY OF INTEGER;
      BEGIN
      IF Arr.SIZE > Other.Arr.SIZE THEN
        LongArr := Arr;
	ShortArr := Other.Arr;
       ELSE
        LongArr := Other.Arr;
	ShortArr := Arr;
	END;
      FOR i := 0 TO ShortArr.SIZE - 1 DO
	RESULT := RESULT + BitsInInt(SYSTEM.BitXor (LongArr[i], ShortArr[i]));
        END;
      FOR i := ShortArr.SIZE TO LongArr.SIZE - 1 DO
	RESULT := RESULT + BitsInInt(LongArr[i]);
        END;
      END Distance;

  END BitMap;

END BitMap;
