/*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, "C":5, "D":20 ,"E":30 }
	w={"D":10, "C":3, "B":5, "A":6}
	del w["A"]
	del w["Dickens"]
	del w["Mary"]
	del w["aZ"]
	del w 
	w={"B":3, "A":10}
	w["A"]=10
	w["B"]=20
	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> 

/* 定義dict結構 */
typedef struct dict { 	/* 引線二元搜尋樹節點之資料結構，實作字典 */
	 char key[20]; 		/* 紀錄該節點的「鍵」(key)內容 */
	 int value; 	/* 紀錄「鍵」對應之「值」(value)內容 */
	 struct dict *llink; 	/* 指向左子樹根或引線用途 */
	 struct dict *rlink; 	/* 指向右子樹根或引線用途 */
	 int lbit; 		/* 指示 llink 是否為正常指標 */
	 int rbit; 		/* 指示 rlink 是否為正常指標 */
 } dict;

void show(void);      /* 輸出函數 */
void insert(char [], int);  /* 將資料加入二元搜尋樹 */
void insert_left(struct dict *s, struct dict *t);
void insert_right(struct dict *s, struct dict *t);
void removing(char []);  	/* 將資料從二元搜尋樹中移除 */
void inorder(struct dict *);  /* 資料以中序法輸出 */
void free_all_nodes(struct dict *node);

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

dict *root = NULL, *ptr, *prev ,*head = NULL ;

int main(){ 

	head = (dict *)malloc(sizeof(dict));
    if (head == NULL) {
        printf("記憶體分配失敗！\n");
        return 1;
    }
	head->lbit = head->rbit = 1;
	head->rlink = head;
	head->llink = root;
	
	char  *token, key[12], line[128];
	const char *s = " ={},";	/* 分隔符記的字元 */ 
	int   value;
	char  *rest ,option;
	
   	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);
//    				printf("key=%s,value=%d\n",key,value);
    				insert(key,value);
				} 
   			}
		}else if (strstr(line,"del")) {
			if(sscanf(line,"del w[%[^]]]",key)){
				removing(key);
				printf("\n新的root節點為w[%s]\n",root->key);
			}else{
				printf("無法判讀將刪除哪一個元素，將刪除整個字典? (y/n) => ");
				scanf("%c",&option);
				fflush(stdin);
				if (option == 'y' || option == 'Y') {
					free_all_nodes(root);
					root = NULL;
				}else{
		            printf("取消刪除所有字典\n");
		        }	
			}
		}else if (strstr(line,"+=")) {	/* line含有"+=" */ 
   			sscanf(line,"w[%[^]]] +=%d",key,&value);
   			dict *modify_node;
		   	if((modify_node = search(key)) == NULL){  /* 找不到資料則顯示錯誤 */
		        printf("錯誤! %s 不在此二元搜尋樹中!\n", key); 
		    }else{
		    	modify_node->value += value;
				printf("新設w[%s]=%d\n",key,modify_node->value);
			}
		}else if (strstr(line,"=")) {	/* line含有"=" */
   			sscanf(line,"w[%[^]]] = %d",key,&value);
   			dict *add_node;
   			if (root == NULL){
			   insert(key,value);
			   printf("新設w[%s]=%d\n",key,root->value);
			}else{
				if((add_node = search(key)) == NULL){  /* 找不到資料則新增資料 */
			   		insert(key,value);
			        printf("%s 不在此二元搜尋樹中!\n", key); 
			        printf("新設w[%s]=%d\n",key,value);
			    }else{
			    	add_node->value = value;
			    	printf("新設w[%s]=%d\n",key,add_node->value);
				}
			} 
		}else if (sscanf(line,"w[%[^]]]?",key)==1){
			dict *read_node; 
		   	if((read_node = search(key)) == NULL){  /* 找不到資料則新增資料 */
		        printf("錯誤! %s 不在此二元搜尋樹中!\n", key); 
		    }else{
		    	printf("字典元素w[%s]=%d\n",key,read_node->value);
			}
		}else if (strstr(line,"?")) show();
		else printf("語法無法辨認，sorry!\n");
	}
	printf("\n程式結束，刪除所有節點，bye ~\n");
	free_all_nodes(root);
   	free(head);
   	
   	return 0;
}

