#include "BigNums.h"
#include "Error.h"
#include "Boolean.h"

//#define __SmallModel__
#ifdef __SmallModel__
static const int BigNumInitialLength = 2;
static const long root = 100L;
static const int perCell = 4;

#else
static const int BigNumInitialLength = 4;//ArrayDefaultLength;
static const long root = 10000L;
static const int perCell = 8;

#endif
static const long over = root*root;
static const long half = over/2;
static const long allnines = over - 1;
static const long maxCell = over - over/10;
static const long funnyNum = maxCell-1;

inline  // private inlines are ok.  They must be defined before the first call.
void BigNum::copy(const BigNum& b)
{	_value = b._value;
	_length = b._length;
}

inline
void BigNum::free()
{
}

//inline  // inlines must be in the interface file if public
void BigNum::negate()
{	complement();
	inc();
}

//inline
BigNum::BigNum(unsigned int length, char)  // private
:_value(length),
 _length(length)
{  //Uninitialized cells
}

BigNum::BigNum(long v)
: 	_value(BigNumInitialLength, 0L),
	_length(BigNumInitialLength)
{	//zero();
	int isNeg = v<0;
	if(isNeg) v=-v;
	_value[0] = v % over;
	_value[1] = v/over;
	if(isNeg) negate();
}

BigNum::BigNum(const char* x)
: 	_value(BigNumInitialLength,0L),
	_length(BigNumInitialLength)
{	fromString(x);
}

BigNum::BigNum(const String &x)
: 	_value(BigNumInitialLength, 0L),
	_length(BigNumInitialLength)
{	char * y = x.value();
	fromString(y);
	delete [] y;
}

void BigNum::complement()
{	int i;
	for (i = 0; i<_length; ++i)
		_value[i] = allnines - _value[i];
}

void BigNum::inc()
{	int i;
	long carry = 1L;
	for (i = 0; i<_length; ++i)
	{	_value[i] += carry;
		if(_value[i] > allnines)
		{	carry = 1L;
      	_value[i] -= over;
		}
		else
			carry = 0L;
	}
	if(carry == 1L)
	{	_value.extendBy(1);
		_length++;
		_value[_length - 1] = 1L;
	}
}

void BigNum::dec()
{	int i;
	long carry = 0L;
	int bigVal = _value[_length-1] == maxCell;
	for (i=0; i<_length-1; ++i)
		if(_value[i] != 0L)
		{	bigVal = false; break;}
	if (bigVal)
	{	_value.extendBy(1);
		_length++;
		_value[_length -1] = allnines;
		for(i=0; i< _length-2; ++i)
			_value[i] = allnines;
		_value[_length-2] = funnyNum;
	}
	else
	{	for (i = 0; i<_length; ++i)
		{	_value[i] += carry + allnines;
			if(_value[i] > allnines)
			{	carry = 1L;
				_value[i] -= over;
			}
			else
				carry = 0L;
		}
	}
}

void BigNum::zero()
{	for(int i = 0; i<_length; ++i)
		_value[i] = 0L;
}

int BigNum::sgn()const 
{
	if(_value[_length-1] >= half) return -1;
	for(int i = 0; i< _length; ++i)
		if(_value[i] != 0) return 1;
	return 0;
}

BigNum * BigNum::add(BigNum& b)
{  int signs = 0; // mixed signs
	if(_length>b._length)b.setLength(_length);
	else if(b._length > _length) setLength(b._length);
	BigNum *result = new BigNum(_length,0);// uninitialized
	if(sgn()>0 && b.sgn()>0) signs = 1; // both pos
	else if(sgn()<0 && b.sgn()<0) signs = -1; // both neg
	long carry = 0L;
	int i;
	long value;
	for(i=0; i<_length; ++i)
	{	value = _value[i] + b._value[i] + carry;
		if(value > allnines)
		{	value -= over;
			carry = 1L;
		}
		else
			carry = 0L;
		result->_value[i] = value;
	} // reuse the last value below
	if(signs == 1 && value >= half)
	{	result->_value.extendBy(1, 0L);
		result->_length++;
	}
	else if(signs == -1 && value < half)
	{	result->_value.extendBy(1, allnines);
   	result->_length++;
	}
	return result;
}

inline
BigNum * BigNum::subtract(BigNum& b)
{	BigNum local = b;
	local.negate();
	return add(local);
}

