#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;
}