#include <string.h>
#include <math.h>
#include "bigint.h"

char *BigInt::addBigInt (char *n1, char *n2) {
   if (n1 == NULL) return n2;
   if (n2 == NULL) return n1;
   
   int d1 = strlen(n1);
   int d2 = strlen(n2);
   int size = (d1 > d2) ? d1+1 : d2+1;
   
   char *result = new char[size+1];
   result[size] = 0;
   for (int i=0 ; i < size ; i++) result[i] = '0';
   int acc = 0;
   while (d1 > 0 || d2 > 0) {
      int n = acc;
      if (d1 > 0) n += n1[--d1] - '0';
      if (d2 > 0) n += n2[--d2] - '0';
      result[--size] = (n % 10) + '0';
      acc = (n / 10);
   }
   if (acc > 0) result[--size] = acc + '0';
   return &result[size];
}

// Second of several functions for use by the multiplier only.
// Multiply a given BigInteger by 10^s (that is, shift the BigInteger
// s places to the left).
char *BigInt::shiftLeft (char *numb, int s) {
   if (s <= 0) return numb;
   char *result = new char[strlen(numb)+s+1];
   int i=0;
   for ( ; i < (int)strlen(numb) ; i++) result[i] = numb[i];
   for ( ; s > 0 ; s--) result[i++] = '0';
   result[i] = 0;
   return result;
}

// Third of several functions intended for use by the multiplier only.
// Mutiply a given BigInteger by a single digit.
// Assume '0' <= d && d <= '9' and n is non-negative.
char *BigInt::multiplyLine (char *numb, char d) {
   char *result = new char[strlen(numb)+2];
   result[strlen(numb)+1] = 0;
   int carry = 0;
   for (int i=strlen(numb)-1 ; i >=0 ; i--) {
      int r = carry + (d - '0')*(numb[i] - '0');
      result[i+1] = (r % 10) + '0';
      carry = (r / 10);
   }
   if (carry > 0) {
      result[0] = carry + '0';
      return result;
   }
   return &result[1];
}

int BigInt::cmp(char *str1, char *str2) {
   if (strlen(str1) > strlen(str2)) return 1;
   if (strlen(str2) > strlen(str1)) return -1;
   for (size_t i=0 ; i < strlen(str1) ; i++) {
      if (str1[i] < str2[i]) return -1;
      if (str1[i] > str2[i]) return 1;
   }
   return 0;
}

BigInt *BigInt::divideByTen() {
   char *str = new char[strlen(numb)+1];
   strcpy(str,numb);
   if (strlen(str) > 0) {
      str[strlen(str)-1] = 0;
      return new BigInt(str);
   } else {
      return NULL;
   }
}

BigInt::BigInt(char *numb) {
   if (numb == NULL) {
      this->numb = NULL;
      sign = false;
      return;
   }
   if (numb[0] == '-') {
      this->numb = new char[strlen(numb)];
      strcpy(this->numb, &numb[1]);
      sign = true;
   } else {
      this->numb = new char[strlen(numb)+1];
      strcpy(this->numb,numb);
      sign = false;
   }
}

BigInt::BigInt(int numb) {
   if (numb < 0) {
      this->sign = true; 
      numb = -numb;
   } else 
      this->sign = false;
   char n[1024];
   sprintf(n,"%d",numb);
   this->numb = new char[strlen(n)+1];
   strcpy(this->numb,n);
}

char *BigInt::value () { return numb; }

BigInt *BigInt::toBigInt(long long numb) {
   bool sign = false;
   if (numb < 0) {
      numb = -numb;
      sign = true;
   }
      
   if (this->numb == NULL) delete this->numb;
   int ndigits;
   // Set aside the proper number of bytes to stick the string into
   if (numb > 0)
      ndigits = (int)ceil(log10((double)(numb+1)));
   else if (numb < 0)
      ndigits = (int)ceil(log10(-(double)(numb-1)))+1;  // +1 for '-' sign
   else 
      ndigits = 1;  // Catch this case as special because log10(0) is big
   this->numb = new char[ndigits+1];
   
   // Terminate the string with a 0
   // Special case of numb=0: put a '0' into the 1st position and return
   this->numb[ndigits] = 0;
   if (numb == 0) {
      this->numb[0] = '0';
      this->sign = false;
      return this;
   }
   
   // Install the bits.  This works regardless of the sign of numb
   for (int i=ndigits-1 ; numb != 0 ; i--) {
      this->numb[i] = (numb % 10) + '0';
      numb /= 10;
   }
   this->sign = sign;
   return this;
}

