#include<iostream>
#include<conio.h>
#include<string.h>
#include<stdio.h>
#include<iomanip>
#include <windows.h>
#include <sstream>
#include<fstream>
#include<ctime>
#include <windows.h>
#define MAX 500
using namespace std;

struct Date{
	int ngay;
	int thang;
	int nam;
};
struct Sach{
	string TenSach;
	string MaSach;
	int TrangThai;
	int ViTri;
};
struct NodeSach{
	Sach sach;
	NodeSach *next;
};typedef NodeSach *PtrSach;
struct DauSach{
	string ISBN;
	string TenDauSach;
	int SoTrang;
	int SoSach;
	int SoLanMuon;
	int ViTri;
	string TacGia;
	int Nam;
	string TheLoai;
	PtrSach FirstSach;
};
struct DanhSachSach{
	int n = -1;
	DauSach nodes[MAX];
};
struct MuonTra{
	string TenSachMT;
	string MaSachMT;
	Date NgayMuon;
	Date NgayTra;
	int TrangThaiMT;
};
struct NodeMuonTra{
	MuonTra muontra;
	NodeMuonTra *next;
};typedef NodeMuonTra *PtrMuonTra;
struct DocGia{
	int MaDG;
	int SoSachM;
	string Ho,Ten,Phai;
	int TrangThai;
	PtrMuonTra FirstMuonTra;
};
struct MangTamDocGia{
	int n=0;
	DocGia nodes[MAX];
};
struct NodeDocGia{
	DocGia docgia;
	NodeDocGia *right;
	NodeDocGia *left;
};typedef NodeDocGia *PtrDocGia;

void gotoxy( int column, int line ){
  COORD coord;
  coord.X = column;
  coord.Y = line;
  SetConsoleCursorPosition(
    GetStdHandle( STD_OUTPUT_HANDLE ),
    coord
    );
}
int wherex( void )
{
    HANDLE hConsoleOutput;
    hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);
    CONSOLE_SCREEN_BUFFER_INFO screen_buffer_info;
    GetConsoleScreenBufferInfo(hConsoleOutput, &screen_buffer_info);
    return screen_buffer_info.dwCursorPosition.X;
}
int wherey( void )
{
    HANDLE hConsoleOutput;
    hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);
    CONSOLE_SCREEN_BUFFER_INFO screen_buffer_info;
    GetConsoleScreenBufferInfo(hConsoleOutput, &screen_buffer_info);
    return screen_buffer_info.dwCursorPosition.Y;
}
void SetColor(WORD color)
{
    HANDLE hConsoleOutput;
    hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);
    CONSOLE_SCREEN_BUFFER_INFO screen_buffer_info;
    GetConsoleScreenBufferInfo(hConsoleOutput, &screen_buffer_info);
    WORD wAttributes = screen_buffer_info.wAttributes;
    color &= 0x000f;
    wAttributes &= 0xfff0;
    wAttributes |= color;
    SetConsoleTextAttribute(hConsoleOutput, wAttributes);
}
void SetBGColor(WORD color)
{
    HANDLE hConsoleOutput;
    hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);

    CONSOLE_SCREEN_BUFFER_INFO screen_buffer_info;
    GetConsoleScreenBufferInfo(hConsoleOutput, &screen_buffer_info);

    WORD wAttributes = screen_buffer_info.wAttributes;
    color &= 0x000f;
    color <<= 4;
    wAttributes &= 0xff0f;
    wAttributes |= color;
    SetConsoleTextAttribute(hConsoleOutput, wAttributes);
}
void hidecursor()
{
	CONSOLE_CURSOR_INFO CursorInfo;
	CursorInfo.dwSize = 30;
	CursorInfo.bVisible = false;
	SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &CursorInfo);
}
void unhidecursor(){
	CONSOLE_CURSOR_INFO CursorInfo;
	CursorInfo.dwSize = 30;
	CursorInfo.bVisible = true;
	SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &CursorInfo);
}
void Inxy(int x, int y, string z, bool lightbar){
	gotoxy(x,y);
	if(lightbar){
		SetColor(0);
		SetBGColor(15);
	}
	cout<<z<<string(48-z.length(),' ');
	SetColor(15);
	SetBGColor(0);	
}
void Inxy(int x, int y, string z){
	gotoxy(x,y);
	cout<<z;	
}
void NhapSo(int &x){
	x =0;
	char c;
	int count=0;
	while(c=getch()){
		if(c>47 && c<58 && x<1){
			cout<<c;
			x= x*10 +(c -48);
			count++;
		}
		if(c == 8 && x>=0){
			if(count>0){
				count--;			
				x = x/10;
				gotoxy(wherex()-1,wherey());
				cout<<" ";
				gotoxy(wherex()-1,wherey());
			}
			else if(count==0){
				gotoxy(wherex(),wherey());
			}
		}
		if( c == 13 && x !=NULL){
			break;
		}
	}
	cout<<endl;
}
bool SoSanhChuoi(string s1, string s2){
	for(int i = 0; i < s1.length(); i++){
		s1[i] = toupper(s1[i]);
	}
	for(int i = 0; i < s2.length(); i++){
		s2[i] = toupper(s2[i]);
	}
	if(s1 == s2)
		return true;
	else 
		return false;		
}
string ToUpperCase(string s){
	string supper="";
	for(int i=0;i<s.length();i++){
		supper += toupper(s[i]);
	}
	return supper;
}
string CheckIsbn(DanhSachSach &dss, string s){	
	string temp;
	for(int i=0;i<dss.n;i++){
		if(SoSanhChuoi(dss.nodes[i].ISBN,s)==true){
			int j = atoi(s.substr(s.length()-2,s.length()).c_str());
			if(j<9){
				stringstream ss;
				j++;
				ss<<j;
				temp = s.erase(s.length()-1)+ss.str();
				s = temp;
			}
			else if(j>=9){
				stringstream ss;
				j++;
				ss<<j;
				temp = s.erase(s.length()-2)+ss.str();
				s = temp;
			}
		}
	}
	return s;   
}
string IsbnOfSach(PtrMuonTra &First, string tensach){//ham tra ve ma ISBN cua ten sach
	string isbn,temp;
	for(PtrMuonTra mt = First;mt!=NULL;mt=mt->next){
		if(SoSanhChuoi(mt->muontra.TenSachMT,tensach)==true && mt->muontra.TrangThaiMT ==0){
			temp = mt->muontra.MaSachMT;
			isbn = temp.substr(0,temp.length()-3);
			break;
		}
	}
	return isbn;
}
bool CheckDM(PtrDocGia p,string tensach,string isbn){
	for(PtrMuonTra mt = p->docgia.FirstMuonTra;mt!=NULL;mt=mt->next){
		if(SoSanhChuoi(IsbnOfSach(p->docgia.FirstMuonTra,tensach),isbn)==true && mt->muontra.TrangThaiMT == 0){
			return true;
			break;
		}
	}
	return false;	
}
string GetUpperCase(string s){
	string sboss = s.substr(0,1);
	int pos =0;
	for(int i=0;i<s.length();i++){
		if(s[i] == ' '){
			pos = i;
			sboss += s.substr(pos+1,1);	
		}
	}
	return sboss;
}
char *strlwr(char *str)
{
  unsigned char *p = (unsigned char *)str;
  while (*p){
     *p = tolower((unsigned char)*p);
      p++;
}
  return str;
}
// hàm xóa các khoang trang thua o dau và cuoi chuoi
void Xoa_Khoang_Trang_Thua_Dau_Va_Cuoi(string &str)
{
	// Buoc 1: Xóa het tat ca các kí tu khoang trang thua dau chuoi
	// cho vòng lap while lap cho den khi nào kiem tra kí tu dau tiên - vi trí 0 không phai là khoang trong thì dung
	while (str[0] == ' ')
	{
		str.erase(str.begin() + 0); // xóa kí t? t?i v? trí 0
	}


	// Bu?c 2: Xóa het tat ca các kí tu khoang trang thua o cuoi chuoi
	while (str[str.length() - 1] == ' ')
	{
		str.erase(str.begin() + str.length() - 1); // xóa kí t? t?i v? trí cu?i c?a chu?i
	}
}

// hàm xóa khoang trang thua o giua các tu
void Xoa_Khoang_Trang_Giua_Cac_Tu(string &str)
{
	for (int i = 0; i < str.length(); i++)
	{
		// neu 2 kí tu liên tiep nhau mà là khoang trong ==> xóa di 1 kí tu
		if (str[i] == ' ' && str[i + 1] == ' ')
		{
			str.erase(str.begin() + i);
			i--;
		}
	}
}

