/* 
Program: dict.c (Report comments/bugs to chikh@yuntech.edu.tw)
Function: 擴充書binarySearchTree.c範例程式，實作字典功能，要求的規格詳見課程網頁的第六次作業公告 
Notes: 輸入可為 
	w={"Mary":10, "Tom":3, "Charlie":5, "Bob":6, "Dickens":20, 4:2, "z":0, "Za":12, "aZ":8}
	del w["Dickens"]
	w["Mary"]=1
	w["Tom"]+=2
	w[4]?
	w?
*/ 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>		/* for strcmp() */

/* 定義dict結構 */
typedef struct dict {
    char   key[20];  
    int    value;  	
    struct dict *llink;	/* 左子鏈結 */
    struct dict *rlink;	/* 右子鏈結 */
} dict;

//void insert();		/* 新增函數 */
void prune();			/* 刪除函數 */
void modify(char, char [], int);  /* 修改函數 */
void show(char, char []);   /* 輸出函數 */
void process(char [], int);	/* 將資料加入二元搜尋樹 */
void drop(char []);		/* 將資料從二元搜尋樹中移除 */
dict *replace(dict *);  /* 尋找替代節點並移動至適當位置 */
void connect(dict *, char); /* 調整鏈結 */
void inorder(dict *);		/* 資料以中序法輸出 */
void deleteAll(dict *);		/* 刪除所有節點 */ 

dict *search(char []);  	/* 搜尋節點 */
dict *search_re_r(dict *);  /* 搜尋右子樹中的替代節點 */
dict *search_re_l(dict *);  /* 搜尋左子樹中的替代節點 */
dict *search_p(dict *); 	/* 搜尋父節點 */

dict *root, *ptr; 			/* root為根節點，為全域變數 */ 

int main()
{
	char  *token, key[12], line[128];
	const char *s = " ={},";	/* 分隔符記的字元 */ 
	int   value;
	char  *rest, option;
   	
   	printf("\n輸入存取字典的陳述，逕按<Enter>結束程式\n");
   	while (1) {
   		printf("\n指令==> ");
   		fgets(line,128,stdin); //gets(line);
   		if (line[0]=='\n') break;	/* 輸入空字串則跳離此迴圈 */ 
   		if (strstr(line,"{")) {
   			sscanf(line,"w = {%[^}]}",line);
			rest = line;
			while (token = strtok_r(rest,s,&rest)) { /* strtok_r()的用法可參見 http://bit.ly/3VcvbbZ */ 
    			if (strstr(token,":")) {			 /* token含有":" */ 
    				sscanf(token,"%[^:]:%d",key,&value);
    				//printf("Token #%d: 鍵=%s; 值=%d\n",++i,key,value);
    				process(key,value);	/* 把key,value插入樹中 */ 
				} 
   			}
		}
		else if (strstr(line,"del")) {
			if (sscanf(line,"del w[%[^]]]",key)) 
				drop(key);
			else {
				printf("無法判讀將刪除哪一個元素，將刪除整個字典? (y/n) => ");
				scanf("%c",&option);
				fflush(stdin);
				if (option == 'y' || option == 'Y') {
					deleteAll(root);
					root = NULL;
				}
			}	
   			//printf("刪除運算：辨識鍵=%s\n",key);
		}
   		else if (strstr(line,"+=")) {	/* line含有"+=" */ 
   			sscanf(line,"w[%[^]]] +=%d",key,&value);
   			//printf("遞增運算：辨識鍵=%s；運算元=%d\n",key,value);
   			modify('+',key,value);
		}
   		else if (strstr(line,"=")) {	/* line含有"=" */
   			sscanf(line,"w[%[^]]] = %d",key,&value);
   			//printf("指派運算：辨識鍵=%s; 運算元=%d\n",key,value);
   			modify('s',key,value);
		}
		else if (sscanf(line,"w[%[^]]]",key)==1)
			//printf("讀值運算：辨識鍵=%s\n",key);
			show('@',key);
		else if (strstr(line,"?"))
			//printf("顯示整個字典內容\n");
			show('*',NULL);
		else 
			printf("語法無法辨認，sorry!\n");
	}
	
	/*
    char option;

    while (1) {
        puts("");
        puts("********************");
        puts("     <1> insert");
        puts("     <2> delete");
        puts("     <3> modify");
        puts("     <4> show");
        puts("     <5> quit");
        puts("********************");
        printf("Enter your choice: ");
        option = getchar();
        fflush(stdin);
        printf("\n");
        switch(option) {
            case '1':
                insert();
                break;
            case '2':
                prune();
                break;
            case '3':
                modify();
                break;
            case '4':
                show();
                break;
            case '5':
                exit(0);
            default :
                puts("選項錯誤!");
        }
    }
    */
    
    return 0;
}

