IMPLEMENTATION MODULE YLinked;

FROM Streams IMPORT StdOut;

  CLASS Linkable(Covariant IN Linkable);
    INHERITS Comparable;
    
    VAR
      Prev, Nxt: Covariant;
      
    METHOD Next8: Covariant;
      BEGIN
      WHAT Nxt.Nxt.Nxt.Nxt.Nxt.Nxt.Nxt.Nxt OF
        IN Covariant:
          RESULT := TAG;
          END;
        END;
      END Next8;
      
    METHOD Prev8: Linkable;
      BEGIN
      WHAT Prev.Prev.Prev.Prev.Prev.Prev.Prev.Prev OF
        IN Covariant:
          RESULT := TAG;
          END;
        END;
      END Prev8;

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

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

    METHOD Attach (Before, After: Covariant);
      BEGIN
      Prev := Before;
      WHAT THIS OF
        IN Covariant:
          IF Before <> VOID THEN
            Before.Nxt := TAG;
            END;
          Nxt := After;
          IF After <> VOID THEN
            After.Prev := TAG;
            END;
          END;
        END;
      END Attach;

    METHOD AttachLeft (Other: Covariant);
      BEGIN
      Prev := Other;
      IF Other <> VOID THEN  
        WHAT THIS OF
          IN Covariant:
            Other.Nxt := TAG;
            END;
          END;
        END;
      END AttachLeft;

    METHOD AttachRight (Other: Covariant);
      BEGIN
      Nxt := Other;
      IF Other <> VOID THEN
        WHAT THIS OF
          IN Covariant:
            Other.Prev := TAG;
            END;
          END;
        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 SortingPool(Element IN Linkable);
    CONST
      PoolSize = 32;
    VAR
      RunPool: ARRAY OF LinkedList(Element);

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

    METHOD Enter (List: LinkedList(Element));
      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(Element);
      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(Element IN Linkable);
    INHERITS AbstractList(Element);

    VAR
      ErrCode,
      TheSize,
      RefPos: INTEGER;
      
      RefElement,
      First, 
      Last: Element;
      
    METHOD Check;
      VAR
        p, q: Element;
        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 := Cast(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 Cast (l: Linkable): Element;
      BEGIN
      WHAT l OF
        IN Element:
          RESULT := TAG;
          END;
        END;
      END Cast;

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

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

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

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

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

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

    METHOD Merge (Other: LinkedList(Element));
      VAR
        Prev, SourceP, ToAddP: Element;
        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: Element);
    BEGIN
    El.Attach (VOID, First);
    First := El;
    TheSize := TheSize + 1;
    END AttachLeft;

  METHOD AttachRight (El: Element);
    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 YLinked;
