#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<crtdbg.h>
 
#define FLUSH while (getchar () != '\n')
#define FILE_IN "countries.txt"
 
// Type Definitions 
 
typedef char KEY_TYPE;
typedef struct {
	char *name;
	char *capital;
	long population;
	} COUNTRY;
 
typedef struct {
	KEY_TYPE key[3];
	COUNTRY list;
	} DATA;
 
typedef struct nodeTag {
	DATA			data;
	struct nodeTag*	link;
	} NODE;
 
// Prototype Declarations
char getOption	  (void);
void printMenu    (void);
 
int   searchList  (NODE *pList, NODE **pPre, NODE **pCur, char target[]);
NODE *insertNode  (NODE *pList, NODE *pPre,  DATA  item);
NODE *deleteNode  (NODE *pList, NODE *pPre,  NODE *pCur);
void  printList   (NODE *pList);
NODE *destroyList (NODE *pList);
 
NODE *buildList (void);
 
NODE *processListManager (NODE *pList);
void  searchManager      (NODE *pList);
NODE *insertManager	     (NODE *pList);
NODE *deleteManager      (NODE *pList);
 
int getData ( FILE *spIn, DATA *data );
void insertCommas ( NODE *pWalker, char *population );
void printCountry ( NODE *list, char populationInCommas[] );
int insertHandler ( DATA *data, char target[] );
 
int main ( void )
{
//  Local Definitions 
    NODE *list = NULL;
 
//  Statements 
    printf("\t\t LAB 8 - LINKED LISTS\n\n");
 
	list = buildList();
    printMenu();
	processListManager ( list );
	list = destroyList ( list );
 
	printf("\n\t\tEnd of LAB 8 - LINKED LISTS"
		   "\n\t\tHave a great day!\n");
 
 
    printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Leak\n");
 
    return 0;
 
}// main 
 
/*	==================== getOption ====================
	Gets and validates the user's option.
		Pre		: nothing
		Post	: valid option returned
*/
char getOption	(void)
{
//  Local Definitions 
	char option;
 
//  Statements 
	printf ("\n\nPlease enter the option: ");
	scanf  ("%c", &option);
    FLUSH;
	option = toupper (option);
    while(strchr("LSIDME", option) == NULL)
    {
        printf("\a*** Invalid option! ***\n");
        printf("Enter one of the following letters: L, S, I, D, M, E: " );
        scanf  ("%c", &option);
        FLUSH;
	    option = toupper (option);
    }
 
	return option;
 
} // getOption 
 
/* ============================== printMenu ==============================
	Prints the menu to the screen.
	   PRE  : nothing
	   POST : menu printed
*/
void printMenu (void)
{
//  Local Definitions 
 
//  Statements 
	printf("\n\t\t**********************"
           "\n\t\t*                    *"
	       "\n\t\t*   L - List         *"
           "\n\t\t*   S - Search       *"
	       "\n\t\t*   I - Insert       *"
	       "\n\t\t*   D - Delete       *"
	       "\n\t\t*   M - Print Menu   *"
	       "\n\t\t*   E - Exit         *"
	       "\n\t\t*                    *"
	       "\n\t\t**********************");
 
	return;
 
} // printMenu 
 
/* ============================== processListManager ====================
	Process user's option by calling appropriate functions.
	   PRE  : pList - a pointer to the first node of a linked list
	   POST : pList - might be changed after inserting or deleting 
*/
 
NODE *processListManager (NODE *pList)
{
//  Local Definitions
	char option;
 
//  Statements
	do
	{
		option = getOption();
		switch(option)
		{
		    case 'L' : printList (pList);
				       break;
		    case 'S' : searchManager (pList);
				       break;
		    case 'I' : pList = insertManager (pList);
				       break;
		    case 'D' : pList = deleteManager (pList);
				       break;
		    case 'M' : printMenu ();
				       break;
		    case 'E' : printf("End of processing!\n");
                       break;
           default  :  break;
		} 
	} while (option != 'E');
 
	return pList;
 
} // processListManager 
 
