IMPLEMENTATION MODULE ArrayList;

FROM Streams IMPORT StdOut;

  CLASS ArrayList(Element);
    INHERITS AbstractList (Element);

    CONST
      InitialSize = 7; -- (48 - 16 / 4) - 1

    VAR
      TheUsedItems: INTEGER;
      TheArr: ARRAY OF Element;

    METHOD Ajust;
      BEGIN
      IF TheArr <> VOID THEN
        IF TheUsedItems = 0 THEN
	  TheArr := VOID;
	 ELSIF TheArr.SIZE > InitialSize THEN
          IF (TheArr.SIZE - TheUsedItems) > (TheUsedItems / 8) THEN
  	    TheArr := TheArr.SLICE (0, TheUsedItems);
	    END;
	  END;
	END;
      END Ajust;
      
    REDEFINE METHOD Row: ARRAY OF Element; 
      BEGIN   
      IF TheUsedItems > 0 THEN
        RESULT := TheArr.SLICE (0, TheUsedItems);
        END;            
      END Row;  

    METHOD MakeRoom;
      VAR
        IncrSize: INTEGER;
	Temp: ARRAY OF Element;
      BEGIN
      IF TheArr = VOID THEN
        TheArr.CREATE (InitialSize);
	ASSERT TheUsedItems = 0;
       ELSIF TheUsedItems = TheArr.SIZE THEN
	IncrSize := TheArr.SIZE / 2;
	IF IncrSize < 16 THEN
	  IncrSize := 16;
	  END;
	Temp.CREATE (IncrSize);
	TheArr := TheArr + Temp;
	END;
      ASSERT TheArr <> VOID;
      ASSERT TheUsedItems >= 0;
      ASSERT TheUsedItems < TheArr.SIZE;
      END MakeRoom;
           
    REDEFINE METHOD Append (El: Element);
      BEGIN
      MakeRoom;
      ASSERT TheUsedItems >= 0;
      TheArr[TheUsedItems] := El;
      TheUsedItems := TheUsedItems + 1;
      ASSERT Last = El;
      ASSERT TheUsedItems > 0;
      END Append;

    REDEFINE METHOD Insert (Pos: INTEGER;
                            El: Element);
      BEGIN
      ASSERT TheUsedItems >= 0;
      ASSERT Pos >= 0;
      MakeRoom;
      IF Pos >= TheUsedItems THEN
        TheArr[TheUsedItems] := El;
       ELSE
        FOR i := TheUsedItems TO Pos + 1 BY -1 DO
          TheArr [i] := TheArr[i-1];
          END;
        TheArr[Pos] := El;
	END;
      TheUsedItems := TheUsedItems + 1;
      END Insert;

    REDEFINE METHOD Delete (Pos: INTEGER);
      BEGIN
      IF (Pos >= 0) AND (Pos < TheUsedItems) THEN
	FOR i := Pos TO TheUsedItems - 2 DO
	  TheArr [i] := TheArr [i+1];
	  END;
	TheArr [TheUsedItems - 1] := VOID;
	TheUsedItems := TheUsedItems - 1;
        END;
      END Delete;

    REDEFINE METHOD Get (Pos: INTEGER): Element;
      BEGIN
      ASSERT Pos < TheUsedItems;
      IF (Pos >= 0) AND (Pos < TheUsedItems) THEN
	RESULT := TheArr [Pos];
        END;
      END Get;

    REDEFINE METHOD Size: INTEGER;
      BEGIN
      RESULT := TheUsedItems;
      ASSERT RESULT >= 0;
      END Size;

    REDEFINE METHOD Purge;
      BEGIN
      TheUsedItems := 0;
      TheArr := VOID;
      END Purge;

    METHOD ShouldSwapIndex (One, Two: INTEGER): BOOLEAN;
      BEGIN
      RESULT := ShouldSwap (TheArr[One], TheArr[Two]);
      ASSERT RESULT IMPLIES NOT ShouldSwap (TheArr[Two], TheArr[One]);
      END ShouldSwapIndex;

    METHOD IsSorted(From, To: INTEGER): BOOLEAN;
      BEGIN
      ASSERT From >= 0;
      ASSERT From < TheUsedItems;
      ASSERT To >= 0;
      ASSERT To < TheUsedItems;
      RESULT := TRUE;
      FOR i := To TO From + 1 BY -1 WHILE RESULT DO
        RESULT := NOT ShouldSwapIndex (i-1, i);
	END;
      END IsSorted;

    REDEFINE METHOD Sort;

      METHOD Swap (One, Two: INTEGER);
	VAR
          Temp: Element;
        BEGIN
	Temp := TheArr [One];
	TheArr [One] := TheArr [Two];
	TheArr [Two] := Temp;
	END Swap;

      METHOD BubbleSort (From, To: INTEGER): INTEGER;
	VAR
	  Changed: BOOLEAN;
	  BEGIN
	Changed := TRUE;
	FOR j := From TO To + 1 WHILE Changed DO
	  Changed := FALSE;
	  FOR i := From TO To-1 DO
	    IF ShouldSwapIndex (i, i+1) THEN
	      Swap (i, i+1);
	      Changed := TRUE;
	      RESULT := RESULT + 1;
	      END;
	    END;
	  END;
	END BubbleSort;

      METHOD OrderTriad (One, Two, Three: INTEGER);
	VAR
	  Modified: BOOLEAN;
	  BEGIN
	Modified := TRUE;
	FOR i := 1 TO 5 WHILE Modified DO
          Modified := FALSE;
	  IF ShouldSwapIndex (One, Two) THEN
	    Swap (One, Two);
	    Modified := TRUE;
	    END;
	  IF ShouldSwapIndex (Two, Three) THEN
	    Swap (Two, Three);
	    Modified := TRUE;
	    END;
	  END;
	END OrderTriad;

      METHOD DoSort (From, To: INTEGER);
	VAR
          Left, Right, Middle: INTEGER;
        BEGIN
	IF NOT IsSorted (From, To) THEN
 	  IF To-From < 6 THEN
	    VOID := BubbleSort (From, To);
	   ELSE
	    Middle := (From + To) / 2;
	    OrderTriad (From, Middle, To);
	    ASSERT NOT ShouldSwapIndex (From, Middle);
	    ASSERT NOT ShouldSwapIndex (Middle, To);
	    ASSERT NOT ShouldSwapIndex (From, To);
	    Left := From;
	    Right := To;
	    WHILE Left < Right DO
	      WHILE (Left < Right) AND 
                   NOT ShouldSwapIndex (Left, Middle) DO
	        Left := Left + 1;
	        END;
              WHILE (Left < Right) AND 
                   NOT ShouldSwapIndex (Middle, Right) DO
	        Right := Right - 1;
	        END;
	      IF Left < Right THEN
	        ASSERT ShouldSwapIndex (Left, Right);
	        Swap (Left, Right);
	       ELSE
	        IF ShouldSwapIndex (Middle, Left) THEN
	          Left := Left - 1;
	       	  Right := Left;
		  END;
	        END;
	      END;
	    DoSort (From, Left-1);
	    ASSERT Left > From;
	    DoSort (Left, To);
	    ASSERT IsSorted (From, To);
	    END;
	  END;
	END DoSort;

      BEGIN
      IF TheUsedItems > 0 THEN
        DoSort (0, TheUsedItems - 1);
	ASSERT IsSorted (0, TheUsedItems - 1);
	END;
      END Sort;


    REDEFINE METHOD Index (El: Element): INTEGER;
      BEGIN
      RESULT := -1;
      IF TheUsedItems > 0 THEN
        FOR i := 0 TO TheUsedItems - 1 WHILE RESULT < 0 DO
	  IF TheArr [i] = El THEN
	    RESULT := i;
	    END;
	  END;
	END;
      END Index;

    REDEFINE METHOD Reverse;
      VAR
        Temp: Element;
      BEGIN
      FOR i := 0 TO (TheUsedItems / 2) - 1 DO
	Temp := TheArr[i];
	TheArr[i] := TheArr[TheUsedItems -i-1];
	TheArr[TheUsedItems -i-1] := Temp;
        END;
      END Reverse;

    REDEFINE METHOD SetElement (Pos: INTEGER;
  	       	                El: Element);
      BEGIN
      IF Pos < TheUsedItems THEN
        TheArr [Pos] := El;
       ELSIF Pos = TheUsedItems THEN
	Append (El);
       ELSE
        ASSERT FALSE;
        END;
      END SetElement;

    REDEFINE METHOD CLONE(Other: ArrayList(Element));
      BEGIN
      ASSERT TheArr = Other.TheArr;
      ASSERT TheUsedItems = Other.TheUsedItems;

      IF TheArr <> VOID THEN
        Other.TheArr := TheArr.CLONE;
	END;
      END CLONE;
      
    METHOD AppendList (Other: ArrayList(Element));
      VAR
        a: ARRAY OF Element;
        OldSize: INTEGER;
      BEGIN
      IF (Other <> VOID) AND (Other.TheArr <> VOID) THEN
        IF TheArr = VOID THEN
          TheArr := Other.TheArr.CLONE;
          TheUsedItems := Other.TheUsedItems;
         ELSE
          IF (TheUsedItems < TheArr.SIZE) THEN
            a := TheArr.SLICE (0, TheUsedItems);
           ELSE
            a := TheArr;
            END;
          TheArr := a + Other.TheArr;
          TheUsedItems := TheUsedItems + Other.TheUsedItems;
          Ajust;
          END;
        END;
      END AppendList;
      
  END ArrayList;

END ArrayList;
