/* file name: btree.c */
/* 利用B-TREE來處理數據--加載、儲存、新增、刪除、修改、查詢、輸出 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#define MAX 2    /* 每一節點內至多可放數據筆數 */
#define MIN 1    /* 每一節點內至少需放數據筆數 */
typedef struct student {    /* 數據結構 */
 int count;                /* 節點數據數 */
 int id[MAX+1];            /* ID號碼--鍵值 */
 char name[MAX+1][11];     /* 姓名 */
 int score[MAX+1];         /* 分數 */
 struct student *link[MAX+1];    /* 子鏈接 */
} Node_type;
Node_type *root;
void init_f(FILE *);  /* 初始化函數 */
void insert_f(void);  /* 新增函數 */
Node_type *access(int, char *, int, Node_type *);  /* 將新增數據加入B-tree中 */
int topdown(int, char *, int, Node_type *, int *, char *, int *,
   Node_type **);  /* 從根節點往下逐一尋找插入點，將數據新增的函數 */
/* 將數據置于某特定節點中 */
void putdata(int, char *, int, Node_type *, Node_type *, int);
void broken(int, char *, int, Node_type *, Node_type *, int, int *, char *,
   int *, Node_type **);  /* 將一節點劃分為二 */
void update_f(void);  /* 修改函數 */
void delete_f(void);  /* 刪除函數 */
Node_type *removing(int, Node_type *);  /* 將數據從B-tree中刪除 */
int deldata(int, Node_type *);  /* 刪除數據函數 */
void move(Node_type *, int);  /* 將節點中的數據逐一往左移 */
void replace(Node_type *, int);  /* 尋找替代節點 */
void restore(Node_type *, int);  /* 數據刪除后的調整工作 */
void getleft(Node_type *, int);  /* 向左兄弟節點借一筆數據 */
void getright(Node_type *, int);  /* 向右兄弟節點借一筆數據 */
void combine(Node_type *, int);  /* 節點合并 */
void list_f(void);  /* 輸出函數 */
void show(Node_type *);  /* 以遞歸方式依序將數據輸出 */
void query_f(void);  /* 查詢函數 */
void save(Node_type *, FILE *);  /* 儲存函數 */
void quit(void);  /* 結束函數 */
Node_type * search(int, Node_type *, int *);  /* 依鍵值查找某特定節點函數 */
int searchnode(int, Node_type *, int *);  /* 依鍵值查找節點中某特定數據函數 */


void main(void)
{
     int flag=0, times=1;  /* times是判斷是否為第一次進入需要加載輸入文件 */
    FILE *infile, *outfile;
    char choice, filename[11], ans;
    system("cls");
    while(1)
    {
        if(times == 1)
    	{
        	do
    		{
                    /* 要求輸入加載文件名稱 */
                printf("\n  Please enter input file name: ");
                scanf("%s", filename);
                if((infile = fopen(filename, "r")) == NULL)
        		{
                    puts("  File name not found!!");
                	flag = 0;
        		}
        		else
                	flag = 1;
            }  while(flag == 0);  /* flag為0時，表示輸入錯誤，會要求重新輸入 */
            times++;
    	}
        fseek(infile, 0, 0);
        init_f(infile);
     do
     {
            printf("\n");
            puts("  *********************");
            puts("        1.insert");
            puts("        2.update");
            puts("        3.delete");
            puts("        4.list");
            puts("        5.query");
            puts("        6.save");
            puts("        7.quit");
            puts("  *********************");
            printf("  Please enter your choice(1..7): ");
            choice = getche();
            printf("\n");
            switch(choice)
            {
                case '1':
     	           insert_f();
            		break;
                case '2':
                	update_f();
            		break;
                case '3':
                	delete_f();
            		break;
                case '4':
                	list_f();
            		break;
                case '5':
                	query_f();
            		break;
                case '6':
                	flag = 0;
        			do
        			{
                        puts("\n  ---- SAVE ----");
                        printf("  Please enter saving file name: ");
                        scanf("%s", filename);
                        if((outfile = fopen(filename, "w")) == NULL)
        				{
                            puts(" File name can not be used!!");
                			flag = 0;
        				}
            			else
                           flag=1;
                    }  while(flag == 0);
                    save(root, outfile);
                    printf("  Save OK!\n");
                    fclose(outfile);
            		break;
                case '7': printf("  Are you sure? (Y/N): ");
                    ans = getche();
                    ans = toupper(ans);
                    if(ans == 'Y')
        			{
                        fclose(infile);
                		quit();
        			}
            		break;
                default: puts("  Choice error!!");
    		}
        }  while(choice != '7');
    }
}


/* 讀入輸入文件數據至B-tree中，infile為輸入文件名稱 */
void init_f(FILE *infile)
{
    int init_id, init_score;
    char init_name[11];
    root = NULL;
    while(fscanf(infile, "%d %10s %d\n", &init_id, init_name, &init_score)
            		!= EOF)
    {
        root = access(init_id, init_name, init_score, root);
    }
}

/* 新增一筆數據，并調整為B-tree */
void insert_f(void)
{
     int position, insert_id, insert_score; /* position記錄數據在節點中新增的位置 */
    Node_type *node;
    char ans, insert_name[11];
    puts("\n  ---- INSERT ----");
    puts("  Please enter detail data");
    printf("  ID number: ");
    scanf("%d", &insert_id);
     /* 找尋新增數據是否已存在，若存在，則顯示錯誤 */
    node = search(insert_id, root, &position);
    if(node != NULL)
        puts(" ID number has existed!!");
    else
    {
        printf("  Name: ");  /* 要求輸入其它詳細數據 */
        scanf("%s'", insert_name);
        printf("  Score: ");
        scanf("%d", &insert_score);
        printf("  Are you sure? (Y/N): ");
        ans = getche();
        printf("\n");
        ans = toupper(ans);
        if(ans == 'Y')
            root = access(insert_id, insert_name, insert_score, root);
    }
}

