#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define bool char
typedef struct _trie_node{
	bool end; /* 要記錄是不是字串結尾 */ 
	int dat; /* 對應的資料 */
	struct _trie_node *child[27]; /* A-Z 對應 0-25，26 代表 - 符號 */
}TRI;
TRI* t_root;
bool bad;
void mstr(char* in){
	int i;
	for(i=0;in[i]!='\0';i++){
		if(in[i] >= 'a' && in[i] <= 'z'){
			in[i]-=32;
		}else if(in[i] <= 'A' || in[i] >= 'Z'){
			in[i]='-';
		}
	}
}
int convert(char a){
	if(a>= 'A' && a<= 'Z'){
		return (a-'A');
	}
	return 26;
}
char convertback(int a){
	if(a==26){
		return '-';
	}
	return (a+'A');
}
TRI* makenode(void){
	TRI* tmp=malloc(sizeof(TRI));
	tmp->end=0;
	memset(tmp->child,0,sizeof(tmp->child));
	return tmp;
}
void t_query(const char* pre,char* buf,int count,TRI* now){
	int i;
	if(now->end){
		buf[count]='\0';
		bad=0;
		printf("%s%s -> %d\n",pre,buf,now->dat);
	}
	for(i=0;i<27;i++){
		if(now->child[i] != NULL){
			buf[count]=convertback(i);
			t_query(pre,buf,count+1,now->child[i]);
		}
	}
}
int main(){
	puts("(Data Structure) trie 模擬程式");
	int in;
	int i;
	TRI* tmp;
	t_root=makenode();
	char ins[17],tpc,buf[17];
	while(1){
		printf("\n1 加入一個對應\n"
				"2 修改一個對應\n"
				"3 刪除一個對應\n"
				"4 查詢\n"
				"請選擇：");
		scanf("%d",&in);
		getchar();
		switch(in){
			case 1:
				printf("字串：");
				fgets(ins,16,stdin);
				ins[strlen(ins)-1]='\0';
				mstr(ins);
				printf("整數：");
				scanf("%d",&in);
				for(i=0,tmp=t_root;ins[i]!='\0';i++){
					if(tmp->child[tpc=convert(ins[i])] == NULL){
						tmp->child[tpc]=makenode();
					}
					tmp = tmp->child[tpc];
				}
				tmp->dat = in;
				tmp->end = 1;
				break;
			case 2:
				printf("字串：");
				fgets(ins,16,stdin);
				ins[strlen(ins)-1]='\0';
				mstr(ins);
				for(i=0,bad=0,tmp=t_root;ins[i]!='\0';i++){
					if(tmp->child[tpc=convert(ins[i])] == NULL){
						bad=1;
						break;
					}
					tmp = tmp->child[tpc];
				}
				if(bad || tmp->end == 0){
					puts("錯誤：沒有這個字串");
					continue;
				}
				printf("原先的值：%d\n",tmp->dat);
				printf("整數：");
				scanf("%d",&(tmp->dat));
				break;
			case 3:
				printf("字串：");
				fgets(ins,16,stdin);
				ins[strlen(ins)-1]='\0';
				mstr(ins);
				for(i=0,bad=0,tmp=t_root;ins[i]!='\0';i++){
					if(tmp->child[tpc=convert(ins[i])] == NULL){
						bad=1;
						break;
					}
					tmp = tmp->child[tpc];
				}
				if(bad || tmp->end == 0){
					puts("錯誤：沒有這個字串");
					continue;
				}
				tmp->end=0; /* 清除標記，並沒有釋放記憶體空間 */
				break;
			case 4:
				printf("字串：");
				fgets(ins,16,stdin);
				ins[strlen(ins)-1]='\0';
				mstr(ins);
				for(i=0,bad=0,tmp=t_root;ins[i]!='\0';i++){
					if(tmp->child[tpc=convert(ins[i])] == NULL){
						bad=1;
						break;
					}
					tmp = tmp->child[tpc];
				}
				if(bad){
					puts("錯誤：沒有這個字串");
					continue;
				}
				bad=1;
				t_query(ins,buf,0,tmp);
				if(bad){
					puts("錯誤：沒有這個字串");
					continue;
				}
				break;
			default:
				puts("錯誤：沒有這個操作");
		}
	}
	return 0;
}