program adtdemo (infile1,output);
    {adtdemo reads a file of single digit integers, one per line, and puts
     them into a list L. The list is then printed, purged of duplicate elements
     and printed again.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

      LIST ADT (a LINKED LIST (with header cell) implementation)

NOTES:-    1. NO ERROR CHECKING is performed in this implementation.
              The caller has responsibility for ensuring that the
              position to be RETRIEVE'd or DELETED actually exists.

           2. The position operated on by RETRIEVE, INSERT and DELETE
              is the position FOLLOWING the one pointed to by the
              position pointer (ENDLIS returns a pointer to the last
              element, and FIRST to the header cell (NOT the first element)).}


type
  infotype = integer;
  list = ^listype;
  position = list;
  listype = record
              info: infotype;
              next: list
            end;


{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

var
  infile1: text;
  L: list;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

function FIRST (L: list): position;
  begin
    FIRST:= L
  end;
function ENDLIS (L: list): position;
  var
    p: position;
  begin
    p:= L;
    while p^.next <> nil do
      p:= p^.next;
    ENDLIS:= p
  end;
function NEXT (p: position; L:list): position;
  begin
    NEXT:= p^.next
  end;
function RETRIEVE (p: position; L: list): infotype;
  begin
    RETRIEVE:= p^.next^.info
  end;
procedure DELETE (p: position; L: list);
  begin
    p^.next:= p^.next^.next
  end;
procedure MAKENULL (var L: list);
  begin
    new(L);
    L^.next:=nil;
  end;
procedure INSERT (x: infotype; p: position; var L: list);
  var
    q: position;
  begin
    new(q);
    q^.info:=x;
    q^.next:=p^.next;
    p^.next:=q
  end;
procedure REVERSE (L: list);
  var
    p,q,r: position;
  begin
    p:= L;
    q:= L^.next;
    r:= q^.next;
    while r<>nil do
      begin
        if p=L
          then
            q^.next:=nil
          else
            q^.next:=p;
        p:=q;
        q:=r;
        r:=r^.next
      end;
    q^.next:=p;
    L^.next:=q
  end;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

procedure read_in (var f: text; var L: list);
    {read_in reads the input text file and puts the elements in list L. One
     single digit integer per line is the expected file format.}
  var
    p: position;
    v: infotype;
  begin
    p:= FIRST(L);
    while not eof(f) do
      begin
        readln (f,v);
        INSERT (v, p, L);
        p:= NEXT(p, L)
      end
  end;

procedure print_out (var L: list);
    {print_out prints list L, after a linefeed. The elements are expected to be
     single digit integers (a field width of 2 is used with no formatting) if
     this is not the case the output will look confused.}
  var
    p: position;
  begin
    writeln;
    p:= FIRST(L);
    while p <> ENDLIS(L) do
      begin
        write (RETRIEVE(p, L):2);
        p:= NEXT(p, L)
      end
  end;

function SAME (a,b: infotype): boolean;
    {SAME returns true if its arguments are identical, false otherwise}
  begin
    SAME:= a=b
  end;

procedure purge (var L: list);
    {purge removes duplicate elements from list L}
  var
    p,q: position;  {p will be the "current" position in L, and q will move
                     ahead to find equal elements}
  begin
    p:= FIRST(L);
    while p <> ENDLIS(L) do
      begin
        q:= NEXT(p, L);
        while q <> ENDLIS(L) do
          if SAME (RETRIEVE(p, L), RETRIEVE(q, L))
            then
              DELETE(q, L)
            else
              q:= NEXT(q, L);
        p:= NEXT(p, L)
      end  {while}
  end;   {purge}

{     *  *  *     MAIN PROGRAM CODE STARTS HERE    *  *  *}

begin
  reset(infile1);
  MAKENULL(L);
  read_in (infile1, L);
  print_out (L);
  purge (L);
  print_out (L)
end.