// hàm viet hoa kí tu dau cua moi tu
void In_Hoa_Ki_Tu_Dau_Moi_Tu(string &str)
{
	// Buoc 1: chuyen chuoi str ve chuoi in thuong
	strlwr((char *)str.c_str()); // hàm chuy?n chu?i str v? chu?i in thu?ng
	// Buoc 2: viet hoa kí tu dau cua moi tu
	if (str[0] != ' ')
	{
		if (str[0] >= 97 && str[0] <= 122)
		{
			str[0] -= 32;
		}
		
	}
	// kí tu tai vi trí i là khoang trong, i + i khác khoang trong thì kí tu tai vi trí i + 1 chính là kí tu dau tiên cua moi tu
	for (int i = 0; i < str.length() - 1; i++)
	{
		if (str[i] == ' ' && str[i + 1] != ' ')
		{
			// A: 65
			// B: 66
			// Z: 90
			// a: 97
			// b: 98
			// c: 99
			// z: 122
			if (str[i + 1] >= 97 && str[i + 1] <= 122)
			{
				// - 32 là chuyen ky tu in hoa sang in thuong
				str[i + 1] -= 32; // <=> str[i + 1] = str[i + 1] - 32;
			}
		}
	}
}
string ChuanHoaChuoi(string s){
	string str = s;
	Xoa_Khoang_Trang_Thua_Dau_Va_Cuoi(str);
	Xoa_Khoang_Trang_Giua_Cac_Tu(str);
	In_Hoa_Ki_Tu_Dau_Moi_Tu(str);
	return str;
}
void SwapDauSach(DauSach &a,DauSach &b){
	DauSach c;
	c = a;
	a = b;
	b = c;
}
void SwapDocGia(DocGia &a, DocGia &b){
	DocGia c;
	c = a;
	a = b;
	b = c;
}
void QuickSort_SLM(DanhSachSach &dss,int n){
	{struct Element_Stack{
		int q,r;
	};
	Element_Stack Stack[50];
	int sp =0;
	int i,j,q,r;
	DauSach x,temp;
	Stack[0].q = 0;
	Stack[0].r = n-1;
	do{
		//lay q phan hoach ra tu stack
		q = Stack[sp].q;
		r = Stack[sp].r;
		sp--;
		do{
			//phan doan day con a[q],...,a[r]
			x = dss.nodes[(q+r)/2];
			i =q; j =r;
			do{
				while(dss.nodes[i].SoLanMuon>x.SoLanMuon) i++;
				while(dss.nodes[j].SoLanMuon<x.SoLanMuon) j--;
				if(i<=j){
					temp = dss.nodes[i];
					dss.nodes[i] = dss.nodes[j];
					dss.nodes[j] = temp;
					i++;j--;
				}
			}while(i<=j);
			if(i<r)	//phan thu ba co tu 2 phan tu tro len
			{
				//dua vao stack chi so dau va chi so cuoi cua phan thu ba
				sp++;
				Stack[sp].q = i;
				Stack[sp].r = r;
			}
		r = j; //chuan bi vi tri de phan hoach phan co gia tri nho hon chot	
		}while(q<r);
	}while(sp!=-1); //ket thuc khi stack rong~
	}
}
void QuickSort_Name(DanhSachSach &dss,int n){
	{struct Element_Stack{
		int q,r;
	};
	Element_Stack Stack[50];
	int sp =0;
	int i,j,q,r;
	DauSach x,temp;
	Stack[0].q = 0;
	Stack[0].r = n-1;
	do{
		//lay q phan hoach ra tu stack
		q = Stack[sp].q;
		r = Stack[sp].r;
		sp--;
		do{
			//phan doan day con a[q],...,a[r]
			x = dss.nodes[(q+r)/2];
			i =q; j =r;
			do{
				while(dss.nodes[i].TenDauSach<x.TenDauSach) i++;
				while(dss.nodes[j].TenDauSach>x.TenDauSach) j--;
				if(i<=j){
					temp = dss.nodes[i];
					dss.nodes[i] = dss.nodes[j];
					dss.nodes[j] = temp;
					i++;j--;
				}
			}while(i<=j);
			if(i<r)	//phan thu ba co tu 2 phan tu tro len
			{
				//dua vao stack chi so dau va chi so cuoi cua phan thu ba
				sp++;
				Stack[sp].q = i;
				Stack[sp].r = r;
			}
		r = j; //chuan bi vi tri de phan hoach phan co gia tri nho hon chot	
		}while(q<r);
	}while(sp!=-1); //ket thuc khi stack rong~
	}
}
int MaxQH(PtrMuonTra &);
int CountNodeDG(PtrDocGia &);
void SortDocGia(PtrDocGia &root,MangTamDocGia &dsdg){
	const int STACKSIZE = MAX;
	PtrDocGia Stack[STACKSIZE];
	int sp = -1,i=0;
	PtrDocGia p = root;
	dsdg.n = 0;
	while(p!=NULL){
		if(p->docgia.TrangThai == 0){	
			dsdg.nodes[i].TrangThai;
			dsdg.nodes[i].MaDG= p->docgia.MaDG;
			dsdg.nodes[i].Ho = p->docgia.Ho;
			dsdg.nodes[i].Ten = p->docgia.Ten;
			dsdg.nodes[i].Phai = p->docgia.Phai;	
			dsdg.nodes[i].TrangThai = p->docgia.TrangThai;
			dsdg.nodes[i].FirstMuonTra = p->docgia.FirstMuonTra;
			i++;
			dsdg.n++;
		}
		if(p->right!=NULL)
			Stack[++sp]=p->right;
		if(p->left!=NULL)
			p=p->left;
		else if(sp == -1)
			break;
		else p=Stack[sp--];
	}
	for(int i =0;i<dsdg.n;i++)
	for(int j =i+1;j<dsdg.n;j++){
		if(MaxQH(dsdg.nodes[i].FirstMuonTra)<MaxQH(dsdg.nodes[j].FirstMuonTra)){
			SwapDocGia(dsdg.nodes[i],dsdg.nodes[j]);
		}
	}
}
void InDocGiaQH(MangTamDocGia &dsdg,PtrDocGia &root){
//	dsdg.n = CountNodeDG(root);
	int mdgsize = 4,hosize = 10,tensize = 34,gtsize =6,sttsize = 20;
	cout<<setw(mdgsize)<<left<<"MaDG"<<setw(hosize)<<left<<"|Ho"<<setw(tensize)<<left<<"|Ten"<<setw(gtsize)<<left<<"|Phai"<<setw(sttsize)<<left<<"|Trang thai"<<"|NQH"<<endl;
	for(int i=0;i<80;i++)
	cout<<"=";
	for(int i = 0;i<dsdg.n;i++){
		cout<<setw(mdgsize)<<left<<dsdg.nodes[i].MaDG<<setw(hosize)<<left<<"|"+dsdg.nodes[i].Ho<<setw(tensize)<<left<<"|"+dsdg.nodes[i].Ten;
		cout<<setw(gtsize)<<left<<"|"+dsdg.nodes[i].Phai;
		if(dsdg.nodes[i].TrangThai ==0)
			cout<<setw(sttsize)<<left<<"|Da huy kich hoat";
		cout<<"|"<<MaxQH(dsdg.nodes[i].FirstMuonTra)-15;
		cout<<endl;
	}
}
Date Today(){
	Date today;
	time_t t = time(0);   // get time now
    struct tm *now = localtime( &t );
    today.ngay = now->tm_mday;
    today.thang = (now->tm_mon+1);
    today.nam = (now->tm_year+1900);
    return today;
}
//Tru 2 ngay thang voi nhau, tra ve so ngay cach nhau
int TruNgayThang(int d, int m, int y){
	int t=0;
	while(y<=Today().nam){
		if(Today().thang == m && Today().nam == y){
			t += Today().ngay -d;
			break;
		}
		else{ 
			if( m==4 || m == 6 || m == 9 || m==11) //Cac thang 4,6,9,11 co 30 ngay
				t+= 30-d;
			if( m==1 || m==3 || m==5 || m==7 || m==8 || m==10 || m==12)//cac thang 1,3,5,7,8,10,12 co 31 ngay
				t+= 31-d;
			if(m==2){
				if (y%4 ==0 && y%100 !=0 || y%400==0)//nam nhuan
					t +=29-d;
				else t +=28-d;
			}
			m++;d=0;
			if(m==13){
				y++;m=1;
			}
		}
	}
	return t;
}