/* 新增函數，新增一筆新的資料 */
/* 
void insert()
{
    char key[20];
    int  value;
    
	puts("=====INSERT DATA=====");
    printf("姓名: ");
    scanf("%s", key);
    printf("分數: ");
    scanf("%d", &value);
    fflush(stdin);
    process(key, value);
}
*/

/* 刪除函數，將資料從二元搜尋樹中刪除 */
void prune(char key[])	/* 本函數原名為delete_f()，這裡改名令程式看起來乾脆一些 */ 
{
    //char key[20];
    
	if (root == NULL) {
        puts("字典內無任何資料");
        return;
    }
    //puts("=====DELETE DATA=====");
    //printf("請輸入欲刪除的姓名: ");
    //scanf("%s", key);
    //fflush(stdin);
    drop(key);
}

/* 修改資料，修改學生成績 */
void modify(char mode, char key[], int value)
{
    dict *node;
    //char key[20];
    
    //if (root == NULL) {	/* 判斷根節點是否為NULL，若為空，根本沒得玩，於是直接返回，不會有後續 */
        //puts("二元搜尋樹是空的!");
        //return;
    //}
    //puts("=====MODIFY DATA===== ");
    //printf("請輸入欲修改的姓名: ");
    //scanf("%s", key);
    //fflush(stdin);
    if ((node=search(key)) == NULL)
        //printf("%s不在二元搜尋樹中!\n", key);
        process(key,value);
    else {
        /* 列出原資料狀況 */
        //printf("姓名: %s\n", node->key);
        //printf("分數: %d\n\n", node->value);
        //printf("請輸入新的分數: ");
        //scanf("%d", &node->value);
        //fflush(stdin);
        if (mode == '+')
        	node->value += value;
        else if (mode == 's')
        	node->value = value;
        value = node->value;
    }
    printf("新設w[%s]=%d\n",key,value);
}

/* 輸出函數，將資料輸出至螢幕 */
void show(char mode, char key[])
{
	dict *node;
	
	if (mode == '@') {
		if ((node=search(key)) == NULL)
        	printf("w[%s]不存在\n",key);
        else
        	printf("字典元素w[%s]=%d\n",key,node->value);
	}
	else {
    	if (root == NULL) {	/* 判斷根節點是否為NULL */
        	puts("字典無任何內容");
        	return;
    	}
    	//puts("=====SHOW DATA=====");
    	printf("字典變數內部儲存的元素(key:value)如下\n");
    	inorder(root);  /* 以中序法輸出資料 */
	}
    
}