NODE *buildList (void)
{
// Local Declarations
	NODE *pList;
	NODE *pPre;
	NODE *pCur;
	DATA data;
	FILE *spIn;
	int result;
 
// Statements
	if ( ! ( spIn = fopen ( FILE_IN, "r" ) ) )	{
		printf("Error opening file %s\n", FILE_IN);
		exit(100);
	}
	pList = NULL;
	while ( getData ( spIn, &data ) ) {
		result = searchList(pList, &pPre, &pCur, data.key);
		if ( !result )
			pList = insertNode(pList, pPre, data);
	}
	fclose ( spIn );
	return pList;
} // buildList
 
int getData ( FILE *spIn, DATA *data )
{
// Local Declarations
	int result;
 
// Statements
	data->list.name = (char*)calloc(21, sizeof(char));
	data->list.capital = (char*)calloc(16, sizeof(char));
	result = fscanf ( spIn, "%2s %20[^;] %*c %15[^;] %*c %ld", 
					  data->key, data->list.name, 
					  data->list.capital, &(data->list.population) );
	if ( result == 4 )
		return 1;
	else {
		free ( data->list.name );
		free ( data->list.capital );
		return 0;
	}
} // getData
 
NODE *insertNode  (NODE *pList, NODE *pPre, DATA item)
{
// Local Declarations
	NODE *pNew;
 
// Statements
	if ( ! ( pNew = (NODE*)malloc(sizeof(NODE))))
		printf("Memory is unavailable.\n"),
			exit(200);
	pNew->data = item;
	if ( pPre == NULL ) {
		pNew->link = pList;
		pList = pNew;
	}
	else {
		pNew->link = pPre->link;
		pPre->link = pNew;
	}
   return pList;
} // insertNode
 
int searchList (NODE *pList, NODE **pPre, NODE **pCur, char target[])
{
// Local Declarations
	int found = 0;
 
// Statements
	*pPre = NULL;
	*pCur = pList;
	while (*pCur != NULL) {
		if (strcmp ( target, (*pCur)->data.key) == 0 ){
			found = 1;
			break;
		}
		*pPre = *pCur;
		*pCur = (*pCur)->link;
	}
   return found;
} // searchList
 
void printList (NODE *pList)
{
// Local Declarations
	NODE *pWalker;
// Statements	
	printf(	"== ====================\n"
			"ID NAME                \n"
			"== ====================\n");
	pWalker = pList;
	while ( pWalker ) {
		printf("%s %-20s\n",
			   pWalker->data.key, pWalker->data.list.name);
		pWalker = pWalker->link;
	}
	printf( "=======================" );
   return;
} // printList
 
void insertCommas ( NODE *pWalker, char *population )
{
// Local Declarations
	char printString[15];
	char tempString[15];
	char insertComma[] = ",";
	int strLength;
	int checkRmdr;
	int i;
// Statements
	*printString = '\0';
	sprintf(tempString, "%ld", pWalker->data.list.population);
	strLength = strlen ( tempString );
	checkRmdr = strLength % 3;
	if ( checkRmdr > 0 ) {
		strncat ( printString, tempString, checkRmdr );
		strcat ( printString, insertComma );
	}
	for ( i = checkRmdr; i < (int) strlen ( tempString );  ) {
		strncat ( printString, tempString + i, 3 );
		i += 3;
		strcat ( printString, insertComma );
	}
	printString[strlen(printString) - 1] = '\0';
	strcpy (population, printString);
	return;
} // insertCommas
 
void searchManager (NODE *pList)
{
// Local Declarations
	NODE *pPre;
	NODE *pCur;
	char target[3];
	char populationInCommas[15];
 
// Statements
	printf("Please enter a key: ");
	scanf("%2s", target);
	FLUSH;
	if ( searchList ( pList, &pPre, &pCur, target ) ) {
		insertCommas(pCur, populationInCommas);
		printCountry(pCur, populationInCommas);
	}
	else
		printf("Country could not be found. Please try again.");
   return;
} // searchManager
 
void printCountry ( NODE *list, char populationInCommas[] )
{
// Statements
	printf(	"\n        ID: %s\n"
				"      Name: %s\n"
			    "   Capital: %s\n"
				"Population: %s\n", list->data.key, 
									list->data.list.name,
									list->data.list.capital, 
									populationInCommas);
} // printCountry
 
