#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#include "btree.h"


/*

bs_開頭的都是實(shí)現(xiàn)B-樹的接口函數(shù)

*/


static int  bs_search_key(BSTREE_NODE *p, BSTREE_KEY k);
static int  bs_split_node(BSTREE_NODE *&q, BSTREE_NODE *&ap);
static int  bs_new_root(BSTREE_NODE *&t, BSTREE_NODE *p, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap);
static void bs_remove(BSTREE_NODE *p, int i);
static void bs_successor(BSTREE_NODE *p, int i);
static void bs_move_right(BSTREE_NODE *p, int i) ;
static void bs_move_left(BSTREE_NODE *p, int i) ;
static void bs_combine(BSTREE_NODE *p, int i) ;
static void bs_restore(BSTREE_NODE *p,int i);
static void bs_insert_node(BSTREE_NODE *&q, int i, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap) ;
static int  bs_search_node(BSTREE_KEY k, BSTREE_NODE *p, int &i);
static int  bs_delete_record(BSTREE_KEY k, BSTREE_NODE * p);
static void bs_display_tree(BSTREE_NODE *t);
void        bs_test_tree(void) ;



/*

在p-key[1..keynum]中找i,使得p->key[i]<= k < p->key[i + 1]

*/
static int bs_search_key(BSTREE_NODE *p, BSTREE_KEY k) {
	int i;
	for(i = 0; i < p->keynum && p->key[i + 1] <= k; i++);
	return i;
}



/*

在M階t樹上查找關(guān)鍵字k,返回結(jié)果BSTREE_RESULT(ptr, i, tag),查找成功
tag = 1,ptr指向找到節(jié)點(diǎn)i個(gè)關(guān)鍵字等于k;否則特征值tag=0,等于k的值應(yīng)
當(dāng)插入在指針ptr所指結(jié)點(diǎn)中第i和第i+1個(gè)關(guān)鍵字之間

*/
BSTREE_RESULT bs_search_tree(BSTREE_NODE *t, BSTREE_KEY k) {

	BSTREE_NODE *p = t, *q = NULL;
	int found = 0, i = 0;
	BSTREE_RESULT rs;

	while(p != NULL && !found) {

		i = bs_search_key(p, k);

		if (i > 0 && p->key[i] == k) {
			found = 1;
		} else {
			q = p;
			p = p->ptr[i];
		}
	}

	rs.i = i;
	if (found == 1) { 
		rs.ptr = p; rs.tag = 1; 
	} else { 
		rs.ptr = q; rs.tag = 0;
	}
	return rs;

}



/*

將x和ap與rec分別插入到q->key[i + 1]和q->ptr[i + 1]中q->rec[i + 1]

*/
static void bs_insert_node(BSTREE_NODE *&q, int i, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap) {
	int j;

	for(j = q->keynum; j > i; j--) {
		q->key[j + 1] = q->key[j];
		q->rec[j + 1] = q->rec[j];
		q->ptr[j + 1] = q->ptr[j];
	}
	q->rec[i + 1] = r;
	q->key[i + 1] = x;
	q->ptr[i + 1] = ap;

	if (ap != NULL) 
		ap->parent = q;
	q->keynum++;

}



/*

將節(jié)點(diǎn)q分裂成兩個(gè)節(jié)點(diǎn)，前一半保留，后一半移入新生節(jié)點(diǎn)ap

*/
static int bs_split_node(BSTREE_NODE *&q, BSTREE_NODE *&ap) {

	int s = (DEF_BSTREE_STEPS + 1) / 2;
	int i;
	
	ap = (BSTREE_NODE *)calloc(1, sizeof(BSTREE_NODE));
	if (ap == NULL) return -1;

	ap->ptr[0] = q->ptr[s];

	for( i = s + 1; i <= DEF_BSTREE_STEPS; i++) {

		ap->key[i - s] = q->key[i];
		ap->rec[i - s] = q->rec[i];
		ap->ptr[i - s] = q->ptr[i];
		
		if (ap->ptr[i - s] != NULL) {
			ap->ptr[i - s]->parent = ap;
		}
	}
	ap->keynum = q->keynum - s;
	ap->parent = q->parent;

	for(i = 0; i <= q->keynum - s; i++) {
		if (ap->ptr[i] != NULL) {
			ap->ptr[i]->parent = ap;
		}
	}
	q->keynum = s - 1;
	return 0;
}



