package bigints;

/** The BigInt class is a class that allows us to store and manipulate arbitrarily
 * large integers. It does this by storing the individidual decimal digits in an
 * array. Since the array can be made arbitrarily large, this allows use to
 * represent positive integers of any length.
 * 
 * Note that I have made absolutely no effort to optimize this class in any
 * way. Some things that could be done to make the class more efficient include
 * - use an array of Byte instead of array of int to store digits
 * - resize the digits array to twice its existing size whenever we need to
 *   resize it.
 */

public class BigInt {
  // The decimal digits in a BigInt are stored in this array. The least significant
  // digit (the rightmost digit in the decimal number) is in position 0 in this
  // array, and the remaining digits are stored in right-to-left order.
  private int[] digits; 
  
  // Convenient helper method to convert a string into an array of decimal 
  // digits.
  private void initializeFromString(String value) {
     digits = new int[value.length()];
    for(int n = 0;n < value.length();n++) {
      char ch = value.charAt(n);
      int x = ch - '0';
      digits[digits.length-1-n] = x;
    }
  }
  
  // Default constructor - makes a completely empty number
  BigInt() {
    digits = new int[0];
  }
  
  public BigInt(String value) {
   initializeFromString(value);
  }

  public BigInt(int value) {
    String str = Integer.toString(value);
    initializeFromString(str);
  }
  
  public String toString() {
    StringBuilder builder = new StringBuilder();
    for(int n = digits.length - 1;n >= 0;n--) {
      char ch = (char) (digits[n] + '0');
      builder.append(ch);
    }
    return builder.toString();
  }
  
  public int toInt() {
    String str = toString();
    return Integer.parseInt(str);
  }
  
  // pos == 0 is the rightmost digit, pos == digitCount()-1 is the 
  // leftmost digit.
  public int getDigit(int pos) {
    if(pos >= digits.length)
      return 0;
    return digits[pos];
  }
  
   // pos == 0 is the rightmost digit, pos == digitCount()-1 is the 
  // leftmost digit.
  public void setDigit(int pos,int value) {
    if(pos >= digits.length) {
      // Make a new, larger array to accomodate the value
      int[] temp = new int[pos+1];
      // Fill it with 0s
      for(int n = 0;n < temp.length;n++)
        temp[n] = 0;
      // Copy over the old digits
      for(int n = 0;n < digits.length;n++)
        temp[n] = digits[n];
      // Replace the original array with digits.
      digits = temp;
    }
    digits[pos] = value;
  }
  
  public int digitCount() {
    return digits.length;
  }
  
  public static BigInt add(BigInt a,BigInt b) {
    BigInt result = new BigInt();
    int carry = 0;
    
    int length = a.digitCount();
    if(b.digitCount() > length)
      length = b.digitCount();
    
    for(int n = 0;n < length;n++) {
      int total = a.getDigit(n) + b.getDigit(n) + carry;
      if(total >= 10) {
        carry = 1;
        total = total % 10;
      }
      else 
        carry = 0;
      result.setDigit(n,total);
    }
    if(carry == 1)
      result.setDigit(length, carry);
    
    return result;
  }
  
     public static void main(String[] args) {
        BigInt a = new BigInt(1);
        for(int n = 0;n < 500;n++) {
          System.out.println(a.toString());
          a = BigInt.add(a, a);
        }
    }

}