/*
Program: file-records-adds-drops-v2.c (Report comments/bugs to chikh@yuntech.edu.tw)
Function: 改良file-records-adds-drops-v1.c，使得排序方式可以標準函數庫的qsort()實作
Notes: 1) 本程式實現雙向串列，但為了省卻參數傳來傳去衍生的細節困擾，宣告head、tail與total(節點
		  個數)為全域變數，以求扼要
	   2) 雖head與tail均為全域變數，本程式仍刻意設showAll()、sortName()、sortEng()、sortMath()
	      等函式傳入head引數，以利同學發想參數傳遞的基本形式
	   3) 若把head與tail宣告為main()內的區域變數，同學也應知道如何讓程式正確執行 
	   4) 關於sscanf()的用法，推薦陳鍾誠老師整理的一篇技術短文 http://ccckmit.wikidot.com/cp:sscanf
*/

#include <stdio.h>	
#include <stdlib.h> /* for malloc(), calloc(), qsort() */ 
#include <string.h>	/* for strcmp() */
#include <conio.h> 	/* for getche() */

typedef struct student student;
struct student {
	char    name[24]; 
	int     eng, math;
	student *prev;
	student *next;
} *head, *tail, dummy; 

int total = 0;

void traceBack(student *tail) /* 從頭至尾顯示每一個節點的內容 */
{
	student *ptr; /* 指向每一節點所用的指標 */
	
	printf("\n回溯顯示學生紀錄如下：\n");
	for (ptr = tail; ptr != NULL; ptr = ptr->prev) 
		printf("%s\t%d\t%d\n",ptr->name,ptr->eng,ptr->math);
}

void showAll(student *head, student *tail) /* 顯示串列內每一個節點的內容 */
{
	student *ptr; /* 指向每一節點所用的指標 */
	
	printf("學生\t\t英文\t數學\n---------------+-------+-----\n");
	for (ptr = head; ptr != NULL; ptr = ptr->next) 
		printf("%s\t%d\t%d\n",ptr->name,ptr->eng,ptr->math);
		
	traceBack(tail);
}

/* 傳入引數為一長字串(譬如Steve Jobs 50 60)，從中萃取姓名、英文、數學科成績等
   資料形成新節點，並把節點加入串列的尾部(調整tail) */
void addRecord(char line[], int showEntireList) 
{
	char    name[24], str[24]; 
    student *ptr = tail;
    
	//tail = tail->next = (student *)malloc(sizeof(student));	//創建新節點所需空間，並成為tail所指的學生紀錄之後的元素 
	tail = tail->next = (student *)calloc(1,sizeof(student));
	tail->prev = ptr;
	
	while (1) {
		if (sscanf(line,"%[A-Za-z.] %[^\n]",str,line) == 0) {	/* 讀取大小寫字母或句點組成的英文名字，讀入str，第一個空白之後的所有字串設為line */ 
			sscanf(line,"%d %d",&tail->eng,&tail->math);
			break;
		}
		sprintf(tail->name,tail->name[0]=='\0'? "%s%s": "%s %s",tail->name,str);	/* 讀到的英文名加入tail指標所指節點的name欄位之中 */ 
	}
	tail->next = NULL;	
    total++;	/* 節點個數增1 */
    if (showEntireList) { //從頭顯示串列所有資料
    	printf("\n增加一筆資料：%s\t%d\t%d\n\n",tail->name,tail->eng,tail->math);
		showAll(head,tail);
	}
}

/* 傳入引數為一長字串(譬如Steve Jobs 50 60)，將從中提取姓名(忽略英文、數學科成績)藉以
   比對串列中是否有名字相符的(目標)節點，若有，將把該節點的前後節點串連起來 */
void deleteRecord(char line[])
{
	char    fullName[24] = {0}, str[24];
    student *ptr;
    int score;
	
	while (1) {
		if (sscanf(line,"%[a-zA-Z.] %[^\n]",str,line) == 0) break;
		sprintf(fullName,fullName[0]=='\0'? "%s%s" : "%s %s",fullName,str); //sprintf(fullName,fullName[0]=='\0'? "%s%s " : "%s %s ",fullName,str);
	}
		
    for (ptr = head; ptr != NULL; ptr = ptr->next) 
    	if (!strcmp(ptr->name,fullName)) break;  /* 找到，立即跳離迴圈 */ 
	
	if (ptr != NULL) { 			/* ptr不為空，代表發現目標 */ 
		if (ptr->prev==NULL) {	/* 若將被刪除的節點是串列頭，則調整head為目標下一節點 */
			head = ptr->next;
			head->prev = NULL;
		}
		else {
			ptr->prev->next = ptr->next;	/* 把前一節點與目標下一節點串連起來(繞過目標節點) */ 
			if (ptr != tail) 
				ptr->next->prev = ptr->prev;	/* 下一節點的prev欄位指向前一節點 */
			else
				tail = ptr->prev;
		}	
		printf("\n移除一筆資料：%s\t%d\t%d\n\n",ptr->name,ptr->eng,ptr->math);
    	free(ptr);	/* 刪除目標節點所佔空間 */
    	total--;	/* 節點個數少1 */
		showAll(head,tail);
	}
	else
		printf("擬移除的紀錄(%s)在資料表中不存在\n",fullName);
}