String BigNum::asString() 
{	int isNegative = _value[_length-1] >= half;
	if(isNegative) negate();
	String result;
	int i = 0; // which cell
	int j = 0; // which digit
	long value = _value[0];
	while ( i < _length)
	{	result = (value % 10L + '0') + result;
		value /= 10L;
		j++;
		if(j == perCell){
			j = 0; 
			i++; 
			if(i < _length) value = _value[i];
		}		 		
	}
	if (isNegative) 
	{	negate();
		result = '-' + result;
	}
	return result;
}

//inline
BigNum::BigNum(const BigNum & C)
{	copy(C);
}

//BigNum::~BigNum()
//{	free();os<<"ST"<<endl;
//}

const BigNum& BigNum::operator= (const BigNum& b)
{	if(this != &b)
	{	free();
		copy(b);
	}
	return *this;
}

void BigNum::dump(ostream & os)
{	int i;
	os<<"Dump: " << _length<<endl;
	for (i = _length-1; i>=0; --i)
		os << _value[i]<<endl;
	os << endl;
}

void BigNum::fromString(const char* x) // only used in constructors. 
{	// zero();  // may be needed if used elsewhere
	int n = strlen(x);
	int isNegative = false;
	if(n != 0)
	{	int extends = n - _length*perCell +1;
		if(extends > 0)
		{	int extra = extends / perCell +1;
			_value.extendBy(extra,0L);
			_length += extra;
		}
		const char* current = x + n - 1; // last char
		while(*current == ' ' || *current == '	')current--;
		while(*x == ' ' || *x == '	')x++;
		if(*x == '-'){x++; isNegative = true;}
		int i = 0; // which cell of the value we are building.
		int j = 0; // which digit of the current cell;
		long pow = 1L;
		while (x <= current)
		{	if(*current == ' ' || *current == '	'){current--;continue;}
			_value[i] += pow * long(*current - '0');
			j++;
			current--;
			pow *= 10L;
			if ( j == perCell) { j = 0; i++; pow = 1L;}
		}
		if(isNegative) negate();	
	}
}

void BigNum::setLength(int n)
// If n > current length it is padded to length n.
// If n < current length it is truncated as much as possible
// (but not shorter than n) without changing the value.
{	int i;
	long val;
	if(sgn() >= 0) val = 0L;
	if(n<1) n = 1;
	else if (sgn() < 0) val = allnines;
	int diff = n - _length;
	if(diff>0)  // extending
	{
	_value.extendBy(diff,val);
		_length += diff;
	}
	else if(diff<0) // truncating
	{	int cell = _length - 1;
		while(cell >= n-1
				&& _value[cell] == val
				&& (sgn()>0 ? _value[cell-1] < half
								: _value[cell-1] >= half ) )
		{cell--;
		}
		cell++; // length of the new array
		Array<long> newValue(cell);
		for(i = 0; i<cell; i++)
			newValue[i] = _value[i];
		_value = newValue;
      _length = cell;
	}
}

void BigNum::leftShift(int n)
{  if(n>0)
	{	_value.extendBy(n);
		_length += n;
		int i;
		for (i = _length-1; i>=n; --i)
			_value[i] = _value[i-n];
		for( i=0; i<n; ++i)
			_value[i] = 0L;
	}
}

BigNum * BigNum::multiply(BigNum& B)
{	int signs = 0; // true for an odd number of signs
	int wasNeg=0, bWasNeg = 0;
	if(sgn()<0)
	{  signs = 1;
		wasNeg = 1;
		negate();
	}
	if(B.sgn()<0)
	{ 	signs = 1-signs;
		bWasNeg = 1;
		B.negate();
	}
	BigNum * result = new BigNum(0L);
//	result->zero();
	BigNum prod(B);
	for(int i = 0; i<_length; ++i)
	{	longMult(_value[i], prod);
		prod.leftShift(i);
		BigNum *temp = result->add(prod);
		delete result;
		result = temp;
		prod = B;
	}
	if(wasNeg)negate();
	if(bWasNeg)B.negate();
	if(signs)result->negate();
	return result;
}
int llmult(long left, long right, long& hi, long& lo);

