import java.util.ArrayList;  // omit if using an array instead

/* UnboundedNatural.java
** Authors: R. McCloskey and < STUDENT's NAME >
** For: Prog. Assg. #1, CMPS 144
** Date: February 2026
** Collaborated with: ...
** Known Defects: ...
**
** An instance of this class represents an immutable natural number
** (i.e., nonnegative integer).  The arithmetic operations addition,
** subtraction, and multiplication are supported (in the form of
** "generator" methods), as is equality testing.
**
** What makes this class interesting is that there is no fixed upper bound 
** upon the value that an instance of the class can represent, making it 
** unlike any primitive data type used for representing integers (i.e., 
** byte, short, int and long) and unlike the corresponding "wrapper" 
** classes (java.lang.Integer, etc.)
*/
public class UnboundedNatural {

   // class constants
   // ---------------

   public final static UnboundedNatural ZERO = new UnboundedNatural("0");
   public final static UnboundedNatural ONE = new UnboundedNatural("1");


   // instance variables
   // ------------------

   protected ArrayList<Integer> digits; // stores the digits from least
                                        // to most significant
   // alternative:
   // protected int[] digits;

   // class invariant (recommended): 
   //   'digits' includes no elements that correspond to leading zeros


   // constructors
   // ------------

   /* Initializes this object so that it represents the number described
   ** by the given string, which is assumed to be an unsigned decimal
   ** numeral (meaning that each of its characters is in the range '0'..'9').
   ** Example: If the given string is "67823", this object should become
   ** one that represents the number denoted by 67823.
   */
   public UnboundedNatural(String digitStr) {
      // STUB
   }


   /* Initializes this object so that it represents the given value of type int.
   ** pre: num >= 0
   */
   public UnboundedNatural(int num) { this(num + ""); }
   

   /* Initializes this object to be that whose instance variable 'digits'
   ** is a clone of the provided value.
   ** Meant for use only within this class and descendant classes (and
   ** NOT by client programs).
   */
   protected UnboundedNatural(ArrayList<Integer> digits) {
      this.digits = (ArrayList<Integer>)(digits.clone());
      trimLeadingZeros();
   }
   // Alternative if instance variable 'digits' is of type int[]:
   //protected BigIntUnsigned(int[] otherDigits) {
   //   this.digits = otherDigits.clone();
   //   trimLeadingZeros();
   //}


   // observers
   // ---------

   /* Returns the decimal numeral corresponding to this object's value.
   ** E.g., if this object represents 5689, the string returned should be 
   ** "5689".  A leading zero should appear only if this object represents
   ** zero.
   */
   public String toString() {
      String result;
      final int N = this.numDigits();
      if (N == 0) { result = "0"; }
      else {
         StringBuilder s = new StringBuilder(this.numDigits());
         for (int k = this.numDigits(); k != 0; k--) {
            s = s.append(digitAt(k-1));
         } 
         result = s.toString();
      }
      return result;
   }

   /* Reports whether or not 'this' and 'other' represent the same
   ** natural number.
   */
   public boolean equals(UnboundedNatural other) {
      // STUB
      return true;
   }

   // mutators
   // --------

   //  None


   // generators
   // ----------

   /* Returns a new instance of this class that represents the sum of
   ** this object and the other one (i.e., this one plus the other one)
   */
   public UnboundedNatural plus(UnboundedNatural other) {
      // The # of digits in the sum is at most one more than the # of digits
      // in the larger of 'this' and 'other'
      final int numDigitsMax = 1 + Math.max(this.numDigits(), other.numDigits());
      ArrayList<Integer> resultDigits = new ArrayList<Integer>(numDigitsMax);


      // < MISSING CODE >


      return new UnboundedNatural(resultDigits);
   }


   /* Returns a new instance of this class that represents the difference
   ** of this object and the other one (i.e., this one minus the other one).
   ** pre: The number represented by 'this' object must not be less than that 
   **      represented by 'other'
   */
   public UnboundedNatural minus(UnboundedNatural other) {
      // The # of digits in the result is at most the # of digits in 'this'.
      final int numDigitsMax = this.numDigits();
      ArrayList<Integer> resultDigits = new ArrayList<Integer>(numDigitsMax);


      // < MISSING CODE >


      return new UnboundedNatural(resultDigits);
   }


   /* Returns a new instance of this class that represents the product of
   ** the numbers represented by this object and the other one (i.e., this 
   ** one times the other one).  The code is based upon this recursive
   ** description of multiplication:
   **             { 0                   if a=0                 (1)
   **     a * b = { (a/2)*(2b)          if a>0 and a is even   (2)
   **             { ((a-1)/2)*(2b) + b  if a>0 and a is odd    (3)
   **
   ** Note that (3) can be written as (a/2)*(2b) + b because
   ** (a-1)/2 = a/2 when a is positive (and '/' denotes integer division).
   */
   public UnboundedNatural times(UnboundedNatural other) {
      // STUB
      return null;
   }


   // utilities
   // ---------

   /* Given a decimal digit (i.e., a char value in the range '0'..'9'),
   ** returns the corresponding value of type int.  The code exploits the
   ** fact that the numeric codes used for representing decimal digits are
   ** consecutive (e.g., '0' = 48, '1' = 49, ..., '9' = 57) and that Java
   ** allows one char value to be subtracted from another, producing an int.
   */
   protected int digitCharToInt(char digit) { return digit - '0'; }


   /* Removes any elements of 'digits' that correspond to leading zero's.
   */
   protected void trimLeadingZeros() {
      int k = digits.size() - 1;
      while (k != -1  &&  digits.get(k) == 0) {
         digits.remove(k);
         k--;
      }
   }

   /* Returns the number of digits in the (decimal) numeral representing
   ** this object, not including leading zeros.
   */
   protected int numDigits() { 
      // This code assumes that 'digits' includes no leading zeros.
      return digits.size();
      // If using an int[] array:  return digits.length
   }

   /* Returns the digit in the 10^k column of the decimal numeral
   ** corresponding to this object.
   ** pre: k >= 0
   */
   protected int digitAt(int k) {
      if (digits.size() <= k) { return 0; }
      else { return digits.get(k); }
   }

   /* Reports whether or not this natural number is even.
   */
   protected boolean isEven() { return this.digitAt(0) % 2 == 0; }

   /* Returns a new instance of this class that represents twice
   ** the number represented by this object.
   */
   protected UnboundedNatural doubleOf() {
      // STUB
      return null;
   }

   /* Returns the floor of half of this natural number.
   */
   protected UnboundedNatural halfOf() {
      // STUB
      return null;
   }

}