int nameAscend(const void *a, const void *b) /* 遞增模式 */ 
{
	student **x = (student **)a;
	student **y = (student **)b;
	
	char lastName[16], nextLastName[16];
	
	sscanf((**x).name,"%s %s %s",lastName,lastName,lastName);
    sscanf((**y).name,"%s %s %s",nextLastName,nextLastName,nextLastName);
	
	return strcmp(lastName,nextLastName); //return strcmp((**x).name,(**y).name);
}

int engDescend(const void *a, const void *b) /* 遞減模式 */ 
{
	student **x = (student **)a;
	student **y = (student **)b;
	
	return (**y).eng - (**x).eng;
}

int mathDescend(const void *a, const void *b) /* 遞減模式 */ 
{
	student **x = (student **)a;
	student **y = (student **)b;
	
	return (**y).math - (**x).math;
}

int sortName(student *head, student *indexName[]) /* 請研讀第二單元之「複習：C語言陣列」講義第62-67頁內容 */
{ 
	int 	i, j;
	char    lastName[20], nextLastName[20], firstName[20];
	student *ptr, *temp;
	
	for (i = 0, ptr = head; ptr != NULL; i++, ptr = ptr->next) 
		indexName[i] = ptr; /* indexName[i]保存串列第i節點的位址，將藉此進行排序 */
	
	qsort(indexName,total,sizeof(indexName[0]),nameAscend);
	
	return 1;
}

/* 傳入引數為串列開頭元素位址與索引陣列indexEng[]的起始位址，將以英文成績高低作為排序依據； 
   本函式運作原理與上面sortName()相同 */
int sortEng(student *head, student *indexEng[]) 
{ 
	int 	i, j;
	student *ptr, *temp;
	
	for (i = 0, ptr = head; ptr != NULL; ptr = ptr->next) 
		indexEng[i++] = ptr; /* indexEng[i]保存串列第i節點的位址，將藉此進行排序 */
	
	qsort(indexEng,total,sizeof(indexEng[0]),engDescend);
	
	return 1;
}

/* 傳入引數為串列開頭元素位址與索引陣列indexMath[]的起始位址，本函式將以數學成績高低作為排序依據；
   本函式運作原理與上面sortEng()相同 */
int sortMath(student *head, student *indexMath[]) 
{ 
	int 	i, j;
	student *ptr, *temp;
	
	for (i = 0, ptr = head; ptr != NULL; i++, ptr = ptr->next) 
		indexMath[i] = ptr; /* indexMath[i]保存串列第i節點的位址，將藉此進行排序 */
	
	qsort(indexMath,total,sizeof(indexMath[0]),mathDescend);
	
	return 1;
}

