/*Notes: 輸入可為 
	w={"Mary":10, "Tom":3, "Charlie":5, "Bob":6, "Dickens":20, 4:9, "z":0, "Za":12, "aZ":8}
	w={10:10, 20:3, 5:5, 17:6, 23:20, 18:9, 3:0, 9:12}
	w={10:10, 5:5, 9:6, 3:20, 7:9}
	w={"A":10, "B":3, "Charlie":5, "Bob":6, "Dickens":20}
	w={"A":6,"B":5,"C":3,"D":10}
	w={"A":6,"B":5}
	del w["A"]
	del w["Dickens"]
	del w["Mary"]
	del w["aZ"]
	del w
	w["Mary"]=1
	w["Tom"]+=2
	w[4]?
	w?
*/

#include <stdio.h>	/* for sscanf(), printf() */
#include <stdlib.h>	
#include <string.h>	/* for strstr(), strtok(), strtok_r() */
#include <conio.h> 

/* 定義student結構 */
typedef struct student {
    char name[20];  /* 學生姓名 */
    int score;  /* 學生成績 */
    struct student *llink;  /* 左子鏈結 */
    struct student *rlink;  /* 右子鏈結 */
}student;

void show(void);      /* 輸出函數 */
void insert(char [], int);  /* 將資料加入二元搜尋樹 */
void removing(char []);  /* 將資料從二元搜尋樹中移除 */
void inorder(struct student *);  /* 資料以中序法輸出 */
void free_all_nodes(struct student *node);
void find_newroot(void);  /* 搜尋新的樹跟節點 */

student *search_p(struct student *node);
student *search(char []);  /* 搜尋節點 */

student *root, *ptr, *prev;

int main(){ 
	char  *token, key[12], line[128];
	const char *s = " ={},";	/* 分隔符記的字元 */ 
	int   value;
	char  *rest ,choice[3];
	
   	printf("輸入存取字典的陳述，逕按<Enter>結束程式\n");
   	while (1) {
   		printf("\n指令 => ");
   		fgets(line,128,stdin);		/* 使用gets()讀取也可以，但因gets()未設讀入字元數的限制，可能導致儲存輸入字元的陣列空間爆掉 */ 
   		if (line[0]=='\n') break;	/* 輸入空字串則跳離此迴圈 */ 
   		if (strstr(line,"{")) {		/* line含有"{" */ 
   			sscanf(line,"w = {%[^}]}",line);
			rest = line;
			while (token = strtok_r(rest,s,&rest)) { /* strtok_r()的用法可參見 http://bit.ly/3VcvbbZ */ 
    			/* printf("%s\n",token); */ 
    			if (strstr(token,":")) {/* token含有":" */ 
    				sscanf(token,"%[^:]:%d",key,&value);
    				insert(key,value);
//    				printf("Token #%d: 鍵=%s; 值=%d\n",++i,key,value);
				} 
   			}
		}else if (strstr(line,"del")) {
		    if(strcmp(line,"del w\n")==0){
		        printf("無法判讀將刪除哪一個元素，將刪除整個字典(y/n) => ");
		        fgets(choice, sizeof(choice), stdin);
		        if(strcmp(choice,"y\n")==0){
		            free_all_nodes(root);
					root = NULL;
		        }else{
		            printf("取消刪除所有字典\n");
		        }
		    }else{
		        if(sscanf(line,"del w[%[^]]]",key)==1){
		        	if(strcmp(key,root->name)==0){
	//		        	printf("刪除的元素w[%s]為root節點\n",key);
						find_newroot();
	//					printf("新的root節點為w[%s]\n",root->name);
					}else{
						removing(key);
					}
				}
		    }
		}else if (strstr(line,"+=")) {	/* line含有"+=" */ 
   			sscanf(line,"w[%[^]]] +=%d",key,&value);
   			student *modify_node;
		   	if((modify_node = search(key)) == NULL){  /* 找不到資料則顯示錯誤 */
		        printf("錯誤! %s 不在此二元搜尋樹中!\n", key); 
		    }else{
		    	modify_node->score += value;
				printf("新設w[%s]=%d\n",key,modify_node->score);
			}
		}else if (strstr(line,"=")) {	/* line含有"=" */
   			sscanf(line,"w[%[^]]] = %d",key,&value);
   			student *add_node;
   			if (root == NULL){
			   insert(key,value);
			   printf("新設w[%s]=%d\n",key,root->score);
			}else{
				if((add_node = search(key)) == NULL){  /* 找不到資料則新增資料 */
			   		insert(key,value);
			        printf("%s 不在此二元搜尋樹中!\n", key); 
			        printf("新設w[%s]=%d\n",key,value);
			    }else{
			    	add_node->score = value;
			    	printf("新設w[%s]=%d\n",key,add_node->score);
				}
			} 
		}else if (sscanf(line,"w[%[^]]]?",key)==1){
			student *read_node; 
		   	if((read_node = search(key)) == NULL){  /* 找不到資料則新增資料 */
		        printf("錯誤! %s 不在此二元搜尋樹中!\n", key); 
		    }else{
		    	printf("字典元素w[%s]=%d\n",key,read_node->score);
			}
		}else if (strstr(line,"?")) show();
		else printf("語法無法辨認，sorry!\n");
	}
   	
   	printf("\n程式結束，bye ~\n");
   	return 0;
}