//Ham tra ve vi tri thu i cua sach trong dau sach
PtrSach nodepointer(PtrSach &First, int i){
	PtrSach p;
	int vt = 0;
	for (p=First;p!=NULL && vt<i;p=p->next){
		vt++;
	}
	return p;
}
PtrMuonTra nodepointerMT(PtrMuonTra &First, int i){
	PtrMuonTra mt;
	int vt = 0;
	for (mt=First;mt!=NULL && vt<i;mt=mt->next){
		vt++;
	}
	return mt;
}
void InitTree(PtrDocGia &root){
	root = NULL;
}
void Insert_Node(PtrDocGia &p, DocGia a){
	if (p==NULL){
		p = new NodeDocGia;
		p->docgia = a;
		p->left = NULL;
		p->right = NULL;
	}
	else if (a.MaDG<p->docgia.MaDG)
		Insert_Node(p->left,a);
	else if (a.MaDG>p->docgia.MaDG)
		Insert_Node(p->right,a);
}
void Insert_lastMT(PtrMuonTra &FirstMT, MuonTra smt){
	PtrMuonTra p = new NodeMuonTra;
	p->muontra = smt;
	p->next = NULL;
	if(FirstMT == NULL)
		FirstMT = p;
	else{
		PtrMuonTra Last;
		for(Last = FirstMT;Last->next!=NULL;Last = Last->next);
		Last->next = p;
	}
}
void NhapDocGia(PtrDocGia &root, ifstream &readers){
	stringstream ss;
	while(!readers.eof()){
		DocGia docgia;
		string madg, sosachm;
		getline(readers,madg);
		if(atoi(madg.c_str())!=0){
			getline(readers,docgia.Ho);
			getline(readers,docgia.Ten);
			getline(readers,sosachm);
			getline(readers,docgia.Phai);
			docgia.MaDG = atoi(madg.c_str());
			docgia.FirstMuonTra = NULL;
			docgia.SoSachM = atoi(sosachm.c_str());
			Insert_Node(root,docgia);
		}
		else break;
	}	
}
int CountMQH(PtrDocGia &,int);
void NhapTrangThai(PtrDocGia &root){
	const int STACKSIZE = MAX;
	PtrDocGia Stack[STACKSIZE];
	int sp = -1;
	PtrDocGia p = root;
	MuonTra mt;
	while(p!=NULL){
		if(CountMQH(root,p->docgia.MaDG)>0)
			p->docgia.TrangThai = 0;
		else if(CountMQH(root,p->docgia.MaDG)==0)
			p->docgia.TrangThai = 1;
		if(p->right!=NULL)
			Stack[++sp]=p->right;
		if(p->left!=NULL)
			p=p->left;
		else if(sp == -1)
			break;
		else p=Stack[sp--];
	}
}
PtrDocGia TimDocGia(PtrDocGia &,int);
void ThemDocGia(PtrDocGia &root){
	unhidecursor();
	DocGia dg;
	int num;
	int y = 1;
	cout<<"Ban muon them bao nhieu doc gia: ";
	NhapSo(num);
	Sleep(900);
	for(int i=0;i<num;i++){
		dg.MaDG = CountNodeDG(root)+1;
		string ho,ten,gt;
		ThemDocGia:
		system("cls");
		gotoxy(55,23);
		cout<<"Nhap vao ""Thoat"" de ngung";
		gotoxy(0,0);
		cout<<"Ma doc gia: "<<dg.MaDG<<endl;
		cout<<"Nhap ho doc gia: ";
		fflush(stdin);getline(cin,ho);
		if(ho!=""){
			gotoxy(55,23);
			cout<<"                               ";
			gotoxy(0,2);
			if(SoSanhChuoi(ho,"thoat")==false){
				dg.Ho = ChuanHoaChuoi(ho);
				cout<<"Nhap ten doc gia: ";
				NhapTen:
				fflush(stdin);getline(cin,ten);
				if(ten!=""){
					dg.Ten = ChuanHoaChuoi(ten);
					cout<<"Nhap gioi tinh: ";
					NhapGioiTinh:
					fflush(stdin);getline(cin,gt);
					if(gt!="" && SoSanhChuoi(gt,"nam")==true || SoSanhChuoi(gt,"nu")==true){
						dg.Phai = ChuanHoaChuoi(gt);
						dg.FirstMuonTra = NULL;
						dg.TrangThai =1;
						dg.SoSachM =0;
						Insert_Node(root,dg);
						cout<<"Da them doc gia thanh cong"<<endl;
						Sleep(900);
					}
					else if(gt=="" || SoSanhChuoi(gt,"nam") == false || SoSanhChuoi(gt,"nu") == false){
						cout<<"Gioi tinh khong hop le, vui long nhap lai";
						Sleep(900);
						gotoxy(0,wherey());
						cout<<"                                                              ";
						gotoxy(0,wherey()-1);
						cout<<"                                         ";
						gotoxy(0,wherey());
						cout<<"Nhap gioi tinh: ";
						goto NhapGioiTinh;
					}
				}
				else if(ten == ""){
					cout<<"Ten khong hop le. Vui long nhap lai";
					Sleep(900);
					gotoxy(0,wherey());
					cout<<"                                                  ";
					gotoxy(0,wherey()-1);
					cout<<"Nhap ten doc gia: ";
					goto NhapTen;
				}
			}
			else {
				break;
			}	
		}
		if(ho == ""){
			cout<<"Ho khong hop le. Vui long nhap lai";
			Sleep(1000);
			goto ThemDocGia;
		}	
	}	
}
void NLR (PtrDocGia &root){
	int mdgsize = 4,hosize = 11,tensize = 38,gtsize =6,sttsize = 21;
	cout<<setw(mdgsize)<<left<<"MaDG"<<setw(hosize)<<left<<"|Ho"<<setw(tensize)<<left<<"|Ten"<<setw(gtsize)<<left<<"|Phai"<<setw(sttsize)<<"|Trang thai";
	for(int i=0;i<80;i++)
		cout<<"=";
	const int STACKSIZE = MAX;
	PtrDocGia Stack[STACKSIZE];
	int sp = -1;
	PtrDocGia p = root;
	while(p!=NULL){
		cout<<setw(mdgsize)<<left<<p->docgia.MaDG<<setw(hosize)<<left<<"|"+p->docgia.Ho<<setw(tensize)<<left<<"|"+p->docgia.Ten<<setw(gtsize)<<left<<"|"+p->docgia.Phai;
		if(p->docgia.TrangThai == 0)
			cout<<"|Da huy kich hoat"<<endl;
		else if(p->docgia.TrangThai ==1)
			cout<<"|Da kich hoat"<<endl;
		else cout<<"|Khong xac dinh"<<endl;	
		if(p->right!=NULL)
			Stack[++sp]=p->right;
		if(p->left!=NULL)
			p=p->left;
		else if(sp == -1)
			break;
		else p=Stack[sp--];
	}
}
void NhapMuonTra(PtrDocGia &root, ifstream &muontra){
	const int STACKSIZE = MAX;
	PtrDocGia Stack[STACKSIZE];
	int sp = -1;
	PtrDocGia p = root;
	MuonTra mt;
	while(p!=NULL){
		for(int i=0;i<p->docgia.SoSachM && !muontra.eof();i++){
			string masachmt,ngaym,thangm,namm,ngayt,thangt,namt,trangthai;
			getline(muontra,mt.MaSachMT,'\n');
			getline(muontra,mt.TenSachMT);
			getline(muontra,ngaym,'/');
			getline(muontra,thangm,'/');
			getline(muontra,namm,'\n');
			getline(muontra,ngayt,'/');
			getline(muontra,thangt,'/');
			getline(muontra,namt,'\n');
			getline(muontra,trangthai);
			mt.NgayMuon.ngay = atoi(ngaym.c_str());
			mt.NgayMuon.thang = atoi(thangm.c_str());
			mt.NgayMuon.nam = atoi(namm.c_str());
			mt.NgayTra.ngay =atoi(ngayt.c_str());
			mt.NgayTra.thang = atoi(thangt.c_str());
			mt.NgayTra.nam = atoi(namt.c_str());
			mt.TrangThaiMT = atoi(trangthai.c_str());
			Insert_lastMT(p->docgia.FirstMuonTra,mt);
		}
		if(p->right!=NULL)
			Stack[++sp]=p->right;
		if(p->left!=NULL)
			p=p->left;
		else if(sp == -1)
			break;
		else p=Stack[sp--];
	}
}
PtrDocGia TimDocGia(PtrDocGia &root, int x){
	PtrDocGia p;
	p = root;
	while(p!=NULL && p->docgia.MaDG!=x)
		if(x < p->docgia.MaDG)
			p=p->left;
		else
			p=p->right;
	return (p);
}
void Insert_last(PtrSach &First, Sach s){
	PtrSach p = new NodeSach;
	p->sach = s;
	p->next=NULL;
	if(First ==NULL)
		First =p;
	else{
		PtrSach Last;
		for(Last=First;Last->next!=NULL;Last = Last->next);
		Last->next = p;
		}
}
void NhapDauSach(DanhSachSach &dss, ifstream &bookhead){
	int i=0;
	while(!bookhead.eof()){
		string nam,sotrang,sosach,vitri,isbn;
		getline(bookhead,isbn,'\n');
		if(SoSanhChuoi(isbn," ")==false){
//			getline(bookhead,dss.nodes[i].ISBN,'\n');
			getline(bookhead,nam,'\n');
			getline(bookhead,sotrang,'\n');
			getline(bookhead,sosach,'\n');
			getline(bookhead,dss.nodes[i].TacGia,'\n');
			getline(bookhead,dss.nodes[i].TenDauSach,'\n');
			getline(bookhead,dss.nodes[i].TheLoai,'\n');
			getline(bookhead,vitri,'\n');
			dss.nodes[i].ISBN = isbn;
			dss.nodes[i].SoLanMuon =0;
			dss.nodes[i].Nam = atoi(nam.c_str());
			dss.nodes[i].SoTrang = atoi(sotrang.c_str());
			dss.nodes[i].SoSach = atoi(sosach.c_str());
			dss.nodes[i].ViTri = atoi(vitri.c_str());
			dss.nodes[i].FirstSach = NULL;	
			i++;
			dss.n++;
		}
		else if(SoSanhChuoi(isbn," ")==true) break;
		QuickSort_Name(dss,dss.n);
	}	
}
void NhapSach(DanhSachSach &dss, ifstream &book){
	Sach s;
	for(int i=0;i<dss.n;i++)
	for(int j=0;j<dss.nodes[i].SoSach && !book.eof();j++){
		string trangthai,vitri,masach;
		getline(book,masach);
		if(SoSanhChuoi(masach," ")==false){
			getline(book,s.TenSach);
			getline(book,trangthai);
			getline(book,vitri);
			s.MaSach = masach;
			s.TrangThai = atoi(trangthai.c_str());
			s.ViTri = atoi(vitri.c_str());
			Insert_last(dss.nodes[i].FirstSach,s);
		}
		else break;
	}
}
//vi tri cua sach trong dau sach tim theo ten
int BookHeadPos(DanhSachSach &dss, string bookname){
	for (int i=0;i<dss.n;i++){
		if(SoSanhChuoi(dss.nodes[i].TenDauSach,bookname) == true){
			return i;
		}
	}
	return -1;
}
//tim theo ma isbn
int ViTriDauSach(DanhSachSach &dss, string isbn){
	for (int i=0;i<dss.n;i++){
		if(SoSanhChuoi(dss.nodes[i].ISBN,isbn) == true){
			return i;
		}
	}
	return -1;
}
//int ViTriDG(MangTamDocGia &dsdg, int mmdocgia){
//	for (int i=0;i<dsdg.n;i++){
//		if(SoSanhChuoi(dsdg.nodes[i].MaDG,mmadocgia) == true){
//			return i;
//			break;
//		}
//	}
//	return -1;
//}
int ViTriSach(PtrSach &First,string s){
	int count =0;
	for(PtrSach t =First;t!=NULL;t=t->next){
		if(SoSanhChuoi(t->sach.MaSach,s)==false)
			count++;
		if(SoSanhChuoi(t->sach.MaSach,s)==true)
			break;
	}
	return count;
}
//Vi tri sach trong danh sach muon tra
int ViTriSachMT(PtrMuonTra &First,string s){
	int pos =0;
	for(PtrMuonTra t =First;t!=NULL;t=t->next){
		if(SoSanhChuoi(t->muontra.TenSachMT,s)==false || (t->muontra.TrangThaiMT == 2 && SoSanhChuoi(t->muontra.TenSachMT,s)==true) ||(t->muontra.TrangThaiMT == 1 && SoSanhChuoi(t->muontra.TenSachMT,s)==true))
			pos++;
		if(SoSanhChuoi(t->muontra.TenSachMT,s)==true && t->muontra.TrangThaiMT == 0)
			break;
	}
	return pos;
}
int ViTriSachMTISBN(PtrMuonTra &First,string isbn){
	int pos =0;
	for(PtrMuonTra t =First;t!=NULL;t=t->next){
		string ms = t->muontra.MaSachMT.substr(0,t->muontra.MaSachMT.length()-3);
		if(SoSanhChuoi(ms,isbn)==false || (t->muontra.TrangThaiMT == 2 && SoSanhChuoi(ms,isbn)==true) ||(t->muontra.TrangThaiMT == 1 && SoSanhChuoi(ms,isbn)==true))
			pos++;
		if(SoSanhChuoi(ms,isbn)==true && t->muontra.TrangThaiMT == 0)
			break;
	}
	return pos;
}
int CountDauSach(DanhSachSach &,string);
void InDauSach(DanhSachSach &dss){
	unhidecursor();
	string tendausach,esc="Thoat";
	int vt;
	InDauSach:
	system("cls");
	gotoxy(55,23);
	cout<<"Nhap ""Thoat"" de tro ve";
	gotoxy(0,0);
	cout<<"Nhap ten sach ban muon in: ";
	fflush(stdin);getline(cin,tendausach);
	tendausach = ChuanHoaChuoi(tendausach);
	Sleep(600);
	if(SoSanhChuoi(tendausach,esc)==false){
		int countds = CountDauSach(dss,tendausach);
		if(countds==1){
			system("cls");
			vt = BookHeadPos(dss,tendausach);
			cout<<"ISBN: "<<dss.nodes[vt].ISBN<<endl;
			cout<<"Ten sach: "<<dss.nodes[vt].TenDauSach<<endl;
			cout<<"Nam xuat ban: "<<dss.nodes[vt].Nam<<endl;
			cout<<"So trang: "<<dss.nodes[vt].SoTrang<<endl;
		//	cout<<""<<dss.nodes[vt].SoSach<<endl;
			cout<<"So lan duoc muon: "<<dss.nodes[vt].SoLanMuon<<endl;
			cout<<"Vi tri:"<<dss.nodes[vt].ViTri<<endl;
			cout<<"Tac gia: "<<dss.nodes[vt].TacGia<<endl;	
			cout<<"The loai: "<<dss.nodes[vt].TheLoai<<endl;
		}
		else if(countds>1){
			NhapISBN:
			system("cls");
			gotoxy(55,23);
			cout<<"Nhap ""Thoat"" de tro ve";
			gotoxy(0,0);
			cout<<"Thu vien co "<<countds<<" ten sach theo yeu cau. Hay nhap ISBN cua sach ban muon xem thong tin"<<endl;
			string isbn;
			for(int i=0;i<dss.n;i++){
				if(SoSanhChuoi(dss.nodes[i].TenDauSach,tendausach)==true){
					cout<<"Ma ISBN: "<<dss.nodes[i].ISBN<<"    "<<"Ten sach: "<<dss.nodes[i].TenDauSach<<"    "<<"Tac gia: "<<dss.nodes[i].TacGia<<endl;
				}
			}
			cout<<"Nhap ma ISBN: ";
			fflush(stdin);getline(cin,isbn);
			if(SoSanhChuoi(isbn,esc)==false){
				vt = ViTriDauSach(dss,ChuanHoaChuoi(isbn));
				if(vt!=-1){
					system("cls");
					cout<<"ISBN: "<<dss.nodes[vt].ISBN<<endl;
					cout<<"Ten sach: "<<dss.nodes[vt].TenDauSach<<endl;
					cout<<"Nam xuat ban: "<<dss.nodes[vt].Nam<<endl;
					cout<<"So trang: "<<dss.nodes[vt].SoTrang<<endl;
				//	cout<<""<<dss.nodes[vt].SoSach<<endl;
					cout<<"So lan duoc muon: "<<dss.nodes[vt].SoLanMuon<<endl;
					cout<<"Vi tri: "<<dss.nodes[vt].ViTri<<endl;
					cout<<"Tac gia: "<<dss.nodes[vt].TacGia<<endl;	
					cout<<"The loai: "<<dss.nodes[vt].TheLoai<<endl;
				}
				else if(vt ==-1){
					cout<<"ISBN khong hop le, vui long nhap lai"<<endl;
					Sleep(900);
					goto NhapISBN;
				}
			}
		}
		else if(CountDauSach(dss,tendausach)==0){
			cout<<"Khong tim thay sach. Vui long nhap lai."<<endl;	
			Sleep(900);
			goto InDauSach; 	
		}
	}
}
void InAllDauSach(DanhSachSach &dss){
	for(int i=0;i<dss.n;i++){
	cout<<"ISBN: "<<dss.nodes[i].ISBN<<endl;
	cout<<"Ten sach: "<<dss.nodes[i].TenDauSach<<endl;
	cout<<"Nam xuat ban: "<<dss.nodes[i].Nam<<endl;
	cout<<"So trang: "<<dss.nodes[i].SoTrang<<endl;
	cout<<"So sach: "<<dss.nodes[i].SoSach<<endl;
	cout<<"So lan muon: "<<dss.nodes[i].SoLanMuon<<endl;
	cout<<"Tac gia: "<<dss.nodes[i].TacGia<<endl;	
	cout<<"The loai: "<<dss.nodes[i].TheLoai<<endl;
	cout<<endl;
	}		
}
void InAllDauSachTheoDong(DanhSachSach &dss){
	int namelen = 55;
	cout<<setw(namelen)<<left<<"Ten sach"<<"|Tac gia"<<endl;
	for(int i=0;i<80;i++){
		cout<<"=";
	}
	cout<<endl;
	for(int i=0;i<dss.n;i++){
		cout<<setw(namelen)<<left<<dss.nodes[i].TenDauSach.substr(0,55)<<"|"<<dss.nodes[i].TacGia.substr(0,30)<<endl;
	}
}
void InSach(DanhSachSach &dss){
	unhidecursor();
	string ttensach,esc = "Thoat";
	InSach:
	system("cls");
	gotoxy(55,23);
	cout<<"Nhap ""Thoat"" de tro ve";
	gotoxy(0,0); 
	cout<<"Nhap ten sach ban muon in: ";
	fflush(stdin);getline(cin,ttensach);
	if(SoSanhChuoi(ttensach,esc)==false){
		Sleep(500);
		system("cls");
		int vt;
		int counts = CountDauSach(dss,ttensach);
		if(counts == 1){
			vt = BookHeadPos(dss,ttensach);	
			for(PtrSach p=dss.nodes[vt].FirstSach;p!=NULL;p=p->next){
				cout<<"Ma sach: "<<p->sach.MaSach<<endl;
				cout<<"Ten sach: "<<p->sach.TenSach<<endl;
				if(p->sach.TrangThai == 0)
					cout<<"Cho muon duoc"<<endl;
				else if(p->sach.TrangThai ==1)
					cout<<"Da co doc gia muon"<<endl;
				else if(p->sach.TrangThai == 2)
					cout<<"Sach da thanh ly"<<endl;
				else cout<<"Trang thai: khong xac dinh"<<endl;
				cout<<"Vi tri :"<<p->sach.ViTri<<endl;
				cout<<endl;
			}
		}
		else if(counts > 1){
			NhapISBN:
			system("cls");
			gotoxy(55,23);
			cout<<"Nhap ""Thoat"" de tro ve";
			gotoxy(0,0);
			cout<<"Thu vien co "<<counts<<" cuon sach thoa yeu cau. Hay nhap ISBN cua sach ban muon xem thong tin"<<endl;
			string isbn;
			for(int i=0;i<dss.n;i++){
				if(SoSanhChuoi(dss.nodes[i].TenDauSach,ttensach)==true){
					cout<<"Ma ISBN: "<<dss.nodes[i].ISBN<<"    "<<"Ten sach: "<<dss.nodes[i].TenDauSach<<"    "<<"Tac gia: "<<dss.nodes[i].TacGia<<endl;
				}
			}
			cout<<"Nhap ma ISBN: ";
			fflush(stdin);getline(cin,isbn);
			Sleep(500);
			if(SoSanhChuoi(isbn,esc)==false){
				vt = ViTriDauSach(dss,isbn);
				if( vt != -1){
					system("cls");
					for(PtrSach p=dss.nodes[vt].FirstSach;p!=NULL;p=p->next){		
						cout<<"Ma sach: "<<p->sach.MaSach<<endl;
						cout<<"Ten sach: "<<p->sach.TenSach<<endl;
						if(p->sach.TrangThai == 0)
							cout<<"Cho muon duoc"<<endl;
						else if(p->sach.TrangThai ==1)
							cout<<"Da co doc gia muon"<<endl;
						else if(p->sach.TrangThai == 2)
							cout<<"Sach da thanh ly"<<endl;
						else cout<<"Trang thai: khong xac dinh"<<endl;
						cout<<"Vi tri :"<<p->sach.ViTri<<endl;
					}
				}
				else if(vt == -1){
					cout<<"Ma ISBN khong hop le, vui long nhap lai"<<endl;
					Sleep(900);
					goto NhapISBN;
				}
			}
			else if(SoSanhChuoi(isbn,esc)==true)
				return;
		}
		else if (counts ==0){
			cout<<"Khong tim thay sach, vui long nhap lai";
			Sleep(900);
			goto InSach;
		}
	}
	if(SoSanhChuoi(ttensach,esc)==true){
		return;
	}	
}
void InMuonTra (PtrDocGia &root){
	unhidecursor();
	int a;
	cout<<"Nhap ma doc gia: ";
	NhapSo(a);
	PtrDocGia temp = TimDocGia(root,a);
	if(temp!=NULL){
		system("cls");
		cout<<"Ma doc gia: "<<temp->docgia.MaDG<<endl;
		cout<<"Ho ten: "<<temp->docgia.Ho<<" "<<temp->docgia.Ten<<endl;
		cout<<"Gioi tinh: "<<temp->docgia.Phai<<endl;
		if(temp->docgia.TrangThai ==0)	
			cout<<"Trang thai: Da huy kich hoat"<<endl;
		else if(temp->docgia.TrangThai ==1)
			cout<<"Trang thai: Da kich hoat"<<endl;
			cout<<"So sach doc gia da muon: "<<temp->docgia.SoSachM<<endl;
			cout<<endl;
			for(PtrMuonTra p =temp->docgia.FirstMuonTra;p!=NULL;p=p->next){
				cout<<"Ma sach: "<<p->muontra.MaSachMT<<endl;
				cout<<"Ten sach: "<<p->muontra.TenSachMT<<endl;
				cout<<"Ngay muon: "<<p->muontra.NgayMuon.ngay<<"/"<<p->muontra.NgayMuon.thang<<"/"<<p->muontra.NgayMuon.nam<<endl;
				if(p->muontra.NgayTra.ngay == 0)
					cout<<"";
				else if(p->muontra.NgayTra.ngay !=0)
					cout<<"Ngay tra: "<<p->muontra.NgayTra.ngay<<"/"<<p->muontra.NgayTra.thang<<"/"<<p->muontra.NgayTra.nam<<endl;
				if(p->muontra.TrangThaiMT==0)
					cout<<"Dang muon"<<endl;
				else if(p->muontra.TrangThaiMT == 1)
					cout<<"Da tra"<<endl;
				else if(p->muontra.TrangThaiMT == 2)
					cout<<"Da lam mat"<<endl;
				else cout<<"Trang thai: Khong xac dinh"<<endl;
			cout<<endl;
		}
	}
	else cout<<"Khong tim thay doc gia";
}
int CountMT(PtrDocGia &,int);
void InMuon(PtrDocGia &root){
	unhidecursor();
	int a;
	cout<<"Nhap ma doc gia: ";
	cin>>a;
	PtrDocGia temp = TimDocGia(root,a);
	if(temp!=NULL){
		system("cls");
		cout<<"Ma doc gia: "<<temp->docgia.MaDG<<endl;
		cout<<"Ho ten: "<<temp->docgia.Ho<<" "<<temp->docgia.Ten<<endl;
		cout<<"Gioi tinh: "<<temp->docgia.Phai<<endl;
		if(temp->docgia.TrangThai ==0)		
			cout<<"Trang thai: Da huy kich hoat"<<endl;
		else if(temp->docgia.TrangThai ==1)
			cout<<"Trang thai: Da duoc kich hoat"<<endl;
		cout<<"So sach doc gia dang muon: "<<CountMT(root,a)<<endl;
		cout<<endl;
		for(PtrMuonTra p =temp->docgia.FirstMuonTra;p!=NULL;p=p->next){
			if(p->muontra.TrangThaiMT == 0){
				cout<<"Ma sach: "<<p->muontra.MaSachMT<<endl;
				cout<<"Ten sach: "<<p->muontra.TenSachMT<<endl;
				cout<<"Ngay muon: "<<p->muontra.NgayMuon.ngay<<"/"<<p->muontra.NgayMuon.thang<<"/"<<p->muontra.NgayMuon.nam<<endl;
				if(p->muontra.TrangThaiMT==0)
					cout<<"Trang thai: Dang muon"<<endl;
				else cout<<"Trang thai: Khong xac dinh"<<endl;
				cout<<endl;
			}
		}
	}
	else cout<<"Khong tim thay doc gia";
}
void TopSachPhoBien(DanhSachSach &dss){
	string top10 = "***Top 10 sach duoc muon nhieu nhat***";
	gotoxy(40-(top10.length()/2),0);
	cout<<ToUpperCase(top10)<<endl;
	cout<<endl;
	int namelen = 41,stt = 4,tglen=20;
	cout<<setw(stt)<<left<<"STT"<<setw(namelen)<<left<<"|Ten sach"<<setw(tglen)<<left<<"|Tac gia"<<"|So lan muon"<<endl;
	for(int i=0;i<80;i++)
		cout<<"=";
	cout<<endl;
	for(int i=0;i<10;i++){
		cout<<setw(stt)<<left<<(i+1)<<setw(namelen)<<left<<"|"+dss.nodes[i].TenDauSach<<setw(tglen)<<left<<"|"+dss.nodes[i].TacGia<<setw(stt)<<left<<"|"<<dss.nodes[i].SoLanMuon<<endl;
	}
}
void CountDMed(PtrDocGia &root, DanhSachSach &dss){
	int count =0;
	const int STACKSIZE = 500;
	PtrDocGia Stack[STACKSIZE];
	int sp = -1;
	PtrDocGia p = root;
	MuonTra mt;
	while(p!=NULL){
		for(PtrMuonTra mt =p->docgia.FirstMuonTra;mt!=NULL;mt = mt->next){
			int vt;
			string isbn;
			if(mt->muontra.TrangThaiMT == 1 || mt->muontra.TrangThaiMT ==2 || mt->muontra.TrangThaiMT == 0){
//				vt = BookHeadPos(dss,mt->muontra.TenSachMT);
				isbn = mt->muontra.MaSachMT.substr(0,mt->muontra.MaSachMT.length()-3);
				vt = ViTriDauSach(dss,isbn);
				dss.nodes[vt].SoLanMuon++;
			}
		}
		if(p->right!=NULL)
			Stack[++sp]=p->right;
		if(p->left!=NULL)
			p=p->left;
		else if(sp == -1)
			break;
		else p=Stack[sp--];
	}	
}
int CountMT(PtrDocGia &root,int x){
	int count =0;
	PtrDocGia p= TimDocGia(root,x);	
	for(PtrMuonTra q =p->docgia.FirstMuonTra;q!=NULL;q=q->next){
		if(q->muontra.TrangThaiMT==0)
			count++;
	}
	return count;
}
//dem so ngay muon sach qua han cua doc gia
int CountMQH(PtrDocGia &root,int x){
	int count = 0;
	PtrDocGia p =TimDocGia(root,x);
	for(PtrMuonTra q =p->docgia.FirstMuonTra;q!=NULL;q=q->next){
		if(TruNgayThang(q->muontra.NgayMuon.ngay,q->muontra.NgayMuon.thang,q->muontra.NgayMuon.nam)>15 && q->muontra.TrangThaiMT ==0)
			count++;
	}
	return count;
}
//Dem so sach co dang muon cua doc gia theo ten
int CountS(PtrMuonTra &First, string s){//s la ten sach
	int count =0;
	for(PtrMuonTra mt = First;mt!=NULL;mt=mt->next){
		if(mt->muontra.TrangThaiMT == 0 && SoSanhChuoi(mt->muontra.TenSachMT,s) == true){
			count++;
		}
	}
	return count;
}
//tim so ngay muon qua han nhieu nhat trong danh sach muon cua doc gia
int MaxQH(PtrMuonTra &First){
	int max = 0;
	for(PtrMuonTra mt= First;mt!=NULL;mt=mt->next){
		if( mt->muontra.TrangThaiMT == 0 && TruNgayThang(mt->muontra.NgayMuon.ngay,mt->muontra.NgayMuon.thang,mt->muontra.NgayMuon.nam)>max){
			max = TruNgayThang(mt->muontra.NgayMuon.ngay,mt->muontra.NgayMuon.thang,mt->muontra.NgayMuon.nam);
		}
	}
	return max;
}
int CountNodeDG(PtrDocGia &root){
	int count =0;
	const int STACKSIZE = MAX;
	PtrDocGia Stack[STACKSIZE];
	int sp = -1;
	PtrDocGia p = root;
	MuonTra mt;
	while(p!=NULL){
		count++;
		if(p->right!=NULL)
			Stack[++sp]=p->right;
		if(p->left!=NULL)
			p=p->left;
		else if(sp == -1)
			break;
		else p=Stack[sp--];
	}
	return count;
}
int CountDauSach(DanhSachSach &dss, string s){
	int count =0;
	for(int i=0;i<dss.n;i++){
		if(SoSanhChuoi(dss.nodes[i].TenDauSach,s)==true){
			count++;
		}
	}
	return count;
}
bool KTQuaHan(PtrMuonTra &First){
	for(PtrMuonTra p = First; p!=NULL; p=p->next){
		if(TruNgayThang(p->muontra.NgayMuon.ngay,p->muontra.NgayMuon.thang,p->muontra.NgayMuon.nam)>15 && p->muontra.TrangThaiMT == 0){
			return true;
			break;			
		}
	}
	return false;
}
void ThemSach(DanhSachSach &,string);
void ThemDauSach(DanhSachSach &dss){
	unhidecursor();
	int nn;
	string isbn,ttensach;
	string esc = "Thoat";
	cout<<"Ban muon them bao nhieu dau sach: ";
	NhapSo(nn);
	Sleep(800);
	for(int i=0;i<nn;i++){
		string s0 = "00";
		dss.n++;
		ThemDauSach:
		system("cls");
		gotoxy(55,23);
		cout<<"Nhap ""Thoat"" de dung";
		gotoxy(0,0);
		cout<<"Nhap ten sach: ";
		fflush(stdin);getline(cin,ttensach);
		gotoxy(55,23);
		cout<<"                           ";
		gotoxy(0,1);
		if(SoSanhChuoi(ttensach,esc)==false){
			if(ttensach != ""){
				dss.nodes[dss.n-1].TenDauSach = ChuanHoaChuoi(ttensach);
				if(GetUpperCase(dss.nodes[dss.n-1].TenDauSach).length()<=5)
					isbn = ToUpperCase(GetUpperCase(dss.nodes[dss.n-1].TenDauSach))+s0;
				else if (GetUpperCase(dss.nodes[dss.n-1].TenDauSach).length()>5)
					isbn = ToUpperCase(GetUpperCase(dss.nodes[dss.n-1].TenDauSach)).substr(0,5)+s0;
				dss.nodes[dss.n-1].ISBN = CheckIsbn(dss,isbn);
				cout<<"Nhap so trang: ";
				NhapSo(dss.nodes[dss.n-1].SoTrang);
				cout<<"Nhap so sach: ";
				NhapSo(dss.nodes[dss.n-1].SoSach);
				cout<<"Nhap tac gia: ";
				fflush(stdin);getline(cin,dss.nodes[dss.n-1].TacGia);
				cout<<"Nhap nam xuat ban: ";
				NhapSo(dss.nodes[dss.n-1].Nam);
				cout<<"Nhap the loai: ";
				fflush(stdin);getline(cin,dss.nodes[dss.n-1].TheLoai);
				cout<<"Nhap vi tri: ";
				NhapSo(dss.nodes[dss.n-1].ViTri);
				dss.nodes[dss.n-1].FirstSach =NULL;
				ThemSach(dss,dss.nodes[dss.n-1].ISBN);
				cout<<"Da them dau sach thanh cong"<<endl;
				Sleep(900);
			}
			else if(ttensach == ""){
				cout<<"Ten sach khong hop le. Vui long nhap lai"<<endl;
				Sleep(900);
				goto ThemDauSach;
			}		
		}
		else if(SoSanhChuoi(ttensach,esc)==true){
			break;
		}
	}
}
void ThemSach(DanhSachSach &dss, string iisbn){
	int vt = ViTriDauSach(dss,iisbn);
	for(int i=0;i<dss.nodes[vt].SoSach;i++){
		Sach sach;
		string s0 = "000",temp,masach;
		sach.TenSach = dss.nodes[vt].TenDauSach;
		masach = dss.nodes[vt].ISBN + s0;
		if(i<10){
			stringstream ss;
			ss<<(i);
			temp = masach.erase(masach.length()-1,masach.length())+ss.str();
		}
		if(i>=10 && i<100){
			stringstream ss;
			ss<<(i);
			temp = masach.erase(masach.length()-2,masach.length())+ss.str();
		}
		if(i>=100 && i<1000){
			stringstream ss;
			ss<<(i);
			temp = masach.erase(masach.length()-3,masach.length())+ss.str();
		}
		sach.MaSach =temp;
		sach.TrangThai =0;
		sach.ViTri = dss.nodes[vt].ViTri;
		Insert_last(dss.nodes[vt].FirstSach,sach);
	}
	QuickSort_Name(dss,dss.n);
}
void MuonSach(PtrDocGia &root, DanhSachSach &dss){
	unhidecursor();
	char k,g;
	string esc = "Thoat";
	while(1){	
		int mmadocgia,ssm;
		system("cls");
		cout<<"Nhap ma doc gia: ";
		NhapSo(mmadocgia);
		Sleep(500);
		PtrDocGia p = TimDocGia(root,mmadocgia);
		if(p==NULL){
			cout<<"Ma doc gia khong ton tai, vui long nhap lai"<<endl;
			Sleep(1000);
			continue;
		}
		if(p->docgia.TrangThai == 0){
			cout<<"The cua ban da bi huy kich hoat do muon sach qua han. Vui long tra sach de kich hoat lai the"<<endl;
			break;
		}
		sosachmuon:
		system("cls");
		cout<<"Ma doc gia: "<<p->docgia.MaDG<<endl;
		cout<<"Nhap so sach ban muon muon: ";
		NhapSo(ssm);
		Sleep(500);		
		int c = CountMT(root,mmadocgia);
		int tong = c+ssm;
		if (p!=NULL && ssm>0 &&tong<=3 && p->docgia.TrangThai ==1 && KTQuaHan(p->docgia.FirstMuonTra)==false){	
			string ttensach;
			do{
				MuonTra mt;
				PtrSach t = NULL;
				int vt;
				MuonSach:
				system("cls");
				gotoxy(55,23);
				cout<<"Nhap ""Thoat"" de dung";
				gotoxy(0,0);
				cout<<"Nhap ten sach ban muon muon: ";
				fflush(stdin);getline(cin,ttensach);
				if(SoSanhChuoi(ttensach,esc)==true) break;	
				if(CountDauSach(dss,ttensach)==1){
					vt = BookHeadPos(dss,ttensach);
					if(vt==-1){
						cout<<"Sach khong ton tai. Vui long chon sach khac."<<endl;
						Sleep(800);
						continue;
					}
					else if(vt != -1 && CheckDM(p,ttensach,dss.nodes[vt].ISBN) == false){
						for(PtrSach q=dss.nodes[vt].FirstSach;q!=NULL;q=q->next){
							if(q->sach.TrangThai==0){
								int pos = ViTriSach(dss.nodes[vt].FirstSach,q->sach.MaSach);//vi tri cua sach dang tim trong dau sach
								t =nodepointer(dss.nodes[vt].FirstSach,pos);						
								break;
							}
						}
						if(t == NULL){
							cout<<"Sach ban muon muon da het, vui long chon sach khac"<<endl;
							Sleep(800);
							continue;
							}
						else{
							p->docgia.SoSachM++;
							t->sach.TrangThai = 1;	
							mt.TenSachMT = t->sach.TenSach;
							mt.MaSachMT = t->sach.MaSach;
							mt.TrangThaiMT = 0;
							mt.NgayMuon.ngay = Today().ngay;
							mt.NgayMuon.thang = Today().thang;
							mt.NgayMuon.nam = Today().nam;
							mt.NgayTra.ngay =0;
							mt.NgayTra.thang =0;
							mt.NgayTra.nam =0;
							Insert_lastMT(p->docgia.FirstMuonTra,mt);
							for(PtrSach s =dss.nodes[vt].FirstSach;s!=NULL;s=s->next){
								if(SoSanhChuoi(s->sach.MaSach,mt.MaSachMT)==true){
									s->sach.TrangThai = 1;
									break;
								}
							}
							dss.nodes[vt].SoLanMuon++;
							cout<<"Da muon thanh cong"<<endl;
							Sleep(800);
							ssm--;
							if (ssm==0) break;
						}
					}
					else if(vt != -1 && CheckDM(p,ttensach,dss.nodes[vt].ISBN) == true){
						cout<<"Ban da muon sach nay roi. Vui long chon sach khac"<<endl;
						Sleep(800);
						goto MuonSach;
					}
				}
				else if(CountDauSach(dss,ttensach)==0){
					cout<<"Thu vien khong co sach ban can muon. Vui long chon sach khac"<<endl;
					Sleep(800);
					goto MuonSach;
				}
				else if(CountDauSach(dss,ttensach)>1){
					NhapISBN:
					system("cls");
					gotoxy(55,23);
					cout<<"Nhap ""Thoat"" de dung";
					gotoxy(0,0);
					cout<<"Thu vien co "<<CountDauSach(dss,ttensach)<<" ten sach theo yeu cau. Hay nhap ISBN cua sach ban can muon"<<endl;
					string isbn;
					for(int i=0;i<dss.n;i++){
						if(SoSanhChuoi(dss.nodes[i].TenDauSach,ttensach)==true){
							cout<<"Ma ISBN: "<<dss.nodes[i].ISBN<<setw(15)<<"Ten sach: "<<dss.nodes[i].TenDauSach<<setw(15)<<"Tac gia: "<<dss.nodes[i].TacGia<<endl;
						}	
					}
					cout<<"Nhap ma ISBN: ";
					fflush(stdin);getline(cin,isbn);
					if(isbn == ""){
						cout<<"Ma ISBN khong hop le, vui long nhap lai";
						Sleep(900);
						goto NhapISBN;
					}
					if(SoSanhChuoi(ChuanHoaChuoi(isbn),esc)==true) break;
					vt = ViTriDauSach(dss,ChuanHoaChuoi(isbn));
					if(vt!=-1 && CheckDM(p,ttensach,dss.nodes[vt].ISBN) == false){
						for(PtrSach q=dss.nodes[vt].FirstSach;q!=NULL;q=q->next){
							if(q->sach.TrangThai==0){
								int pos = ViTriSach(dss.nodes[vt].FirstSach,q->sach.MaSach);//vi tri cua sach dang tim trong dau sach
								t =nodepointer(dss.nodes[vt].FirstSach,pos);						
								break;
							}
						}
						if(t == NULL){
							cout<<"Sach ban muon muon da het, vui long chon sach khac"<<endl;
							Sleep(800);
							continue;
							}
						else{
							p->docgia.SoSachM++;
							t->sach.TrangThai = 1;	
							mt.TenSachMT = t->sach.TenSach;
							mt.MaSachMT = t->sach.MaSach;
							mt.TrangThaiMT = 0;
							mt.NgayMuon.ngay = Today().ngay;
							mt.NgayMuon.thang = Today().thang;
							mt.NgayMuon.nam = Today().nam;
							mt.NgayTra.ngay =0;
							mt.NgayTra.thang =0;
							mt.NgayTra.nam =0;
							Insert_lastMT(p->docgia.FirstMuonTra,mt);
							for(PtrSach s =dss.nodes[vt].FirstSach;s!=NULL;s=s->next){
								if(SoSanhChuoi(s->sach.MaSach,mt.MaSachMT)==true){
									s->sach.TrangThai = 1;
									break;
								}
							}
							dss.nodes[vt].SoLanMuon++;
							cout<<"Da muon thanh cong"<<endl;
							Sleep(800);
							ssm--;
							if (ssm==0) break;
						}		
					}
					else if( vt != -1 && CheckDM(p,ttensach,dss.nodes[vt].ISBN) == true){
						cout<<"Ban da muon sach nay roi. Vui long nhap lai"<<endl;
						Sleep(800);
						goto NhapISBN;
					}
					else if(vt ==-1){
						cout<<"ISBN khong hop le, vui long nhap lai"<<endl;
						Sleep(800);
						goto NhapISBN;
					}
				}
			}while(k!=27);	
		}
		else if(CountMT(root,p->docgia.MaDG)>=3){
			cout<<"Ban dang muon 3 cuon sach. Vui long tra sach truoc khi muon tiep."<<endl;
			Sleep(800);
		}
		else if(KTQuaHan(p->docgia.FirstMuonTra) == true){
			cout<<"Ban co it nhat 1 sach muon qua han. Vui long tra sach truoc khi muon tiep"<<endl;
			Sleep(800);
			}
		else if(tong >3){
			cout<<"Hien tai ban dang muon "<<c<<" cuon sach. Ban chi co the muon them toi da "<<3-c<<" cuon sach"<<endl;
			Sleep(800);
			goto sosachmuon;
		}
		else if(ssm<=0){
			cout<<"So sach ko hop le. Vui long nhap lai"<<endl;
			Sleep(800);;
			goto sosachmuon;
		}
	break;
	}
}
void TraSach(DanhSachSach &dss, PtrDocGia &root){
	unhidecursor();
	int mmadocgia,sst,dangmuon,muonquahan,sosach;
	string ttensach,esc = "Thoat";
	NhapMaDocGia:
	system("cls");
	cout<<"Nhap ma doc gia: ";
	NhapSo(mmadocgia);
  	Sleep(500);
	PtrDocGia p = TimDocGia(root,mmadocgia);
	if(p==NULL){
		cout<<"Khong tim thay doc gia. Vui long nhap lai";
		Sleep(900);
		goto NhapMaDocGia;
	}	
	if(p!=NULL){
		dangmuon = CountMT(p,mmadocgia);
		muonquahan = CountMQH(p,mmadocgia);
		if(dangmuon == 0){
			cout<<"Ban khong muon cuon sach nao"<<endl;
		}
		else{
			Trasach:
			system("cls");
			cout<<"Ban muon tra may cuon sach: ";
			NhapSo(sst);
			Sleep(500);
			if(sst>dangmuon){
				cout<<"Hien tai ban dang muon "<<dangmuon<<" cuon sach. Vui long nhap lai."<<endl;
				Sleep(800);
				goto Trasach;
			}	
			while(sst>0){
				int vt,vtmt;
				NhapTen:
				system("cls");
				gotoxy(55,23);
				cout<<"Nhap ""Thoat"" de dung";
				gotoxy(0,0);
				cout<<"Nhap ten sach ban muon tra: ";
				fflush(stdin);getline(cin,ttensach);
				if(SoSanhChuoi(esc,ttensach)==false){
					sosach = CountS(p->docgia.FirstMuonTra,ttensach);
					if(sosach==1){
						vt = BookHeadPos(dss,ttensach);
						vtmt = ViTriSachMT(p->docgia.FirstMuonTra,ttensach);
						PtrMuonTra mt = nodepointerMT(p->docgia.FirstMuonTra,vtmt);
						if(vt == -1)
							cout<<"Thu vien khong co sach nay. Vui long nhap lai."<<endl;
						else if(mt == NULL){
							cout<<"Ban khong muon sach nay. Vui long nhap lai"<<endl;
							Sleep(800);
							continue;
						}
						else if(mt!=NULL && mt->muontra.TrangThaiMT == 1){
							cout<<"Ban da tra sach nay roi"<<endl;
							Sleep(800);
							continue;
						}				
						else if(mt!=NULL && mt->muontra.TrangThaiMT == 0){
							mt->muontra.NgayTra.ngay = Today().ngay;
							mt->muontra.NgayTra.thang = Today().thang;
							mt->muontra.NgayTra.nam = Today().nam;
							mt->muontra.TrangThaiMT = 1;
							for(PtrSach s = dss.nodes[vt].FirstSach;s!=NULL;s=s->next){
								if(SoSanhChuoi(s->sach.MaSach,mt->muontra.MaSachMT)==true){
									s->sach.TrangThai = 0;
									break;
								}
							}
							cout<<"Da tra thanh cong"<<endl;
							sst--;
							muonquahan--;
							if(muonquahan == 0){
								if(p->docgia.TrangThai ==0)
									p->docgia.TrangThai =1;
							}
							Sleep(800);
						}
					}
					else if(sosach == 0){
						cout<<"Ban khong muon sach nay. Vui long nhap lai"<<endl;
						Sleep(800);
						goto NhapTen;
					}
					else if(sosach >1){
						string isbn;
						NhapISBN:
						system("cls");
						cout<<"Ban dang muon 2 cuon trung ten. Vui long nhap ma so de tra sach"<<endl;
						for(PtrMuonTra mt = p->docgia.FirstMuonTra;mt!=NULL;mt=mt->next){
							if(SoSanhChuoi(mt->muontra.TenSachMT,ttensach)==true && mt->muontra.TrangThaiMT == 0){
								string temp = mt->muontra.MaSachMT.substr(0,mt->muontra.MaSachMT.length()-3);
								cout<<temp<<"		"<<mt->muontra.TenSachMT<<endl;
							}
						}
						cout<<"Nhap ISBN: ";
						fflush(stdin);getline(cin,isbn);
						vt = ViTriDauSach(dss,isbn);
						int vtmt = ViTriSachMTISBN(p->docgia.FirstMuonTra,isbn);
						PtrMuonTra mt = nodepointerMT(p->docgia.FirstMuonTra,vtmt);
						if(vt == -1 || isbn ==""){
							cout<<"Ma ISBN khong hop le. Vui long nhap lai."<<endl;
							Sleep(900);
							goto NhapISBN;
						}
						else if(mt == NULL){
							cout<<"Ban khong muon sach nay. Vui long nhap lai"<<endl;
							continue;
						}
						else if(mt!=NULL && mt->muontra.TrangThaiMT == 1){
							cout<<"Ban da tra sach nay roi"<<endl;
							continue;
						}				
						else if(mt!=NULL && mt->muontra.TrangThaiMT == 0){
							mt->muontra.NgayTra.ngay = Today().ngay;
							mt->muontra.NgayTra.thang = Today().thang;
							mt->muontra.NgayTra.nam = Today().nam;
							mt->muontra.TrangThaiMT = 1;
							for(PtrSach s = dss.nodes[vt].FirstSach;s!=NULL;s=s->next){
								if(SoSanhChuoi(s->sach.MaSach,mt->muontra.MaSachMT)==true){
									s->sach.TrangThai = 0;
									break;
								}
							}
							cout<<"Da tra thanh cong"<<endl;
							sst--;
							muonquahan--;
							if(muonquahan == 0){
								if(p->docgia.TrangThai ==0)
									p->docgia.TrangThai =1;
							}
							Sleep(800);
						}
					}
				}
				else if(SoSanhChuoi(ttensach,esc)==true){
					break;
				}
			}
		}
	}
}
void LuuCSDL(DanhSachSach &dss,PtrDocGia &root,ofstream &FileDauSach,ofstream &FileSach,ofstream &FileMuonTra,ofstream &FileDocGia){	
	system("cls");
	hidecursor();
	if(!FileDauSach || !FileSach || !FileMuonTra || !FileDocGia){
		cout<<"Khong the mo file"<<endl;
	}
	else{
		//Luu danh sach dau sach va sach
		QuickSort_Name(dss,dss.n);
		for(int i=0;i<dss.n;i++){
			FileDauSach<<dss.nodes[i].ISBN<<endl;
			FileDauSach<<dss.nodes[i].Nam<<endl;
			FileDauSach<<dss.nodes[i].SoTrang<<endl;
			FileDauSach<<dss.nodes[i].SoSach<<endl;
			FileDauSach<<dss.nodes[i].TacGia<<endl;
			FileDauSach<<dss.nodes[i].TenDauSach<<endl;
			FileDauSach<<dss.nodes[i].TheLoai<<endl;
			FileDauSach<<dss.nodes[i].ViTri<<endl;
			for(PtrSach s = dss.nodes[i].FirstSach;s!=NULL;s=s->next){
				FileSach<<s->sach.MaSach<<endl;
				FileSach<<s->sach.TenSach<<endl;
				FileSach<<s->sach.TrangThai<<endl;
				FileSach<<s->sach.ViTri<<endl;
			}
		}
		//Luu danh sach doc gia va muon tra
		const int STACKSIZE = MAX;
		PtrDocGia Stack[STACKSIZE];
		int sp = -1;
		PtrDocGia p = root;
		MuonTra mt;
		while(p!=NULL){
			FileDocGia<<p->docgia.MaDG<<endl;
			FileDocGia<<p->docgia.Ho<<endl;
			FileDocGia<<p->docgia.Ten<<endl;
			FileDocGia<<p->docgia.SoSachM<<endl;
			FileDocGia<<p->docgia.Phai<<endl;
			for(PtrMuonTra mt = p->docgia.FirstMuonTra;mt!=NULL;mt=mt->next){
				FileMuonTra<<mt->muontra.MaSachMT<<endl;
				FileMuonTra<<mt->muontra.TenSachMT<<endl;
				FileMuonTra<<mt->muontra.NgayMuon.ngay<<"/"<<mt->muontra.NgayMuon.thang<<"/"<<mt->muontra.NgayMuon.nam<<endl;
				FileMuonTra<<mt->muontra.NgayTra.ngay<<"/"<<mt->muontra.NgayTra.thang<<"/"<<mt->muontra.NgayTra.nam<<endl;
				FileMuonTra<<mt->muontra.TrangThaiMT<<endl;
			}
			if(p->right!=NULL)
				Stack[++sp]=p->right;
			if(p->left!=NULL)
				p=p->left;
			else if(sp == -1)
				break;
			else p=Stack[sp--];
		}
		gotoxy(40-(17/2),2);
		cout<<"Da luu thanh cong"<<endl;
	}
}

