/* implementation details for a linked list of names,
   based on a general interface */
/* author:  Henry M. Walker  */
/* updates: Jerod Weinman  */

#include "list-proc.h"

#include <string.h> /* library for string comparison */
#include <stdio.h>  /* library for standard I/O */
#include <stdlib.h> /* C library for memory allocation */

/* helper function to read a string into a buffer of length MAXSTRLEN */
void
getString (const char * prompt, char * buffer)
{
  int numTokens;
  do {
    printf ("%s", prompt);
    numTokens = scanf (SCANSTR(MAXSTRLEN), buffer);
    if (numTokens==0) {
      printf ("Error reading value. Please try again.\n");
      continue;
    }
  } while (numTokens==0);
} // getString


void
addName (node_t ** 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+1];
  node_t * newNode = malloc (sizeof (node_t));
  node_t * listPtr;
  node_t * prevPtr;
  
  if (newNode==NULL) {
    perror ("Unable to allocate node");
    return;
  }

  getString ("Enter name to be inserted into list: ", newNode->data);

  if (*firstPtr == NULL) {
    /* insert name's node at start of list */
    newNode->next = *firstPtr;
    *firstPtr = newNode;
  }
  else {
    getString ( "Enter old name which new name should precede, \n"
                "or enter ? if new name should be placed last: ", oldName );
        
    if (strncmp (oldName, (*firstPtr)->data, MAXSTRLEN) == 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!=NULL &&
             strncmp (oldName, listPtr->data, MAXSTRLEN) != 0) {
        prevPtr = listPtr;
        listPtr = prevPtr->next;
      } // while

      newNode->next = prevPtr->next;
      prevPtr->next = newNode;
    } // else if strncmp
  } // else if *firstPtr == NULL
  printf ("%s inserted into the list\n\n", newNode->data);
} // addName


void
countList (const node_t * 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
*/
  int count = 0;
  for (node_t * current = (node_t *)first ; // discard const for iteration
       current != NULL ;
       current = current->next )
  {
    count++;
  }

  printf ("The list contains %d nodes\n\n", count);
} // countList


void
deleteName (node_t ** 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+1];
  node_t * listPtr;
  node_t * prevPtr;

  if (*firstPtr) {/* list is non-empty */
    getString ("Enter name to be deleted: ", name);
    
    if (strncmp(name, (*firstPtr)->data, MAXSTRLEN) == 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) &&
              (strncmp (name, listPtr->data, MAXSTRLEN) != 0)) {
        prevPtr = listPtr;
        listPtr = prevPtr->next;
      } // while

      /* determine whether we ran out of items or found match */
      if (listPtr != NULL) { 
        /* 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");
  } 
}  // deleteName


void
print (const node_t * 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
*/    

  printf ("The names on the list are:\n\n");

  for (node_t * current = (node_t *)first ; // discard const for iteration
       current != NULL ;
       current = current->next ) {
    printf ("%s\n", current->data);
  }

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


void
printLast (const node_t * 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
*/
  if (first == NULL) {
    printf ("The list is empty --- no last element\n\n");
    return;
  }
  node_t * current;
  for (current = (node_t *)first ; // discard const for iteration
       current->next != NULL ;
       current = current->next )
    ;
  printf ("The last name on the list is %s\n\n", current->data);
} // printLast


/* the following function is used as a helper to printReverse,
   so this function is declared before printReverse
   The function is not included in the prototypes at the start,
   because it is used only as a private helper */
void
printReverseHelper (const node_t * 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
*/
  if (first != NULL) {
    printReverseHelper (first->next);
    printf("\t%s\n", first->data);
  }
} // printReverseHelper


void printReverse (const node_t * 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
                   Printing includes initial yitle
*/
  printf ("The list in reverse order is:\n");
  printReverseHelper (first);
  printf("\n\n");
} // printReverse

void
putFirst (node_t ** 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 to move an item to the front of the list\n");
  if (*firstPtr == NULL) {
    printf ("list is empty, so no items available to move\n\n");
    return;
  }
  
  char str [MAXSTRLEN+1];
  getString ("Enter name of item:  ", str);

  if (strncmp ((*firstPtr)->data, str, MAXSTRLEN) == 0) {
    printf ("item already first\n\n");
    return;
  }

  node_t * ptr = (*firstPtr)->next;
  node_t * prevPtr = *firstPtr;

  /* move along list to find item */
  while ((ptr != NULL) && (strncmp (ptr->data, str, MAXSTRLEN) != 0)) {
    prevPtr = ptr;
    ptr = ptr->next;
  }

  if (ptr == NULL)
    printf ("item not found\n\n");
  else { /* move item's node to front */
    prevPtr->next = ptr->next;
    ptr->next = (*firstPtr);
    *firstPtr = ptr;
    printf ("item moved to front\n\n");
  }
} // putFirst