# 1.2. Implementation We are going to create a class called [`LongInteger`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/algebraic/LongInteger.java) inheriting `SignedNumeral` that can store an indefinite size of an integer value beyond the [primitive types](https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html) such as `int` and `long`. > What is so special about primitive data types in Java? {% hint style="info" %} Java SE provides a similar class called [`BigInteger`](https://download.java.net/java/GA/jdk14/docs/api/java.base/java/math/BigInteger.html) although the implementations of `LongInteger`and`BigInteger`are completely independent. {% endhint %} ## Field Let us declare the member field `digits` that is an array of bytes holding the values of this integer: {% code lineNumbers="true" %} ```java public class LongInteger extends SignedNumeral { /** The values of this integer (excluding the sign). */ protected byte[] digits; ... ``` {% endcode %} * `L1`: `LongInteger` is passed to specify the generic type `T` in `SignedNumeral`. The `i`'th dimension of `digits` is the `i`'th least significant digit in the integer such that the integer `12345` would be stored as `digits = {5, 4, 3, 2, 1}`, which makes it convenient to implement the arithmetic methods, `add()` and `multiply()`. > Is the array of bytes the most efficient way of storing a long integer? ## Constructors Let us define the following three constructors: {% code lineNumbers="true" %} ```java /** Creates a long integer with the default value of "0". */ public LongInteger() { this("0"); } /** * Creates a long integer by copying the specific object. * @param n the object to be copied. */ public LongInteger(LongInteger n) { super(n.sign); digits = Arrays.copyOf(n.digits, n.digits.length); } /** * Creates a long integer with the specific sign and values. * @param n the sign and values to be set. * @see #set(String) */ public LongInteger(String n) { set(n); } ``` {% endcode %} * `L2`: the *default* constructor that initializes this integer with `0` by calling the constructor in `L20`. * `L10`: a *copy* constructor that initializes this integer with `n`. * `super()`: calls the corresponding constructor in the super class, `SignedNumeral`. * [`Arrays.copyOf()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html#copyOf\(byte\[],int\)): creates a new array by copying `n.digits`. * `L20`: a constructor that initializes this integer with `n` by passing it to the `set()` method. > Do the constructors in `L10` and `L20` call any constructor in the super class? `Arrays.copyOf()` is a [static method](https://docs.oracle.com/javase/tutorial/java/javaOO/classvars.html) referenced by the class type `Arrays`, not an object. Java provides many classes with static methods that are commonly used (e.g., [`Arrays`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html), [`Collections`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Collections.html)). > Can you call non-static methods or fields in the body of a static method? {% hint style="info" %} The `static` keyword must not be abused to quickly fix compile errors unless it is intended. {% endhint %} ## Method: `set()` Let us define the `set()` method that takes a string and sets the sign and the value of this integer: {% code lineNumbers="true" %} ```java /** * Sets the sign and values of this integer. * @param n the sign and values to be set. * @throws NullPointerException when `n` is null. * @throws InvalidParameterException when `n` contains non-digit character * except for the first character that can be [+-\d]. */ public void set(String n) { // 'n' must not be null if (n == null) throw new NullPointerException(); // set this.sign sign = switch (n.charAt(0)) { case '-' -> { n = n.substring(1); yield Sign.NEGATIVE; } case '+' -> { n = n.substring(1); yield Sign.POSITIVE; } default -> Sign.POSITIVE; }; // set this.digits digits = new byte[n.length()]; for (int i = 0, j = n.length() - 1; i < n.length(); i++, j--) { byte v = (byte)(n.charAt(i) - 48); if (0 > v || v > 9) { String s = String.format("%d is not a valid value", v); throw new InvalidParameterException(s); } digits[j] = v; } } ``` {% endcode %} * `L1-7`: javadoc comments. * `L4`: this method throws [`NullPointerException`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/NullPointerException.html) if `n` is null. * `L5`: this method throws [`InvalidParameterException`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/security/InvalidParameterException.html) if the format of `n` is invalid. * `L10-11`: throws the `NullPointerException`. * `L14-18`: checks the first character of `n` and sets `this.sign` using the [switch](https://docs.oracle.com/en/java/javase/14/language/switch-expressions.html) expression. * `String` member methods: [`charAt()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/String.html#charAt\(int\)), [`substring()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/String.html#substring\(int\)). * `yield`: returns the value of this switch statement for the condition (introduced in Java 14). * `L21-30`: sets the value of `n` to `this.digits` . * `L23`: for-loop can handle multiple variables such as `i` and `j`. * `L24`: gets the [ASCII](https://en.wikipedia.org/wiki/ASCII) value of `n.charAt(i)`. * `L25-28`: throws the `InvalidParameterException` if `v` is not a digit. * `L29`: stores the value in the reverse order. * `L27`: [`String.format()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/String.html#format\(java.lang.String,java.lang.Object...\)) is a static method in `String`. > When should we use [`throw`](https://docs.oracle.com/javase/tutorial/essential/exceptions/throwing.html) statements over [`try..catch`](https://docs.oracle.com/javase/tutorial/essential/exceptions/handling.html) blocks for error handling and vice versa? {% hint style="info" %} This type of method is called a *setter*. Java encourages making member fields *private* and creating getters and setters to access the fields for [encapsulation](https://en.wikipedia.org/wiki/Encapsulation_\(computer_programming\)), which is not necessarily encouraged by other languages. {% endhint %} ## Method: `add()` Let us override the `add()` method that calls two helper methods: ```java @Override public void add(LongInteger n) { if (sign == n.sign) addSameSign(n); else addDifferentSign(n); } ``` * `L3-4`: adds `n` to this integer that has the same sign by calling `addSameSign()`. * `L5-6`: adds `n` to this integer that has a different sign by calling `addDifferentSign()`. The following shows an implementation of `addSameSign()` based on the simple arithmetic: {% code lineNumbers="true" %} ```java /** * Adds the specific integer that has the same sign as this integer. * @param n the integer to be added with the same sign. */ protected void addSameSign(LongInteger n) { // copy this integer to result[] int m = Math.max(digits.length, n.digits.length); byte[] result = new byte[m + 1]; System.arraycopy(digits, 0, result, 0, digits.length); // add n to result for (int i = 0; i < n.digits.length; i++) { if (i < n.digits.length) result[i] += n.digits[i]; if (result[i] >= 10) { result[i] -= 10; result[i + 1] += 1; } } // set this.digits digits = result[m] == 0 ? Arrays.copyOf(result, m) : result; } ``` {% endcode %} * `L7-9`: creates the byte array `result` by copying values in this integer. * `L8`: the dimension of `result` can be 1 more than `m` after the addition. * Static methods: [`Math.max()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/StrictMath.html#max\(int,int\)), [`System.arraycopy()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/System.html#arraycopy\(java.lang.Object,int,java.lang.Object,int,int\)). * `L12-19`: adds `n` to `results` (if exists) from the least significant digit. * `L15-18`: pass a carry to the next digit. * `L22`: trims the most significant digit if it is `0`. > What are tradeoffs to make the size of `result` to be `m` instead of `m+1` and vice versa? The following shows `addDifferentSign()` that throws [`UnsupportedOperationException`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/UnsupportedOperationException.html): {% code lineNumbers="true" %} ```java /** * Adds the specific integer that has a different sign from this integer. * @param n the integer to be added with a different sign */ protected void addDifferentSign(LongInteger n) { throw new UnsupportedOperationException(); } ``` {% endcode %} The implementation of `addDifferentSign()` is quite similar to `addSameSign()` although it involves a few more logics. We will leave this as an [exercise](/dsa-java/java-essentials/exercises.md). {% hint style="info" %} In practice, `addSameSign()`and `addDifferentSign()` should be *private*. We made them *protected* for exercise purposes. {% endhint %} ## Method: `multiply()` Let us override the `multiply()` method: {% code lineNumbers="true" %} ```java @Override public void multiply(LongInteger n) { // set this.sign sign = (sign == n.sign) ? Sign.POSITIVE : Sign.NEGATIVE; // multiply this and n and save it to result byte[] result = new byte[digits.length + n.digits.length]; for (int i = 0; i < digits.length; i++) { for (int j = 0; j < n.digits.length; j++) { int k = i + j, prod = digits[i] * n.digits[j]; result[k] += prod; result[k + 1] += result[k] / 10; result[k] %= 10; } } // set this.digits int m; for (m = result.length - 1; m > 0; m--) if (result[m] != 0) break; digits = ++m < result.length ? Arrays.copyOf(result, m) : result; } ``` {% endcode %} * `L4`: sets the sign after the multiplication. * `L7-15`: multiplies `n` to this integer: * `L7`: the max-dimension of `results` is `digits.length + n.digits.length`. * `L12-13`: pass a carry to the next digit. * `L18-20`: trims the most significant digit iteratively if it is `0`. * `L20`: `++m` increments `m` before the comparison. > What is the worst-case complexity of the `multiply()` method? ## Method: `main()` Let us create a runnable class called [`LongIntegerRun`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/algebraic/LongIntegerRun.java) that contains the main method: > Can we define the main method in `LongInteger` instead without creating `LongIntegerRun`? {% code lineNumbers="true" %} ```java public class LongIntegerRun { static public void main(String[] args) { System.out.println(args); } } ``` {% endcode %} * `L2`: the parameter `args` �is passed from the command line. > Why does the main method need to be *static*? This prints something like the following: ``` [Ljava.lang.String;@d716361 ``` * `[`: one-dimensional array. * `L`: the element of this array is an object. * `java.lang.String`: the type of object. * `d716361`: the hash code of this array in hexadecimal. > What is the hash code of an object? Every object implicitly inherits [`Object`](https://docs.oracle.com/javase/tutorial/java/IandI/objectclass.html) that defines a few member methods including [`toString()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/Object.html#toString\(\)), which gets called automatically by the `println()` method to retrieve the string representation of this object. We can use the helper method [`Arrays.toString()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html#toString\(java.lang.Object\[]\)) that gives a more readable representation: {% code lineNumbers="true" %} ```java static public void main(String[] args) { System.out.println(Arrays.toString(args)); } ``` {% endcode %} > How is the `Arrays.toString()` method implemented? Since no argument is passed to the main method at the moment, this prints an empty array: ```java [] ``` If you set the arguments to `123 -456` using the `[Run - Edit Configurations - Program arguments]`setting, it prints the following array: ``` [123, -456] ``` Given those two arguments, we can create two integers: {% code lineNumbers="true" %} ```java static public void main(String[] args) { LongInteger a = new LongInteger(args[0]); LongInteger b = new LongInteger(args[1]); System.out.println(a); System.out.println(b); } ``` {% endcode %} This prints something like the following, which are returned by `a.toString()`: ``` edu.emory.cs.algebraic.LongInteger@4d7e1886 edu.emory.cs.algebraic.LongInteger@3cd1a2f1 ``` > How is the `toString()` method implemented in the `Object` class? ## Method: `toString()` To print a more readable representation, we need to override the `toString()` method in `LongInteger`: {% code lineNumbers="true" %} ```java public class LongInteger extends SignedNumeral { ... @Override public String toString() { StringBuilder build = new StringBuilder(); if (sign == Sign.NEGATIVE) build.append("-"); for (int i = digits.length - 1; i >= 0; i--) build.append(digits[i]); return build.toString(); } ... ``` {% endcode %} * `L5`: [`StringBuilder`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/StringBuilder.html) provides an efficient way of concatenating different data types into one string. > What are the advantages of using `StringBuilder` instead of concatenating values with the `+` operator as follows: > > {% code lineNumbers="true" %} > > ```java > String s = ""; > if (sign == Sign.NEGATIVE) s += "-"; > for (int i = digits.length - 1; i >= 0; i--) > s += digits[i]; > return s; > ``` > > {% endcode %} Given the overridden method, the above main method now prints the following: ``` 123 -456 ``` > What are the advantages of overriding `toString()` instead of creating a new method with the same code, and calling the new method to get the string representation of `LongInteger`? ## Method: `compareTo()` Java does not allow [operator overloading](https://en.wikipedia.org/wiki/Operator_overloading), so it is not possible to use logical operators to compare the two integers above, `a` and `b`: ```java boolean c = a < b; // gives a compile error ``` In fact, any object that is comparable must inherit the interface [`Comparable`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/Comparable.html) as follows: ```java public class LongInteger extends SignedNumeral implements Comparable { ... } ``` * `L2`: `LongInteger` is passed to `Comparable` as a generic type. > Is `extends` always used to inherit a class whereas `implements` is used to inherit an interface? The `Comparable` interface contains one abstract method called [`compareTo()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/lang/Comparable.html#compareTo\(T\)) that returns a negative value if this object is smaller than `n`, a positive value if this object is greater than `n`, and zero if this object equals to `n`. The `compareTo()` method must be overridden by the `LongInteger` class: {% code lineNumbers="true" %} ```java @Override public int compareTo(LongInteger n) { if (isPositive()) return n.isNegative() ? 1 : compareAbs(n); else return n.isPositive() ? -1 : -compareAbs(n); } ``` {% endcode %} The `compareAbs()` method compares the absolute values of `this` and `n`: {% code lineNumbers="true" %} ```java /** * @param n the object to be compared. * @return a negative integer, zero, or a positive integer as the absolute value of this object is * less than, equal to, or greater than the absolute value of the specified object. */ public int compareAbs(LongInteger n) { int diff = digits.length - n.digits.length; if (diff == 0) { for (int i = digits.length - 1; i >= 0; i--) { diff = digits[i] - n.digits[i]; if (diff != 0) break; } } return diff; } ``` {% endcode %} * `L7`: if `digits` has more dimensions, its absolute value is greater. * `L10-13`: compares the significant digits iteratively. > Is it safe to use the same variable `i` to iterate both `digits` and `n.digits`? Once `LongInteger` properly inherits `Comparable` by overriding `compareTo()`, objects instantiated by this class can be compared using many built-in methods. {% code lineNumbers="true" %} ```java static public void main(String[] args) { List list = new ArrayList<>(); list.add(new LongInteger("78")); list.add(new LongInteger("-45")); list.add(new LongInteger("0")); list.add(new LongInteger("6")); list.add(new LongInteger("-0")); list.add(new LongInteger("-123")); list.sort(Comparator.naturalOrder()); System.out.println(list); list.sort(Comparator.reverseOrder()); System.out.println(list); } ``` {% endcode %} * `L2`: [`ArrayList`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/ArrayList.html) is a specific implementation of the interface [`List`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/List.html). * All collections in Java inheriting [`AbstractCollection`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/AbstractCollection.html) uses generics. * `<>`: the *diamond* operator that infers the generic type from its declaration. * `L11`: sorts the list in ascending order using [`sort()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/List.html#sort\(java.util.Comparator\)) and [`Comparator.naturalOrder()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Comparator.html#naturalOrder\(\)). * `L14`: sorts the list in descending order using [`sort()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/List.html#sort\(java.util.Comparator\)) and [`Comparator.reverseOrder()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Comparator.html#reverseOrder\(\)). > What is the advantage of declaring `list` as `List` instead of `ArrayList`?\ > What kind of sorting algorithm does `Collections.sort()` use? The above code prints the following sorted lists: ``` [-123, -45, -0, 0, 6, 78] [78, 6, 0, -0, -45, -123] ``` > What would be the case that needs to distinguish `-0` from `0`? --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://emory.gitbook.io/dsa-java/java-essentials/implementation.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.