//familytree.h
#include<string.h>
#include<iostream>
#include<fstream.h>

struct member
{
    member *wife,*brother;
	char *name;
	int  sex;
	char *birth;
    char *father;
	int  marital_status;
	char *spouse;
	int  generation;//代
	member(){wife=brother=NULL;}
	member(char *n,int s,char *bi,char *f,int m,char *sp,int g,member*w=NULL,member*b=NULL);
};
member::member(char *n,int s,char *bi,char *f,int m,char *sp,int g,member*w,member*b)
{
	name=n;
	sex=s;
    birth=bi;
	father=f;//父親或丈夫
	marital_status=m;//婚姻狀況
	spouse=sp;//配偶
	generation=g;
	wife=w;
	brother=b;
}
class familytree
{
public:
	//***************創建族譜****************//
	familytree(){count=0;countg=0;root=NULL;};
	~familytree(){deletetree(root);};
	bool add(member *new_member);//插入一個家族成員
	void deletetree(member *sub_root);//清除家族信息
	void deletefamily(){deletetree(root);}
    //***************打印功能****************//
	void print(member *m);//打印一個成員的信息
    void printfamily(member *sub_root);//打印家族的所有成員（前序遍歷）
	void printf(){printfamily(root);}
    //***************統計功能****************//
	int  getcount()const{return count;};//取家族成員人數
	int  getgeneration(member *sub_root);//取家族總共幾代 
	int  getcountg(){getgeneration(root);return countg;}
   	//***************查詢功能****************//
	bool findmember(char *name,member *father,member *&p);//找出相應名字的節點的指針
	void showfather(char *childname);//找出相應節點的父親或丈夫并打印出其信息來
    void showwife(char *husbanddname);//找出相應節點的妻子并打印出其信息來
    void showchilden(char *fatherdname);//找出相應節點的孩子并打印出其信息來
    void showbrother(char *brothername);//找出相應節點的兄弟姐妹并打印出其信息來
	void showoneself(char *name);//找出相應節點并打印其信息
private:
	int count;//家族人員的總人數
	int countg;//代
	member *root;//祖先節點
};

bool familytree::findmember(char *name,member *father,member *&p)//找出相應名字的節點的指針,并賦給p
{
	if(father==NULL)
	{
		p=NULL;
		return false;
	}
    else if(strcmp(father->name,name)==0)//比較字符串
	{
		 p=father;
		 return true;
	}
	else
	{
		if(findmember(name,father->brother,p))
		{
			return findmember(name,father->brother,p);
		}
		else{return findmember(name,father->wife,p);}
	}
}

bool familytree::add(member *new_member)//插入一個家族成員節點
{
	if(root==NULL)
	{
		root=new_member;
		count++;
        new_member->generation=1;//祖先為第一代
		return true;
	}
	member *temp=NULL,*temp1=NULL,*temp2=NULL;
	if(!findmember(new_member->father,root,temp)){return false;}//找不到新成員的父親
	else
	{
        findmember(new_member->father,root,temp);
	    if(strcmp(new_member->father,new_member->spouse)==0)//如果father和spouse的名字相同，則是father的妻子
		{
		   temp->wife=new_member;
           new_member->generation=temp->generation;
		   temp->marital_status=1;//妻子與丈夫同一代
           temp->spouse=new_member->name;
		   return true;
		}
	    if(temp->wife!=NULL)//是father的兒子
		{
		    temp=temp->wife;//找出妻子節點
            temp1=temp;
			while(temp->brother!=NULL){temp=temp->brother;}
	 	    temp->brother=new_member;//在最后一個兒子節點后插入新成員節點
			if(temp1==temp){new_member->generation=temp->generation+1;}//兒子代數=母親代數+1
			else{new_member->generation=temp->generation;}//和兄弟同一代
			count++;
			return true;
		}
		cout<<"\nERROR! "<<new_member->father<<" has no wife yet.\n\n";
		return false;
	}
}
void familytree::deletetree(member *sub_root)//清除家族信息
{
	if(sub_root!=NULL)
	{
		deletetree(sub_root->brother);
		deletetree(sub_root->wife);
		delete sub_root;
	}
}
void familytree::print(member *m)//打印一個成員的信息
{
	cout<<m->name;
	if(m->sex==0){cout<<"\t♀";}
	else{cout<<"\t♂";}
	cout<<"   "<<m->birth<<"         "<<m->father<<"       "; 
	if((m->sex==0)&&(strcmp(m->father,m->spouse)!=0)) //如果是女兒的話，則不輸出配偶信息
	{
		if(m->marital_status==0){cout<<"\tsingle"<<"\t "<<"\t          "<<m->generation;}
        else{cout<<"\tmarried"<<"\t        "<<"\t  "<<m->generation;}
        cout<<endl;
	}else{     //如果是其他人員的話，則輸出配偶信息
		if(m->marital_status==0){cout<<"\tsingle"<<"\t "<<"\t          "<<m->generation;} 
    else{cout<<"\tmarried"<<"        "<<m->spouse<<"\t  "<<m->generation;}
    cout<<endl;
	}
}
void familytree::printfamily(member *sub_root)//打印家族的所有成員（前序遍歷）
{
	if(sub_root!=NULL)
	{                                        
        print(sub_root);
		printfamily(sub_root->wife);
		printfamily(sub_root->brother);
	}
}
void familytree::showfather(char *childname)//找出相應節點的父親或丈夫并打印出其信息來
{
	member *temp1=NULL,*temp2=NULL;
	if(!findmember(childname,root,temp1))
	{
		cout<<"ERROR!The name "<<childname<<" is not found in the family!\n";
		return;
	}
	findmember(childname,root,temp1);
	if(!findmember(temp1->father,root,temp2))
	{
		cout<<"ERROR!Can't find "<<childname<<"'s father!\n";
		return;
	}
	else//找到被查詢的節點及其父親節點
	{
        findmember(temp1->father,root,temp2);
		if(strcmp(temp1->father,temp1->spouse)==0)//判斷找的是丈夫還是父親
		{
			cout<<"---------------------------------"<<childname<<"'s husband------------------------------------\n";
		}else{cout<<"---------------------------------"<<childname<<"'s father-----------------------------------\n";}
		cout<<"name"<<"   sex"<<"    birthday"<<"    father(husband)"<<"   marital status"<<"   spouse"<<"   generation";
		print(temp2);
		cout<<endl;
		return;
	}
}