void queryUser(student *head, student *indexName[], student *indexEng[], student *indexMath[])
{
	int i, n;
	int engSorted = 0, mathSorted = 0; /* 分別紀錄英文科排序與數學科排序是否已執行過 */
	
	while (1) {
		printf("\n**************************************************************************************\n" \
			   "* 1 以姓式排序  2 以英文排序  3 英文第n名紀錄  4 以數學排序  5 數學第n名紀錄  0 結束 *\n" \
			   "**************************************************************************************\n" \
			   "選擇將執行哪一項功\能？(0--5) ==> "); 
		switch (getche()) { 
			case '1':
				printf("\n\n以姓式排序結果如下：\n");
    			sortName(head,indexName);
    			for (i = 0; i < total; i++) 
					printf("%s\t%d\t%d\n",indexName[i]->name,indexName[i]->eng,indexName[i]->math);
				break;
			case '2':
				printf("\n\n以英文成績排序結果如下：\n");
				engSorted = sortEng(head,indexEng);
				for (i = 0; i < total; i++) 
					printf("%s\t%d\t%d\n",indexEng[i]->name,indexEng[i]->eng,indexEng[i]->math);
    			break;
    		case '3':
    			if (!engSorted) 
    				printf("\n尚未以英文科成績高低作排序，請先選擇\'2\'功\能\n");
				else {
    				printf("\n查詢英文第n名的資料，輸入n (1-%d) ==> ",total);
    				scanf("%d",&n);
    				printf("英文第%d高分者：%s\t%d\t%d\n",n,indexEng[n-1]->name,indexEng[n-1]->eng,indexEng[n-1]->math);
				}					
				break; 
    		case '4':
    			printf("\n\n以數學成績排序結果如下：\n");
				mathSorted = sortMath(head,indexMath);
				for (i = 0; i < total; i++) 
					printf("%s\t%d\t%d\n",indexMath[i]->name,indexMath[i]->eng,indexMath[i]->math);
				break;					
			case '5':
    			if (!mathSorted) 
    				printf("\n尚未以數學科成績高低作排序，請先選擇\'4\'功\能\n");
				else {
    				printf("\n查詢數學第n名的資料，輸入n (1-%d) ==> ",total);
    				scanf("%d",&n);
    				printf("數學第%d高分者：%s\t%d\t%d\n",n,indexMath[n-1]->name,indexMath[n-1]->eng,indexMath[n-1]->math);
				}					
				break; 
			case '0':
				return;
			default:
				printf("有效的選擇為0--5，請重新輸入\n");
				system("pause");
		}
	}
}

int main()
{
	int     i;
	char    line[120], mode; /* mode用於區分增減資料的工作模式 */ 
	   	
   	tail = &dummy;	/* dummy為暫時用途的節點，導入此節點將使得tail或head初始運作避免出錯，同學可理解這樣寫與你原先的做法有何差別? */
    
    FILE *inputFile;/* 輸入檔案在程式內部的代稱 */
	if ((inputFile=fopen("YunTechStudents.txt","r")) == NULL) {   /* 設定開檔模式為輸入用途，檢視檔案可否開啟，若input為空，代表檔案不存在 */
		printf("輸入檔不存在\n");
		exit(1);	/* 退出程式 */
	}
	
	for (i = 0; i < 4; i++) fgets(line,120,inputFile);	/* 輸入文檔開頭的四列文字消化掉 */
	while (fgets(line,120,inputFile) != NULL) { 		/* 未觸及檔案末端，代表尚有資料可讀取，重複迴圈內動作 */
  		//讀取一整列內容，存入line字串變數之中 
  		if (!strcmp(line,"**************************************\n")) break; /* 已讀取到分隔線，將切換到另一處理模式 */
  		addRecord(line,0);	//讀取到的整列內容(譬如Steve Jobs 50 60)交由addRecord()萃取入串列；false代表不需從頭顯示串列所有資料 
  	}
  	
  	printf("第一階段資料讀取完畢，共有%d筆記錄\n\n",total);
  	head = dummy.next; /* 定調head指向dummy.next所指節點 */
  	head->prev = NULL;
	showAll(head,tail);
	
	printf("\n以上為輸入檔案\"分隔線\"以上的資料，按任意鍵開始增減資料 ...\n"); //system("pause");
	getche();
   	
   	while (fgets(line,120,inputFile) != NULL) { 
		sscanf(line,"%c %[^\n]s",&mode,line);	 /* 讀取'+'或'-'設入mode變數中，界定不同的處理模式 */
  		if (mode == '+') 		/* 增加紀錄 */
		  	addRecord(line,1);	/* 整列line變數交由addRecord()萃取所需資料，並從頭顯示串列所有資料 */
		else if (mode == '-') 	/* 刪減紀錄 */
			deleteRecord(line);	/* line所含姓名將由deleteRecord()比對，若存在於串列，將移除該筆紀錄並從頭顯示串列所有資料 */
		else 
			printf("未知指令，sorry :(\n");
  	}
  	fclose(inputFile);
  	
  	student *indexName[100], *indexEng[100], *indexMath[100]; /* 欄位的索引陣列，預設可記100個節點位址 */
  	/* 若不想使用如上固定長度的陣列，可改依total數值分配相應元素個數的陣列，但請留意底下寫法 */
  	/*
	student **indexName = (student **)malloc(total*sizeof(student *)), 
	  	    **indexEng = (student **)malloc(total*sizeof(student *)), 
			**indexMath = (student **)malloc(total*sizeof(student *)); 
	*/

    queryUser(head,indexName,indexEng,indexMath);	/* 產生功能選單，並依選項執行相應的功能 */ 
	printf("程式結束，Bye∼\n");
	
	return 0;
}