/* A program shell to maintain a linked list of names */

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

/* Maximum length of names */
#define MAXSTRLEN 128

typedef struct node listNode;

struct node
{ char data[MAXSTRLEN];
  struct node* next;
};

/* function prototypes, listed in alphabetical order */

void
addName (listNode** firstPtr);
/* pre-condition:  firstPtr points to the pointer
                   designating the head of a list
  post-condition:  a name is read and
                   inserted into the list at a designated place
*/

void
countList (listNode* first);
/* pre-condition:  first designates the first node of a list 
  post-condition:  the number of items on the list is counted and printed
                   the list itself is unchanged
*/

void
deleteName (listNode** firstPtr);
/* pre-condition:  firstPtr points to the pointer designating the head of a list
  post-condition:  a name is read and
                   that name is deleted from the list
*/

void
print (listNode* first);
/* pre-condition:  first designates the first node of a list 
  post-condition:  The items on the list are printed from first to last
                   the list itself is unchanged
  note:  processing proceeds iteratively
*/

void
printRec (listNode* first);
/* pre-condition:  first designates the first node of a list 
  post-condition:  The items on the list are printed from first to last
                   the list itself is unchanged
  note:  processing proceeds recursively
*/

void
printLast (listNode* first);
/* pre-condition:  first designates the first node of a list 
  post-condition:  the last item on the list is printed; 
                   the list itself is unchanged
  note:  processing proceeds iteratively
*/

void
printLastRec (listNode* first);
/* pre-condition:  first designates the first node of a list 
  post-condition:  the last item on the list is printed; 
                   the list itself is unchanged
  note:  processing proceeds recursively
*/

void
printReverse (listNode* first);
/* pre-condition:  first designates the first node of a list 
  post-condition:  The items on the list are printed from last to first
                   the list itself is unchanged
*/

void
putFirst (listNode** firstPtr);
/* pre-condition:  first designates the first node of a list 
  post-condition:  a name is read, located on the list,
                   and placed at the beginning of the list
  note:  processing proceeds iteratively
*/


/* Print menu options to the screen */
void
printMenu ()
{
  printf("Options available\n");
  printf("I - Insert a name into the list\n");
  printf("D - Delete a name from the list\n");
  printf("C - Count the number of items on the list\n");
  printf("F - Move an item to the front of the list\n");
  printf("L - Print the last item on the list (iteratively)\n");
  printf("M - Print the last item on the list (recursively)\n");
  printf("P - Print the names on the list (iteratively)\n");
  printf("S - Print the names on the list (recursively)\n");
  printf("R - Print the names in reverse order\n");
  printf("Q - Quit\n");
}

/* program to coordinate the menu options and call the requested function */
int
main (void)
{
  listNode * first = NULL;   /* pointer to the first list item */
  char option[MAXSTRLEN];          /* user response to menu selection */

  printf("Program to Maintain a List of Names\n");

  while (1) {
      printMenu(); /* print menu options */
      printf("Enter desired option: "); /* determine user selection */
      scanf("%s", option);
    
      switch (option[0]) {
        case 'I':
        case 'i': addName(&first);
          break;
        case 'D':
        case 'd': deleteName(&first);
          break;
        case 'C':
        case 'c': countList(first);
          break;
        case 'F':
        case 'f': putFirst(&first);
          break;
        case 'L':
        case 'l': printLast(first);
          break;
        case 'M':
        case 'm': printLastRec(first);
          break;
        case 'P':
        case 'p': print(first);
          break;
        case 'S':
        case 's': printRec(first);
          break;
        case 'R':
        case 'r': printReverse(first);
          break;
        case 'Q':
        case 'q':
          printf("Program terminated\n");
          return 0;
          break;
        default: printf("Invalid Option - Try Again!\n");
          continue;
      } // switch
  } // while
} // main

