#include "btree.h"


//復制結點,將某個結點的值復制到另外一個值上
void KeyTypeCopy(KeyType &bak,KeyType k){
	bak.key = k.key;
	strcpy(bak.bname,k.bname);
	bak.left = k.left;
	bak.total = k.total;
	strcpy(bak.writter,k.writter);
	bak.user = k.user;
}

//在一個結點中查找元素,返回結點的位置
int Search(BTree p, KeyType K) {	
	if(!p)
		return -1;
	int i=0;
    for(i = 0; i < p->keynum && p->key[i+1].key <= K.key; i++);
    return i;
}

// 在m階B樹T上查找關鍵字K，返回結果(pt,i,tag)
Result SearchBTree(BTree T, KeyType K){ 
   BTree p, q;
   int found, i;
   Result R;
   //初始化變量
   p = T; 
   q = NULL; 
   found = FALSE; 
   i = 0; 
   // 初始化，p指向待查結點，q指向p的雙親
   while (p && !found) {
      i = Search(p, K); 
      // 找到待查關鍵字                  
      if (i > 0 && p->key[i].key == K.key) 
		  found = TRUE;    
      else { 
		  q = p;  
		  p = p->ptr[i]; //在另一個分支上查找
	  }
   }
   if (found) {  // 查找成功
     R.pt = p; 
	 R.i = i;  
	 R.tag = 1;  
   } 
   else {      // 查找不成功
     R.pt = q;  
	 R.i = i; 
	 R.tag = 0; 
   }
   // 返回結果信息: K的位置(或插入位置)
   return R;              
}

//插入一條記錄
void Insert(BTree &q, int i, KeyType x, BTree ap) {
	int n = q->keynum;	
	for (int j = n; j > i; j--) { //騰出空間		
		KeyTypeCopy(q->key[j + 1],q->key[j]); //復制結點值
		q->ptr[j + 1] = q->ptr[j];
	}
	KeyTypeCopy(q->key[i + 1],x);	
	q->ptr[i + 1] = ap;
	if (ap) 
		ap->parent = q;  
	q->keynum++;
}

//分離結點
void split(BTree &q, int s, BTree &ap) {
  int i,j,n = q->keynum;
  ap = (BTree)malloc(sizeof(BTNode));
  ap->ptr[0] = q->ptr[s];
  for (i = s + 1,j = 1; i <= n; i++,j++) {
	KeyTypeCopy(ap->key[j],q->key[i]);
    ap->ptr[j] = q->ptr[i];
  }
  ap->keynum = n - s;
  ap->parent = q->parent;
  for (i = 0; i <= n - s; i++)     
    if (ap->ptr[i]) 
		ap->ptr[i]->parent = ap;
  q->keynum = s-1;
}



//生成一個新的樹結點
void NewRoot(BTree &T, BTree p, KeyType x, BTree ap) {
  T = (BTree)malloc(sizeof(BTNode));

  T->keynum = 1;  //設置當前結點的元素個數
  T->ptr[0] = p;  //設置左邊結點的樹根
  T->ptr[1] = ap;  //設置右邊的樹根  
  KeyTypeCopy(T->key[1],x);  //將 x 元素的結點值復制到 T 的第一個元素中
  //當孩子不空的時候就設置當前結點為孩子的雙親
  if (p) 
	  p->parent= T;        
  if (ap) 
	  ap->parent = T;  
  T->parent = NULL;  //當前結點的雙親為空
}

