In this fourth lab, we continue modifying the source code for the Polynomial class from the first two labs to allow equality and ordering comparisons to take place between objects of that type. Modify the class definition so that this class now implements Comparable. Then write the following methods to implement equality and ordering comparisons.

@Override public boolean equals(Object other)

Returns true if the other object is also a Polynomial of the exact same degree as this, so that the coefficients of this and other polynomial are pairwise equal. If the other object is anything else, this method returns false. (You can actually implement this method last after implementing the method compareTo, since at that point its logic will be a one-liner after the instanceof check.)

@Override public int hashCode()

Whenever you override the equals method in a subclass, you should also override the hashCode method to ensure that two objects that their equals method considers to be equal will also have equal hash codes. This method computes and returns the hash code of this polynomial, used to store and find this object inside some instance of HashSet, or some other hash table based data structure. This hash code is computed by adding up the coefficients of this polynomial, but so that the coefficient for term k is multiplied by the element in position k % 5 in the array [547, 619, 877, 1013, 1163]. Define that array inside your class as a named constant MULTIPLIERS.

public int compareTo(Polynomial other)

Implements the ordering comparison between this and other polynomial, as required by the interface Comparable, allowing the instances of Polynomial to be sorted or stored inside some instance of TreeSet. This method returns +1 if this is greater than other, -1 if other is greater than this, and 0 if both polynomials are equal in the sense of the equals method.

A total ordering relation between polynomials is defined by the rule that any polynomial of higher degree is automatically greater than any polynomial of lower degree, regardless of their coefficients. For two polynomials whose degrees are equal, the result of the order comparison is determined by the highest-order term for which the coefficients of the polynomials differ, so that the polynomial with a larger such coefficient is considered to be greater in this ordering.

Be careful to ensure that this method ignores the leading zeros of high order terms if you have them inside your polynomial coefficient array, and that the ordering comparison criterion is precisely the one defined in the previous paragraph.

TestCode:

import static org.junit.Assert.*; import org.junit.After; import org.junit.Before; import org.junit.Test; import java.util.Random; import java.io.*; import java.util.*; import java.util.zip.CRC32; public class PolynomialTestThree { @Test public void testEquals() { int[] c1 = {-10, 99, 11, 12}; int[] c2 = {-10, -99, 11, 12}; Polynomial p1 = new Polynomial(c1); Polynomial p2 = new Polynomial(c2); Polynomial p3 = new Polynomial(c1); assertTrue(p1.equals(p1)); assertTrue(p1.equals(p3)); assertFalse(p1.equals(p2)); assertFalse(p2.equals(p1)); assertFalse(p1.equals("hello world")); } @Test public void testCompareTo() { int[] c1 = {-10, 99, 11, 12}; int[] c2 = {-10, -99, 11, 12}; int[] c3 = {42, 10000000}; Polynomial p1 = new Polynomial(c1); Polynomial p2 = new Polynomial(c2); Polynomial p3 = new Polynomial(c3); assertEquals(+1, p1.compareTo(p2)); assertEquals(-1, p2.compareTo(p1)); assertEquals(+1, p1.compareTo(p3)); assertEquals(-1, p3.compareTo(p2)); assertEquals(0, p1.compareTo(p1)); } private static final int SEED = 12345; private static final int TRIALS = 100000; private Polynomial createRandom(int deg, Random rng) { int[] c = new int[deg + 1]; for(int j = 0; j < deg + 1; j++) { c[j] = rng.nextInt(20) - 10; } return new Polynomial(c); } @Test public void massTest() { Random rng = new Random(SEED); TreeSet tree = new TreeSet(); HashSet hash = new HashSet(); CRC32 check = new CRC32(); for(int i = 0; i < TRIALS; i++) { Polynomial p1 = createRandom(rng.nextInt(10), rng); Polynomial p2 = createRandom(rng.nextInt(10), rng); assertEquals(tree.contains(p1), hash.contains(p1)); tree.add(p1); hash.add(p1); assertEquals(0, p1.compareTo(p1)); assertEquals(0, p2.compareTo(p2)); assertEquals(p1.compareTo(p2), -p2.compareTo(p1)); check.update(p1.compareTo(p2)); } assertEquals(tree.size(), hash.size()); for(Polynomial p: tree) { assertTrue(hash.contains(p)); } for(Polynomial p: hash) { assertTrue(tree.contains(p)); } assertEquals(28339163L, check.getValue()); } }