#ifndef BIGINTEGER_H_H
#define BIGINTEGER_H_H
#include <stdlib.h>
#include <iostream>
#include <string>
#include <math.h>
#include "GlobalObject.h"

using namespace std;

const int defaultSize = 50;

template <class T>
class BigInteger
{
public:
	BigInteger(const T* D, SYMBOL smbl);						//constructor

	BigInteger(int sz = defaultSize, SYMBOL smbl = PLUS);		//constructor

	BigInteger(const BigInteger<T>& obj);					//copy constructor
				
	~BigInteger(){											//destructor		
		delete []Data;
	}
	
	SYMBOL GetSymbol() const{									//return the symbol of big integer
		return Symbol;
	}

	void SetSymbol(SYMBOL smbl){								//set the symbol of big integer
		Symbol = smbl;
	}
	
	int Size() const{										//return the maximal size of a big integer
		return MaxSize;
	}

	int Length() const{										//return the length of a big integer	
		return Last + 1;
	}

	void SetLength(int newLen, const char& c = '0');		//set the length of a big integer

	T GetData(int i) const{									//get the ith value of a big integer	
		return (i > 0 && i <= Last + 1) ? Data[i - 1] : NULL;
	}

	void SetData(int i, const T& c);						//set the ith value of a big integer with char 'c'

	void FillNumber(const T& c);							//set the number with character 'c'

	bool IsEmpty() const{									//check if the big integer is null	
		return Last == -1 ? true : false;
	}

	bool IsFull() const{									//check if the length attains the maximal size of big integer
		return (Last == MaxSize - 1) ? true : false;
	}

	BigInteger<T> operator + (const BigInteger<T>& obj);			//addition

	BigInteger<T> operator - (const BigInteger<T>& obj);			//substraction

	BigInteger<T> operator * (const BigInteger<T>& obj);			//multiplication

	BigInteger<T> operator = (const BigInteger<T>& obj);	//overload operator '=' endow value

	bool operator > (const BigInteger<T>& obj);				//overload operator >

	bool operator < (const BigInteger<T>& obj);				//overload operator <

	bool operator == (const BigInteger<T>& obj);			//overload operator ==


	void Input();											//input a big integer

	void Output();											//output a big integer

	friend ifstream& operator >>(ifstream& in, BigInteger<T>& obj);
	
	friend ofstream& operator <<(ofstream& out,const BigInteger<T>& obj);

	friend int MinKthPower(int a, int b, const int& k);		//get the minimal value of a integer k of power while lager than a and b

	friend BigInteger<T> abs(const BigInteger<T>& obj);		//

	friend BigInteger<T> standardize(const BigInteger<T>& obj);		//

	friend BigInteger<T> PositiveIntSubstraction(const BigInteger<T>& a, const BigInteger<T> &b);

	friend BigInteger<T> TraditionalMultiplication(const BigInteger<T>& a, const BigInteger<T>& b);	//Traditional big integer Multiplication Algorithm

	friend BigInteger<T> OptimizedMultiplication(const BigInteger<T>& a, const BigInteger<T>& b, int div = 2);	//Optimized big integer Multiplication Algorithm

	friend BigInteger<T> LeftShift(const BigInteger<T>&a, int n);		//shift big integer to the left n bits

	friend BigInteger<T> OptimizedFuncion(BigInteger<T> M[], BigInteger<T> N[], int orignLen, int div);

	BigInteger<T> ZERO();									//define 0
private:
	int MaxSize;											//the maximal size of big integer
	int Last;												//the index of the highest bit of a big integer
	SYMBOL Symbol;											//denote the plus or minus of big integer, true:flus, otherwise minus
	T* Data;												//an array save the value of a big integer
	void Resize(int newSize);								//resize the size of big integer
};

#endif //BIGINTEGER_H_H