/* 處理二元搜尋樹，將新增資料加入至二元搜尋樹中 */
void insert(char name[], int score){
    struct student *node, *prev;
    /* 資料已存在則顯示錯誤 */
    if (search(name) != NULL) {
        printf("%s 已存在!\n", name);
        return;
    }
    ptr = (struct student *) malloc(sizeof(struct student));
    strcpy(ptr->name, name);
    ptr->score = score;
    ptr->llink = ptr->rlink = NULL;
    if (root == NULL)  /* 當根節點為NULL的狀況 */
        root = ptr;
    else { /* 當根節點不為NULL的狀況 */
        node = root;
        while (node != NULL) { /* 搜尋資料插入點 */
            prev = node;
            if(strcmp(ptr->name, node->name) < 0)
                node = node->llink;
            else
                node = node->rlink;
        }
        if (strcmp(ptr->name, prev->name) < 0)
            prev->llink = ptr;
        else
            prev->rlink = ptr;
    }
}

/* 將資料從二元搜尋樹中移除 */
void removing(char name[]){
    student *del_node = search(name);
    if (del_node == NULL) {
        printf("%s 不在此二元搜尋樹中!\n", name);
        return;
    }
    
    student *parent = search_p(del_node);
    
    // 處理沒有子節點的情況
    if (del_node->llink == NULL && del_node->rlink == NULL) {
        if (parent->llink == del_node) {
            parent->llink = NULL;
        } else {
            parent->rlink = NULL;
        }
    }else if (del_node->llink == NULL || del_node->rlink == NULL) {  // 處理一邊有子節點的情況
        student *child = (del_node->llink != NULL) ? del_node->llink : del_node->rlink;
        if (parent->llink == del_node) {
            parent->llink = child;
        } else {
            parent->rlink = child;
        }
    }else{ //處理兩邊有子節點的情況
    	if(del_node == parent->rlink){
    		parent->rlink = del_node->llink;
    		if(del_node->llink->rlink != NULL){ //若刪除的節點的子節點還有右節點的情況
    			student *child = del_node->llink->rlink;
    			printf("%s\n",child->name);
    			while(child->rlink!= NULL){ //找右節點直到最底 
    				child = child->rlink;
    				printf("%s\n",child->name);
				}
				child->rlink = del_node->rlink;
			}else parent->rlink->rlink = del_node->rlink;  //沒有則直接替換
    		
		}else{
			parent->llink = del_node->llink;
			if(del_node->rlink->llink != NULL){ //若刪除的節點的子節點還有左節點的情況 
    			student *child = del_node->rlink->llink;
    			printf("%s\n",child->name);
    			while(child->llink!= NULL){ //找左節點直到最底 
    				child = child->llink;
    				printf("%s\n",child->name);
				}
				child->llink = del_node->llink;
			}else parent->llink->rlink = del_node->rlink; //沒有則直接替換
		}  
	}
    free(del_node);  /* 釋放記憶體 */
	printf("刪除w[%s]元素\n",name);
}

