#include <iostream>
#include <string>

using namespace std;


//Sturcture definition
struct Panda
{
	string ZooName;
	string Gender;
	string Age;
	string ID;
	Panda *next;
};

typedef Panda* Node; //aliasing

string getID(void); //Function that gets the ID
void displayList(Node); //Display the List
Node insertNode(Node, Node); //Insert nodes inorder
Node sortNode(Node, Node); //sorts by Zoo Name
Node deleteNode(Node, string); //Delete a Node
Node createNode(void); //Allocate memory for the node
Node populateNode(Node); //Populate the node with values
void displayNode(Node);	//Display the created node
Node searchList(Node, string); //Search the list based on the ID
Node searchGender( Node, string); //Search the list based on Gender
char menu(); //Menu to choose from the options
void welcome(); //Greeting
 


int main()
{
   char choice;
   string userID;
   Node head = NULL ; //to store the head of the list
   Node newNode = NULL; // to store the new node that is created befor it is inserted into the list
   Node found = NULL; // a temporary varibale to store the found node during search
   
   welcome();

   while(1)
   {
	    choice =menu();
        switch (choice)  
		{
		   //Load the current list from "zoo.dat" file
			case 'a': 
			
				break;
          
			//Display current list
			case 'b': displayList(head);
				break;
		   
			//Add a new panda
		   case 'c': newNode = createNode();
					 newNode = populateNode(newNode);
					 head = insertNode(head, newNode);
			    break;
            
			//Delete a panda
		   case 'd': userID = getID();
	                 head = deleteNode(head, userID);
				break;
		   
		   //Search by Gender and Display
		   case 'e': userID = getID();
			         found = searchList(head, userID);
				     displayNode(found);
				break;
		   
		   //Sort by name of Zoo
		   case 'f': displayList(head);
					 head = sortNode(head, newNode);
				break;  
			
		   //Exit and update file
		   case 'g': return 1;

		   default: continue;
		}
   }
}



//creating a new empty node
Node createNode(void)
{
	Node newNode = new Panda;
	newNode->next = NULL;
	return newNode;
}



//populating an empty node
Node populateNode(Node newNode)
{
	cout << "Enter Zoo Name: ";
	cin >> newNode->ZooName;
	cout << "Enter Gender: ";
	cin >> newNode->Gender;
	cout << "Enter Age: ";
	cin >> newNode->Age;
	cout << "Enter ID: ";
	cin >> newNode->ID;
    return newNode;
}

//prompts the user to enter a ID for search and delete operations
string getID()
{
	string userID;
	cout << "Enter the ID you wish to delete/search: ";
	cin >> userID;
	return userID;
}


//displays a single node
void displayNode(Node node)
{
	//If address(node) sent is empty
	if(node == NULL)
	{
		cout << "Sorry. ID was not found";
	}
	else
	{
		cout << endl;
		cout << "Zoo Name:"<< node->ZooName << endl;
		cout << "Gender:"<< node->Gender << endl;
		cout << "Age:"<< node->Age << endl;
		cout << "ID; "<< node->ID << endl;
		return;
	}
}

//function to display full list
void displayList(Node head)
{
	Node Temp;

	if( head == NULL )
	{
		cout << "The list is empty."<< endl;
		return;
	}
   
	Temp = head;

	cout << "The list is as follows:" << endl;
	while (Temp != NULL)
	{
		displayNode(Temp);
		Temp = Temp->next;
	}
	return;
}

//Function to insert a new node in order of its ID
Node insertNode(Node head, Node newNode)
{
	Node prev, current;
	
	//case1: When the list is empty
	if(head == NULL)
	{
		return newNode;
	}
	//end of case1
	prev = NULL;
	current = head;
    
	
	//case2: When the newNode has to become the headNode
	if(newNode->ID < head->ID )
	{
		newNode->next = head;
		return newNode;
	}
    //end of case2
     
	//case3: The list is not empty and the newNode need not have to be the headNode
	while(current != NULL)
	{
		if(current->ID < newNode->ID)
		{
			prev=current;
			current=current->next;
		}
		else
			break;
	}

    //case 3.1: If the newNode has to be the last node
	if(current == NULL)
	{
		prev->next=newNode;
		return head;
	}
	//end of case3.1
    
	//case 3.2: newNode goes some where in the middle
    else
	{
		prev->next=newNode;
		newNode->next=current;
		return head;
	}
	//end of case3

}

//Function to insert a new node in order of its ZooName
Node sortNode(Node head, Node newNode)
{
	Node prev, current;
	
	//case1: When the list is empty
	if(head == NULL)
	{
		return newNode;
	}
	//end of case1
	prev = NULL;
	current = head;
    
	
	//case2: When the newNode has to become the headNode
	if(newNode->ZooName < head->ZooName )
	{
		newNode->next = head;
		return newNode;
	}
    //end of case2
     
	//case3: The list is not empty and the newNode need not have to be the headNode
	while(current != NULL)
	{
		if(current->ID < newNode->ZooName)
		{
			prev=current;
			current=current->next;
		}
		else
			break;
	}

    //case 3.1: If the newNode has to be the last node
	if(current == NULL)
	{
		prev->next=newNode;
		return head;
	}
	//end of case3.1
    
	//case 3.2: newNode goes some where in the middle
    else
	{
		prev->next=newNode;
		newNode->next=current;
		return head;
	}
	//end of case3

}



//functions to search for a Node 
Node searchList(Node head,string userID)
{
	Node current = head;

	//case1: When the list is empty
	if(head == NULL)
	{
		return head;
	}
	//end of case1
    
	//case2:
	while(current != NULL)
	{
		//ID found
		if(current->ID == userID)
		{
             return current;
		}
		else //ID was not found
		{
			current=current->next;
		}
	}

	//If we get to the end of the list without finding the ID
	if(current == NULL)
	{
		return NULL;
	}
     return head;
}



//Function to delete a Node
Node deleteNode(Node head,string userID)
{
	Node current = head, prev=NULL;

	//case1: When the list is empty
	if(head == NULL)
	{
		cout << "List is empty"<< endl;
		return head;
	}
	//end of case1

    //case2: The head node is to be deleted
	if(head->ID == userID)
	{
		head = head->next;
		delete current;  
		return head;
	}

	//case3: We have to delete an intermediate node
	while(current != NULL)
	{
		//UIN found
		if(current->ID == userID)
		{
             prev->next = current->next;
			 delete current;
			 return head;
		}
		else //ID was not found
		{
			prev=current;
			current=current->next;
		}
	}

	//If we get to the end of the list without finding the ID
	if(current == NULL)
	{
		cout << "ID was not found. Could not perform the delete function."<< endl;
		return head;
	}
     return head;
}

//user menu
char menu()
{
	char choice;
	
	cout<<endl;

	cout << "Enter your choice of Operation  "<< endl << endl;;
	cout << "***********************************"<<endl;
	cout << " a. Load the current list."<< endl;
	cout << " b. Display the current list."<< endl;
	cout << " c. Add a new panda."<< endl;
	cout << " d. Delete a panda."<< endl;
	cout << " e. Search by gender and display."<< endl;
	cout << " f. Sort by Zoo Name."<< endl;
	cout << " g. Exit and Update file."<< endl;
	cout << "***********************************"<<endl<<endl;;
	cout << "Your Choice: ";
	cin >> choice;
	system("cls");
	cout << endl;
	return choice;
	
}

//welcome screen
void welcome()
{
	cout << "***********************************"<< endl;
	cout << "        PANDA LINKED LIST"		     << endl;
	cout << "***********************************"<< endl;
}