/*

生成含信息(t,x,r,ap,p)的新的根節(jié)點(diǎn)*t,原t和ap為子樹指針

*/
static int bs_new_root(BSTREE_NODE *&t, BSTREE_NODE *p, BSTREE_KEY x, BSTREE_RECORD *r, BSTREE_NODE *ap) {

	t = (BSTREE_NODE *)calloc(1, sizeof(BSTREE_NODE));
	if (t == NULL) return -1;	
	t->keynum = 1;
	t->ptr[0] = p;
	t->key[1] = x;
	t->rec[1] = r;
	t->ptr[1] = ap;

	if (p  != NULL) p->parent  = t;
	if (ap != NULL) ap->parent = t;
	t->parent = NULL;	
	return 0;

}




/*

在m階B-樹T上結(jié)點(diǎn)*q的key[i]與key[i+1]之間插入關(guān)鍵字K的指針r。若引起
結(jié)點(diǎn)過大,則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整,使T仍是m階B-樹。

*/
int bs_insert_tree(BSTREE_NODE *&t, BSTREE_KEY k, BSTREE_RECORD *r, BSTREE_NODE *q, int i) {

	BSTREE_KEY x;
	BSTREE_NODE *ap;
	BSTREE_RECORD *e;
	int finish, nr, s, status, max;
	
	max = DEF_BSTREE_STEPS - 1;
	if (q == NULL) {
		status = bs_new_root(t, NULL, k, r, NULL);
		return status;
	} else {
		x  = k;	e  = r;	ap = NULL;
		finish = nr = 0; 
		while(nr == 0 && finish == 0) {
			bs_insert_node(q, i, x, e, ap);
			if(q->keynum <= max) {
				finish = 1;
				break;
			} else {
				s = (DEF_BSTREE_STEPS + 1)/2;
				status = bs_split_node(q, ap);
				if (status < 0) { //內(nèi)存申請(qǐng)失敗
					return status;
				}
				x = q->key[s];
				e = q->rec[s];
				if(q->parent) {
					q = q->parent;
					i = bs_search_key(q, x);
				} else {
					nr = 1;
					break;
				}
			}
		}

		if(nr == 1) {
			status = bs_new_root(t, q, x, e, ap);
			return status;
		}
	}
	return 0;
}




/*

刪除節(jié)點(diǎn)P第i個(gè)元素

*/
static void bs_remove(BSTREE_NODE *p, int i) {
	int j;

	for(j = i + 1; j <= p->keynum; j++) {
		p->key[j - 1] = p->key[j];
		p->rec[j - 1] = p->rec[j];
		p->ptr[j - 1] = p->ptr[j];		
	}
	p->keynum--;
}


/*

查找被刪除關(guān)鍵字p-key[i](在非葉子節(jié)點(diǎn)中)的替代葉子節(jié)點(diǎn)

*/
static void bs_successor(BSTREE_NODE *p, int i) {
	BSTREE_NODE *q;
	for(q = p->ptr[i]; q->ptr[0] != NULL; q = q->ptr[0]);
	p->key[i] = q->key[1];
	p->rec[i] = q->rec[1];
}


