//////////////////////////////////////////////////////////////////////////
//姓名: 林文清
//學號: 0610374
//專業: 計算機科學與技術
//課程: 數據結構
//////////////////////////////////////////////////////////////////////////

enum Error_code{success,overflow,duplicate_error,not_present};  //結果返回類型
static int one_sqare=27;    //設置顯示圖形每個方格的邊的長度
//////////////////////////////////////////////////////////////////////////
//B-Tree的結點數據結構B_node的聲明
//////////////////////////////////////////////////////////////////////////
template <class Record>
class B_node{
public:
	int count;      //記錄存入的關鍵字數
	Record* data;   //關鍵字指針
	B_node<Record>** branch;   //每個B-Tree節點的枝節邊指針
	//構造函數
	B_node(int num){            //num為階數
		data=new Record[num-1];
		branch=new B_node<Record>* [num];
		count=0;     //初始關鍵數為0
	}
	//析構函數
	~B_node(){
		delete []data;
		delete []branch;
	}
};
//////////////////////////////////////////////////////////////////////////
//B-tree類的聲明
//////////////////////////////////////////////////////////////////////////
template <class Record>
class B_tree
{
	int order;    //階數
	B_node<Record> *root;  //根節點
	bool whether_created;  //用于判斷是否已經構造了B-Tree
public:
	//無參構造函數
	B_tree(){
		root=NULL;
		whether_created=false;
	}
	//含參構造函數
	B_tree(int num){
		order=num;
		whether_created=true;
		root=NULL;
	}
	Error_code set_order(int);           //設置階數
	Error_code insert(Record);           //插入關鍵字
	Error_code search_tree(Record&);     //在樹中查找關鍵字
	Error_code search_node(B_node<Record> *, const Record &, int &);         //在結點中查找關鍵字
	Error_code push_down(B_node<Record>*,Record,Record&,B_node<Record>* &);  //在結點中插入關鍵字
	Error_code recursive_search_tree(B_node<Record> *, Record &);            //遞歸查找關鍵字
	void push_in(B_node<Record> *,const Record &,B_node<Record> *,int );     //往上一個結點中插入關鍵字
    void split_node(B_node<Record> *,const Record &,B_node<Record> *,int,B_node<Record> * &,Record &); //分裂結點
    Error_code remove(const Record &);                               //刪除關鍵字
	Error_code recursive_remove(B_node<Record> *, const Record &);   //遞歸刪除結點
	void remove_data(B_node<Record> *, int);                         //直接刪除關鍵字
	void copy_in_predecessor(B_node<Record> *,int);                  //從上一個結點摘一個結點過來
	void restore(B_node<Record> *, int);                             //重新存儲結點
	void move_left(B_node<Record> *,int);                            //向左移動結點
	void move_right(B_node<Record> *,int);                           //向右移動結點
	void combine(B_node<Record> *,int);                              //合并結點
	void print_B_tree(B_node<Record>*,CDC*,CPoint,int);              //遞歸打印結點
	void display(CDC*,CPoint);                                       //打印結點
};
template<class Record>
Error_code B_tree<Record>::set_order(int num)
{
	if (!whether_created)
	{
		order=num;
		whether_created=true;
		return success;
	}
	return duplicate_error;
}
template<class Record>
Error_code B_tree<Record>::search_node(B_node<Record> *current, const Record &target, int &position)
{
	position = 0;
	while (position < current->count &&target > current->data[position])
		position++;
	if (position<current->count&&target==current->data[position])
		return success;
	else
		return not_present;
}
template<class Record>
Error_code B_tree<Record> ::recursive_search_tree(B_node<Record> *current, Record &target)
{
	Error_code result = not_present;
	int position;
	if (current != NULL) {
		result = search_node(current, target,position);    //在結點中查找
		if (result == not_present) //如果要插入的關鍵字不在B-Tree中
			result = recursive_search_tree (current->branch[position], target);
		else                        //如果要插入的關鍵字在B-Tree中
			target = current->data[position];
	}
	return result;
}
template<class Record>
Error_code B_tree<Record> ::search_tree(Record &target)
{
	return recursive_search_tree(root, target);
}
template<class Record>
void B_tree<Record>::push_in( B_node<Record> *current,const Record &entry,B_node<Record> *right_branch,int position)
{
	//采用類似插入排序的方式插入關鍵字
	for (int i = current->count; i > position; i--) {
		current->data[i] = current->data[i-1];
		current->branch[i+1] = current->branch[i];
	}
	current->data[position] = entry;
	current->branch[position+1] = right_branch;
	current->count ++;
}
template<class Record>
void B_tree<Record> :: split_node(B_node<Record> *current,const Record &extra_entry, B_node<Record> *extra_branch,int position,B_node<Record> * &right_half, Record &median)
{
	right_half = new B_node<Record>(order);
	int mid = order/2;            //從中間位置開始分裂
	if (position <= mid) {        //如果要插入的關鍵字的位置小于等于中間位置
		for (int i = mid; i < order - 1; i++) {
			right_half->data[i - mid] = current->data[i];
			right_half->branch[i + 1 - mid] =current->branch[i +1];
		}
		current->count = mid;
		right_half->count = order - 1 - mid;
		push_in(current, extra_entry,extra_branch, position);
	}
	else {                       //如果要插入的關鍵字的位置小于中間位置
		mid++;
		for (int i = mid; i < order - 1; i++) {
			right_half->data[i - mid] = current->data[i];
			right_half->branch[i + 1 - mid] =current->branch[i + 1];
		}
		current->count = mid;
		right_half->count = order - 1 - mid;
		push_in(right_half, extra_entry, extra_branch, position -mid);
	}
	median = current->data[current->count - 1];
	right_half->branch[0] = current->branch[current->count];
	current->count--;
}
template <class Record,int order>
Error_code B_tree<Record>::push_down(B_node<Record>* current,Record new_entry,Record& median,B_node<Record>* &right_branch)
{
	Error_code result;
	int position;
	if(current==NULL)   //如果指針為空
	{
		median=new_entry;
		right_branch=NULL;
		result=overflow;
	}
	else{         //指針不為空
		if(search_node(current,new_entry,position)==success)    //如果要插入的關鍵字在B-Tree中
			result=duplicate_error;
		else{                                                   //如果要插入的關鍵字不在B-Tree中
			Record extra_entry;
			B_node<Record> *extra_branch;
			result=push_down(current->branch[position],new_entry,extra_entry,extra_branch);
			if(result==overflow){   //如果溢出
				if(current->count<(order-1)){    //如果插入當前結點不會溢出
					result=success;
					push_in(current,extra_entry,extra_branch,position);   //直接插入該結點
				}
				else   //如果插入當前結點會溢出,則分裂結點
					split_node(current,extra_entry,extra_branch,position,right_branch,median);
			}
		}
	}
	return result;
}
template <class Record,int order>
Error_code B_tree<Record>::insert(Record new_entry)
{
	Record median;
	B_node<Record> *right_branch,*new_root;
	Error_code result=push_down(root,new_entry,median,right_branch);
	if(result==overflow)   //如果插入溢出到根結點,則根結點分裂
	{
		new_root=new B_node<Record>(order);
		new_root->count=1;
		new_root->data[0]=median;