/* 
 * linked_list.c - this program illustrates the basic functionality
 * of a singly-linked list dynamic data structure.  The user has the
 * capability to add nodes, clear the list, and print the contents of
 * the list.  Function prototypes for search and delete are included,
 * but are not implemented.
 *
 */

#include <stdio.h>

// This is the structure that defines each node in our linked list.
// Notice the self referential structure that we use to point to the
// next item in the list.
typedef struct node {
	int payload;
	struct node* next;
} node_t;


// This is the structure that we use to keep track of our linked list,
// also known as the 'head'.  We keep a pointer to the first node in the
// linked list, or NULL if none exists.  We also keep a counter of the
// number of items in the list.
typedef struct head {
	node_t* first_node;
	int     num_nodes;
} head_t;


// Function Prototypes
int     new_node(head_t* head);
int     delete_node(head_t* head, int number);
void    clear_list(head_t* head);
void    print_list(head_t head);
node_t* find_node(head_t* head, int number);

int do_menu(int num_nodes);


// Main Program
int main(void) {

	int  choice = 0;
	int  retval;
	int  j;
	char c;
	
	head_t int_list;	// the structure that keeps track of our list

	int_list.first_node = NULL;
	int_list.num_nodes  = 0;

	// Our main program loop.  We accept one selection per loop, only
	// exiting when the user selects the quit item.
	while (choice != 5) {
		
		choice = do_menu(int_list.num_nodes);

		switch(choice) {
			
			case 1:		// The user wants to add a node
				retval = new_node(&int_list);
				
				if (retval) {
					printf("Node Added\n");
					int_list.num_nodes++;
				} else {
					printf("Out of memory.  ");
					printf("Node not added\n");
				}	

				break;

			case 2:		// The user wants to print the list

				print_list(int_list);

				break;
				
			case 3:		// The user wants to delete a node

				printf("\tWhich number do you want to delete? ");
				scanf("%d", &j);

				retval = delete_node(&int_list, j);

				if (!retval) {
					printf("\n\t**Requested node not found!**\n");
					printf("\tNo node deleted...\n\n");
				}
				
				break;

			case 4:		// The user wants to clear the list

				clear_list(&int_list);
				break;


			case 5:		// The user wants to quit
				break;	


			default:	// The user entered bad data
				printf("%d is not an option.  ");
				printf("Please try again.\n\n");

		}
	}


	printf("Clearing the list.\n");
	clear_list(&int_list);
	
	printf("Exiting.\n");
	return 0;
}


// This function asks the user for a number to place in a new node.
// It accepts one parametmer, a pointer to a list node.  It returns
// 1 on success, and 0 on failure (if memory cannot be allocated).
//
// Precondition:  head is NULL if the list is empty
// Postcondition: head points to the new element in the list, and
//                the new node points to the following element, or
//                is NULL if that element doesn't exist.

int new_node(head_t* head) {

	int     i;
	int     retval;
	node_t* new;
	
	printf("\tPlease enter the number for the new node: ");
	scanf("%d", &i);

	new = (node_t *) malloc (sizeof(node_t));

	if (new == NULL) {
		retval = 0;
	} else {
		new->payload = i;
		
		new->next = head->first_node;
		head->first_node = new;
		retval = 1;
	}
	
	return retval;
}



// This function accepts a pointer to the first node in the list, and 
// a number of the payload stored in the node we wish to delete.  This 
// function would traverse the list and search for the node containing 
// the specified payload.  If the node is found, it is deleted from
// the list.  In this case, the function returns 1; If the node is not
// found, the function returns 0.
//
// Note that this list ONLY deletes one instance of the user-specified
// number in the case of duplicate entries.
//
// Precondition:  head is NULL if the list is empty
// Postcondition: the list pointed to by head contains one less element
//                if the node containing number is found.  Head is NULL
//                if the last item in the list is deleted.

int delete_node(head_t* head, int number) {

	node_t* current;
	node_t* temp;
	int     retval = 0;
	int     found = 0;

	// If there is nothing on the list, we don't have to do anything
	if (head->first_node != NULL) {

		current = head->first_node;

		// If it is the first node in our list, we have a special
		// case (because the head node is different than the other
		// nodes).
		if (current->payload == number) {
			head->first_node = current->next;

			free(current);

			printf("\t**Node deleted**\n");
			head->num_nodes--;
			retval = 1;
		} else {

		
			while ((current->next != NULL) && !found) {

				if (current->next->payload == number) {
					found = 1;
				} else {
					current = current->next;
				}
		
			}
			
			if (found) {
				temp = current->next;
				current->next = temp->next;

				free(temp);

				printf("\t**Node Deleted**\n");
				head->num_nodes--;
				retval = 1;
			}
		}
	}			
	return retval;
}


// This function accepts a pointer to the head object of our linked list.
// It clears the memory for each node.
// 
// Preconditions:  head points to a valid head object
// Postconditions: head represents an empty list
void clear_list(head_t* head) {
	node_t* current;
	node_t* temp;
	int     count;
	int     n;
	
	current = head->first_node;

	n = head->num_nodes;
	for (count = 0; count < n; count++) {
		temp    = current;
		current = current->next;

		free(temp);
		head->num_nodes--;
	}

	head->first_node = NULL;

	printf("\n\t** List cleared.  ");
	printf("\tList now contains %d nodes.\n\n", head->num_nodes);
}



// This function accepts a linked-list head object.  It then prints
// the data inside of each node in the list.
//
// Preconditions:  head is correctly initialized
// Postconditions: none
void print_list(head_t head) {

	node_t* current = head.first_node;

	printf("List contains %d items:\n\n", head.num_nodes);
	printf("(head)-->");

	while (current != NULL) {

		if (current->next == NULL) {
			printf("[%d]-->NULL\n", current->payload);
		} else {
			printf("[%d]-->", current->payload);
		}

		current = current->next;
	}

	if (head.first_node == NULL) {
		printf("NULL");
	}

	printf("\n\n");
}


// This function would perform identically to the delete_node function,
// except that it would return a pointer to the node (if it was found)
// instead of deleting the node.  Note that it would need to return
// NULL if the node could not be found.
node_t* find_node(head_t *head, int number) { }


// This function prints the menu and accepts the user's input.
// It has no input parameters, and returns the integer containing
// the number of the user's menu selection.
int do_menu(int num_nodes) {

	int i;
	
	printf("Linked List Demonstration\n");
	printf("=========================\n\n");
	printf("(1) - Add a new node\n");
	printf("(2) - Display the list\n");
	printf("(3) - Delete a node\n");
	printf("(4) - Clear the list\n");
	printf("(5) - Quit\n\n");
	printf("List currently contains %d nodes.\n", num_nodes);
	printf("Please enter your selection: ");
	
	scanf("%d", &i);

	printf("\n\n");
	return i;
}