/*

把一個(gè)關(guān)鍵字移動(dòng)到右兄弟中

*/
static void bs_move_right(BSTREE_NODE *p, int i) {
	int c;

	BSTREE_NODE *t = p->ptr[i];

	for(c = t->keynum; c > 0; c--) {
		t->key[c + 1] = t->key[c];
		t->ptr[c + 1] = t->ptr[c];
		t->rec[c + 1] = t->rec[c];
	}

	t->ptr[1] = t->ptr[0];
	t->key[1] = p->key[i];
	t->rec[1] = p->rec[i];
	t->keynum++;

	t = p->ptr[i-1];
	p->key[i] = t->key[t->keynum];
	p->rec[i] = t->rec[t->keynum];
	p->ptr[i]->ptr[0] = t->ptr[t->keynum];
	t->keynum--;

}


/*

把關(guān)鍵字移動(dòng)到左兄弟中

*/
static void bs_move_left(BSTREE_NODE *p, int i) {   
	
	int c;
	BSTREE_NODE *t;
	
	t = p->ptr[i-1];
	t->key[t->keynum] = p->key[i];
	t->rec[t->keynum] = p->rec[i];
	t->ptr[t->keynum] = p->ptr[i]->ptr[0];
	t->keynum++;

	t = p->ptr[i];
	p->key[i] = t->key[1];
	p->rec[i] = t->rec[1];
	p->ptr[0] = t->ptr[1];
	t->keynum--;

	for(c = 1;c <= t->keynum; c++) {

		t->key[c] = t->key[c + 1];
		t->rec[c] = t->rec[c + 1];
		t->ptr[c] = t->ptr[c + 1];

	}
}


/*

將三個(gè)節(jié)點(diǎn)合并到一個(gè)節(jié)點(diǎn)中

*/
static void bs_combine(BSTREE_NODE *p, int i) {   
	int c;

	BSTREE_NODE *q = p->ptr[i];
	BSTREE_NODE *l = p->ptr[i-1];

	l->keynum++;

	l->key[l->keynum] = p->key[i];
	l->rec[l->keynum] = p->rec[i];
	l->ptr[l->keynum] = q->ptr[0];
	
	for(c = 1;c <= q->keynum; c++) {
		l->keynum++;
		l->key[l->keynum] = q->key[c];
		l->rec[l->keynum] = q->rec[c];
		l->ptr[l->keynum] = q->ptr[c];
		
	}
	
	for(c = i; c < p->keynum; c++) {
		p->key[c] = p->key[c + 1];
		p->rec[c] = p->rec[c + 1];
		p->ptr[c] = p->ptr[c + 1];
	}
	p->keynum--;
	
	free(q);
}


/*

關(guān)鍵字刪除后，調(diào)整B-樹，找到一個(gè)關(guān)鍵字將其插入到p->ptr[i]中

*/
static void bs_restore(BSTREE_NODE *p,int i) {

	int min = (DEF_BSTREE_STEPS - 1) / 2;
	
	if(i == 0) {
		if (p->ptr[1]->keynum > min) {
			bs_move_left(p, 1);
		} else {
			bs_combine(p, 1);
		}
	} else if (i == p->keynum) {
		if(p->ptr[i - 1]->keynum > min) {
			bs_move_right(p, i);
		} else {
			bs_combine(p, i);
		}
	} else if (p->ptr[i - 1]->keynum > min) {
		bs_move_right(p, i);	
	} else if (p->ptr[i + 1]->keynum > min) {
		bs_move_left(p, i + 1);
	} else {
		bs_combine(p, i);
	}
}


/*

在節(jié)點(diǎn)p中找關(guān)鍵字為看的位置i，成功返回1,否則返回0

*/
static int bs_search_node(BSTREE_KEY k, BSTREE_NODE *p, int &i) {   

	if(k < p->key[1])	{
		i = 0; 
		return 0;
	} else{
		i = p->keynum;
		while(k < p->key[i] && i> 1)
			i--;
		return (k == p->key[i]);
	}
}


