package pr01;

public class VeryBigInteger {

   // we should be able to change the base by modifying only these static
   // variables
   private static String digits = "0123456789";
   private static int base = 10;

   private int[] vals;
   private boolean plus;
   private boolean extraCredit1 = true;
   private boolean extraCredit2 = true;

   public VeryBigInteger(String numString) {
      plus = true;
      int numSkip = 0;
      if (numString.startsWith("-")) {
         plus = false;
         numSkip = 1;
      }
      else if (numString.startsWith("+"))
         numSkip = 1;
      if (extraCredit1) {
         for (int i = numSkip; i < numString.length() - 1; i++)
            if (numString.charAt(i) == '0')
               numSkip++;
            else
               break;
      }
      vals = new int[numString.length() - numSkip];
      for (int i = 0; i < vals.length; i++) {
         vals[i] =
             digits.indexOf(numString.charAt(numString.length() - i - 1));
         if (vals[i] == -1) // replace any invalid digits by 0.
            vals[i] = 0;
      }
   }

   // assumes that vals is valid, and removes leading 0's.
   // zero is represented by an array with a single zero digit.
   private VeryBigInteger(int[] vals) {
      int countLeading = 0;
      plus = true;
      if (!extraCredit1) {
         this.vals = vals;
         fixSign();
         return;
      }
      if ((vals.length == 1) || (vals[vals.length - 1] != 0))
         this.vals = vals;
      else {
         for (int i = 0; i < vals.length - 1; i++)
            if (vals[vals.length - i - 1] == 0)
               countLeading++;
            else
               break;
      }
      // this.vals = vals;
      this.vals = new int[vals.length - countLeading];
      for (int i = 0; i < this.vals.length; i++)
         this.vals[i] = vals[i];
      fixSign(); // do not allow -0
   }

   // do not allow -0
   private void fixSign() {
      if ((vals.length == 1) && (vals[0] == 0))
         plus = true;
   }

   public VeryBigInteger add(VeryBigInteger op2) {
      VeryBigInteger newVBI;
      if (plus == op2.plus) {
         newVBI = addMagnitude(op2);
         newVBI.plus = plus;
      } else if (greaterMagnitude(op2)) {
         newVBI = subtractMagnitude(op2);
         newVBI.plus = plus;
      } else {
         newVBI = op2.subtractMagnitude(this);
         newVBI.plus = op2.plus;
      }
      newVBI.fixSign();
      return newVBI;
   }

   public VeryBigInteger subtract(VeryBigInteger op2) {
      VeryBigInteger newVBI;
      if (plus != op2.plus) {
         newVBI = addMagnitude(op2);
         newVBI.plus = plus;
      } else if (greaterMagnitude(op2)) {
         newVBI = subtractMagnitude(op2);
         newVBI.plus = plus;
      } else {
         newVBI = op2.subtractMagnitude(this);
         newVBI.plus = !op2.plus;
      }
      newVBI.fixSign();
      return newVBI;
   }

   public VeryBigInteger multiply(VeryBigInteger op2) {
      VeryBigInteger newVBI;
      newVBI = multiplyMagnitude(op2);
      newVBI.plus = plus && op2.plus || !plus && !op2.plus;
      return newVBI;
   }

   public VeryBigInteger[] divideAndRemainder(VeryBigInteger op2) {
      VeryBigInteger[] result;
      result = divideAndRemainderMagnitude(op2);
      result[0].plus = plus && op2.plus || !plus && !op2.plus;
      result[1].plus = plus;
      return result;
   }

   // this asumes that a VeryBigInteger does not have leading 0's except for 0
   private VeryBigInteger[] divideAndRemainderMagnitude(VeryBigInteger op2) {
      int[] quotient;
      int[] remainder;
      VeryBigInteger[] result;
      result = new VeryBigInteger[2];
      int maxShift;
      if (!extraCredit2) {
         result[0] = new VeryBigInteger("0");
         result[1] = new VeryBigInteger("0");
         return result;
      }
      remainder = new int[vals.length];
      for (int i = 0; i < vals.length; i++)
         remainder[i] = vals[i];
      maxShift = vals.length - op2.vals.length;
      if (maxShift < 0) {
         result[0] = new VeryBigInteger("0");
         result[1] = new VeryBigInteger(remainder);
         return result;
      }
      quotient = new int[maxShift + 1];
      for (int i = maxShift; i >= 0; i--)
         quotient[i] = divideOne(remainder, op2.vals, i);
      result[0] = new VeryBigInteger(quotient);
      result[1] = new VeryBigInteger(remainder);
      return result;
   }

