/*
    ADT BTree{
	   數據對象：D={n,A0,K1,A1,K2,A2,…,Kn,An}
	   數據關系：R1={}
	   void KeyTypeCopy(KeyType &bak,KeyType k)
	     初始條件：k存在
		 操作結果：將 k 中的全部值復制到 bak 中
	   int Search(BTree p, KeyType K)
	     初始條件：樹結點 p 存在
		 操作結果：查找 k 在p中的位置，返回在p中的位置
	   Result SearchBTree(BTree T, KeyType K)
	     初始條件：T存在
		 操作結果：查找k在T中的位置，并以Result的結構體返回
	   void Insert(BTree &q, int i, KeyType x, BTree ap)
	     初始條件：q存在
		 操作結果：在m階B-樹q上結點ap的key[i]與key[i+1]之間插入關鍵字k
		           若引起結點過大，則沿雙親進行必要的結點分裂調整，使q還是m階B-樹
	   Status InsertBTree(BTree &T, KeyType K)
	     初始條件：k存在
		 操作結果：將k插入T樹中
	   int position(BTree T)
	     初始條件：T存在
		 操作結果：返回T在雙親的第幾個結點
	   Status fix(BTree &root,BTree p)
	     初始條件：root存在
		 操作結果：刪除結點的時候調整樹結點的個數，使樹還是B-樹
	   Status combine(BTree &root,BTree &p)
	     初始條件：root 存在
		 操作結果：當刪除結點的時候不能向兄弟結點借的時候就合并，將雙親和兄弟結點合并成一個結點
	   void exchange(BTree &T,int i)
	     初始條件：T存在
		 操作結果：將T結點的第i個結點和右下最左結點交換，并將T的第i個結點刪除
	   Status DeleteBTree(BTree &T,KeyType k)
	     初始條件：T存在
		 操作結果：將T中的k結點刪除，如果存在就刪除，否則就直接返回
	   void display(BTree T,int k)
	     操作結果：將B-樹以層次的形式顯示
	}ADT BTree
*/
#ifndef BITREE_H
#define BITREE_H

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
#include<dos.h>
#include<time.h>
#include <iostream>
#include <string>
using namespace std;

//******** 定義一些全局變量 *********
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define m 3 //表示是 2-3 樹

//************ 借閱者的存儲結構體 ************
typedef struct User{
	unsigned int number; //借書證號碼
	int year;
	int month;
	int day;  //借書時間
	int dyear;  //截至日期的年
	int dmonth;   //截至日期的月
	int dday;   //截至日期的日
	struct User *next;  //下一個借閱者
}User; //定義用戶的的信息
//********** 書的存儲結構體 *******************
typedef struct Book{
	unsigned int key;     //圖書的書號
    char bname[20]; // 書名
    char writter[20]; // 著者 
    unsigned int left;     // 現存量
    unsigned int total;     // 總存量
	User *user;  //借閱該書的人
}Book;  //定義書的信息
//********** B- 樹的存儲結構 *******************
typedef Book KeyType;
typedef struct BTNode{
	int keynum; //結點中關鍵字個數，即結點的大小
	struct BTNode *parent; //指向雙親結點
	KeyType key[m + 1];  //關鍵字向量， 0 號單元沒有用
	struct BTNode *ptr[m + 1]; //子樹指針向量
}BTNode,*BTree;
//************ 查找結果的存儲結構體 ***********
typedef struct{
	BTNode *pt;  //指向找到的結點
 	int i;  //1……m，在結點中的關鍵字序號
	int tag; //B- 樹的查找結果類型
}Result;
//************* 函數聲明部分 *******************
//輸入書的具體信息
void InBookMess(KeyType &book);
//輸入書的關鍵字
void InBookKey(KeyType &book);
//顯示書的具體信息,如果書存在就顯示
void ShowBookMess(Book book);
//顯示一個結點中所包含的全部信息,顯示單個結點
string ShowBTNode(BTree p);
//顯示,以層次的方法顯示樹的結點
string display(BTree T,int k);
//復制關鍵字的信息
void KeyTypeCopy(KeyType &bak,KeyType k);
//查找在某個結點中的位置
int Search(BTree p, KeyType K);
//查找
Result SearchBTree(BTree T, KeyType K);
//插入
void Insert(BTree &q, int i, KeyType x, BTree ap);
//分裂結點
void split(BTree &q, int s, BTree &ap);
//生成一個新的結點
void NewRoot(BTree &T, BTree p, KeyType x, BTree ap);
//將書的信息插入到 B- 樹中
Status InsertBTree(BTree &T, KeyType K);
//刪除結點,通過關鍵字 k 刪除
Status DeleteBTree(BTree &T,KeyType k);
//刪除樹結點
Status DeleteBT(BTree &T,KeyType k);
//與右最左結點交換
void exchange(BTree &T,int i);
//用戶借閱
Status BorrowBook(BTree T,KeyType k);
//注銷對借閱者的登記，改變該書的顯存量
Status ReturnBook(BTree T,KeyType k);
//日記 log 的寫出
void writeLog(string mess);
//void writeLog(string mess,int num);
//將整型數據轉換成字符串
string itos(int i);
//將字符數組轉換成字符串
string ctos(char i[]);
//查找作者的全部書籍
Status searchAuthorB(BTree T);

#endif