IMPLEMENTATION MODULE Linked;

FROM Streams IMPORT StdOut;
IMPORT String;

  CLASS Linkable; 
    INHERITS Comparable;
    
    VAR
      Prev, Nxt: Linkable;
      
    METHOD Next8: Linkable;
      BEGIN
      RESULT := Nxt.Nxt.Nxt.Nxt.Nxt.Nxt.Nxt.Nxt;
      END Next8;
      
    METHOD Prev8: Linkable;
      BEGIN
      RESULT := Prev.Prev.Prev.Prev.Prev.Prev.Prev.Prev;
      END Prev8;

    METHOD Next: Linkable;
      BEGIN
      RESULT := Nxt;
      END Next;

    METHOD Previous: Linkable;
      BEGIN
      RESULT := Prev;
      END Previous;

    METHOD Attach (Before, After: Linkable);
      BEGIN
      Prev := Before;
      IF Before <> VOID THEN
        Before.Nxt := THIS;
        END;
      Nxt := After;
      IF After <> VOID THEN
        After.Prev := THIS;
        END;
      END Attach;

    METHOD AttachLeft (Other: Linkable);
      BEGIN
      Prev := Other;
      IF Other <> VOID THEN
        Other.Nxt := THIS;
        END;
      END AttachLeft;

    METHOD AttachRight (Other: Linkable);
      BEGIN
      Nxt := Other;
      IF Other <> VOID THEN
        Other.Prev := THIS;
        END;
      END AttachRight;

    METHOD Detach;
      BEGIN
      Prev := VOID;
      Nxt := VOID;
      END Detach;

    REDEFINE METHOD CREATE;
      BEGIN
      Detach;
      END CREATE;

    REDEFINE METHOD CLONE(Org: Linkable);
      BEGIN
      Detach;
      END CLONE;

  END Linkable;
-----------------------------------------------
  CLASS StringLinkable;
    INHERITS Linkable;

    VAR
      Value: ARRAY OF CHAR;

    REDEFINE METHOD CREATE (InitialValue: ARRAY OF CHAR);
      BEGIN
      BASE;
      Value := InitialValue;
      END CREATE;

    REDEFINE METHOD IsGreater (Other: Comparable): BOOLEAN;
      BEGIN
      WHAT Other OF
        IN StringLinkable:
          RESULT := String.Compare (Value, TAG.Value) = String.Greater;
          END;
        END;
      END IsGreater;

    METHOD SetString (a: ARRAY OF CHAR);
      BEGIN
      Value := a;
      END SetString;

    METHOD GetString: ARRAY OF CHAR;
      BEGIN
      RESULT := Value;
      END GetString;

  END StringLinkable;
-----------------------------------------------
  CLASS SortingPool;
    CONST
      PoolSize = 32;
    VAR
      RunPool: ARRAY OF LinkedList;

    REDEFINE METHOD CREATE;
      BEGIN
      RunPool.CREATE (PoolSize);
      END CREATE;

    METHOD Enter (List: LinkedList);
      VAR
        PoolNr: INTEGER;
      BEGIN
      WHILE RunPool [PoolNr] <> VOID DO
        List.Merge (RunPool [PoolNr]);
        RunPool [PoolNr] := VOID;
        PoolNr := PoolNr + 1;
        END;
      RunPool [PoolNr] := List;
      END Enter;

    METHOD Purge: LinkedList;
      BEGIN
      FOR i := 0 TO PoolSize - 1 DO
        IF RunPool[i] <> VOID THEN
          IF RESULT = VOID THEN
            RESULT := RunPool[i];
           ELSE
            RESULT.Merge (RunPool[i]);
            END;
          END;
        END;
      END Purge;

    END SortingPool;