NODE *insertManager (NODE *pList)
{
// Local Declarations
	NODE *pPre;
	NODE *pCur;
	DATA insertData;
	int position;
	char target[3];
	int counter = 1;
// Statements
	printf("Please enter a key: ");
	scanf("%2s", target);
	FLUSH;
	if ( ! ( searchList ( pList, &pPre, &pCur, target ) ) ) {
		position = insertHandler ( &insertData, target );
 
		switch (position) {
			case 1:	pPre = NULL;
					break;
			case 2:	pPre = pList;
					while (pPre) {
						pPre = pPre->link;
						counter++;
					}
					counter /= 2;
					pPre = pList;
					while ( counter != 1 ) {
						pPre = pPre->link;
						counter--;
					}
					break;
			case 3:	pPre->link = NULL;
					break;
		}
		pList = insertNode( pList, pPre, insertData );
	}
	else
		printf("That country ID already exists. Please try again.");
   return pList;
}
 
int insertHandler ( DATA *data, char target[] )
{
// Local Declarations
	int position = 0;
 
// Statements
	if ( ! ( data->list.name = (char*)calloc(21, sizeof(char)))) {
		printf("Memory Unavailable.\n");
		exit(300);
	}
	if ( ! ( data->list.capital = (char*)calloc(16, sizeof(char)))) {
		printf("Memory Unavailable.\n");
		exit(400);
	}
	strcpy ( data->key, target );
	printf("Enter the country's name: ");
	scanf("%s", data->list.name);
	FLUSH;
	printf("Enter the country's capital: ");
	scanf("%s", data->list.capital);
	FLUSH;
	printf("Enter the country's population: ");
	scanf("%ld", &(data->list.population));
	FLUSH;
	while ( position < 1 || position > 3 ) {
		printf("Where would you like to place this new country?\n"
			   "Beginning(1), Middle(2), End(3): ");
		scanf("%d", &position);
		FLUSH;
		if ( position < 1 || position > 3 )
			printf("Incorrect option. Please try again.\n");
	}
   return position;
} // insertHandler
 
NODE *deleteNode (NODE *pList, NODE *pPre, NODE *pCur)
{
// Statements
	if ( pPre == NULL )
		pList = pCur->link;
	else
		pPre->link = pCur->link;
	free ( pCur );
   return pList;
} // deleteNode
 
NODE *deleteManager (NODE *pList)
{
// Local Declarations
	NODE *pPre = NULL;
	NODE *pCur;
	char target[3];
// Statements
	printf("Please enter a key: ");
	scanf("%2s", target);
	FLUSH;
	if ( searchList ( pList, &pPre, &pCur, target ) )
		pList = deleteNode ( pList, pPre, pCur );
	else
		printf("Country could not be found. Please try again.");
   return pList;
} // deleteManager
 
NODE *destroyList (NODE *pList)
{
// Local Declarations
	NODE *pPre = NULL;
	NODE *pCur;
 
// Statements
	while ( pList ) {
		pCur = pList;
		free ( pCur->data.list.name );
		free ( pCur->data.list.capital );
		pList = deleteNode ( pList, pPre, pCur );
	}
   return pList;
} // destroyList

HU Hungary; Budapest; 10006835
MX Mexico; Mexico; 106202903
CN China; Beijing; 1306313812
NP Nepal; Kathmandu; 27676547
MU Mauritius; Port Louis; 1230602
FR France; Paris; 60656178
ES Spain; Madrid; 40341462
EG Egypt; Cairo; 77505756
TW Taiwan; Taipei; 22894384
GR Greece; Athens; 10668354
US United States; Washington, DC; 295734134
AU Australia; Canberra; 20090437
LI Liechtenstein; Vaduz; 33717
RU Russia; Moscow; 143420309
CA Canada; Ottawa; 32805041
MC Monaco; Monaco; 32409
BR Brazil; Brasilia; 186112794
IR Iran; Tehran; 68017860
FR France; Paris; 60656178
DO Dominican Republic; Santo Domingo; 8950034
FJ Figi; Suva; 893354

list = processListManager(list);