/*

查找并刪除關(guān)鍵字k

*/
static int bs_delete_record(BSTREE_KEY k, BSTREE_NODE * p) {  

	int i;
	int found;
	int min = (DEF_BSTREE_STEPS - 1) / 2;
	
	if(p == NULL)
		return 0;
	else {
		if (( found = bs_search_node(k,p,i)) == 1) {
			if(p->ptr[i-1] != NULL)	{
				bs_successor(p, i);
				bs_delete_record(p->key[i], p->ptr[i]);
			} else 
				bs_remove(p, i);
		} else 
			found = bs_delete_record(k, p->ptr[i]);
		
		if(p->ptr[i] != NULL)
			if(p->ptr[i]->keynum < min)
				bs_restore(p, i);
		return found;
	}
}


/*

從B-樹root中刪除關(guān)鍵k,若在一個(gè)節(jié)點(diǎn)中刪除指定關(guān)鍵字，不再有其他關(guān)鍵字，則刪除該節(jié)點(diǎn)
0: 表示沒有該關(guān)鍵字
1: 表示刪除成功,并且刪除了該節(jié)點(diǎn)
2: 成功刪除該關(guān)鍵字

*/
int bs_delete_tree(BSTREE_NODE * &root, BSTREE_KEY k)  {
	
	BSTREE_NODE *p;
	if(bs_delete_record(k, root) == 0)
		return 0;
	else if (root->keynum == 0) {
		p = root;
		root = root->ptr[0];
		free(p);
		return 1;
	}
	return 2;
}



/*++++++++++++++++++測(cè)試代碼+++++++++++++++++++++++++++++++++++++++/
/*

顯示B-樹的數(shù)據(jù)

*/
void bs_display_tree(BSTREE_NODE *t) {
	int i;

	if (t != NULL) {

		printf("[");
		for(i = 1; i < t->keynum; i++)
			printf(" %d ", t->key[i]);
		printf(" %d ", t->key[i]);
		printf("]");

		if (t->keynum > 0) {
			if (t->ptr[0] != NULL) printf("(");

			for( i = 0; i < t->keynum; i++) {
				bs_display_tree(t->ptr[i]);
				if (t->ptr[i + 1] != NULL)
					printf(",");
			}
			bs_display_tree(t->ptr[t->keynum]);
			if (t->ptr[0] != 0)
				printf(")");
		}
	}
}

void bs_test_tree(void) {

	BSTREE_NODE *t = NULL;
	BSTREE_RESULT s;
	int j, n = 10;
	typedef struct MREC {
		int i;
		char a[20];
		SOCKET s;
	} MREC;

	BSTREE_KEY a[] = {4,9,0,1,8,6,3,5,2,7}, k;
	MREC rec[10];
	rec[0].i = 1000;strcpy(rec[0].a, "ABCDEF"); rec[1].i = 2; strcpy(rec[1].a, "GH");rec[2].i = 3; rec[3].i = 4; rec[4].i = 5;rec[5].i = 6;rec[6].i = 7;rec[7].i=8;rec[8].i=9;rec[9].i = 10;
	printf("\n");
	printf("創(chuàng)建一棵%d階B-樹:\n", DEF_BSTREE_STEPS);

	for(j = 0; j < n; j++) {
		s = bs_search_tree(t, a[j]);
		if (s.tag == 0) 
			bs_insert_tree(t, a[j], (BSTREE_RECORD *)&rec[j], s.ptr, s.i);
		printf("  第%2d步,插入%d: ", j + 1, a[j]);
		bs_display_tree(t);
		printf("\n");
	}
	printf("查詢操作\n");
	k = 9;
	s = bs_search_tree(t, k);
	if (s.tag == 0) {
		printf("沒有找到key=%d\n", k);
	} else {
		printf("找到 key = %d, rec.i=%d,rec.a=%s\n", k, ((MREC *)s.ptr->rec[s.i])->i,((MREC *)s.ptr->rec[s.i])->a);
	}
	printf("刪除操作:\n");
	k = 8;
	bs_delete_tree(t, k);
	printf(" 刪除 %d:", k);

	bs_display_tree(t);
	printf("\n");
	k = 1;
	bs_delete_tree(t, k);
	printf("  刪除%d: ", k);
	bs_display_tree(t);
	printf("\n\n");

}

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/