void insert(char key[], int value) {
    // 檢查是否已存在
    if (search(key) != NULL) {
        printf("%s 已存在!\n", key);
        return;
    }

    // 建立新節點
    ptr = (struct dict *) malloc(sizeof(struct dict));
    strcpy(ptr->key, key);
    ptr->value = value;
    ptr->lbit = ptr->rbit = 0;
	ptr->llink = ptr->rlink = head;  // 明確初始化為 NULL

    // 處理空樹的情況
    if (root == NULL) {
        root = ptr;
        head->llink = root;    // head 的左鏈結指向 root
        root->llink = head;    // root 的左執行緒指向 head
        root->rlink = head;    // root 的右執行緒指向 head
        return;
    }

    // 尋找插入位置
    dict *current = root;
    dict *parent;

    while (1) {
        parent = current;
        if (strcmp(ptr->key, current->key) < 0) {  // 往左走
            if (current->lbit == 0) {  // 找到插入位置
                insert_left(current, ptr);
                break;
            }
            current = current->llink;
        }else {  // 往右走
            if (current->rbit == 0) {  // 找到插入位置
                insert_right(current, ptr);
                break;
            }
            current = current->rlink;
        }
    }
}

// 在某節點左方插入新節點
void insert_left(struct dict *s, struct dict *t) {
    t->llink = s->llink;  // 新節點的左子節點指向原節點的左子節點
    t->rlink = s;          // 新節點的右子節點指向原節點
    t->lbit = s->lbit;      // 新節點繼承原節點的左位元值
    t->rbit = 0;            // 設定右位元為引線 
    s->llink = t;          // 原節點的左子節點指向新節點
    s->lbit = 1;            // 設定左位元為正常鏈結
    
    if (t->lbit == 1) {
        dict *p = t->llink;
        while (p->rbit == 1)
            p = p->rlink;
        p->rlink = t;
    }
}

// 在某節點右方插入新節點
void insert_right(struct dict *s, struct dict *t) {
    t->rlink = s->rlink;  // 新節點的右子節點指向原節點的右子節點
    t->rbit = s->rbit;      // 新節點繼承原節點的右位元值
    t->llink = s;          // 新節點的左子節點指向原節點
    t->lbit = 0;            // 設定左位元為引線 
    s->rlink = t;          // 原節點的右子節點指向新節點
    s->rbit = 1;            // 設定右位元為正常鏈結
    
    // 尋找前驅節點並更新引線
    if (t->rbit == 1) {
        dict *p = t->rlink;
        while (p->lbit == 1)
            p = p->llink;
        p->llink = t;
    }
}

/* 將資料從二元搜尋樹中移除 */
void removing(char key[]) {
    dict *del_node = search(key);
    if (del_node == NULL) {
        printf("%s 不在此二元搜尋樹中!\n", key);
        return;
    }
    
    dict *parent = search_p(del_node);
    
    //若為葉節點
    if (del_node->lbit == 0 && del_node->rbit == 0) {
        if (parent == NULL) {  // 刪除的是根節點
            root = NULL;
            head->llink = head;
        } else if (parent->llink == del_node) {
            parent->llink = del_node->llink;  // 繼承左引線 
            parent->lbit = 0;
        } else {
            parent->rlink = del_node->rlink;  // 繼承右引線 
            parent->rbit = 0;
        }
        free(del_node);
    }
    
    // 若只有左子樹
    else if (del_node->lbit == 1 && del_node->rbit == 0) {
        dict *left_child = del_node->llink;
        dict *successor = del_node->rlink;  // 保存後繼節點
        
        // 找到左子樹的最右節點
        dict *rightmost = left_child;
        while (rightmost->rbit == 1) {
            rightmost = rightmost->rlink;
        }
        
        // 更新連接
        rightmost->rlink = successor;
        if (parent == NULL) {
            root = left_child;
            head->llink = root;
        } else if (parent->llink == del_node) {
            parent->llink = left_child;
        } else {
            parent->rlink = left_child;
        }
        free(del_node);
    }
    
    // 若只有右子樹
    else if (del_node->lbit == 0 && del_node->rbit == 1) {
        dict *right_child = del_node->rlink;
        dict *predecessor = del_node->llink;  // 保存前驅節點
        
        // 找到右子樹的最左節點
        dict *leftmost = right_child;
        while (leftmost->lbit == 1) {
            leftmost = leftmost->llink;
        }
        
        // 更新連接
        leftmost->llink = predecessor;
        if (parent == NULL) {
            root = right_child;
            head->llink = root;
        } else if (parent->llink == del_node) {
            parent->llink = right_child;
        } else {
            parent->rlink = right_child;
        }
        free(del_node);
    }
    
    // 若有兩個子樹
    else {
        // 找左子樹中最大的節點
        dict *predecessor = del_node->llink;
        dict *pred_parent = del_node;
        
        while (predecessor->rbit == 1) {
            pred_parent = predecessor;
            predecessor = predecessor->rlink;
        }
        
        // 複製後繼節點的數據到被刪除節點
        strcpy(del_node->key, predecessor->key);
        del_node->value = predecessor->value;
        
        // 移除後繼節點
        if (pred_parent == del_node) {
            del_node->llink = predecessor->llink;
            del_node->lbit = predecessor->lbit;
        } else {
            pred_parent->rlink = predecessor->rlink;
            pred_parent->rbit = predecessor->rbit;
        }
        
        free(predecessor);
    }
    
    printf("刪除w[%s]元素\n", key);
}