void familytree::showwife(char *husbandname)//找出相應節點的妻子并打印出其信息來
{
	member *temp=NULL;
	if(!findmember(husbandname,root,temp))
	{
		cout<<"ERROR! The name "<<husbandname<<" is not found in the family!\n";
		return;
	}
	findmember(husbandname,root,temp);
	temp=temp->wife;
	if(temp==NULL)
	{
		cout<<"He don't have wife yet!\n";
		return;
	}
	else
	{
		cout<<"----------------------------------"<<husbandname<<"'s wife------------------------------------\n";
		cout<<"name"<<"   sex"<<"    birthday"<<"    father(husband)"<<"   marital status"<<"   spouse"<<"   generation";
		print(temp);
		cout<<endl;
		return;
	}
}
void familytree::showchilden(char *fatherdname)//找出相應節點的孩子并打印出其信息來
{
	member *temp=NULL;
    if(!findmember(fatherdname,root,temp))
	{
		cout<<"ERROR! The name "<<fatherdname<<" is not found in the family!\n";
		return ;
	}
	findmember(fatherdname,root,temp);
	if(strcmp(temp->father,temp->spouse)==0)   //若為妻子結點
	{
     temp=temp->brother;
	}
	else if(temp->sex==0)   //若為除妻子結點外的女性結點
	{cout<<"He doesn't have any children yet!\n"; return;}  
	else if(temp->marital_status==0) //若為未婚結點
	{cout<<"He doesn't have any children yet!\n"; return;}
	else{
	temp=temp->wife;
	temp=temp->brother;
	}
	if(temp==NULL)
	{
		cout<<"He doesn't have any children yet!\n";
		return;
	}
	else
	{
        cout<<"-----------------------------------"<<fatherdname<<"'s children---------------------------------\n";
		cout<<"name"<<"   sex"<<"    birthday"<<"    father(husband)"<<"   marital status"<<"   spouse"<<"   generation";
	    int num=0;
	    while(temp!=NULL)
		{
		    num++;
            print(temp);
			temp=temp->brother;

		}
		cout<<"He has "<<num<<" children\n";
        cout<<endl;
		return;
	}
}
        
void familytree::showbrother(char *brothername)//找出相應節點的兄弟姐妹并打印出其信息來
{
	member *temp1,*temp2;
	if(!findmember(brothername,root,temp1))
	{
		cout<<"ERROR! The name "<<brothername<<" is not found in the family!\n";
		return;
	}
	else
	{
		findmember(brothername,root,temp1);
		if(strcmp(temp1->father,temp1->spouse)==0) cout<<"ERROR! she is "<<temp1->father<<"'s wife!\n";
		else
		{
			if(temp1==root)
			{
				cout<<"ERROR! "<<brothername<<" is the ancestor!\n";
				return;
			}
			else
			{
				findmember(temp1->father,root,temp2);
				temp2=temp2->wife;
				temp2=temp2->brother;
				cout<<"--------------------------------"<<brothername<<"'s brothers----------------------------------\n";
				cout<<"name"<<"   sex"<<"    birthday"<<"    father(husband)"<<"   marital status"<<"   spouse"<<"   generation";
	            int num=0;
	            while(temp2!=NULL)
		       {
				   if(strcmp(temp2->name,brothername)!=0)//不輸出被查找的成員的信息
				   {
					   num++;
                       print(temp2);
			           temp2=temp2->brother;					   
				   }
				   else{temp2=temp2->brother;}
   		       }
		       cout<<brothername<<" has "<<num<<" brothers\n";
               cout<<endl;
		       return;
			}
		}
	}
}
int familytree::getgeneration(member *sub_root)//取家族總共幾代 
{
	if(sub_root!=NULL)
	{
		getgeneration(sub_root->brother);
		getgeneration(sub_root->wife);
		if(sub_root->generation>countg){countg=sub_root->generation;}
	}
	return countg;
}

void familytree::showoneself(char *name)
{
	member *temp=NULL;
	if(!findmember(name,root,temp))
	{
		cout<<"ERROR! The name "<<name<<" is not found in the family!\n";
		return ;
	}
	findmember(name,root,temp);
	cout<<"--------------------------------"<<name<<"'s information----------------------------------\n";
	cout<<"name"<<"   sex"<<"    birthday"<<"    father(husband)"<<"   marital status"<<"   spouse"<<"   generation";
    print(temp);
	return;
}