#include "bignum.h"
BigNum BigNum::Big_Small(BigNum&x)  // 計算x>=y
{
	int mid=0;
	Erase_Zero();
	x.Erase_Zero();
	BigNum result;
	int len=str.length();
	int x_len=x.str.length();
	result.str.resize(len);
	for (int i=len-1,j=x_len-1,k=len-1;j>=0;i--,j--,k--)
	{
		int middle;
		middle=str[i]-x.str[j]-mid;
		if (middle<0)
		{
			mid=1;
			middle=middle+10;
		}
		else mid=0;
		result.str[k]=middle+'0';
	}
	for (i=len-x_len-1,k=i;i>=0;i--,k--)
	{   
		int middle;
		middle=str[i]-'0'-mid;
		if (middle<0)
		{
			mid=1;
			middle=middle+10;
		}
		else mid=0;
		result.str[k]=middle+'0';
	}	
	return result;
}
BigNum::BigNum(string x)
{
	str=x;
}
void BigNum::Input()     
{
	string s;
	cout<<"請輸入你要計算的大數："<<endl;
	cin>>s;
	str=s;
}
BigNum& BigNum::Erase_Zero()
{
	int length=str.length();
	for (int i=0;i<length;i++)
	{
		if (str[0]=='0')
		{
			str.erase(str.begin());
		}
		else if (str[0]=='-')
		{
			int j=1;
			while (str[j]=='0')
			{
				str.erase(1,1);
			}	
		}
		else break;
	}
	for (i=0;i<str.length();)
	{
		if (str[i]==0)
		{
			str.erase(i,1);
		}
		else i++;
	}
	return *this;
}
void BigNum::Output()
{
	cout<<"結果是："<<endl;
	Erase_Zero();
	if(str.length()==0)cout<<"0"<<endl;
	else if (str.length()==1&&str[0]=='-')
	{
		cout<<"0"<<endl;
	}
	else cout<<str<<endl;
}
BigNum BigNum::Add(BigNum&x)
{
	BigNum add_bignum;
	Erase_Zero();
	x.Erase_Zero();
	int fir_len=str.length(),sec_len=x.str.length();
	int max_n=(fir_len>sec_len?fir_len:sec_len);
	add_bignum.str.resize(max_n+1);
	int min_n=(fir_len>=sec_len?sec_len:fir_len);
	int mid=0;
	for (int i=fir_len-1,j=sec_len-1,ii=max_n;i>=0&&j>=0;i--,j--,ii--)
	{
		int first=str[i]-'0',second=x.str[j]-'0',result;
		result=first+second+mid;
		mid=result/10;
		add_bignum.str[ii]=result%10+'0';
	}
	if (ii==0)
		{
			add_bignum.str[0]=mid+'0';  //進位99+1
		} 
	else if (fir_len>sec_len)
	{
		for (int i=fir_len-sec_len-1,ii=i+1;i>=0;i--,ii--)
		{
			int result=str[i]-'0',res;
			res=result+mid;
			mid=res/10;
			add_bignum.str[ii]=res%10+'0';
		}
		if (ii==0)
		{
			add_bignum.str[0]=mid+'0';
		} 
	}
	else if (sec_len>fir_len)
	{
		for (int j=sec_len-fir_len-1,ii=j+1;j>=0;j--,ii--)
		{
			int result=x.str[j]-'0',res;
			res=result+mid;
			mid=res/10;
			add_bignum.str[ii]=res%10+'0';
		}
		if (ii==0)
		{
			add_bignum.str[0]=mid+'0';
		}
	}
	return add_bignum;
}
BigNum BigNum::Sub(BigNum &x)
{
	BigNum sub_bignum;
	int len=str.length(),x_len=x.str.length();
	if ((str>=x.str&&len==x_len)||len>x_len) sub_bignum=Big_Small(x);
	else 
	{
		BigNum mid_sub;
		mid_sub=x.Big_Small(*this);
		int len=mid_sub.str.length();
		sub_bignum.str.resize(len+1);
		sub_bignum.str[0]='-';
		for (int i=0;i<len;i++)
		{
			sub_bignum.str[i+1]=mid_sub.str[i];
		}
	}
	return sub_bignum;

}
BigNum BigNum::operator -(BigNum&x)
{
	BigNum sub;
	Erase_Zero();
	x.Erase_Zero();
	int fir_len=str.length(),sec_len=x.str.length();
	int max_n=(fir_len>sec_len?fir_len:sec_len);
	sub.str.resize(max_n+1);
	if(str.length()>40||x.str.length()>40)throw MaxSize();
	if (str[0]=='-'&&x.str[0]=='-')
	{
		string str2;
		str2=x.str;
		x.str.erase(x.str.begin());
		sub=*this+x;
		x.str=str2;
		return sub;
	}
	else if (str[0]!='-'&&x.str[0]=='-')
	{
		string mid_s;
		mid_s=x.str;
		x.str.erase(x.str.begin());
		sub=*this+x;
		x.str=mid_s;
		return sub;
	}
	else if (str[0]=='-'&&x.str[0]!='-')
	{
		string str1;
		str1=str;
		str.erase(str.begin());
		BigNum mid;
		mid=*this+x;         ////////////////////////////
		sub.str.resize(max_n+2);
		sub.str[0]='-';
		for (int i=0,j=1;i<mid.str.length();i++,j++)
		{
			sub.str[j]=mid.str[i];
		}
		str=str1;
		return sub;
	}
	else
	{
		sub=Sub(x);	
		return sub;	 
	} 
}
BigNum BigNum::operator +(BigNum&x)
{
	BigNum add_bignum;
	Erase_Zero();
	x.Erase_Zero();
	int fir_len=str.length(),sec_len=x.str.length();
	int max_n=(fir_len>sec_len?fir_len:sec_len);
	add_bignum.str.resize(max_n+1);
	if(str.length()>40||x.str.length()>40)throw MaxSize();
	if (str[0]=='-'&&x.str[0]!='-')
	{
		string mid_s;
		mid_s=str;
		str.erase(str.begin());
		add_bignum=x.Sub(*this);
		str=mid_s;
		return add_bignum;
	}
	else if (str[0]!='-'&&x.str[0]=='-')
	{
		string mid_s;
		mid_s=x.str;
		x.str.erase(x.str.begin());
		add_bignum=Sub(x);
		x.str=mid_s;
		return add_bignum;
	}
	else if (str[0]=='-'&&x.str[0]=='-')
	{
		string str1,str2;
		str1=str,str2=x.str;
		str.erase(str.begin());
		x.str.erase(x.str.begin());
		BigNum mid;
		mid=Add(x);
		add_bignum.str.resize(max_n+2);
		add_bignum.str[0]='-';
		for (int i=0,j=1;i<mid.str.length();i++,j++)
		{
			add_bignum.str[j]=mid.str[i];
		}
		str=str1;
		x.str=str2;
		return add_bignum;

	}
	else 
	{
		add_bignum=Add(x);
		return add_bignum;
	}
}
BigNum BigNum::Mul(BigNum&x)
{
	Erase_Zero();
	x.Erase_Zero();
	BigNum mul_bignum;
	int len=str.length(),x_len=x.str.length();
	mul_bignum.str.resize(len+x_len);
	int mid=0;//進位
	for (int k=len+x_len-1;k>=0;k--)//積第k位=求和(第m位*第n位)m+n=k+1
	{
		int add=0;          
		int first,second;
		for (first=len-1;first>=0;first--)
		{
			second=k-first-1;
			if(second<x_len&&second>=0)add=add+(str[first]-'0')*(x.str[second]-'0');
		}
		add=add+mid;
		mul_bignum.str[k]=add%10+'0';
		mid=add/10;
	}
	return mul_bignum;
}
BigNum BigNum::operator *(BigNum&x)
{
	BigNum mul;
	Erase_Zero();
	x.Erase_Zero();
	int len=str.length(),x_len=x.str.length();
	mul.str.resize(len+x_len);
	if(str.length()>40||x.str.length()>40)throw MaxSize();
	if (str[0]=='-'&&x.str[0]=='-')
	{
		string str1,str2;
		str1=str,str2=x.str;
		str.erase(str.begin());
		x.str.erase(x.str.begin());
		mul=Mul(x);
		str=str1,x.str=str2;
		return mul;
	}
	else if (str[0]!='-'&&x.str[0]=='-')
	{
		string str2;
		str2=x.str;
		x.str.erase(x.str.begin());
		BigNum mid;	
		mid=Mul(x);
		mul.str.resize(len+x_len+2);
		mul.str[0]='-';
		for (int i=0,j=1;i<mid.str.length();i++,j++)
		{
			mul.str[j]=mid.str[i];
		}
		x.str=str2;
		return mul;
	}
	else if (str[0]=='-'&&x.str[0]!='-')
	{
		string str1;
		str1=str;
		str.erase(str.begin());
		BigNum mid;	
		mid=Mul(x);
		mul.str.resize(len+x_len+2);
		mul.str[0]='-';
		for (int i=0,j=1;i<mid.str.length();i++,j++)
		{
			mul.str[j]=mid.str[i];
		}
		str=str1;
		return mul;
	}
	else 
	{
		mul=Mul(x);
		return mul;
	}
}
BigNum BigNum::Div(BigNum &x,bool T)
{
	Erase_Zero();
	x.Erase_Zero();
	int len=str.length();
	int x_len=x.str.length();
	BigNum mid_x=x;
	BigNum remain;
	remain.str.resize(len);
	remain.str=str;
	BigNum quotient;
	quotient.str.resize(len);
	if (len<x_len)
	{
		quotient.str.resize(0);
		cout<<"余數";
	    remain.Output();
		return quotient;
	}
	for (int i=x_len-1,j=0;j<=len-x_len;i++,j++)
	{
		mid_x=x;
		for (int jj=i+1;jj<len;jj++)
		{
			mid_x.str.append("0");
		}
		int r_n=remain.str.length(),m_n=mid_x.str.length();
		if ((remain.str>=mid_x.str&&r_n==m_n)||r_n>m_n)
		{
			for (int mm=1;mm<10;mm++)
			{
				remain=remain.Big_Small(mid_x);
				remain.Erase_Zero();
				r_n=remain.str.length();	
				if((remain.str<mid_x.str&&r_n==m_n)||r_n<m_n)break;
			}
		
			quotient.str[j]=mm+'0';
			remain.Erase_Zero();
		}
		else quotient.str[j]='0';
	}
	cout<<"余數";
	if(T)
	{
		remain.Output();
	}
	else if((!T)&&remain.str.length()!=0)
	{
		BigNum One("1");
		quotient.Erase_Zero();
		quotient=quotient+One;
		(x-remain).Output();
	}
	else cout<<"0"<<endl;
	return quotient;
}
BigNum BigNum::operator /(BigNum&x)
{
	BigNum div;
	Erase_Zero();
	x.Erase_Zero();
	int len=str.length(),x_len=x.str.length();
	div.str.resize(len);
	if(x.str.length()==0)throw Zero();
	if(str.length()>40||x.str.length()>40)throw MaxSize();
	if (str[0]=='-'&&x.str[0]=='-')
	{
		string str1,str2;
		str1=str,str2=x.str;
		str.erase(str.begin());
		x.str.erase(x.str.begin());
		div=Div(x,true);
		str=str1,x.str=str2;
		return div;
	}
	else if (str[0]!='-'&&x.str[0]=='-')
	{
		string str2;
		str2=x.str;
		x.str.erase(x.str.begin());
		BigNum mid;	
		mid=Div(x,true);
		div.str.resize(len+1);
		div.str[0]='-';
		for (int i=0,j=1;i<mid.str.length();i++,j++)
		{
			div.str[j]=mid.str[i];
		}
		x.str=str2;
		return div;
	}
	else if (str[0]=='-'&&x.str[0]!='-')///////////
	{
		string str1,str2;
		str1=str,str2=x.str;
		str.erase(str.begin());
		BigNum mid;	
		mid=Div(x,false);
		mid.Erase_Zero();
		if(mid.str[0]=='0')
		{
			div.str.resize(0);
			return div;
		}
		div.str.resize(len+1);
		div.str[0]='-';
		for (int i=0,j=1;i<mid.str.length();i++,j++)
		{
			div.str[j]=mid.str[i];
		}
		str=str1;
		x.str=str2;
		return div;
	}
	else 
	{
		return Div(x,true);
	}
}