/* 刪除數據函數 */
void delete_f(void)
{
    int del_id, position;  /* position記錄刪除數據在節點中的位置 */
    char ans;
    Node_type *node;
    puts("\n  ---- DELETE ----");
    printf("  Please enter ID number: ");
    scanf("%d", &del_id);
    node = search(del_id, root, &position);
    if(node != NULL)
    {
        printf("  Are you sure? (Y/N): ");
        ans = getche();
        printf("\n");
        ans = toupper(ans);
        if(ans == 'Y')
            root = removing(del_id, root);
    }
    else
        puts("  ID number not found!!");
}

/* 將數據從B-tree中刪除，若刪除后節點內數據筆數為0，則一并刪除該節點 */
Node_type *removing(int del_id, Node_type *node)
{
    Node_type *p;
    if(!deldata(del_id, node));
    else
        if(node->count == 0)
    	{
            p = node;
            node = node->link[0];
            free(p);
    	}
    return node;
}

/* 將數據從B-tree中移除，若刪除失敗則傳回0，否則傳回數據在節點中所在位置 */
int deldata(int del_id, Node_type *p)
{
    int k;
    int found;
    if(p == NULL)
        return 0;
    else
    {
        if((found = searchnode(del_id, p, &k)) != 0)
    	{
            if(p->link[k-1])
    		{
            replace(p, k);
            if(!(found = deldata(p->id[k], p->link[k])))
                printf("  Key not found");
    		}
        	else
            move(p,k);
    	}
        else
            found = deldata(del_id, p->link[k]);
        if(p->link[k] != NULL)
    	{
            if(p->link[k]->count < MIN)
            restore(p, k);
    	}
        return found;
    }
}