-----------------------------------------------
  CLASS LinkedList;

    VAR
      ErrCode,
      TheSize: INTEGER;
      RefPos: INTEGER;
      
      RefElement,
      First, Last: Linkable;
      
    METHOD Check;
      VAR
        p, q: Linkable;
        BEGIN
      IF TheSize = 0 THEN
        ASSERT First = VOID;
        ASSERT Last = VOID;
       ELSE
        ASSERT First <> VOID;
        ASSERT Last <> VOID;
        p := First;
        ASSERT p.Previous = VOID;
        FOR i := 1 TO TheSize-1 DO
          q := p.Next;
          IF (q = VOID) OR (q.Previous <> p) THEN
            IF (q = VOID) THEN
              StdOut.WriteString ("q is VOID ");
             ELSE
              StdOut.WriteString ("Chaining error ");
              END;
            StdOut.WriteInt (i, 0);
            StdOut.WriteInt (TheSize, 5);
            StdOut.WriteLn;
            ASSERT FALSE;
            END;
          p := q;
          END;
        ASSERT p.Next = VOID;
        ASSERT Last = p;
        END;
      END Check;

    METHOD ErrorCode: INTEGER;
      BEGIN
      RESULT := ErrCode;
      END ErrorCode;

    METHOD Get(Nr: INTEGER): Linkable;
      BEGIN
      IF (Nr >= TheSize) OR (Nr < 0) THEN
        ErrCode := WrongSpotError;
       ELSE
        IF RefElement = VOID THEN
          RefPos := -999;
          END;
        ErrCode := NoError;
        IF Nr = RefPos THEN
          RESULT := RefElement;
         ELSIF Nr = RefPos - 1 THEN
          RESULT := RefElement.Previous;
         ELSIF Nr = RefPos + 1 THEN
          RESULT := RefElement.Next;
         ELSE
          RESULT := First;
          FOR i := 1 TO Nr / 8 DO
            RESULT := RESULT.Next8;
            END;
          FOR i := 1 TO Nr MOD 8 DO
            RESULT := RESULT.Next;
            END;
          END;
        RefPos := Nr;
        RefElement := RESULT;
        END;
      END Get;

    METHOD Set(Nr: INTEGER;
               Link: Linkable);
      VAR
        p: Linkable;
      BEGIN
      ASSERT Link <> VOID;
      Link.Detach;
      ASSERT Link.Next = VOID;
      ASSERT Link.Previous = VOID;
      IF Nr = TheSize THEN
        IF TheSize = 0 THEN
          First := Link;
         ELSE
          Link.Attach (Last, VOID);
          END;
        Last := Link;
        TheSize := Nr + 1;
       ELSE
        p := Get(Nr);
        ASSERT p <> VOID;
        Link.Attach (p.Previous, p.Next);
        IF Nr = 0 THEN
          First := Link;
         ELSIF Nr = TheSize - 1 THEN
          Last := Link;
          END;
        RefPos := Nr;
        RefElement := Link;
        p.Detach;
        END;
      END Set;

    METHOD Insert(Nr: INTEGER;
                  Link: Linkable);
      VAR
        p: Linkable;
      BEGIN
      IF Nr = TheSize THEN
        Set (Nr, Link);
       ELSE
        p := Get(Nr);
        IF p <> VOID THEN
          Link.Attach (p.Previous, p);
          TheSize := TheSize + 1;
          IF Nr = 0 THEN
            First := Link;
            END;
          RefPos := Nr;
          RefElement := Link;
          END;
        END;
      END Insert;

    METHOD Delete (Nr: INTEGER);
      VAR
        Before, Elem: Linkable;
      BEGIN
      IF (Nr >= 0) AND (Nr < TheSize) THEN
        IF Nr = 0 THEN
          Elem := First;
          First := First.Next;
          IF First <> VOID THEN
            First.AttachLeft (VOID);
            END;
         ELSIF Nr = TheSize - 1 THEN
          Elem := Last;
          Last := Last.Previous;
          Last.AttachRight (VOID);
         ELSE
          Elem := Get (Nr);
          Before := Elem.Previous;
          Before.Attach (Before.Previous, Elem.Next);
          END;
        Elem.Detach;
        TheSize := TheSize - 1;
        RefPos := -999;
        RefElement := VOID;
        END;
      END Delete;

    METHOD Size: INTEGER;
      BEGIN
      RESULT := TheSize;
      END Size;

    METHOD Append (Link: Linkable);
      BEGIN
      IF Link <> VOID THEN
        Set (TheSize, Link);
        END;
      END Append;

    METHOD Merge (Other: LinkedList);
      VAR
        Prev, SourceP, ToAddP: Linkable;
        GoOn: BOOLEAN;
      BEGIN
      DEBUG
        Check;
        Other.Check;
        END;
      IF Other.TheSize > 0 THEN
        IF Size = 0 THEN
          ASSERT First = VOID;
          ASSERT Last = VOID;
          First := Other.First;
          Last := Other.Last;
         ELSE -- None of the two list is void
          SourceP := First;
          ToAddP := Other.First;
          ASSERT SourceP <> VOID;
          ASSERT ToAddP <> VOID;
          GoOn := TRUE;
          WHILE GoOn DO
            IF SourceP = VOID THEN
              IF ToAddP <> VOID THEN
                ToAddP.AttachLeft (Last);
                Last := Other.Last;
                END;
              GoOn := FALSE;
             ELSE
              ASSERT ToAddP <> VOID;
              WHILE (SourceP <> VOID) AND ToAddP.IsGreater(SourceP) DO
                SourceP := SourceP.Next;
                END;
              IF SourceP <> VOID THEN        -- SourceP > ToAdd > SourceP.Prev
                ToAddP.AttachLeft (SourceP.Previous);
                IF SourceP = First THEN
                  First := ToAddP;
                  END;
                WHILE (ToAddP.Next <> VOID) AND
                       SourceP.IsGreater(ToAddP.Next) DO
                  ToAddP := ToAddP.Next;
                  ASSERT ToAddP <> VOID;
                  END;
                Prev := ToAddP.Next;
                ToAddP.AttachRight (SourceP);
                ToAddP := Prev;
                IF ToAddP = VOID THEN
                  GoOn := FALSE;
                 ELSE
                  SourceP := SourceP.Next;
                  END;
                END;
              END;
            END;
          END;
        TheSize := TheSize + Other.TheSize;
        Other.First := VOID;
        Other.Last := VOID;
        Other.TheSize := 0;
        END;
      DEBUG
        Check;
        END;
      END Merge;

  METHOD AttachLeft(El: Linkable);
    BEGIN
    El.Attach (VOID, First);
    First := El;
    TheSize := TheSize + 1;
    END AttachLeft;

  METHOD AttachRight (El: Linkable);
    BEGIN
    El.Attach (Last, VOID);
    Last := El;
    TheSize := TheSize + 1;
    END AttachRight;

  METHOD Sort;
    VAR
      Run: LinkedList;
      Keep, Val: Linkable;
      Pool: SortingPool;
    BEGIN
    Pool.CREATE;
    Val := First;
    Run.CREATE;
    WHILE Val <> VOID DO
      Keep := Val.Next;
      CASE Run.TheSize OF
        0:
          Run.First := Val;
          Run.Last := Val;
          Val.Attach (VOID, VOID);
          Run.TheSize := 1;
          END;
        1:
          IF Val.IsGreater (Run.First) THEN
            Run.AttachRight(Val);
           ELSE
            Run.AttachLeft(Val);
            END;
          END;
       ELSE   -- Let's try to attach it at the left or the right side
        IF Run.First.IsGreater (Val) THEN
          Run.AttachLeft(Val);
         ELSIF Val.IsGreater(Run.Last) THEN
          Run.AttachRight(Val);
         ELSE  -- The run is completed !
          Pool.Enter (Run);
          Run.CREATE;
          Keep := Val;
          END;
        END; -- Case
      Val := Keep;
      END; -- While
    Pool.Enter (Run);
    Run := Pool.Purge;
    Pool := VOID;
    First := Run.First;
    Last := Run.Last;
    TheSize := Run.TheSize;
    Run := VOID;
    RefPos := -999;
    RefElement := VOID;
    END Sort;
    
    METHOD Purge;
      BEGIN
      First := VOID;
      Last := VOID;
      RefElement := VOID;
      TheSize := 0;
      RefPos := 0;
      ErrCode := 0;   
      END Purge;
      
    REDEFINE METHOD CLONE (Other: LinkedList);
      BEGIN
      Purge;
      FOR i := 0 TO Other.Size - 1 DO
        Append (Other.Get(i).CLONE);
        END;
      END CLONE;

  END LinkedList;

END Linked;
