//this is avl tree node 
#include "Item.h"
#include<stdio.h>
#include<iostream.h>
#include<iomanip.h>

class avlNode//平衡二叉樹結點類
{
	public:
		avlNode(Index val);//構造函數
		void release();//析構用函數								
		int add(avlNode* &p,Index val);//插入一個值；返回新的avl樹的根結點的指針
		void preorderview(avlNode *current,int i=-1);//前序周游
		avlNode* remove(Index val,avlNode* &waste,int &flag);//刪除以當前結點的為根的avl樹中的val結點
		avlNode* findNodeValue(Index val);//查找val結點
		Index value;//碼值

		int bf;// balance factor
		avlNode * leftptr;//左右指針
		avlNode * rightptr;
		avlNode * removeLeftmostElement(avlNode* &childptr,int &flag);//找到最左的結點
		avlNode * LL_singleRotation();//在插入時候左子樹LL失衡的時候調整，返回新的樹根的指針
		avlNode * RR_singleRotation();//在插入時候右子樹RR失衡的時候調整，返回新的樹根的指針
		avlNode * LR_doubleRotation();//在插入時候左子樹LR失衡的時候調整，返回新的樹根的指針
		avlNode * RL_doubleRotation();//在插入時候右子樹RL失衡的時候調整，返回新的樹根的指針
	
};


avlNode::avlNode(Index val)
{
	value=val;
	leftptr=NULL;
	rightptr=NULL;
	bf=0;
}


void avlNode::release()
{
	if (leftptr)
	{//刪除左子樹中的結點
		leftptr->release();//遞歸調用
		delete leftptr;
		leftptr=0;
	}
	if (rightptr)
	{//刪除右子樹中的結點
		rightptr->release();//遞歸調用
		delete rightptr;
		rightptr=0;
	}
}


int avlNode::add(avlNode* &rp,Index val)
{//返回值表明以當前結點為根的樹是否再插入之后增高，0:非增高，非0:增高
	if (val.account <value.account)
	{//左子樹插入
		if (rp->leftptr==NULL)
			rp->leftptr=new avlNode(val);
		else if(rp->leftptr->add(rp->leftptr,val)==0)//插入后子樹沒有增高
			return 0;
		if (rp->bf==-1)
		{//原來已經傾斜，左邊失衡，需要做平衡處理
	       if (rp->leftptr->bf<0)  //插入在左側，單旋轉
	             rp = LL_singleRotation();
	       else rp = LR_doubleRotation();	//插入在右側，雙旋轉
		   return 0;
		}
		return --bf;   // bf=(0, +1)的情況，不需要調整樹，只要修改bf
	}
	else
	{
		if (rp->rightptr==NULL)
			rp->rightptr=new avlNode(val);
		else if (rp->rightptr->add(rp->rightptr,val)==0)//插入后子樹沒有增高 
			return 0;
		if(rp->bf==1)
		{//原來已經傾斜，需要做平衡處理
	       if (rp->rightptr->bf>0)    //插入在右側，單旋轉
	           rp = RR_singleRotation();
	       else rp = RL_doubleRotation();  //插入點在右側.雙旋轉
		   return 0;
		}
		return ++bf; // bf=(0, -1)的情況，不需要調整樹，只要修改bf
	}
}


avlNode* avlNode::remove(Index val,avlNode* &waste,int &flag)
{
	if (val.account==value.account)
	{
		waste=this;
		//當沒有右子樹的時候返回左子樹
		if(rightptr==NULL)
		{
			flag=1;
			return leftptr;
		}
		//刪除右子樹中的最小結點
		int oldbf=rightptr->bf;
		avlNode* newroot;
		rightptr=rightptr->removeLeftmostElement(newroot,flag);//找到后返回已經平衡的avl樹的根指針
		newroot->leftptr=leftptr;
		newroot->rightptr=rightptr;
		if((flag==1)&&(bf==1))
			flag=1;
		else flag=0;
		if(flag==1)
		{
			newroot->bf=bf--;
		}
		else newroot->bf=bf;
        //左樹的平衡
		avlNode* rightchild=newroot->rightptr;
	    if (rightchild==NULL) 
		    bf--;
	    else if((rightchild->bf!=oldbf)&&(rightchild->bf==0))
		    bf--;
    	if (bf<-1)
		{
		    int newoldbf=newroot->leftptr->bf;
	        if (newoldbf>0)
			{//雙旋轉
    	       return newroot->LR_doubleRotation();
			}
	        else
			{//單旋轉
		       return newroot->LL_singleRotation();
           	}
		}
	    return newroot;
		
	}
	else if(val.account<value.account)
	{//從左子樹中刪除
		if(leftptr==NULL)
			return this;
		//執行刪除
		int oldbf=leftptr->bf;
		leftptr=leftptr->remove(val,waste,flag);//遞歸調用
        //調整左子樹
        avlNode* leftchild=leftptr;
	    //計算刪除后的子樹對當前的根結點的平衡因子的影響
	    if (leftchild==NULL)
		   bf++;
	    else if((leftchild->bf!=oldbf)&&(leftchild->bf==0))
		   bf++;
	    if (bf>1)//失衡
		{//調整
		   int newoldbf=rightptr->bf;
	       if (newoldbf<0)//雙旋轉
		   {
	           return RL_doubleRotation();
		   }
	       else
		   {//單旋轉
		       avlNode* temp= RR_singleRotation();
			   if(flag==1)
				   bf++;
			   return temp;
		   }
		}
    	return this;
	}
	else
	{//從右子樹中刪除
		if(rightptr==NULL)
			return this;
		//執行刪除
		int oldbf=rightptr->bf;
		rightptr=rightptr->remove(val,waste,flag);//遞歸調用
		//調整右子樹
		avlNode* rightchild=rightptr;
    	if (rightchild==NULL) 
		  bf--;
	    else if((rightchild->bf!=oldbf)&&(rightchild->bf==0))
		  bf--;
	    if (bf<-1)
		{
		  int newoldbf=leftptr->bf;
	      if (newoldbf>0)
		  {//雙旋轉
    	      return LR_doubleRotation();
		  }
	      else
		  {//單旋轉
			  avlNode* temp= LL_singleRotation();
			  if(flag==1)
			    bf--;
			   return temp;
		   }
		} 
	    return this;
	}
}