/* 將節點中的數據從k的位置逐一左移 */
void move(Node_type *p, int k)
{
    int i;
    for(i = k+1; i <= p->count; 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->count--;
}

/* 尋找刪除非葉時的替代數據 */
void replace(Node_type *p, int k)
{
    Node_type *q;
    for(q = p->link[k]; q->link[0]; q = q->link[0]);
    p->id[k] = q->id[1];
    strcpy(p->name[k], q->name[1]);
    p->score[k] = q->score[1];
}

/* 數據刪除后，重新調整為B-tree */
void restore(Node_type *p, int k)
{
    if(k == 0)   /* 刪除數據為節點中的第一筆數據 */
    {
        if(p->link[1]->count > MIN)
            getright(p, 1);
        else
            combine(p, 1);
    }
    else
        if(k == p->count)  /* 刪除數據為節點中的最后一筆數據 */
    	{
            if(p->link[k-1]->count > MIN)
                getleft(p, k);
        	else
                combine(p, k);
    	}
        else  /* 刪除數據為節點中其它位置的數據 */
            if(p->link[k-1]->count > MIN)
                getleft(p, k);
        	else
                if(p->link[k+1]->count > MIN)
                    getright(p, k+1);
        		else
                    combine(p, k);
}

/* 向左兄弟節點借數據時，做數據右移的動作 */
void getleft(Node_type *p, int k)
{
    int c;
    Node_type *t;
    t = p->link[k];
    for(c = t->count; c > 0; c--)
    {
        t->id[c+1] = t->id[c];
        strcpy(t->name[c+1], t->name[c]);
        t->score[c+1] = t->score[c];
        t->link[c+1] = t->link[c];
    }
    t->link[1] = t->link[0];
    t->count++;
    t->id[1] = p->id[k];
    strcpy(t->name[1], p->name[k]);
    t->score[1] = p->score[k];
    t = p->link[k-1];
    p->id[k] = t->id[t->count];
    strcpy(p->name[k], t->name[t->count]);
    p->score[k] = t->score[t->count];
    p->link[k]->link[0] = t->link[t->count];
    t->count--;
}

/* 向右兄弟節點借數據時，做左移的動作 */
void getright(Node_type *p, int k)
{
    int c;
    Node_type *t;
    t = p->link[k-1];
    t->count++;
    t->id[t->count] = p->id[k];
    strcpy(t->name[t->count], p->name[k]);
    t->score[t->count] = p->score[k];
    t->link[t->count] = p->link[k]->link[0];
    t = p->link[k];
    p->id[k] = t->id[1];
    strcpy(p->name[k], t->name[1]);
    p->score[k] = t->score[1];
    t->link[0] = t->link[1];
    t->count--;
    for(c = 1; c <= t->count; c++)
    {
        t->id[c] = t->id[c+1];
        strcpy(t->name[c], t->name[c+1]);
        t->score[c] = t->score[c+1];
        t->link[c] = t->link[c+1];
    }
}

/* 將三個節點中的數據合并至一個節點中 */
void combine(Node_type *p, int k)
{
    int c;
    Node_type *l, *q;
    q = p->link[k];
    l = p->link[k-1];
    l->count++;
    l->id[l->count] = p->id[k];
    strcpy(l->name[l->count], p->name[k]);
    l->score[l->count] = p->score[k];
    l->link[l->count] = q->link[0];
    for(c = 1; c <= q->count; c++)
    {
        l->count++;
        l->id[l->count] = q->id[c];
        strcpy(l->name[l->count], q->name[c]);
        l->score[l->count] = q->score[c];
        l->link[l->count] = q->link[c];
    }
    for(c = k; c < p->count; c++)
    {
        p->id[c] = p->id[c+1];
        strcpy(p->name[c], p->name[c+1]);
        p->score[c] = p->score[c+1];
        p->link[c] = p->link[c+1];
    }
    p->count--;
    free(q);
}

/* 數據輸出函數 */
void list_f(void)
{
    puts("\n  ---- LIST ----");
    puts("  *******************************");
    puts("      ID     NAME       SCORE");
    puts("   =============================");
    show(root);
    puts("  *******************************");
}

/* 以遞歸方式輸出節點數據，輸出數據采中序法，nd為欲輸出數據的節點 */
void show(Node_type *nd)
{
    if(nd != NULL)
    {
        if(nd->count > 0)
    	{
            if(nd->count == 1)
    		{
                show(nd->link[0]);
                printf("      %-6d %-10s %4d\n",
                    nd->id[1], nd->name[1], nd->score[1]);
                show(nd->link[1]);
    		}
        	else
            if(nd->count == 2)
    		{
                show(nd->link[0]);
                printf("      %-6d %-10s %4d\n",
                        nd->id[1], nd->name[1], nd->score[1]);
                show(nd->link[1]);
                printf("      %-6d %-10s %4d\n",
                        nd->id[2], nd->name[2], nd->score[2]);
                show(nd->link[2]);
    		}
    	}
    }
}

/* 查詢某一特定數據 */
void query_f(void)
{
    int query_id, position;
    Node_type *quenode;
    puts("\n  ---- QUERY ----");
    printf("  Please enter ID number: ");
    scanf("%d", &query_id);
    quenode = search(query_id, root, &position);
    if(quenode != NULL)
    {
        printf("  ID number: %d\n", quenode->id[position]);
        printf("  Name: %s\n", quenode->name[position]);
        printf("  Score: %d\n", quenode->score[position]);
    }
    else
        puts("  ID number not found!!");
}

/* 將B-tree中的數據儲存到文件中 */
void save(Node_type *node, FILE *outfile)
{
    if(node->count != 0)
    {
        if(node->count == 1)
    	{
            save(node->link[0], outfile);
            fprintf(outfile, "  %6d %10s %4d\n", node->id[1], node->name[1],
                  node->score[1]);
            save(node->link[1], outfile);
    	}
        else
        if(node->count == 2)
    	{
            save(node->link[0], outfile);
            fprintf(outfile, "  %6d %10s %4d\n", node->id[1], node->name[1],
                node->score[1]);
            save(node->link[1], outfile);
            fprintf(outfile, "  %6d %10s %4d\n", node->id[2], node->name[2],
                node->score[2]);
            save(node->link[2], outfile);
    	}
    }
}

/* 結束本系統 */
void quit(void)
{
    printf("\n  Thanks for using, bye bye!!");
    exit(0);
}

/* 查找某一鍵值所在節點，target為查找鍵值，傳回值為target所在節點指針，若沒有找
   到則傳回NULL */
Node_type *search(int target, Node_type *node, int *targetpos)
{
    if(node == NULL)
        return NULL;
    else
        if(searchnode(target, node, targetpos))
            return node;
        else
            return search(target, node->link[*targetpos], targetpos);
}

/* 查找某一鍵值在節點中的位置，target為查找鍵值，k記錄鍵值所在位置，傳回0表
   示查找失敗，傳回1表示查找成功 */

int searchnode(int target, Node_type *p, int *k)
{
    if(target < p->id[1])
    {
        *k = 0;
        return 0;
    }
    else
    {
        *k = p->count;
        while((target < p->id[*k]) && *k > 1)
            (*k)--;
        if(target == p->id[*k])
            return 1;
        else
            return 0;
    }
}