void HelpGiaoDien(int i, bool lightbar){
	hidecursor();	
	switch (i){
		case 1:
			Inxy(0,2," 01.Vat tu",lightbar);break;
		case 2:
			Inxy(0,3," 02.Nhan vien",lightbar);break;
		case 3:
			Inxy(0,4," 03.Hoa don",lightbar);break;
		case 4:
			Inxy(0,5," 04. Thong ke hoa don trong 1 khoang thoi gian",lightbar);break;
		case 5:
			Inxy(0,6," 05. In 10 vât tu co doanh thu cao nhat",lightbar);break;
		
	}
}
void GiaoDien(int choice){
	system("cls");
	Inxy(32,0,"QUAN LY THU VIEN");
	for(int i=1;i<=14;i++){
		HelpGiaoDien(i,false);
	}
	HelpGiaoDien(choice,true);
}
void HelpExit(int i, bool lightbar){
	switch (i){
		case 1:
			Inxy(2,2,"Co",lightbar);break;
		case 2:
			Inxy(2,4,"Khong",lightbar);break;
	}
}
void GiaoDienExit(int choice){
	system("cls");
	for(int i=1;i<=2;i++){
		HelpExit(i,false);
	}
	HelpExit(choice,true);
}
void Choose(DanhSachSach &dss,PtrDocGia &root,ofstream &FileDauSach,ofstream &FileSach,ofstream &FileMuonTra,ofstream &FileDocGia){
	int choice;
	bool lightbar;
	choice = 1;
	GiaoDienExit(choice);
	string save = "Ban co muon luu vao CSDL";
	gotoxy(40-(save.length())/2,0);
	cout<<save;
	while(1){
			if(kbhit()){
			char k = getch();
			switch(k){
				case 80:{
					HelpExit(choice,false);
					if(choice == 2)
						choice =1;
					else 
						choice++;
						HelpExit(choice,true);
						break;
					}
					case 72:{
						HelpExit(choice,false);
						if(choice == 1)
							choice =2;
						else 
							choice--;
						HelpExit(choice,true);
						break;
					}
					case 13:{
						system("cls");
						switch(choice){
							case 1:{
								FileDauSach.open("BookHeadList.txt");
								FileDocGia.open("DocGia.txt");
								FileMuonTra.open("MuonTra.txt");
								FileSach.open("BookList.txt");
								LuuCSDL(dss,root,FileDauSach,FileSach,FileMuonTra,FileDocGia);
								FileDauSach.close();
								FileSach.close();
								FileMuonTra.close();
								FileDocGia.close();
								exit(0);
								break;
							}
							case 2:{
								exit(0);
							}
						}
					}
				system("pause");
				GiaoDienExit(choice);
			}
		}
	}
}