/* 輸出函數，將資料輸出至螢幕 */
void show(void){
    /* 判斷根節點是否為NULL */
    if (root == NULL) {
        puts("二元搜尋樹是空的!");
        return;
    }
//    printf("root為%s\n", root->name);
	printf("字典變數內部儲存的元素(key：value)如下\n");
    inorder(root);  /* 以中序法輸出資料 */
}

/* 以中序法輸出資料，採遞迴方式 */
void inorder(struct student *node ){
    if(node != NULL) {
    
        inorder(node->llink);
        printf("%s：%d\n", node->name, node->score);
        inorder(node->rlink);
    }
}

void find_newroot(){ /* 搜尋新的樹跟節點 左連結最大值*/
	struct student *newroot_node ,*prev;
	
	if(root->llink == NULL && root->rlink == NULL){
		printf("刪除w[%s]元素\n",root->name);
		free(root);
        root = NULL;
		return;
	}
	
	if(root->llink!=NULL){ //找左連結的最大值  
		newroot_node = root->llink;
		
		while(newroot_node->rlink!=NULL){ //找根的替代節點 
			prev = newroot_node;
			newroot_node = newroot_node->rlink;
		}
		if(newroot_node->llink!=NULL){ //若新的根節點有左節點 
			prev->rlink = newroot_node->llink;
		}else prev->rlink = NULL;
		
		if(newroot_node != root->llink ){  //若新的根節點不等於原本根的左節點
			newroot_node->llink = root->llink;
			newroot_node->rlink = root->rlink;
		}else{	//若新的根節點等於原本根的左節點
			newroot_node->rlink = root->rlink;
		}
		printf("刪除w[%s]元素\n",root->name);
		free(root);
		root = newroot_node;
	}else if(root->rlink!=NULL){ //找右連結的最小值  
		newroot_node = root->rlink;
		
		while(newroot_node->llink!=NULL){ //找根的替代節點 
			prev = newroot_node;
			newroot_node = newroot_node->llink;
		}
		if(newroot_node->rlink!=NULL){ //若新的根節點有右節點  
			prev->llink = newroot_node->rlink;
		}else prev->llink = NULL;
		
		if(newroot_node != root->rlink ){ //若新的根節點不等於原本根的右節點
			newroot_node->llink = root->llink;
			newroot_node->rlink = root->rlink;
		}else{ //若新的根節點等於原本根的右節點 
			newroot_node->llink = root->llink;
		}
		printf("刪除w[%s]元素\n",root->name);
		free(root);
		root = newroot_node;
	}
}

/* 搜尋target所在節點 */
struct student *search(char target[]){
    struct student *node;
    node = root;
    while(node != NULL){
        if (strcmp(target, node->name) == 0)
            return node;
        else
            /* target小於目前節點，往左搜尋 */
            if (strcmp(target, node->name) < 0)
                node = node->llink;
            else  /* target大於目前節點，往右搜尋 */
                node = node->rlink;
    }
    return node;
}

/* 搜尋node的父節點 */
struct student *search_p(struct student *node){
    struct student *parent;
    parent = root;
    while (parent != NULL) {
        if (strcmp(node->name, parent->name) < 0) {
            if (strcmp(node->name, parent->llink->name) == 0)
                return parent;
            else
                parent = parent->llink;
        }else {
            if (strcmp(node->name, parent->rlink->name) == 0)
                return parent;
            else
                parent = parent->rlink;
        }
    }
    return NULL;
}

/* 遞迴釋放所有節點的記憶體 */
void free_all_nodes(struct student *node) {
    if (node == NULL) return;
    
    // 先遞迴釋放左子樹
    free_all_nodes(node->llink);
    // 再遞迴釋放右子樹
    free_all_nodes(node->rlink);
    printf("刪除'w[%s]=%d'節點\n",node->name,node->score);
    // 最後釋放當前節點
    free(node);
}