template <class T>
BigInteger<T>::BigInteger(const T* D, SYMBOL smbl /* = PLUS */){
	MaxSize = defaultSize;
	Last = -1;
	Symbol = smbl;
	Data = new T[defaultSize];
	const T* ptr = D;
	int bufLen = 0;
	while(*ptr) {
		bufLen++;
		ptr++;
	}

	if (bufLen > defaultSize) 
		Resize(bufLen);
	
	ptr = D;
	while(*ptr)
		Data[++Last] = *ptr++;
}

template <class T>
BigInteger<T>::BigInteger(int sz /* = defaultSize */, SYMBOL smbl){
	if (sz > 0)	{
		MaxSize = sz;
		Last = -1;
		Symbol = smbl;
		Data = new T[MaxSize];
		if (Data == NULL)		{
			cerr<<"Allocate Memory Error!"<<endl;
			exit(1);
		}
	}
}

template <class T>
BigInteger<T>::BigInteger(const BigInteger<T>& obj){
	MaxSize = obj.Size();
	Last = obj.Length() - 1;
	Symbol = obj.GetSymbol();

	Data = new T[MaxSize];

	if (Data == NULL)	{
		cerr<<"Allocate Memory Error!"<<endl;
		exit(1);
	}

	for (int i = 1; i <= Last + 1; i++)	{
		Data[i - 1] = obj.GetData(i);
	}
}

template <class T>
void BigInteger<T>::Resize(int newSize){
	if (newSize <= MaxSize)	{
		cerr<<"Invalid Size!"<<endl;
		exit(1);
	}
	if (newSize != MaxSize)	{
		T* newarr = new T[newSize];
		if (newarr == NULL)
		{
			cerr<<"Allocate Memory Error!"<<endl;
			exit(1);
		}

		int n = Last + 1;
//		int n = (Last + 1) < newSize ? Last + 1 : newSize;
		T* srcptr = Data;
		T* destptr = newarr;
		while (n--)		{
			*destptr++ = *srcptr++;
		}

		delete []Data;
		Data = newarr;
		MaxSize = newSize;
	}
}

template <class T>
void BigInteger<T>::SetLength(int newLen, const char& c /* =  */){
	if (newLen < 0)	{
		cerr<<"Invalid new length!";
		exit(1);
	}

	if (Length() >= newLen)
		Last = newLen - 1;						//刪除高位

	if (Length() < newLen) {
		if (MaxSize < newLen)
			Resize(newLen);
		for (int i = Length(); i < newLen; i++)
			Data[++Last] = c;					//填補高位	
	}
}

template <class T>
void BigInteger<T>::SetData(int i, const T& c){
	if (i > 0 && i <= Length())
		Data[i - 1] = c;
	else{
		cerr<<"Error in SetData!"<<endl;
		exit(1);
	}
}

template <class T>
void BigInteger<T>::FillNumber(const T& c){
	for (int i = 0; i <= Last; i++)
		Data[i] = c;
}

template <class T>
BigInteger<T> BigInteger<T>::operator + (const BigInteger<T>& obj){
	BigInteger<T> sum, a(*this), b(obj);
	SYMBOL sa = a.GetSymbol(), sb = b.GetSymbol(), ssum = PLUS;
	a = standardize(a);
	b = standardize(b);
	if (sa == sb) {													//同號相加
		ssum = sa;
		int Len1 = a.Length();
		int Len2 = b.Length();
		int Length = Len1 > Len2 ? Len1 : Len2;
		Len1 > Len2 ? b.SetLength(Length) : a.SetLength(Length);	//make up the shorted number same as the longer one
		sum.SetLength(Length);
		
		bool* C = new bool[Length + 1];								//mark (i-1)th carried
		C[0] = 0;
		for (int i = 1; i <= Length; i++){
			sum.SetData(i, a.GetData(i) + b.GetData(i) + C[i - 1] - 48);

			C[i] = 0;
			if (sum.GetData(i) > 57 && sum.GetData(i) <= 67)		{
				C[i] = 1;
				sum.SetData(i,sum.GetData(i) - 10); 
			}
		}
		if (C[Length])												
			sum.SetLength(Length + 1,'1');

		delete []C;		
	}
	else {															//異號相加
		a = abs(a);
		b = abs(b);
		if (a > b) {
			sum = a - b;
			ssum = sa;
		}
		else if (a < b) {
			sum = b - a;
			ssum = sb;
		}
		else 
			sum = ZERO();
	}
	sum.SetSymbol(ssum);	
	return sum;
}