/* 處理二元搜尋樹，將新增資料加入二元搜尋樹 */
void process(char key[], int value)
{
    dict *node, *prev;
    
    if ((node=search(key)) != NULL) {	/* 若資料已存在，則顯示錯誤，因二元搜尋樹要求每個節點的鍵值不重複 */ 
        //printf("%s已存在!\n", key);
        node->value = value;
        return;
    }
    ptr = (dict *)malloc(sizeof(dict)); /* ptr指向即將加入的節點 */ 
    strcpy(ptr->key, key);	/* 把傳入此函數的name引數(字串)複製到ptr->name欄位中 */ 
    ptr->value = value;			/* 把傳入此函數的score引數複製到ptr->score欄位中 */
    ptr->llink = ptr->rlink = NULL;	/* ptr節點的左右子樹先設為空 */
    if (root == NULL)  /* 若root為NULL，代表樹尚未建立，因此以ptr節點作為創始二元樹的根節點 */
        root = ptr;
    else { /* 根節點不為NULL，代表樹已存在，則需找到適合ptr節點插入樹中的位置 */
        node = root;			/* 從根節點開始，透過底下迴圈持續搜尋資料的插入點 */
        while (node != NULL) {	/* node為當下檢視的樹節點，只要不為空，代表尚未底定，須持續尋找 */	
            prev = node;		/* prev記住node現今所指節點；prev將成為ptr的父節點 */	
            if (strcmp(ptr->key, node->key) < 0)	/* 若ptr->name小於node->name，意味著ptr應安插在node的左子樹，因此改令node為左子節點，繼續往下找尋 */ 
                node = node->llink;
            else									/* ptr->name大於node->name，意味著ptr應安插在node的右子樹，故改令node為右子節點，繼續往下找尋 */ 
                node = node->rlink;
        }
        if (strcmp(ptr->key, prev->key) < 0) 	/* 若ptr->name小於prev->name，則把ptr節點設為prev的左子節點，ptr節點以樹葉的形式加入二元樹 */ 
            prev->llink = ptr;					
        else	/* ptr->name大於prev->name，則把ptr節點設為prev的右子節點，ptr節點以樹葉的形式加入二元樹 */ 
            prev->rlink = ptr;
    }
}

/* 將資料從二元搜尋樹中移除 */
void drop(char key[])	/* 本函數原名為removing()，這裡改名令程式看起來乾脆一些 */ 
{
    dict *del_node;		/* del_node記住將被移除的節點位址 */
    
	if ((del_node=search(key)) == NULL)  /* 以傳入的name引數當作比對字串，找尋樹中哪一個節點的name欄位等於該字串；若找不到資料則顯示錯誤 */
    {
        printf("w[%s]不存在\n", key);
        return;
    }
    
    if (del_node->llink != NULL || del_node->rlink != NULL) /* 若del_node節點不為樹葉，則呼叫replace()函數置換該節點內容，內嵌"抓交替"行為 */
        del_node = replace(del_node);						/* 注意傳入replace()的del_node與回傳出來的del_node將不同，回傳出來的是被抓交替的節點位址；replace()內呼叫connecting()調整被抓替的節點遺留的左/右子樹連結方式 */ 
    else  /* 若del_node節點為樹葉，則繼續判別是否為根節點或一般內部節點 */
        if (del_node == root)	/* 若del_node為根節點，則把root指標重置為空 */
            root = NULL;
        else					/* del_node為一般內部節點，則直接呼叫connecting()把該節點移除 */
            connect(del_node, 'n');
    free(del_node);  /* 釋放被抓交替的節點空間 */
    printf("刪除w[%s]元素\n",key);
}

/* 尋找刪除非樹葉的替代節點 */
dict *replace(dict *node)
{
    dict *re_node;	/* 替代節點(被抓交替的節點) */ 
    
    /* 以傳入的node為出發點，呼叫search_re_r()搜尋右子樹替代節點re_node；若右子樹找不到替代節點，再呼叫search_re_l()搜尋左子樹中的替代節點 */
    if ((re_node=search_re_r(node->rlink)) == NULL)
        re_node = search_re_l(node->llink);
    if (re_node->rlink != NULL)  	/* 若替代節點re_node有右子樹，則把該右子樹往上掛為re_node的父節點的左子樹 */
        connect(re_node, 'r');
    else
        if (re_node->llink != NULL)	/* 替代節點re_node有左子樹，則把該左子樹往上掛為re_node的父節點的右子樹 */
            connect(re_node, 'l');
        else  /* re_node指向的替代節點為樹葉 */
            connect(re_node, 'n'); /* 'n'或應改為'm'，以利與後面的程式邏輯一致 */ 
    strcpy(node->key, re_node->key);/* node所指的節點改以re_node節點內容覆蓋掉，完成置換 */ 
    node->value = re_node->value;
    
	return re_node;	/* 回傳被抓交替的節點位址 */ 
}