int llmult(long left, long right, long& hi, long& lo)
// multiplies positive 'perCell' digit numbers with
// results in the pair hi,lo. Returns 0 if hi==0.
{	long leftlo = left % root;
	long lefthi = left / root;
	long rightlo = right % root;
	long righthi = right / root;
	lo = leftlo * rightlo;
	hi = lefthi * righthi;
	long second = leftlo * righthi;
	long secondlo = second % root;
	long secondhi = second / root;
	hi += secondhi;
	lo += secondlo*root;
	 second = lefthi * rightlo;
	 secondlo = second % root;
	 secondhi = second / root;
	hi += secondhi;
	lo += secondlo*root;
	if(lo>root*root)
	{	hi += lo / (root*root);
		lo %= (root*root);
	}
	return hi != 0L;
}

int compare(long f[], long s[], int len)
{	int i;
	for (i = len-1; i>=0; i--)
		if(f[i] < s[i]) return 1;
		else if(f[i] > s[i]) return -1;
	return 0;
}

BigNum * BigNum::divide(BigNum& B)
{	int signs = 0; // true for an odd number of signs
	int wasNeg=0, bWasNeg = 0;
	int i,x;
	if(sgn()<0)
	{  signs = 1;
		wasNeg = 1;
		negate();
	}
	if(B.sgn()<0)
	{ 	signs = 1-signs;
		bWasNeg = 1;
		B.negate();
	}
	if(B.sgn() == 0)userERROR("Zero Divide.");
	setLength(1);
   B.setLength(1); // as short as possible
	if(_length>B._length)B.setLength(_length);
	else if(B._length > _length) setLength(B._length);
	int n = B._length;
	int size = 2 * n;
	long *subrA = new long[size];
	for(i=0;i<n;i++)
	{	subrA[2*i] = B._value[i]%root;
		subrA[2*i+1] = B._value[i] / root;
	}
	long *dvndA= new long[size];
	for(i=0;i<n;i++)
	{	dvndA[2*i] = _value[i]%root;
		dvndA[2*i+1] = _value[i] / root;
	}
	int m = size - 1;
	while(m>0 && subrA[m] == 0L)m--;
	m = size - 1 - m;
	for(i = size - 1; i>=m; i--)
		subrA[i] = subrA[i-m];
	for(i = m-1; i>= 0; i--)
		subrA[i] = 0L;
	int sizeResult = m%2==0? m+2 : m+1;
	BigNum * result = new BigNum(sizeResult / 2 + 1,0);result->zero();
	long *resultA = new long[sizeResult];
	for(i=0;i<sizeResult;i++)
	{	resultA[i] = 0;
	}
	n = size - 1;
	long carry = 0L;
	while(m>=0)
	{  long current = dvndA[n] + carry * root;
//os<<"outer"<<m<<' '<<n<<endl;
		if(subrA[n] == 0)
		{	resultA[m] = 0;
      	}
		else
		{	while(subrA[n]<current)
			{
				long trial = current / (subrA[n] + 1);
//os <<"innerup"<<trial<<endl;
				resultA[m] += trial;
				long carryp = 0L;  // multiply carry
				for(i=0; i<size;i++)
				{	long p = trial*subrA[i] + carryp;
					if(p>=root)
					{  carryp = p/root;
						p %= root;
					}
					else
						carryp = 0L;
					if(p>dvndA[i])
					{	dvndA[i] += root;
						x = i+1;
						while(x<size && dvndA[x] == 0L)
						{	dvndA[x] = root-1;
							x++;
						}
						dvndA[x]--;  // safe?
					}
					dvndA[i] -=p;
				}
				if(n<size-1) carry = dvndA[n+1]; else carry = 0;
				current = dvndA[n] + carry * root;
			}
			while(compare(subrA,dvndA, size) != -1)
			{
//os <<"innerdown"<<endl;
//for(i=size-1;i>=0;i--)os<<dvndA[i]<<' ';
//os<<endl;
//for(i=size-1;i>=0;i--)os<<subrA[i]<<' ';
//os<<endl;

				for(i=0; i<size; i++)
				{	if(subrA[i] > dvndA[i])
					{	dvndA[i] += root;
						x = i+1;
						while(x < size && dvndA[x] == 0L)
						{	dvndA[x] = root-1;
							x++;
						}
						dvndA[x]--; // safe?
					}
					dvndA[i] -= subrA[i];
				}
				resultA[m]++;
			}
			carry = dvndA[n];
			for(i=1; i<size; i++)
				subrA[i-1] = subrA[i];
			subrA[size-1] = 0L;
		}
		m--;
		n--;
	}
//os<<"exiting"<<endl;
//for(i=sizeResult-1;i>=0;i--)os<<resultA[i]<<' ';
//os<<endl;
	for(i = 0; i<sizeResult; i+=2)
	{	result->_value[i/2] = resultA[i] + resultA[i+1]*root;
	}
	delete [] subrA;
	delete [] dvndA;
	delete [] resultA;
	if(wasNeg)negate();
	if(bWasNeg)B.negate();
	if(signs)result->negate();
	return result;
}