void show(void) {
    if (root == NULL) {
        puts("二元搜尋樹是空的!");
        return;
    }
    printf("字典變數內部儲存的元素(key：value)如下\n");
    inorder(root);
}

// 使用引線特性進行中序遍歷
void inorder(dict *root) {
	
    if (root == NULL) {
        printf("二元搜尋樹是空的!\n");
        return;
    }

    dict *current = root;
    
    // 先找到最左邊的節點
    while (current->lbit == 1) {
        current = current->llink;
    }
	
	while (1) {
		
		printf("%s：%d\n", current->key, current->value);

        current = insuc(current);
        
        if (current == NULL || current == head) {
            break;
        }
    }
}

// 尋找中序後繼節點
dict *insuc(dict *ptr) {
    if (ptr == NULL) return NULL;
    
    // 如果有右子樹
    if (ptr->rbit == 1) {
        // 移至右子樹
        ptr = ptr->rlink;
        // 然後一直往左走直到不能再走
        while (ptr->lbit == 1) {
            ptr = ptr->llink;
        }
        return ptr;
    }
    // 如果沒有右子樹，則返回右引線指向的節點
    return ptr->rlink;
}

/* 搜尋target所在節點 */
struct dict *search(char target[]) {
    struct dict *node = root;
    
    while (node != NULL && node != head) {  // 加入 head 的檢查以防止走到頭節點
        int cmp = strcmp(target, node->key);
        if (cmp == 0) {
            return node;  // 找到目標節點
        } else if (cmp < 0) {  // target 小於目前節點，往左搜尋
            if (node->lbit == 0) {  // 如果左邊是引線 
                return NULL;  // 代表找不到目標
            }
            node = node->llink;
        } else {  // target 大於目前節點，往右搜尋
            if (node->rbit == 0) {  // 如果右邊是引線 
                return NULL;  // 代表找不到目標
            }
            node = node->rlink;
        }
    }
    return NULL;  // 找不到目標
}

/* 搜尋node的父節點 */
struct dict *search_p(struct dict *node) {
    if (node == NULL || node == root) {
        return NULL;
    }

    struct dict *current = root;
    struct dict *parent = NULL;

    while (current != NULL && current != head) {
        int cmp = strcmp(node->key, current->key);
        
        if (cmp == 0) {  // 找到目標節點，返回其父節點
            return parent;
        }
        
        parent = current;  // 更新父節點
        
        if (cmp < 0) {  // 目標在左子樹
            if (current->lbit == 0) {  // 如果是引線 
                return NULL;  // 找不到目標
            }
            current = current->llink;
        } else {  // 目標在右子樹
            if (current->rbit == 0) {  // 如果是引線 
                return NULL;  // 找不到目標
            }
            current = current->rlink;
        }
    }
    
    return NULL;  // 沒有找到目標節點
}

// 釋放所有節點
void free_all_nodes(struct dict *root) {
    if (root == NULL) {
        return;
    }

    dict *current = root;
    dict *temp;

    // 找到最左邊的節點
    while (current->lbit == 1) {
        current = current->llink;
    }

    // 使用引線特性遍歷並釋放節點
    while (current != head) {
        temp = current;
        current = insuc(current);
        printf("刪除'w[%s]=%d'節點\n", temp->key, temp->value);
        free(temp);
    }
    root = NULL;
}