> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/java-essentials/implementation.md). # 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`?