int main(){
	int choice=1,n;
	int dgcode;
	string tensach;
	DanhSachSach dss;
	PtrDocGia tree;
	MangTamDocGia dsdg;
	ifstream readers,bookhead,book,muontra;
	ofstream FileDauSach,FileSach,FileDocGia,FileMuonTra;
	bookhead.open("BookHeadList.txt");
	book.open("BookList.txt");
	readers.open("DocGia.txt");
	muontra.open("MuonTra.txt");
	InitTree(tree);	
	if(!bookhead || !book || !readers || !muontra)
		cout<<"Khong the mo file";
	else{
		NhapDauSach(dss,bookhead);
		NhapSach(dss,book);
		NhapDocGia(tree,readers);
		NhapMuonTra(tree,muontra);
		NhapTrangThai(tree);
		CountDMed(tree,dss);
		GiaoDien(choice);
		while(1){
			if(kbhit()){
				char k = getch();
				switch(k){
					case 80:{
						HelpGiaoDien(choice,false);
						if(choice == 14)
							choice =1;
						else 
							choice++;
						HelpGiaoDien(choice,true);
						break;
					}
					case 72:{
						HelpGiaoDien(choice,false);
						if(choice == 1)
							choice =14;
						else 
							choice--;
						HelpGiaoDien(choice,true);
						break;
					}
					case 13:
						system("cls");
						switch(choice){
							case 1:	
							InDauSach(dss);break;
							case 2:
							InSach(dss);break;
							case 3:{
							QuickSort_Name(dss,dss.n);
							InAllDauSachTheoDong(dss);
							break;
							}							
							case 4:
							ThemDocGia(tree);break;
							case 5:
							NLR(tree);break;
							case 6:
							InMuon(tree);break;	
							case 7:
							ThemDauSach(dss);break;	
							case 8:
							MuonSach(tree,dss);break;
							case 9:
							TraSach(dss,tree);break;
							case 10:{
							QuickSort_SLM(dss,dss.n);
							TopSachPhoBien(dss);
							break;
							}
							case 11:{
							SortDocGia(tree,dsdg);
							InDocGiaQH(dsdg,tree);
							break;
							}
							case 12:{
								InMuonTra(tree);
								break;
							}
							case 13:{
								FileDauSach.open("BookHeadList.txt");
								FileSach.open("BookList.txt");
								FileDocGia.open("DocGia.txt",ofstream::out);
								FileMuonTra.open("MuonTra.txt");
								LuuCSDL(dss,tree,FileDauSach,FileSach,FileMuonTra,FileDocGia);
								FileDocGia.close();
								FileDauSach.close();
								FileSach.close();
								FileMuonTra.close();
								break;
							}
							case 14:
								Choose(dss,tree,FileDauSach,FileSach,FileMuonTra,FileDocGia);
						}
					system("pause");					
					GiaoDien(choice);
				}
			}
		}
	}
return 0;
}