/*************************************************
* Filename:     linkedlist.c                     *
* Author:       Sue Evans                        *
* Date Written: 5/1/08                           *
* Section:      201staff                         *
* EMail:        bogar@cs.umbc.edu/               *
*                                                *
* Description:  This file contains the functions *
* necessary to work with a linked list that has  *
* a structure as the data portion of a NODE.     *
*   This set of functions provide the operations *
* needed including creation of a node, insertion,*
* deletion, determining if a list is empty and   *
* the printing of the list.                      *
**************************************************/

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

#include "linkedlist.h"


/***********************************************
* Function: CreateNode()                       *
* Input:    none                               *
* Output:   a pointer (of type NODEPTR) is     * 
*           returned that points to the        *
*           newly allocated NODE.              *
*                                              *
* CreateNode() mallocs the memory necessary    *
* to hold a NODE.  The members of the NODE's   *
* structure are initialized, and the beginning *
* address of that memory is returned.          *
*                                              *
* NOTE: Exits if there is insufficient memory. *                 
***********************************************/ 
NODEPTR CreateNode (void)
{
   NODEPTR newNode;

   /* Get the space needed for the node */
   newNode = (NODEPTR) malloc (sizeof(NODE));
   if (newNode == NULL)
   {
      fprintf (stderr, "Out of Memory - CreateNode\n");
      exit (-1);
   }

   /* Initialize the members to blank or 0. */
   strcpy(newNode -> data.firstName, "");
   strcpy(newNode -> data.lastName,  "");
   newNode -> data.grade = 0;
   newNode -> data.id    = 0;
   newNode -> next = NULL;

   return newNode;
}


/**************************************************
* Function: SetData                               *
* Inputs:   a pointer to a newly-created node     *
*           a STUDENT structure which contains    *
*            the data to be placed into that node *
*                                                 *            
* Output:   None                                  *
*                                                 *
* The data member of the node pointed to by temp  *
* (temp->data) is populated with the values in    *
* newStudent                                      *
**************************************************/ 
void SetData (NODEPTR temp, STUDENT newStudent)
{
   temp -> data = newStudent;
} 


/**************************************************
* Function: Insert                                *
* Inputs:   the address of head which is of type  *
*            NODEPTR * and is called headPtr      *
*            within this function                 *
*           a pointer to the node to insert which *
*            is of type NODEPTR and is called     *
             temp within the function             *
* Output:   None                                  *
*                                                 *
* The node 'temp' is added to the linked list at  *
* the end of the list.                            *
**************************************************/ 
void Insert (NODEPTR* headPtr, NODEPTR temp)
{
   NODEPTR prev, curr;

   /* If the list is empty, add the new node at *
    * the headStructure's head. */
   if (IsEmpty(*headPtr))
   {
       *headPtr = temp;
   }
   else
   {
      prev = NULL;
      curr = *headPtr;

      /* traverse the list until the end */
      while (curr != NULL)
      {
	 prev = curr;
	 curr = curr -> next;
      }
  
      /* insert the node, temp, at the end */
      prev -> next = temp;
     
   }
}

/**************************************************
* Function: Delete                                *
* Inputs:   the address of the head (NODEPTR*)    *
*            called headPtr in the function       *
*           the id of student to be deleted (int) *
* Output: If found, the student id of the         *
*          student being deleted is returned      *
*         If not found, a -1 is returned          *
*                                                 *
* The list is traversed looking for a NODE that   *
* has as the student's id the value passed in as  *
* the target.  If the id number that matches the  *
* target is found, the node is deleted from the   *
* list and the id number is returned.  If the end *
* of the list is reached without encountering the *
* target id number, then -1 is returned           *
**************************************************/ 
int Delete (NODEPTR* headPtr, int target)
{
   NODEPTR prev = NULL, curr = NULL;
   int found = -1;

   if (IsEmpty(*headPtr))
   {
      /* Error deleting from an empty list */
      return -1;
   }
   
   /* traverse the list until the target value is 
    * found */
   
   prev = NULL;
   curr = *headPtr;

   /* first check to see if the node we want is *
    * the first in the list..because then we'd  *
    * have to modify head  (*headPtr)           */
   if(curr->data.id == target)
   {
      *headPtr = curr -> next;
      free(curr);
      found = target;
   }  

   /* otherwise, traverse the list to look *
    * for the target                       */
   else
   {
      while ((curr != NULL) && 
             (curr->data.id != target))
      {
         prev = curr;
         curr = curr -> next;
      }
   
      /* the target was found */      
      if(curr != NULL)
      {
         /* delete the node the contains
	    the target value */
         prev -> next = curr -> next;
         free(curr);
     
         found = target;
      }

      /* the target was not found */
      else
      {
         found = -1;
      }
   }     
      
   return found;
}


/**************************************************
* Function: IsEmpty                               *
* Input:    a pointer to the head of the linked   *
*            list                                 *
* Output:   returns a true value if the list is   *
*            empty; returns 0 (false) if the list *
*            is not empty                         *
**************************************************/
int IsEmpty (NODEPTR head)
{
   /* If the pointer to the list is
   NULL then there is no list.  The
   list is empty, so we return true.
   */
   return (head == NULL);
}


/**************************************************
* Function: PrintList                             *
* Input:    the head of the list                  *
* Ouput:    None                                  *
*                                                 *
* The data in each node in the list is printed    *
* according to the format specified               *
**************************************************/ 
void PrintList (NODEPTR head)
{
   NODEPTR curr;

   if (IsEmpty(head))
   {
      printf ("The list is empty\n");
   }
   else
   {
      /* set the current pointer to the first node of the list */
      curr = head;

      printf("\nFirst Name           Last Name            ID           Grade\n");
      printf("-------------------- -------------------- ------------ ");
      printf("-------\n");

      /*Until the end of the list*/
      while (curr != NULL)
      {
         /* print the current data item */
	 printf("%-20s %-20s %-12d %6d%%\n", curr -> data.firstName, 
		curr -> data.lastName, curr -> data.id, curr -> data.grade);

	 /* move to the next node */
	 curr = curr -> next;
      }
   }   
}