/* This program implements the functions of the Linked List Data Structure.  There are 4 cases.  Case 4 exits, 
case 1  finds an elephant, case 2 adds a new elephant, and case 3 deletes an elephant.  

Note that this program does not use files and does not permanently  save the list.  The list is re-initialized 
each time the program is run.  An improvement to this program would be to use files and permanently  
save the list for use each time the program is run.*/

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

char line[100];
/* declare a self-referential structure */
typedef struct elephant{
	char name[10];
	struct elephant *next;
}ELEPHANT;

main()
{
	int count = 1, num, choice;
	ELEPHANT elephant1, elephant2, elephant3, elephant4, elephant5, elephant6, new_elephant;
	ELEPHANT *start, *new_el, *del, *start_print;

      /******************* function prototypes *****************************/
	ELEPHANT *delete_nth_node(ELEPHANT *ptr, int n);
	ELEPHANT *add_at_nth(ELEPHANT *ptr, ELEPHANT *new1, int n);
	ELEPHANT *find_nth_node(ELEPHANT *ptr, int n);
      
	strcpy(elephant1.name, "Edna");          // Initialize the elephant names
	strcpy(elephant2.name, "Elmer");
	strcpy(elephant3.name, "Ethel");
	strcpy(elephant4.name, "Ella");
	strcpy(elephant5.name, "Eddie");
	strcpy(elephant6.name, "Elf");

	/* link elephants by their trunks to tails */

	elephant1.next = &elephant2;
	elephant2.next = &elephant3;
	elephant3.next = &elephant4;
	elephant4.next = &elephant5;
	elephant5.next = &elephant6;
	elephant6.next = NULL;

	start = &elephant1;
	start_print = &elephant1;    // display pointer
	while (start_print != NULL)
	{
	   printf ("\n Elephant number %d is %s", count++, start_print->name);
	   start_print = start_print -> next;
	}

	while (1)        // always true
	{
	printf("\nWould you like to:\n\t 1) Find an elephant");
	printf("\n\t 2) Add an elephant");
	printf("\n\t 3) Delete an elephant");
	printf("\n\t 4) Exit \n\t?");
        cin >> choice;

	//fgets(line, sizeof(line), stdin);  Classic C input functions 
	//sscanf(line, "%d", &choice);

	switch(choice)	{

	case 1: {
	  start = &elephant1;
	  printf("\n Which elephant number would you like to find?\t");
	  cin >> num;    
      
	  printf ("\n Elephant number %d is %s.", num,
		      		 find_nth_node(start, num)->name);
     break; }

	case 2: {
	  start = &elephant1;
	  printf("\n Where would you like to add an elephant?\t");
          cin >> num; 
     
	  printf("\n What is the new name?");
          cin >> new_elephant.name;
   
	  new_el = &new_elephant;
	  start = add_at_nth(start, new_el, num);
	  printf("The list is now:");
	  count = 1;
	  while (start != NULL)
	    {
	      printf ("\n Elephant number %d is %s\n", count++, start->name);
	      start = start -> next;
	    }
	break; }

	case 3: {
	  printf("\n Which elephant would you like to delete?\t");
	  cin >> num;    

	  start_print = delete_nth_node(start, num);
	  start = start_print;           // start begins at the head of the list
	  printf("The list is now:");
	  count = 1;
	  while (start_print != NULL)
	  {
	    printf ("\n Elephant number %d is %s\n", count++,
						    start_print -> name);
	    start_print = start_print -> next;
	  }
     break; }

	case 4:
	  return(0);     // Escape from the while loop and exit the program

	default:
	  printf("\n Please try again. \n");
     continue;
	}
     }

	return (0);
}

/*********************** function definitions **************************/

  ELEPHANT *find_nth_node(ELEPHANT *ptr, int n)
	{
	if (n < 1)
	 return(NULL);
     while (--n && ptr != NULL)
	 ptr = ptr -> next;          /* step to next node in the list */
	return(ptr);
     }

  ELEPHANT *add_at_nth(ELEPHANT *ptr, ELEPHANT *new1, int n)
	{
	ELEPHANT *find_nth_node(ELEPHANT *ptr, int n), *pred;
	if (n == 1)
	{
	   new1 -> next = ptr;
	   return(new1);
	}
	pred = find_nth_node(ptr, n - 1);

	if (pred == NULL)
	   return (NULL);

	new1 -> next = pred -> next;
	pred -> next = new1;

	return(ptr);
	}

  ELEPHANT *delete_nth_node(ELEPHANT *ptr, int n)
    {
    ELEPHANT *pred, *old, *find_nth_node(ELEPHANT *ptr, int n);
    if (n == 1)
      {
       if (ptr == NULL)
	  return (ptr);
       else {
	  old = ptr;
	  ptr = ptr -> next; }
      }
    else {
	  pred = find_nth_node(ptr, n-1);
	  if (pred == NULL || pred -> next == NULL)
	     return (ptr);
	  old = pred -> next;
	  pred -> next = old -> next;
	 }
    return(ptr);
 }