souravCoder1 · April 16, 2022 14:32 · Mar 21, 2016
diff --git a/Polynomial.java b/Polynomial.java
@@ -0,0 +1,242 @@
+package week4;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Represents an immutable polynomial with integer coefficients (and a single
+ * indeterminate "x"). A typical polynomial is 5x^2 + 3x + 2.
+ */
+public class Polynomial {
+
+	// a list of terms in the polynomial
+	private ArrayList<Term> terms = new ArrayList<Term>();
+
+	/*
+	 * invariant:
+	 * 
+	 * terms != null
+	 * 
+	 * && terms does not contain null terms or terms with zero coefficients
+	 * 
+	 * && terms does not contain more than one term with the same exponent
+	 * 
+	 * && terms is ordered by the exponent of its terms in ascending order.
+	 */
+
+	/** Constructs a new zero polynomial. */
+	public Polynomial() {
+		// do nothing because we won't store terms with zero coefficients
+	}
+
+	/**
+	 * Constructs a new monomial with the given exponent and coefficient.
+	 * 
+	 * @param coefficient
+	 *            the coefficient
+	 * @param exponent
+	 *            the exponent
+	 * @throws NegativeExponentException
+	 *             if exponent < 0
+	 */
+	public Polynomial(int coefficient, int exponent)
+			throws NegativeExponentException {
+		if (exponent < 0) {
+			throw new NegativeExponentException();
+		}
+		if (coefficient != 0) {
+			terms.add(new Term(coefficient, exponent));
+		}
+	}
+
+	/**
+	 * Returns a new polynomial that is the result of adding p to this. Both
+	 * this and parameter p should remain unchanged by this operation.
+	 * 
+	 * @param p
+	 *            the polynomial to be added to this one
+	 * @return a new polynomial that is is the result of adding p to this
+	 */
+	public Polynomial add(Polynomial p) {
+		// the polynomial to be returned, initialised to 0
+		Polynomial result = new Polynomial();
+		/*
+		 * Add each of the terms in this and p to result.terms in exponent
+		 * order. (We essentially traverse both ordered lists of terms
+		 * simultaneously, merging the terms into a new ordered list.)
+		 */
+		int i = 0; // current index into this.terms
+		int j = 0; // current index into p.terms
+		while (i < terms.size() && j < p.terms.size()) {
+			if (terms.get(i).getExponent() == p.terms.get(j).getExponent()) {
+				// the exponents of the terms are equal, so we add them together
+				// before including them in result.terms
+				Term nt = terms.get(i).add(p.terms.get(j));
+                if(nt.getCoefficient() != 0) {
+                    result.terms.add(nt);
+                }
+				i++;
+				j++;
+			} else if (terms.get(i).getExponent() < p.terms.get(j)
+					.getExponent()) {
+				// we append the smaller of the two terms onto result.terms
+				result.terms.add(terms.get(i));
+				i++;
+			} else {
+				// we append the smaller of the two terms onto result.terms
+				result.terms.add(p.terms.get(j));
+				j++;
+			}
+		}
+		// add the remainder of terms in this to the result
+		while (i < terms.size()) {
+			result.terms.add(terms.get(i));
+			i++;
+		}
+		// add the remainder of terms in p to the result
+		while (j < p.terms.size()) {
+			result.terms.add(p.terms.get(j));
+			j++;
+		}
+		return result;
+	}
+//THIS IS THE FUNCTION THATS NOT WORKING MAXI
+	/**
+	 * Returns a new polynomial that is the result of subtracting p from this.
+	 * Both this and parameter p should remain unchanged by this operation.
+	 * 
+	 * @param p
+	 *            the polynomial to be subtracted from this one
+	 * @return a new polynomial that is is the result of subtracting p from this
+	 */
+	public Polynomial subtract(Polynomial p) {
+        Polynomial result = new Polynomial();
+
+        // i is the index of this.terms
+        // j is the index of p.terms
+        int i = 0;
+        int j = 0;
+
+        while(i < terms.size() && j < p.terms.size()) {
+            if (terms.get(i).getExponent() == p.terms.get(j).getExponent()) {
+                Term nt = terms.get(i).subtract(p.terms.get(j));
+                if(nt.getCoefficient() != 0){
+                    result.terms.add(nt);
+                }
+            } else if (terms.get(i).getExponent() < p.terms.get(j)
+                    .getExponent()) {
+                Term zero = new Term(0, terms.get(i).getExponent());
+                Term nt = zero.subtract(terms.get(i));
+                // we append the smaller of the two terms onto result.terms
+                result.terms.add(nt);
+                i++;
+            } else {
+                Term zero = new Term(0, p.terms.get(j).getExponent());
+                Term nt = zero.subtract(p.terms.get(j));
+                // we append the smaller of the two terms onto result.terms
+                result.terms.add(nt);
+                j++;
+            }
+        }
+        // add the remainder of terms in this to the result
+        while (i < terms.size()) {
+            Term zero = new Term(0, terms.get(i).getExponent());
+            Term nt = zero.subtract(terms.get(i));
+            // we append the smaller of the two terms onto result.terms
+            result.terms.add(nt);
+            i++;
+        }
+        // add the remainder of terms in p to the result
+        while (j < p.terms.size()) {
+            Term zero = new Term(0, p.terms.get(j).getExponent());
+            Term nt = zero.subtract(p.terms.get(j));
+            // we append the smaller of the two terms onto result.terms
+            result.terms.add(nt);
+            j++;
+        }
+        return result;
+	}
+
+	/**
+	 * <p>
+	 * Returns the string representation of the polynomial.
+	 * </p>
+	 * 
+	 * <p>
+	 * The zero polynomial is represented by the string "0". The string
+	 * representation of a non-zero polynomial is a list of the non-zero terms
+	 * in the polynomial in descending order of exponent concatenated together
+	 * by a single plus operator with a single space on either side (i.e.
+	 * " + ").
+	 * </p>
+	 * 
+	 * <p>
+	 * There shouldn't be more than one term with the same exponent in the
+	 * string representation, i.e. we would write "3x^4 + 2x + 3" instead of
+	 * "2x^4 + 1x^4 + 2x + 3"
+	 * </p>
+	 * 
+	 * <p>
+	 * A term with a non-zero coefficient a and exponent b is written "a" if b
+	 * is zero, "ax" if b is one, and "ax^b" otherwise.
+	 * </p>
+	 * 
+	 * <p>
+	 * (Note that this representation isn't as nice as it could be. For example,
+	 * we write "1x^2" instead of "x^2", and "3x^2 + -5x" instead of "3x^2 - 5x"
+	 * etc. We are keeping it simple on purpose!)
+	 * </p>
+	 */
+	public String toString() {
+		if (terms.size() == 0) {
+			return "0";
+		}
+		// the string representation under construction
+		String s = "" + terms.get(terms.size() - 1);
+		// add terms in descending order of exponent
+		for (int i = terms.size() - 2; i >= 0; i--) {
+			s = s + " + " + terms.get(i);
+		}
+		return s;
+	}
+
+	/**
+	 * Determines whether this Polynomial is internally consistent (i.e. it
+	 * satisfies its class invariant). This method should only be used for
+	 * testing the implementation of the class.
+	 * 
+	 * @return true if this polynomial is internally consistent, and false
+	 *         otherwise.
+	 */
+	public boolean checkInvariant() {
+		// if terms is null, return false
+		if(terms == null) {return false;}
+		// make a list of exponents to test for doubles
+		List<Integer> exponents = new ArrayList<>();
+		// for loop for checking each term for doubles of exponents or zero coefficients
+		for(int term = 0; term < terms.size(); term++){
+			// check for zero coefficient or null term
+			if(terms.get(term) == null ||
+					terms.get(term).getCoefficient() == 0){return false;}
+			// check for doubles of exponents
+			for(int exponent = 0; exponent < exponents.size(); exponent++) {
+				if (terms.get(term).getExponent() == exponents.get(exponent)){
+					return false;
+				}
+			}
+			// add the exponent to the list of tested exponents
+			exponents.add(terms.get(term).getExponent());
+
+		}
+		// check if exponents are in ascending order
+		if(exponents.size() > 1) {
+			for (int exponent = 1; exponent < exponents.size(); exponent++) {
+				if (exponents.get(exponent) < exponents.get(exponent - 1)) {
+					return false;
+				}
+			}
+		}
+		return true;
+	}
+
+}
diff --git a/PolynomialTest.java b/PolynomialTest.java
@@ -0,0 +1,142 @@
+package week4;
+
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.experimental.theories.suppliers.TestedOn;
+
+/** Some JUnit tests for the Polynomial class. */
+public class PolynomialTest {
+
+	/** Test the zero constructor of Polynomial. */
+	@Test
+	public void testInitialStateZeroPolynomial() {
+		Polynomial p = new Polynomial();
+		Assert.assertEquals("0", p.toString());
+		Assert.assertTrue("Invariant check failed", p.checkInvariant());
+	}
+
+	/** Test the monomial constructor of Polynomial. */
+	@Test
+	public void testInitialStateMonomial() {
+
+		// check initial state of monomial with a zero exponent
+		Polynomial p = new Polynomial(3, 0);
+		Assert.assertEquals("3", p.toString());
+		Assert.assertTrue("Invariant check failed", p.checkInvariant());
+
+		// check initial state of monomial with an exponent of one
+		p = new Polynomial(3, 1);
+		Assert.assertEquals("3x", p.toString());
+		Assert.assertTrue("Invariant check failed", p.checkInvariant());
+
+		// check initial state of monomial with a typical exponent greater than
+		// one
+		p = new Polynomial(3, 4);
+		Assert.assertEquals("3x^4", p.toString());
+		Assert.assertTrue("Invariant check failed", p.checkInvariant());
+
+		// check initial state of monomial with a typical exponent and negative
+		// coefficient
+		p = new Polynomial(-3, 4);
+		Assert.assertEquals("-3x^4", p.toString());
+		Assert.assertTrue("Invariant check failed", p.checkInvariant());
+
+		// check initial state of monomial with a typical exponent and zero
+		// coefficient
+		p = new Polynomial(0, 4);
+		Assert.assertEquals("0", p.toString());
+		Assert.assertTrue("Invariant check failed", p.checkInvariant());
+	}
+
+	/**
+	 * Test that attempting to create a monomial with a negative exponent
+	 * results in a NegativeExponentException
+	 **/
+	@Test(expected = NegativeExponentException.class)
+	public void testNegativeExponent() {
+		Polynomial p = new Polynomial(3, -1);
+	}
+
+	/** Test additions of monomials. **/
+	@Test
+	public void testAdditionOfMonomials() {
+
+		// test addition of monomials where the result has two terms
+		Polynomial p1 = new Polynomial(4, 5);
+		Polynomial p2 = new Polynomial(2, 3);
+		Polynomial actual = p1.add(p2);
+		Assert.assertEquals("4x^5 + 2x^3", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+
+		// test addition of monomials where the result is also a monomial
+		p1 = new Polynomial(4, 5);
+		p2 = new Polynomial(2, 5);
+		actual = p1.add(p2);
+		Assert.assertEquals("6x^5", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+
+		// test addition of monomials where the answer is the zero polynomial
+		p1 = new Polynomial(-4, 2);
+		p2 = new Polynomial(4, 2);
+		actual = p1.add(p2);
+		Assert.assertEquals("0", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+
+		// test addition of a monomial with the zero polynomial
+		p1 = new Polynomial();
+		p2 = new Polynomial(4, 2);
+		actual = p1.add(p2);
+		Assert.assertEquals("4x^2", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+	}
+
+	/** Test additions of polynomials with many terms. **/
+	@Test
+	public void testAdditionOfTypicalPolynomials() {
+		// test multiple typical additions (that produce polynomials with many
+		// terms)
+		Polynomial p1 = new Polynomial(-2, 5); // -2x^5
+		Polynomial p2 = new Polynomial(3, 1); // 3x
+		Polynomial p3 = new Polynomial(6, 2); // 6x^2
+		Polynomial p4 = new Polynomial(2, 0); // 2
+		Polynomial p5 = new Polynomial(1, 2); // 1x^2
+		Polynomial p6 = new Polynomial(5, 8); // 5x^8
+
+		Polynomial actual = p1.add(p2.add(p3.add(p4))).add(p5.add(p6));
+		Assert.assertEquals("5x^8 + -2x^5 + 7x^2 + 3x + 2", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+	}
+
+	/** Test subtractions of monomials. **/
+	@Test
+	public void testSubtractionOfMonomials() {
+		// test addition of monomials where the result has two terms
+		Polynomial p1 = new Polynomial(4, 5);
+		Polynomial p2 = new Polynomial(2, 3);
+		Polynomial actual = p1.subtract(p2);
+		Assert.assertEquals("4x^5 - 2x^3", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+
+		// test addition of monomials where the result is also a monomial
+		p1 = new Polynomial(4, 5);
+		p2 = new Polynomial(2, 5);
+		actual = p1.subtract(p2);
+		Assert.assertEquals("2x^5", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+
+		// test addition of monomials where the answer is the zero polynomial
+		p1 = new Polynomial(4, 2);
+		p2 = new Polynomial(4, 2);
+		actual = p1.subtract(p2);
+		Assert.assertEquals("0", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+
+		// test addition of a monomial with the zero polynomial
+		p1 = new Polynomial();
+		p2 = new Polynomial(-4, 2);
+		actual = p1.subtract(p2);
+		Assert.assertEquals("4x^2", actual.toString());
+		Assert.assertTrue("Invariant check failed", actual.checkInvariant());
+	}
+
+}