/* 將新增數據加入B-TREE，node指加入節點，傳回值為root所在 */
Node_type *access(int app_id, char *app_name, int app_score, Node_type *node)
{
    int x_id, x_score, pushup;   /* pushup判斷節點是否需劃分而往上新增一節點 */
    char x_name[11];
    Node_type *xr, *p;
    pushup = topdown(app_id, app_name, app_score, node, &x_id, x_name,
                        &x_score, &xr);
    if(pushup)   /* 若pushup為1，則配置一個新節點，將數據放入 */
    {
        p = (Node_type *) malloc(sizeof(Node_type));
        p->link[0] = NULL;
        p->link[1] = NULL;
        p->link[2] = NULL;
        p->count = 1;
        p->id[1] = x_id;
        strcpy(p->name[1], x_name);
        p->score[1] = x_score;
        p->link[0] = root;
        p->link[1] = xr;
        return p;
    }
    return node;
}


/* 從樹根往下尋找數據加入節點，將數據新增于B-tree中，參數p為目前所在節點，
   xr記錄數據所對應的子鏈接 */
int topdown(int new_id, char *new_name, int new_score, Node_type *p,
            int *x_id, char *x_name, int *x_score, Node_type **xr)
{
    int k;
     if(p == NULL)  /* p為NULL表示新增第一筆數據 */
    {
        *x_id = new_id;
        strcpy(x_name, new_name);
        *x_score = new_score;
        *xr = NULL;
        return 1;
    }
    else
    {
          if(searchnode(new_id, p, &k))  /* 找尋新增數據鍵值是否重復，若重復則顯示錯誤 */
    	{
            puts("  Data error, ID number has existed!!");
            quit();
            return 0;
    	}
         /* 繼續往下找尋新增節點 */
        if(topdown(new_id, new_name, new_score, p->link[k], x_id, x_name,
                    x_score, xr))
    	{
            if(p->count < MAX)  /* 若新增節點有足夠的空間存放數據，則將數據直接加入該節點 */ 
    		{
            putdata(*x_id, x_name, *x_score, *xr, p, k);
            return 0;
    		}
        	else
    		{
                 /* 若無足夠空間，則須劃分節點 */
                broken(*x_id, x_name, *x_score, *xr, p, k, x_id, x_name, x_score, xr);
                return 1;
    		}
    	}
        else
            return 0;
    }
}

/* 將新增數據直接加入于節點中，xr為新增數據對應的子鏈接所在，p為數據加入的節點 */
void putdata(int x_id, char *x_name, int x_score, Node_type *xr,
                Node_type *p, int k)
{
    int i;
    /* 將節點中的數據逐一右移，以空出新增數據加入的位置 */
    for(i = p->count; i > k; i--)
    {
        p->id[i+1] = p->id[i];
        strcpy(p->name[i+1], p->name[i]);
        p->score[i+1] = p->score[i];
        p->link[i+1] = p->link[i];
    }
    p->id[k+1] = x_id;
    strcpy(p->name[k+1], x_name);
    p->score[k+1] = x_score;
    p->link[k+1] = xr;
    p->count++;
}

/* 將節點一分為二，yr為劃分后新增加的節點 */
void broken(int x_id, char *x_name, int x_score, Node_type *xr, Node_type *p,
            int k, int *y_id, char *y_name, int *y_score, Node_type **yr)
{
    int i;
    int median;    /* median記錄從何處劃分節點 */
    if(k <= MIN)
        median = MIN;
    else
        median = MIN + 1;
    *yr = (Node_type *) malloc(sizeof(Node_type));
     /* 將數據從劃分處開始搬移至新節點中 */
    for(i = median + 1; i <= MAX; i++)
    {
        (*yr)->id[i-median] = p->id[i];
        strcpy((*yr)->name[i-median], p->name[i]);
        (*yr)->score[i-median] = p->score[i];
        (*yr)->link[i-median] = p->link[i];
    }
    (*yr)->count = MAX - median;
    p->count = median;
    if(k <= MIN)
        putdata(x_id, x_name, x_score, xr, p, k);
    else
        putdata(x_id, x_name, x_score, xr, *yr, k - median);
    *y_id = p->id[p->count];
    strcpy(y_name, p->name[p->count]);
    *y_score = p->score[p->count];
    (*yr)->link[0] = p->link[p->count];
    p->count--;
}

/* 修改數據函數 */
void update_f(void)
{
    int update_id, update_score, position;
    char ans, update_name[11];
    Node_type *node;
    puts("\n  ---- UPDATE ----");
    printf("  Please enter ID number: ");
    scanf("%d", &update_id);
    node = search(update_id, root, &position);   /* 找尋欲修改數據所在節點位置 */
    if(node != NULL)
    {
        printf("  Original name: %s\n", node->name[position]);
        printf("  Please enter new name: ");
        scanf("%10s", update_name);
        printf("  Original score: %d\n", node->score[position]);
        printf("  Please enter new score: ");
        scanf("%d", &update_score);
        printf("  Are you sure? (Y/N): ");
        ans = getche();
        printf("\n");
        ans = toupper(ans);
        if(ans == 'Y')
    	{
            node->score[position] = update_score;
            strcpy(node->name[position], update_name);
    	}
    }
    else
        puts("  ID number not found!!");
}