void
addName (listNode** firstPtr) {
/* pre-condition:  firstPtr points to the pointer designating the head of a list
  post-condition:  a name is read and
                   inserted into the list at a designated place
*/

  char oldName[MAXSTRLEN];
  listNode* newNode = (listNode *)malloc(sizeof(listNode));
  listNode* listPtr;
  listNode* prevPtr;

   printf("Enter name to be inserted into list: ");
   scanf("%s", newNode->data);

   if (*firstPtr == NULL) {
     /* insert name's node at start of list */
     newNode->next = *firstPtr;
     *firstPtr = newNode;
   }
  
   else {
     printf("Enter old name which new name should preceed, \n");
     printf("or enter ? if new name should be placed last\n");
     scanf("%s", oldName);

     if (strcmp(oldName, (*firstPtr)->data) == 0) {
       /* insert name's node at start of list */
       newNode->next = *firstPtr;
       *firstPtr = newNode;
     }
     else {
       /* insert name's node after start of the list */
       
       /* start at beginning of list */
       listPtr = (*firstPtr)->next;  /* the current node to search */
       prevPtr = *firstPtr;          /* the node behind listPtr */
       
       while (listPtr && (strcmp (oldName, listPtr->data) != 0)) {
         prevPtr = listPtr;
         listPtr = prevPtr->next;
       }

       newNode->next = prevPtr->next;
       prevPtr->next = newNode;
     }
   }
   printf("%s inserted into the list\n\n", newNode->data);
}

void
countList (listNode* first) {
/* pre-condition:  first designates the first node of a list 
  post-condition:  the number of items on the lsit is counted and printed
                   the list itself is unchanged
*/
  printf("Function countList is not implemented at present\n\n");
}

void
deleteName (listNode** firstPtr) {
/* pre-condition:  firstPtr points to the pointer designating the head of a list
  post-condition:  a name is read and
                   that name is deleted from the list
*/
  char name[MAXSTRLEN];
  listNode* listPtr;
  listNode* prevPtr;

  if (*firstPtr) {/* list is non-empty */
    printf("Enter name to be deleted: ");
    scanf("%s", name);
    
    if (strcmp(name, (*firstPtr)->data) == 0) {
      /* remove first item on list */
      listPtr = *firstPtr;
      *firstPtr = (*firstPtr)->next;
      free(listPtr);
      printf("%s removed as first item on list\n\n", name);
    }
    else {
      /* item to remove is not at beginning of list */
      /* start at beginning of list */
      listPtr = (*firstPtr)->next;  /* the current node to search */
      prevPtr = *firstPtr;          /* the node behind listPtr */
      
      while ( (listPtr != NULL) && (strcmp (name, listPtr->data) != 0)) {
        prevPtr = listPtr;
        listPtr = prevPtr->next;
      }
      
      if (listPtr) { /* determine whether we ran out of items or found match */
        /* remove item from list */
        prevPtr->next = listPtr->next;
        free (listPtr);
        printf("%s deleted from list\n\n", name);
      }
      else {
        printf("%s not found on list\n\n", name);
      }
    } /* end processing of name */
  }
  else {
    printf("List is empty - no deletions are possible\n");
  } 
}

void
print (listNode* first) {
/* pre-condition:  first designates the first node of a list 
  post-condition:  The items on the list are printed from first to last
                   the list itself is unchanged
  note:  processing proceeds iteratively
*/    
  listNode * listElt = first;
  printf("The names on the list are:\n\n");

  while (listElt) {
    printf("%s\n", listElt->data);
    listElt = listElt->next;
  }

  printf("\nEnd of List\n\n");
}

void
printRec (listNode* first) {
/* pre-condition:  first designates the first node of a list 
  post-condition:  The items on the list are printed from first to last
                   the list itself is unchanged
  note:  processing proceeds recursively
*/
  printf("Function printRec is not implemented at present\n\n");
}

void
printLast (listNode* first) {
/* pre-condition:  first designates the first node of a list 
  post-condition:  the last item on the list is printed; 
                   the list itself is unchanged
  note:  processing proceeds iteratively
*/
  printf("Function printLast is not implemented at present\n\n");
}

void
printLastRec (listNode* first) {
/* pre-condition:  first designates the first node of a list 
  post-condition:  the last item on the list is printed; 
                   the list itself is unchanged
  note:  processing proceeds recursively
*/
  printf("Function printLastRec is not implemented at present\n\n");
}

void
printReverse (listNode* first) {
/* pre-condition:  first designates the first node of a list 
  post-condition:  The items on the list are printed from last to first
                   the list itself is unchanged
*/
  printf("Function printReverse is not implemented at present\n\n");
}

void
putFirst (listNode** firstPtr) {
/* pre-condition:  first designates the first node of a list 
  post-condition:  a name is read, located on the list,
                   and placed at the beginning of the list
*/
  printf("Function putFirst is not implemented at present\n\n");
}