//返回 false 表示在原有結點上增加數量，返回 true 表示創建了一個新的結點
Status InsertBTree(BTree &T, KeyType K) {
  // 在m階B樹T上結點*q的key[i]與key[i+1]之間插入關鍵字K。
  // 若引起結點過大，則沿雙親鏈進行必要的結點分裂調整，使T仍是m階B樹。
  BTree ap;
  Result rs;
  BTree q;
  int i;
  char addnum;
  int finished, needNewRoot, s;
  // T是空樹(參數q初值為NULL)
  KeyType x;
  //如果 T 結點為空就生成一個新的結點
  if (!T){                      
    NewRoot(T, NULL, K, NULL); 
  }
  else {
	//查找元素 k 在樹中的位置
    rs = SearchBTree(T,K);
	q = rs.pt; //查找到包含元素 k 的結點
    i = rs.i;  //元素 k 在樹中的位置
    if(rs.tag == 1){  //判斷該元素在樹中是否存在
		if(strcmp(q->key[i].bname,K.bname) != 0){
			printf("\n\t\t\t錄入失敗，原因:\n");
			printf(".\t\t\t書號沖突，請重新為該書編號!\n\n");
			printf("\t\t\t已經存在書號為 %d 的書為:\n",q->key[i].key);
			ShowBookMess(q->key[i]);
			writeLog("錄入書號 " +itos(K.key)+" 失敗!原因：錄入的書號和庫存量中的書號沖突!");
			return FALSE;
		}
	    printf("\n\t\t\t該書已經存在!\n\n");
		printf("\t\t\t是否增加其總量(y/n):");
		scanf("%s",&addnum);
		if(addnum == 'Y' || addnum == 'y'){
			q->key[i].total += K.total; //將總量增加
		    q->key[i].left += K.left;  //將剩余量增加
		    printf("\n\n\t\t\t增加總量后該書的信息如下\n");
			writeLog("增加書號 " +itos(K.key)+" 的總量!");
		}	
		else{
			printf("\n\t\t\t該書的信息如下:\n");
			writeLog("錄入書號 "+itos(K.key)+" 失敗!原因：庫存量中已經存在該書!");
		}
		ShowBookMess(q->key[i]);
	    return FALSE;
	}
    x = K;  
	ap = NULL; 
	finished = needNewRoot = FALSE;     
    while (!needNewRoot && !finished) {
      Insert(q, i, x, ap);  //插入結點
      if (q->keynum < m) 
		  finished = TRUE;  // 插入完成
      else {  // 分裂結點*q
        s = (m+1)/2;   
		split(q, s, ap);  
		x = q->key[s];
        if (q->parent) {  // 在雙親結點*q中查找x的插入位置
          q = q->parent; 
		  i = Search(q, x);  
        } 
		else 
			needNewRoot = TRUE;
      } // else
    } // while
    if (needNewRoot)        // 根結點已分裂為結點*q和*ap
      NewRoot(T, q, x, ap); // 生成新根結點*T,q和ap為子樹指針
  }
  writeLog("錄入 "+itos(K.key)+" 成功!");
  return OK;
}

//一個結點在雙親中的位置,返回其位置 i
int position(BTree T){
	if(!T){
		return 0;
	}
	int i = 0;
	if(T->parent){
		while(i <= T->parent->keynum){
			if(T == T->parent->ptr[i])
				return i; //返回當前的位置
			i++;
		}
	}
	return -1;
}

//調整樹的結構
Status fix(BTree &root,BTree p){
	int i = position(p);  //取得p 在雙親中的位置
	int mid = (m + 1)/2 - 1;  //要交換的臨界點
	BTree temp = NULL;
	int k;
	if(i > 0 && root->ptr[i - 1]->keynum > mid){  //當 i 大于零的時候就可以向左借
		temp = root->ptr[i - 1]; //比自己小的兄弟結點
		p->keynum++; //增加一個結點
		for(k = p->keynum;k > 1;k--){
			KeyTypeCopy(p->key[k],p->key[k - 1]); //將前面的結點后移一位
		}
		if(p->ptr[0]){
			for(k = p->keynum;k >= 1;k--){
				p->ptr[k] = p->ptr[k - 1]; //將要移動的結點的子結點向后移動
			}
		}
		KeyTypeCopy(p->key[1],root->key[i]); //將雙親的結點復制到根
		KeyTypeCopy(root->key[i],temp->key[temp->keynum]); //將小兄弟結點的最大的那個移動到雙親中
		if(temp->ptr[temp->keynum]){  //將兄弟結點的子結點也復制過來
			p->ptr[0] = temp->ptr[temp->keynum]; 
			temp->ptr[temp->keynum]->parent = p; //修改指向雙親的結點
			temp->ptr[temp->keynum] = NULL;
		}
		temp->keynum--;  //將左兄弟刪除一個結點
		return OK;
	}
	if(i < root->keynum && root->ptr[i + 1]->keynum > mid){ //當 i 小于最大數量的時候就可以向右借
		temp = root->ptr[i + 1];
		p->keynum++;  //增加結點的個數
		KeyTypeCopy(p->key[p->keynum],root->key[i + 1]); //將根結點的值復制過來
		KeyTypeCopy(root->key[i + 1],temp->key[1]);  //將右兄弟的結點復制過來
		for(k = 1;k < temp->keynum;k++){
			KeyTypeCopy(temp->key[k],temp->key[k + 1]); //將后面的結點向前移動一位
		}
		if(temp->ptr[0]){
			p->ptr[p->keynum] = temp->ptr[0];
			temp->ptr[0]->parent = p;  //修改指向雙親的結點
			for(k = 0;k < temp->keynum;k++){ //將子結點向前移動
				temp->ptr[k] = temp->ptr[k + 1];
			}
			temp->ptr[k + 1] = NULL;   //將刪除的結點的子結點置為空
		}
		temp->keynum--;  //將右兄弟刪除一個結點
		return OK;
	}
	return FALSE;
}