//static
void longMult(long L, BigNum& B)  //friend function
// Requires L <= allnines.
//  each mult can overflow
// Must do this in halves.
{	int i;
	long carry = 0L;
	unsigned long value;
	long lo,hi;
	int sign = 0;
	if(B.sgn()<0)
	{	sign = 1-sign;
		B.negate();
	}
	if(L<0)
	{	sign = 1-sign;
		L = -L;
	}
	if(L>allnines)L=0;
	for(i=0;i<B._length;++i)
	{  llmult(L, B._value[i],hi,lo);
		value = lo + carry;
		if(value>allnines)
		{	carry = hi + value / over;
			value %= over;
		}
		else
			carry = hi;
		B._value[i] = value;
	}
	if(carry > 0L)
	{	B._value.extendBy(1,carry);
		B._length++;
	}
	if(value >= half)
	{	B._value.extendBy(1, 0L);
		B._length++;
	}
   if(sign == 1) B.negate();
}

BigNum BigNum::operator+(BigNum& b)
{  int signs = 0; // mixed signs
	if(_length>b._length)b.setLength(_length);
	else if(b._length > _length) setLength(b._length);
	BigNum result(_length,0);// uninitialized
	if(sgn()>0 && b.sgn()>0) signs = 1; // both pos
	else if(sgn()<0 && b.sgn()<0) signs = -1; // both neg
	long carry = 0L;
	int i;
	long value;
	for(i=0; i<_length; ++i)
	{	value = _value[i] + b._value[i] + carry;
		if(value > allnines)
		{	value -= over;
			carry = 1L;
		}
		else
			carry = 0L;
		result._value[i] = value;
	} // reuse the last value below
	if(signs == 1 && value >= half)
	{	result._value.extendBy(1, 0L);
		result._length++;
	}
	else if(signs == -1 && value < half)
	{	result._value.extendBy(1, allnines);
   	result._length++;
	}
	return result;
}

BigNum  BigNum::operator-(BigNum& b)
{	BigNum local = b;
	local.negate();
	return (*this)+local;
}

BigNum  BigNum::operator*(BigNum& b)
{	BigNum * temp = multiply(b);
	BigNum result(*temp);
	delete temp;
	return result;
}

BigNum  BigNum::operator/(BigNum& b)
{	BigNum * temp = divide(b);
	BigNum result(*temp);
	delete temp;
	return result;
}

BigNum  BigNum::operator%(BigNum& b)
{	return (*this) - ((*this)/ b * b);
}

BigNum BigNum::operator++()
{	inc();
	BigNum result(*this);
	return result;
}

BigNum BigNum::operator++(int)
{	BigNum result(*this);
	inc();
	return result;
}

int  BigNum::operator==(BigNum& b)
{	if(_length>b._length)b.setLength(_length);
	else if(b._length > _length) setLength(b._length);
	for(int i = 0; i<_length; ++i)
		if(_value[i] != b._value[i]) return false;
	return true;
}

int  BigNum::operator<(BigNum& b)
{	if(sgn()<0 && b.sgn()>0) return true;
	if(sgn()>0 && b.sgn()<0) return false;
	if(_length>b._length)b.setLength(_length);
	else if(b._length > _length) setLength(b._length);
	for(int i = _length -1; i>=0; i--)
	{	if(_value[i] < b._value[i])
		{	if(sgn()>0) return true; else return false;
		}
		else if(_value[i] > b._value[i])
		{	if(sgn()>0) return false; else return true;
		}
	}
	return false;
}

int BigNum::operator!=(BigNum& b)
{	return !((*this)==b);
}

int BigNum::operator<=(BigNum& b)
{	return (*this)< b || (*this) == b;
}

int BigNum::operator>(BigNum& b)
{	return !((*this) <= b);
}

int BigNum::operator>=(BigNum& b)
{	return !((*this) < b);
}