/* 調整二元搜尋樹的鏈結，link為'r'表示處理右鏈結，為'l'表處理左鏈結，為'm'則將鏈結設為NULL */
void connect(dict *node, char link) /* 這裡傳入的node引數為即將被取代的節點位址 */ 
{
    dict *parent;
    parent = search_p(node);  /* 搜尋將被取代的節點的父節點parent */
    
    if (strcmp(node->key, parent->key) < 0)	/* 被取代的節點位於parent的左子樹 */
        if (link == 'r')  						/* 若link為'r'，則把node的右子樹改掛為parent的左子樹，相當於被取代的節點讓出位置 */
            parent->llink = node->rlink;
        else	/* link為'm'，則node為樹葉，此時只需把parent的左子樹設為空 */
            parent->llink = NULL;
    else  		/* 被取代的節點位於parent的右子樹 */ 
        if (link == 'l')  /* 若link為'l'，則把node的左子樹改掛為parent的右子樹，相當於令node讓位 */
            parent->rlink = node->llink;
        else	/* link為'm'，則node為樹葉，此時只需把parent的右子樹設為空 */
            parent->rlink = NULL;
}

/* 以中序追蹤法秀出每個節點紀錄的姓名與成績，採遞迴方式 */
void inorder(dict *node)
{
    if (node != NULL) {
        inorder(node->llink);
        printf("%s:%d\n", node->key, node->value);
        inorder(node->rlink);
    }
}

void deleteAll(dict *node) /* 以後序走訪的方式刪除節點 */ 
{
    if (node != NULL) {
        deleteAll(node->llink);
        deleteAll(node->rlink);
        printf("刪除'w[%s]=%d'節點\n",node->key,node->value);
        free(node);
    }
}

/* 搜尋target所在節點 */
dict *search(char target[])
{
    dict *node;
    node = root;
    while (node != NULL) {
        if (strcmp(target, node->key) == 0)	/* 若target與node所指的節點內存的字串相同，則回傳node所指節點位址 */
            return node;
        else
            if (strcmp(target, node->key) < 0)	/* 若target小於目前節點，則往左搜尋 */
                node = node->llink;
            else  /* target大於目前節點，往右搜尋 */
                node = node->rlink;
    }
    return node;
}

/* 搜尋右子樹替代節點 */
dict *search_re_r(dict *node)
{
    dict *re_node;
    re_node = node;
    while (re_node != NULL && re_node->llink != NULL) /* 尋找node右子樹底部最左節點，此為最接近的節點，由re_node指向 */ 
        re_node = re_node->llink;
    return re_node;	/* 找得到的re_node回傳出去 */ 
}

/* 搜尋左子樹替代節點 */
dict *search_re_l(dict *node)
{
    dict *re_node;
    re_node = node;
    while (re_node != NULL && re_node->rlink != NULL)	/* 尋找node左子樹底部最右節點 */ 
        re_node = re_node->rlink;
    return re_node;	/* 找得到的re_node回傳出去 */ 
}

/* 搜尋node的父節點 */
dict *search_p(dict *node)
{
    dict *parent;
    parent = root;
    while (parent != NULL) {
        if (strcmp(node->key, parent->key) < 0) {	/* 這裡strcmp()<0，意味node位於parent節點的左子樹 */ 
            if (strcmp(node->key, parent->llink->key) == 0)	/* 若parent的左子節點紀錄的name即為我們關心的節點node所載字串 */ 
                return parent;								/* 即把parent回傳出來 */
            else	/* 否則，原parent的左子節點設為下一個目標，繼續往下找尋 */ 
                parent = parent->llink;
        }
        else { 		/* node位於parent節點的右子樹 */ 
            if (strcmp(node->key, parent->rlink->key) == 0) 	/* 若parent的右子節點紀錄的name即為我們關心的節點所載字串 */ 
                return parent;									/* 即把parent回傳出來 */
            else	/* 否則，原parent的右子節點設為下一個目標，繼續往下找尋 */ 
                parent = parent->rlink;
        }
    }
	return NULL;
}