IMPLEMENTATION MODULE HashSpace;

IMPORT SYSTEM;

  CLASS HashSpace(Element IN HashElement);
    VAR
      Data: ARRAY OF Element;
      CursorPos, CursorValue, StoredData, CollisionsCount: INTEGER;

    REDEFINE METHOD CREATE(Size: INTEGER);
      BEGIN
      ASSERT Size > 0;
      Data.CREATE (Size);
      CursorPos := 1;
      END CREATE;
      
    METHOD AllocatedSize: INTEGER;
      BEGIN    
      RESULT := Data.SIZE;
      END AllocatedSize;
      
    METHOD Resize(NewSize: INTEGER);
      VAR
        OldData: ARRAY OF Element;
        BEGIN                       
      OldData := Data;
      Data.CREATE (NewSize);
      CursorPos := 1;
      StoredData := 0;
      CursorValue := 0;
      CollisionsCount := 0;
      FOR i := 0 TO OldData.SIZE - 1 DO
        IF OldData[i] <> VOID THEN
          VOID := Store(OldData[i]);
          END;
        END;
      END Resize;

    METHOD Stored: INTEGER;
      BEGIN
      RESULT := StoredData;
      END Stored;

    METHOD NextPos (i: INTEGER): INTEGER;
      BEGIN
      RESULT := (i + 1) MOD Data.SIZE;
      END NextPos;

    METHOD PrevPos (i: INTEGER): INTEGER;
      BEGIN
      RESULT := (i + Data.SIZE - 1) MOD Data.SIZE;
      END PrevPos;

    METHOD Store(El: Element): BOOLEAN;
      VAR
        i, j: INTEGER;
      BEGIN
      RESULT := TRUE;
      i := SYSTEM.ABS(El.HashValue) MOD Data.SIZE;
      IF Data [i] = VOID THEN
        StoredData := StoredData + 1;
        Data [i] := El;
       ELSE
        CollisionsCount := CollisionsCount + 1;
        j := NextPos(i);
        WHILE (Data [j] <> VOID) AND (i <> j) DO
          j := NextPos(j);
          END;
        IF Data [j] = VOID THEN
          Data [j] := El;
          StoredData := StoredData + 1;
         ELSE
          RESULT := FALSE;
          END;
        END;
      END Store;

    METHOD Purge;
      BEGIN
      IF StoredData > 0 THEN
        FOR i := 0 TO Data.SIZE -1 DO
          Data [i] := VOID;
          END;
        StoredData := 0;
        CursorPos := -1;
        CursorValue := -1;
        CollisionsCount := 0;
        END;
      END Purge;

    METHOD FindPos (Value: INTEGER): INTEGER;
      VAR
        i, Guard: INTEGER;
      BEGIN
      i := SYSTEM.ABS(Value) MOD Data.SIZE;
      Guard := PrevPos (i);
      WHILE (Data[i] <> VOID)
        AND (Data [i].HashValue <> Value)
        AND (i <> Guard) DO
        i := NextPos (i);
        END;
      IF (Data[i] = VOID) OR (i=Guard) THEN
        RESULT := -1;
       ELSE
        RESULT := i;
        END;
      END FindPos;

    METHOD Find (Value: INTEGER): Element;
      VAR
        i: INTEGER;
      BEGIN
      i := FindPos (Value);
      IF i >= 0 THEN
        RESULT := Data [i];
        CursorPos := i;
        CursorValue := Value;
       ELSE
        CursorPos := -1;
        CursorValue := -1;
        END;
      END Find;

    METHOD Next: Element;
      VAR
        Guard: INTEGER;
      BEGIN
      IF CursorPos >= 0 THEN
        Guard := CursorPos;
        CursorPos := NextPos(CursorPos);
        WHILE (Data[CursorPos] <> VOID) AND
              (Data[CursorPos].HashValue <> CursorValue) AND
              (CursorPos <> Guard) DO
          CursorPos := NextPos (CursorPos);
          END;
        IF (Data[CursorPos] = VOID) OR (CursorPos = Guard) THEN
          CursorPos := -1;
         ELSE
          RESULT := Data [CursorPos];
          END;
        END;
      END Next;

    METHOD Delete(El: Element);
      VAR
        Other: Element;
      BEGIN
      Other := Find (El.HashValue);
      WHILE (Other <> VOID) AND (Other <> El) DO
        Other := Next;
        END;
      IF Other <> VOID THEN
        Data [CursorPos] := VOID;
        StoredData := StoredData - 1;
        END;
      END Delete;

    METHOD Collisions: INTEGER;
      BEGIN
      RESULT := CollisionsCount;
      END Collisions;
      
    METHOD LargestBucket: INTEGER;
      VAR
        CurLen: INTEGER;
      BEGIN             
      FOR i := 0 TO Data.SIZE - 1 DO
        IF Data[i] = VOID THEN
          IF RESULT < CurLen THEN
            RESULT := CurLen;
            END;
          CurLen := 0;
         ELSE
          CurLen := CurLen + 1;
          END;
        END;  
      IF CurLen > RESULT THEN
        RESULT := CurLen;
        END;
      END LargestBucket;
      
    METHOD Row: ARRAY OF Element;
      VAR
         Used: INTEGER;
      BEGIN
      RESULT.CREATE (Stored);
      FOR i := 0 TO AllocatedSize-1 DO
        IF Data[i] <> VOID THEN
          RESULT[Used] := Data[i];
          Used := Used + 1;
          END;
        END;                   
      DEBUG 
        FOR i := 0 TO RESULT.SIZE - 1 DO
          ASSERT RESULT[i] <> VOID;
          FOR j := 0 TO i-1 DO
            ASSERT RESULT[i] <> RESULT[j];
            END;
          END;
        END;
      ASSERT Used = Stored;    
      END Row;
      
    REDEFINE METHOD CLONE (Other: HashSpace(Element));
      BEGIN     
      Data := Other.Data.CLONE;
      END CLONE;

  END HashSpace;

END HashSpace;