template <class T>
BigInteger<T> BigInteger<T>::operator - (const BigInteger<T>& obj){
	BigInteger<T> ret, a(*this) ,b(obj);
	SYMBOL sa = a.GetSymbol(), sb = b.GetSymbol(), sret = PLUS;
	a = standardize(a);
	b = standardize(b);
	if (sa == sb) {													//同號相減
		ret = PositiveIntSubstraction(a, b);
		sret = ret.GetSymbol();
		if (sa == MINUS)					//兩個負數相減，設置符號
			sret = ret.GetSymbol() == PLUS ? MINUS : PLUS;
	}
	else {															//異號相減
		sret = sa;
		a = abs(a);
		b = abs(b);
		ret = a + b;
	}	

	ret.SetSymbol(sret);
	return ret;
}

template <class T>
BigInteger<T> BigInteger<T>::operator * (const BigInteger<T>& obj){
//	BigInteger<T> product = TraditionalMultiplication(*this, obj);
	BigInteger<T> product = OptimizedMultiplication(*this, obj, 2);

	return product;
}

template <class T>
BigInteger<T> BigInteger<T>::operator = (const BigInteger<T>& obj){
	MaxSize = obj.Size();
	Last = obj.Length() - 1;
	Symbol = obj.GetSymbol();

	Data = new T[MaxSize];
	
	if (Data == NULL){
		cerr<<"Allocate Memory Error!"<<endl;
		exit(1);
	}
	
	for (int i = 1; i <= Last + 1; i++)	{
		Data[i - 1] = obj.GetData(i);
	}

	return *this;
}

template <class T>
bool BigInteger<T>::operator > (const BigInteger<T>& obj){
	bool ret = true;

	BigInteger<T> a = *this, b = obj;
	a = standardize(a);
	b = standardize(b);

	SYMBOL sa = a.GetSymbol(), sb = b.GetSymbol();
	if (a == b)
		ret = false;

	if (sa == PLUS && sb == MINUS)
		ret = true;

	if (sa == MINUS && sb == PLUS)
		ret = false;

	if (sa == sb)
		if (sa == PLUS) {								//a and b are plus 
			if (a.Length() > b.Length()) 
				ret = true;
			else if (a.Length() < b.Length())
				ret = false;
			else
				for (int i = 1; i <= a.Length(); i++) 
					if (a.GetData(i) > b.GetData(i)) {
						ret = true;
						break;
					}
					else if (a.GetData(i) < b.GetData(i)) {
						ret = false;
						break;
					}
		}
		else{											//a and b are minus 
			if (a.Length() > b.Length()) 
				ret = false;
			else if (a.Length() < b.Length())
				ret = true;
			else
				for (int i = a.Length(); i >=1 ; i--) 
					if (a.GetData(i) > b.GetData(i)) {
						ret = false;
						break;
					}
					else if (a.GetData(i) < b.GetData(i)) {
						ret = true;
						break;
					}
		}

	return ret;
}

template <class T>
bool BigInteger<T>::operator < (const BigInteger<T>& obj){
	bool ret = true;

	BigInteger<T> a = *this, b = obj;
	a = standardize(a);
	b = standardize(b);

	SYMBOL sa = a.GetSymbol(), sb = b.GetSymbol();
	if (a == b)
		ret = false;

	if (sa == PLUS && sb == MINUS)
		ret = false;

	if (sa == MINUS && sb == PLUS)
		ret = true;

	if (sa == sb)
		if (sa == PLUS) {								//a and b are plus 
			if (a.Length() > b.Length())