avlNode* avlNode::removeLeftmostElement(avlNode* &childptr,int &flag)
{//flag 表示子樹高度是否變化
	avlNode* leftchild=leftptr;
	//找到最小的值，返回，否則遞歸調用
	if (leftchild==NULL)
	{
		childptr=this;
		flag=1;
		return rightptr;
	}
	int oldbf=leftchild->bf;
	leftptr=leftchild->removeLeftmostElement(childptr,flag);//遞歸調用
	//調整左子樹平衡
	avlNode* newleftchild=leftptr;
	//計算刪除后的子樹的高度變化
	if((newleftchild==NULL)&&(rightptr==NULL))
		flag=1;
	//計算刪除后的子樹對當前的根結點的平衡因子的影響
	if (newleftchild==NULL)
		bf++;
	else if((newleftchild->bf!=oldbf)&&(newleftchild->bf==0))
		bf++;
	if (bf>1)//失衡
	{//調整
		int newoldbf=rightptr->bf;
	    if (newoldbf<0)//雙旋轉
		{
	       return RL_doubleRotation();
		}
	    else
		{//單旋轉
		   return RR_singleRotation();
		}
	}
	return this;
}


avlNode* avlNode::findNodeValue(Index val)
{
	if (val.account==value.account)
	{
		return this;
	}
	else if (val.account>value.account)
	{//大于的話在右子樹中查找
		if (rightptr!=NULL)
			return rightptr->findNodeValue(val);//遞歸調用
		else 
			return NULL;
	}
	else
	{//小于的話在左子樹中查找
		if (leftptr!=NULL)			
			return leftptr->findNodeValue(val);//遞歸調用
		else
			return NULL;
	}
}
void avlNode::preorderview(avlNode *current,int i)
{
	i++;//層計數器
	if (current)
	{
		cout<<setw(8)<<current->value.account<<setw(10)<<current->bf<<" "<<setw(6)<<i<<endl;
		preorderview(current->leftptr,i);//遞歸調用
		preorderview(current->rightptr,i);//遞歸調用
	}
}

avlNode* avlNode::LL_singleRotation()
{
	avlNode *p;
	p=leftptr;
	leftptr=p->rightptr;
	bf=0;
	p->rightptr=this;
    if(p->bf==0)
	  p->bf=1;
	else p->bf=0;
	return p;
}

avlNode* avlNode::LR_doubleRotation()
{
	avlNode *p,*q;
	q=leftptr;
	p=q->rightptr;
	q->rightptr=p->leftptr;
	leftptr=p->rightptr;
	p->leftptr=q;
	bf=q->bf=0;
	if(p->bf==-1) bf=1;
	if(p->bf==1) q->bf=-1;
	p->rightptr=this;
	p->bf=0;
	return p;
}

avlNode* avlNode::RR_singleRotation()
{
	avlNode *p;
	p=rightptr;
	rightptr=p->leftptr;
	bf=0;
	p->leftptr=this;
    if(p->bf==0) 
	  p->bf=-1;
	else p->bf=0;
	return p;
}

avlNode* avlNode::RL_doubleRotation()
{
	avlNode *p,*q;
	q=rightptr;
	p=q->leftptr;
	q->leftptr=p->rightptr;
	rightptr=p->leftptr;
	p->rightptr=q;
	bf=q->bf=0;
	if(p->bf==-1) q->bf=1;
	if(p->bf==1) bf=-1;
	p->leftptr=this;
	p->bf=0;
	return p;
}

void InsertAccount(int acc)
{
	Item newuser;
	int pass1,pass2;
	cout<<"您的帳號是"<<endl;
	cout<<acc<<endl;
	cout<<"請輸入您的密碼"<<endl;
	cin>>pass1;
	bool flag=false;
	while(flag==false)
	{
		cout<<"請確認，再次輸入您的密碼"<<endl;
		cin>>pass2;
		if(pass1==pass2)
		{
			newuser.password=pass1;
			flag=true;
		}
		else
			cout<<"密碼不匹配，請重新輸入"<<endl;
	}
}