   // shift the denom shift place and subtract as many times
   // as possible, returning the number of times.
   // Note: this modifies num only.
   private int divideOne(int[] num, int[] denom, int shift) {
      int count = 0;
      while (testSubtract(num, denom, shift)) {
         subtractOne(num, denom, shift);
         count++;
      }
      return count;
   }

   // assumes that num is bigger than denom by at least shift
   private boolean testSubtract(int[] num, int[] denom, int shift) {
      if ((num.length > denom.length + shift)
            && (num[denom.length + shift] != 0))
         return true;
      for (int i = 0; i < denom.length; i++) {
         if (num[denom.length + shift - i - 1] > denom[denom.length - i - 1])
            return true;
         if (num[denom.length + shift - i - 1] < denom[denom.length - i - 1])
            return false;
      }
      return true;
   }

   private void subtractOne(int[] num, int[] denom, int shift) {
      int len;
      int carry = 0;
      int temp;
      len = denom.length;
      for (int i = 0; i < len; i++) {
         num[shift + i] = num[shift + i] - denom[i] + carry;
         if (num[shift + i] < 0) {
            num[shift + i] += base;
            carry = -1;
         } else
            carry = 0;
      }
      if (carry != 0)
         num[shift + len]--;
   }

   private VeryBigInteger multiplyMagnitude(VeryBigInteger op2) {
      int[] newVals = new int[vals.length + op2.vals.length];
      for (int i = 0; i < newVals.length; i++)
         newVals[i] = 0;
      for (int i = 0; i < op2.vals.length; i++)
         addMult(op2.vals[i], i, vals, newVals);
      return new VeryBigInteger(newVals);
   }

   // assumes previous calls used smaller shift
   private void addMult(int mult, int shift, int[] source, int[] dest) {
      int carry = 0;
      for (int i = 0; i < source.length; i++) {
         dest[i + shift] = dest[i + shift] + mult * source[i] + carry;
         carry = dest[i + shift] / base;
         dest[i + shift] = dest[i + shift] - carry * base;
      }
      dest[source.length + shift] = carry;

   }

   // return true if this magnitude is greater or equal to op2
   private boolean greaterMagnitude(VeryBigInteger op2) {
      int count1;
      int count2;
      count1 = countSignificantDigits();
      count2 = op2.countSignificantDigits();
      if (count1 > count2)
         return true;
      if (count1 < count2)
         return false;
      for (int i = count1 - 1; i >= 0; i--)
         if (vals[i] != op2.vals[i])
            return vals[i] >= op2.vals[i];
      return true;
   }

   private int countSignificantDigits() {
      int i = vals.length - 1;
      while ((vals[i] == 0) && (i > 1))
         i--;
      return i + 1;

   }

   private VeryBigInteger addMagnitude(VeryBigInteger op2) {
      int[] newVals;
      int len;
      int carry = 0;
      len = Math.max(vals.length, op2.vals.length) + 1;
      newVals = new int[len];
      for (int i = 0; i < len; i++) {
         newVals[i] = carry;
         if (i < vals.length)
            newVals[i] = newVals[i] + vals[i];
         if (i < op2.vals.length)
            newVals[i] = newVals[i] + op2.vals[i];
         if (newVals[i] >= base) {
            newVals[i] = newVals[i] - base;
            carry = 1;
         }
         else
            carry = 0;
      }
      return new VeryBigInteger(newVals);
   }

   // assumes that this one if bigger than the other one
   private VeryBigInteger subtractMagnitude(VeryBigInteger op2) {
      int[] newVals;
      int len;
      int carry = 0;
      len = vals.length;
      newVals = new int[len];
      for (int i = 0; i < len; i++) {
         newVals[i] = carry;
         if (i < vals.length)
            newVals[i] = newVals[i] + vals[i];
         if (i < op2.vals.length)
            newVals[i] = newVals[i] - op2.vals[i];
         if (newVals[i] < 0) {
            newVals[i] = newVals[i] + base;
            carry = -1;
         } else
            carry = 0;
      }
      return new VeryBigInteger(newVals);
   }

   public String toString() {
      String s = "";
      for (int i = 0; i < vals.length; i++)
         s = digits.charAt(vals[i]) + s;
      if (!plus)
         s = "-" + s;
      return s;
   }

   private String arrayToString(int[] a) {
      String s = "";
      for (int i = 0; i < a.length; i++)
         s = s + a[a.length - i - 1] + " ";
      return s;
   }

}