/*program adtdemo
     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 (WITHOUT a header cell) implementation)


NOTES:-    1. The position operated on by RETRIEVE and DELETE
              is the position pointed to by the position pointer.
              (ENDLIS returns a pointer to nil ("one past last element")
              and FIRST to the first element)

           2. INSERT puts its argument after the element pointed to.
              It is not possible to insert ahead of the first element.*/


#include <stdio.h>
#include <stdlib.h>

typedef int infotype;
typedef struct listype {
  infotype info;
  struct listype *next;
} *list;
typedef list position;


/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

main()
{
  void ERROR(void);
  position FIRST(list);
  position ENDLIS(list);
  position NEXT(position, list);
  infotype RETRIEVE(position, list);
  void DELETE(position *, list *);
  void MAKENULL(list *);
  void INSERT(infotype, position *, list *);
  void print_out(list);
  void purge(list);
  int SAME(infotype, infotype);

  list L;
  position p;
  infotype v;
  FILE *fp;

  MAKENULL(&L);
  if((fp = fopen("INDATL", "r"))==NULL) ERROR();
  p= FIRST(L);
  do {
    fscanf(fp,"%d",&v);
    INSERT (v, &p, &L);
  } while (!feof(fp));
  fclose(fp);
  print_out (L);
  purge(L);
  print_out (L);
  return 0;
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

void ERROR (void)
{
  exit (1);
}
position FIRST (list L)
{
  return L;
}
position ENDLIS (list L)
{
  return 0;
}
position NEXT (position p, list L)
{
  return p->next;
}
infotype RETRIEVE (position p, list L)
{
  return p->info;
}
void DELETE (position *p, list *L)
{
  position q;

  if (*p==*L) {
    *L= (*L)->next;
    *p= *L;
  }
  else {
    q= *L;
    while (q->next != *p) q= q->next;
    q->next= (*p)->next;
    q= *p;
    *p= (*p)->next;
    free(q);
  }
}
void MAKENULL (list *L)
{
  *L= 0;
}
void INSERT (infotype x, position *p, list *L)
{
  position q;

  q= (position) malloc(sizeof(struct listype));
  q->info= x;
  if (*L==0) {
    q->next= 0;
    *L= q;
  }
  else {
    q->next= (*p)->next;
    (*p)->next= q;
  }
  *p= q;
}
void print_out (list L)
   /*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.*/
{
  position p;

  printf("\n");
  p= FIRST(L);
  while (p != ENDLIS(L)) {
    printf("%3d",RETRIEVE(p, L));
    p= NEXT(p, L);
  }
  printf("\n");
}

int SAME (infotype a, infotype b)
    /*SAME returns true if its arguments are identical, false otherwise*/
{
  return a==b;
}

void purge (list L)
    /*purge removes duplicate elements from list L*/
{
  position p, q;  /*p will be the "current" position in L, and q will move
                     ahead to find equal elements*/
  p= FIRST(L);
  while (p != ENDLIS(L)) {
    q= NEXT(p, L);
    while (q != ENDLIS(L)) {
      if (SAME (RETRIEVE(p, L), RETRIEVE(q, L))) DELETE(&q, &L);
      else q= NEXT(q, L);
    }
    p= NEXT(p, L);
  }
}