// First of several functions intended for use by the multiplier only.
// Add two BigIntegers.
// Assume numb and this are non-negative numbers.
BigInt *BigInt::addBigInt (BigInt *numb) {
   if (numb == NULL) return this;
   BigInt *result = NULL;
   if (this->sign && !numb->sign) {
      this->sign = false;
      switch (cmp(this->numb,numb->value())) {
      case -1:
	 result = numb->subtractBigInt(this);
	 result->sign = false;
	 break;
      case 1:
	 result = this->subtractBigInt(numb);
	 result->sign = true;
	 break;
      case 0:
	 result = new BigInt(0);
      }
      this->sign = true;
   } else if (!this->sign && numb->sign) {
      numb->sign = false;
      switch (cmp(this->value(),numb->value())) {
      case -1:
	 result = numb->subtractBigInt(this);
	 result->sign = true;
	 break;
      case 1:
	 result = this->subtractBigInt(numb);
	 result->sign = false;
	 break;
      case 0:
	 result = new BigInt(0);
	 break;
      }
      numb->sign = true;
   } else {
      result = new BigInt(addBigInt(this->numb,numb->value()));
      result->sign = this->sign & numb->sign;
   }
   return result;
}

// Multiply two BigIntegers.
BigInt *BigInt::multiplyBigInt (BigInt *numb) {
   char *n1 = this->numb, *n2 = numb->value();
   if (atoi(n1) == 0 || atoi(n2) == 0) return new BigInt("0");
   
   char *result = "0";  // Accumulates the result
   int k=0;             // line multiply shifts k position
   for (int i=strlen(n2)-1 ; i >= 0 ;  i--) 
      result = addBigInt (result, shiftLeft(multiplyLine(n1, n2[i]), k++));
   
   // Strip leading 0s and add '-' if the product is negative
   char *p;
   for (p=result ; !('1' <= *p && *p <= '9') ; p++);
   BigInt *a = new BigInt(p);
   if (this->sign != numb->sign) a->sign = true;
   return a;
}
   
// returns 1 iff numb > this - only positives right now
bool BigInt::lessThanBigInt(BigInt *numb) {
   bool rev1 = false;  // rev1 = T if |this| < |numb|
   bool rev2 = false;  // rev2 = T if |this| > |numb|
   bool result = false;
   char *n1 = this->numb;
   char *n2 = numb->value();
   if (strlen(n1) == strlen(n2)) {
      for (size_t i=0 ; i < strlen(this->numb) ; i++) {
	 if (n2[i] > n1[i]) {
	    rev1 = true;
	    break;
	 } else if (n2[i] < n1[i]) {
	    rev2 = true;
	    break;
	 }
      }
   }
   if (numb->sign && !this->sign) result = false;
   else if (!numb->sign && this->sign) result = true;
   else if (numb->sign && this->sign) {
      if (strlen(n2) > strlen(n1)) result = false;
      else if (strlen(n2) == strlen(n1) && rev1) result = false;
      else if (strlen(n2) == strlen(n1) && rev2) result = true;
      else if (strlen(n2) == strlen(n1)) result = false;
      else result = true;
   } else {
      if (strlen(n2) > strlen(n1)) result = true;
      else if (strlen(n2) == strlen(n1) && rev1) result = true;
      else if (strlen(n2) == strlen(n1) && rev2) result = false;
      else result = false;
   }
   return result;
}

bool BigInt::absoluteLessThanBigInt(BigInt *numb) {
   if (strlen(this->numb) < strlen(numb->value())) return true;
   if (strlen(this->numb) > strlen(numb->value())) return false;
   char *n1 = this->numb;
   char *n2 = numb->value();
   for (size_t i=0 ; i < strlen(this->numb) ; i++) {
      if (n1[i] < n2[i]) return true;
      if (n1[i] > n2[i]) return false;
   }
   return false;
}

bool BigInt::equalsBigInt(BigInt *numb) {
   char *n1 = this->numb;
   char *n2 = numb->value();
   if (this->sign != numb->sign) return false;
   if (strlen(n1) == strlen(n2)) {
      for (size_t i=0 ; i < strlen(this->numb) ; i++) 
	 if (n2[i] != n1[i]) return false;
      return true;
   }
   return false;
}

char *BigInt::complement(char *numb, size_t digits) {
   size_t smaller_digits = strlen(numb);

   // pad the smaller on the front to make lengths equal
   char *tmp = new char[digits+10];  // safety
   int k=digits-1, p=smaller_digits-1;
   while (p >= 0) tmp[k--] = numb[p--];
   while (k >= 0) tmp[k--] = '0';
   
   // 1's complement all digits of the smaller number
   for (size_t i=0 ; i < digits ; i++) tmp[i] = '9' - tmp[i] + '0';
   tmp[digits] = 0;
   return tmp;
   
}