//合并結點
Status combine(BTree &root,BTree &p){
	int k,i = position(p);  //取得p 在雙親中的位置
	int mid = (m + 1)/2 - 1; //交換的條件
	BTree p2;
	if(i == 0){  //如果是第一個位置
		i = 1;
		p2 = root->ptr[i];
		p->keynum++; //增加一個結點
		KeyTypeCopy(p->key[p->keynum],root->key[i]); //將雙親的結點復制下來
		if(p2->ptr[0]){
			p->ptr[p->keynum] = p2->ptr[0]; //將兄弟的子結點也復制過來
			p2->ptr[0]->parent = p; //修改雙親
		}		
		for(k = i;k < root->keynum;k++){ //將雙親的結點向前移動一位
			KeyTypeCopy(root->key[k],root->key[k + 1]);
		}
		p->keynum++;
		p->key[p->keynum] = p2->key[1];
		if(p2->ptr[1]){
			p->ptr[p->keynum] = p2->ptr[1]; //將兄弟的子結點也復制過來
			p2->ptr[1]->parent = p;  //修改指向雙親的結點
		}		
		root->keynum--;
		free(p2);
		p2 = NULL;
		for(k = 1;k <= root->keynum;k++){
			root->ptr[k] = root->ptr[k + 1]; //將雙親結點子結點向前移動
		}
		root->ptr[k + 1] = NULL;
	}
	else if(i > 0){
		p2 = root->ptr[i - 1];		
		p2->keynum++;
		KeyTypeCopy(p2->key[p2->keynum],root->key[i]); //復制根結點的值到子結點中
		if(p->ptr[0]){
			p2->ptr[p2->keynum] = p->ptr[0];
			p->ptr[0]->parent = p2; //修改指向雙親的結點
		}				
		for(k = i;k < root->keynum;k++){
			KeyTypeCopy(root->key[k],root->key[k + 1]); //將結點前移
			root->ptr[k] = root->ptr[k + 1]; //將子結點前移			
		}
		root->ptr[k + 1] = NULL;
		root->keynum--;
		free(p); 
		p = p2;
	}
	return OK;
}

//與右最左結點交換
void exchange(BTree &T,int i){
	BTree p = T;
	User *user = NULL;
	if(p->ptr[i]){
		p = p->ptr[i];
		while(p->ptr[0]){
			p = p->ptr[0];		
		}
		while(T->key[i].user){
			user = T->key[i].user;  //指向要釋放的結點
			T->key[i].user = T->key[i].user->next; //指向下一個結點
			free(user);  //釋放借閱者的信息
		}
		KeyTypeCopy(T->key[i],p->key[1]);  //交換數據
	}	
	while(i < p->keynum){ //將該結點后面的數據后移
		KeyTypeCopy(p->key[i],p->key[i + 1]); //將后一個數據復制到前一個數據
		i++;
	}
	p->keynum--;  //刪除結點
	T = p;
	return;
}


//刪除樹結點
Status DeleteBTree(BTree &T,KeyType k){
	if(T == NULL){  //如果還沒有錄入過書,就直接返回
		printf("\t\t\t書庫為空!\n");
		writeLog("刪除書號為 " + itos(k.key) + " 失敗!原因：當前書的庫存量為空!");
		return FALSE;  
	}
	BTree p;    //查找到的指針
	Result rs;  //查找的結果
	int i = 0,sk = 0;
	rs = SearchBTree(T,k);  //查找
	//如果該 B- 樹中不包含該 k 就返回 false
	if(rs.tag == 0){ //如果查找失敗
		printf("\t\t\t刪除失敗!不存在你想要刪除的信息!\n");
		writeLog("刪除書號為 " + itos(k.key) +"失敗!原因：不存在你要刪除的書!");
		return FALSE;
	}
	p = rs.pt; //將查找到的結點賦值給 p
	i = rs.i;  //在結點中的位置	
	exchange(p,i); //將該結點的值和最右下左角的值交換
	if(p->keynum >= (m + 1)/2 - 1){  //這里的 1 可以用 (m+1)/2 - 1 來代替
		return OK;
	}
	//下面的表示 p->keynum == 0
	if(p == T){  //當只有根結點的時候
		free(T); //把根結點釋放掉
		T = NULL; //把刪除的結點賦值為空                      
		return OK;
	}	
	while(p){  //其他的情況
		if(p == T || p->keynum >= (m + 1)/2 - 1 || !p->parent) //如果 p 結點刪除后還有元素
			return OK;  //用于循環結束的條件
		else{  //否則就要向左右兩邊借元素
			if(fix(p->parent,p) == OK)  //判斷能不能借，可以借就直接返回
				return OK;
		}
		combine(p->parent, p);		
		p = p->parent;
		if((p == T || !p->parent) && p->keynum == 0){  //如果合并后父結點變成空
			T = p->ptr[0];
			free(p);
			p = T;
			T->parent = NULL;
			return OK;
		}		
	}
	return OK;
}