/*
  Student Name:
  Student NETID:
  Email Address:
  Problems Solved:
*/


/*
PROGRAM  : list.c
PURPOSE  : insert/delete in a list implemented with pointers
UNIX COMP: gcc -o list  list.c
PC COMP  : TURBO C++ (tcc) or Borland
TEST     : list list.dat
           list list1.dat
INTERACT : list
REDIRECT : list <list.dat
           list <list1.dat
HELP     : h(elp; q(uit; H(ead x; D(elete x; d(isplay; t(ail x; T(ail x; o(rdered x; b(ackward; a(nother; I(ntersect; s(how_list
EXERCISES: Ex1..Ex6, Ex8, Ex9, Ex12, Ex14
*/

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

typedef char element_type;
typedef struct node *node_ptr;
struct node {
  element_type element;
  node_ptr next;
  node_ptr prev;
};

struct list_record {
  node_ptr head;
  node_ptr tail;
};

typedef node_ptr position;
typedef struct list_record *LIST;


int is_empty(LIST L) {
  return(L->head->next == NULL);
}

int is_last(position p) {
  return(p->next == NULL);
}

position find(element_type x, LIST L) {
position p = NULL;
  if (L != NULL) {
    p = L->head->next;
    while ( (p != NULL) && (p->element !=x) )
      p = p->next;
  }
  return p;
}

position find_previous(element_type x, LIST L) {
position p;
  p = L->head;
  while ( (p->next != NULL) && (p->next->element != x) )
    p = p->next;
  return p;
}

/* Ex1 : create both a pointer to a list and a header node */
/* Ex5 : the tail should also point to the header          */
/* Ex9 : initialize prev pointer                           */
LIST create_list() {
  return(NULL);
}

/* Ex5 : what if the tail is deleted? */
/* Ex9 : take care of prev pointer    */
void delete1(element_type x, LIST L) {
position p, tmp_cell;
  if (L != NULL) {
    p = find_previous(x,L);
    if (p->next != NULL) { 
      tmp_cell = p->next;
      p->next = tmp_cell->next; /* bypass */ 
      free(tmp_cell);
    }
  }
}

/* Ex5 : what if a new element is inserted after the tail? */
/* Ex9 : take care of prev pointer */
void insert(element_type x, LIST L, position p) {
position tmp_cell;

  if (L != NULL) {
    tmp_cell = (position) malloc(sizeof(struct node));
    if (tmp_cell == NULL) 
      printf("Out of space!\n");
    else {
      tmp_cell->element = x;
      tmp_cell->next = p->next;
      p->next = tmp_cell;
    }
  }
} 

/* Ex5 : tail should be reinitialized as in create_list */
void delete_list(LIST L) {
position p, tmp;

  if (L != NULL) {
    p = L->head->next;   
    L->head->next = NULL;
    while (p != NULL) {
      tmp = p->next;
      free(p);
      p = tmp;
    }
  }
}
      
/* Ex2 : insert x at the head of the list */
void head_insert(element_type x, LIST L) {
}
      
/* Ex3 : print all the elements except the header */
 void display_list(LIST L) {
}

/* Ex4 : scan from the head and insert x at the end of the list */
void tail_insert(element_type x, LIST L) {
}

/* Ex5 : insert x directly at the tail of the list using tail pointer */
void Tail_insert(element_type x, LIST L) {
}

/* Ex6 : insert x in order (alpabetically) into the list */
void ordered_insert(element_type x, LIST L) {
}

/* Ex8 : print out the intersection of L and L1 */
void intersect(LIST L, LIST L1) {
}

/* Ex9 : using the prev pointers, print the list backwards */
void backward_list(LIST L) {
}

/* Ex12 : recursive s(how_list */
void show_list(position p) {
}

/* Ex14 : recursive c(ount */

int count (position p) {
  return 0;
}

void cmd_interpreter(FILE *fp) {
char cmd, xtra;
LIST L;
LIST L1;
element_type x;

  L = create_list();
  printf("> ");
  while (fscanf(fp,"%c",&cmd) != EOF) {
    switch (cmd) {
      case 'q' : printf("\n");
                 exit(0);
      case 'h' : printf("h(elp; q(uit; H(ead x; D(elete x; d(isplay; t(ail x; T(ail x; o(rdered x; b(ackward; a(nother; I(ntersect; s(how_list\n");
                 break;
      case 'H' : fscanf(fp," %c",&x);
                 head_insert(x,L);
                 break;
      case 'D' : fscanf(fp," %c",&x);
                 delete1(x,L);
                 break;
      case 'd' : display_list(L);
                 break;
      case 't' : fscanf(fp," %c",&x);
                 tail_insert(x,L);
                 break;
      case 'T' : fscanf(fp," %c",&x);
                 Tail_insert(x,L); 
                 break;
      case 's' : /* Ex12: uncomment this call after create is OK */
                 /* 
                 show_list(L->head->next);
                 */
                 break;
      case 'o' : fscanf(fp," %c",&x);
                 ordered_insert(x,L);
                 break; 
      case 'b' : backward_list(L);
                 break;
                 /* Ex7: create another list (already completed) */ 
      case 'a' : L1 = L;
                 L = create_list();
                 break;
      case 'I' : intersect(L,L1); 
                 break;
      case 'c' : /* Ex14: uncomment this call after create is OK */
                 /*
                 printf("count: %d\n",count(L->head->next));
                 */
                 break;
    }
    fscanf(fp,"%c",&xtra);
    printf("> ");
  }
}

int main(int argc, char *argv[]) {
FILE *fp;
  if (argc == 1)
    fp = stdin;
  else {
    fp = fopen(argv[1],"r");
    if (fp == NULL) {
      printf("No File: %s\n",argv[1]);
      return 1;
    }
  }
  cmd_interpreter(fp);
  return 0;
}