// Assume numb and this are both positive numbers so we do not have sign 
// problems - will be fixed along with multiplyBigInt and addBigInt.
// Completely inefficient!  Must do something about that eventually.
BigInt *BigInt::subtractBigInt(BigInt *numb) {
   size_t i=0;  char *m, *n;
   if (numb == NULL) return this;
   BigInt *result = NULL;
   if (this->sign && numb->sign) {
      switch (cmp(this->numb,numb->value())) {
      case -1:
	 // add the two numbers and then add 1 then
	 // find the first non-zero and truncate to that point
	 m = addBigInt(numb->value(),
		       complement(this->numb,strlen(numb->value())));
	 n = addBigInt(m,"1");
	 i = 1;
	 while (n[i] == '0' && i < strlen(n)) i++;
	 if (i == strlen(n)) result = new BigInt("0");
	 else result = new BigInt(&n[i]); 
	 result->sign = false;
	 break;
      case 1:
	 m = addBigInt(this->numb,
		       complement(numb->value(),strlen(this->numb)));
	 n = addBigInt(m,"1");
	 i = 1;
	 while (n[i] == '0' && i < strlen(n)) i++;
	 if (i == strlen(n)) result = new BigInt("0");
	 else {
	    result = new BigInt(&n[i]); 
	    result->sign = true;
	 }
	 break;
      case 0:
	 result = new BigInt(0);
      }
   } else if (!this->sign && !numb->sign) {
      switch (cmp(this->numb,numb->value())) {
      case -1:
	 // add the two numbers and then add 1 then
	 // find the first non-zero and truncate to that point
	 m = addBigInt(numb->value(),
		       complement(this->numb,strlen(numb->value())));
	 n = addBigInt(m,"1");
	 i = 1;
	 while (n[i] == '0' && i < strlen(n)) i++;
	 if (i == strlen(n)) result = new BigInt("0");
	 else {
	    result = new BigInt(&n[i]); 
	    result->sign = true;
	 }
	 break;
      case 1:
	 m = addBigInt(this->numb,
		       complement(numb->value(),strlen(this->numb)));
	 n = addBigInt(m,"1");
	 i = 1;
	 while (n[i] == '0' && i < strlen(n)) i++;
	 if (i == strlen(n)) result = new BigInt("0");
	 else result = new BigInt(&n[i]); 
	 result->sign = false;
	 break;
      case 0:
	 result = new BigInt(0);
      }
   } else {
      result = new BigInt(addBigInt(this->numb,numb->value()));
      result->sign = this->sign & !numb->sign;
   }
   return result;
}

// Divide this by numb - return the remainder
// Assume both numbers are positive for now.
BigInt *BigInt::modBigInt(BigInt *numb) {
   BigInt *tmp = divideBigInt(numb);
   tmp = tmp->multiplyBigInt(numb);
   return subtractBigInt(tmp);
}

// Divide this by numb - but truncate any remainder
// Assume both numbers are positive for now.
BigInt *BigInt::divideBigInt(BigInt *numb) {
   if (absoluteLessThanBigInt(numb)) return new BigInt("0");
   if (equalsBigInt(numb)) return new BigInt("1");

   BigInt *tm = new BigInt("1");
   BigInt *accum = new BigInt("0");
   BigInt *numerator = new BigInt(this->numb);
   BigInt *denominator = new BigInt(numb->value());
   BigInt *multiplier = new BigInt("1");
   BigInt *divisor = denominator;
   BigInt *td = denominator;
   while (divisor->lessThanBigInt(numerator)) {
      tm = multiplier;
      td = divisor;
      divisor = divisor->multiplyBigInt(new BigInt("10"));
      multiplier = multiplier->multiplyBigInt(new BigInt("10")); 
   }
   while (true) {
      numerator = numerator->subtractBigInt(td);
      accum = accum->addBigInt(tm);
      if (numerator->lessThanBigInt(denominator)) break;
      while (numerator->lessThanBigInt(td)) {
	 if ((td = td->divideByTen()) == NULL) return accum;
	 tm = tm->divideByTen();
      }
   }
   if (this->sign != numb->sign && !accum->equalsBigInt(new BigInt("0"))) 
       accum->sign = true; else accum->sign = false;
   return accum;
}

int BigInt::sizeOf() { return strlen(numb); }

ostream & operator<<(ostream & out, BigInt *bi) {
   if (bi->sign)
      out << '-' << bi->value();
   else
      out << bi->value();
   return out;
}

ostream & operator<<(ostream & out, BigInt &bi) {
   if (bi.sign)
      out << '-' << bi.value();
   else
      out << bi.value();
   return out;
}

BigInt & BigInt::operator*(BigInt &numb) {  return *multiplyBigInt(&numb); }

BigInt & BigInt::operator*(BigInt *numb) {  return *multiplyBigInt(numb); }

BigInt & BigInt::operator/(BigInt &numb) {  return *divideBigInt(&numb); }

BigInt & BigInt::operator/(BigInt *numb) {  return *divideBigInt(numb); }

BigInt & BigInt::operator+(BigInt &numb) {  return *addBigInt(&numb); }

BigInt & BigInt::operator+(BigInt *numb) {  return *addBigInt(numb); }

BigInt & BigInt::operator-(BigInt &numb) {  return *subtractBigInt(&numb); }

BigInt & BigInt::operator-(BigInt *numb) {  return *subtractBigInt(numb); }

BigInt & BigInt::operator%(BigInt &numb) {  return *modBigInt(&numb); }

BigInt & BigInt::operator%(BigInt *numb) {  return *modBigInt(numb); }

bool BigInt::operator<(BigInt &numb) {  return lessThanBigInt(&numb); }

bool BigInt::operator<(BigInt *numb) {  return lessThanBigInt(numb); }

BigInt & BigInt::operator=(BigInt &numb) { 
   this->numb = new char[strlen(numb.value())+1];
   strcpy(this->numb,numb.value());
   sign = numb.sign;
   return *this;
}

BigInt::~BigInt() {
   delete numb;
}