import java.util.ArrayList;

/** Polynomial represents a polynomial from algebra.
    e.g. 4x^3 + 3x^2 - 5x + 2

*/

public class Polynomial extends ArrayList<Double> {

    /**
       no-arg constructor returns a polynomial of degree 1, with value 0
     */
    
    public Polynomial() {
	// invoke superclass constructor, i.e. the
	// constructor of ArrayList<Double> with 
	// parameter 1 (capacity, not size)
	super(1); // we want capacity at least 1 
	this.add(0,0.0); // uses autoboxing
	
    }

    /**
       get the degree of the polynomial.  Always >= 1
       @return degree of the polynomial
     */
    public int getDegree() { return this.size() - 1; }

    /**
       Construct polynomial from int array of coefficients.
       The coefficients are listed in order from highest to lowest degree.
       The degree is the size of the array - 1.


       Example: 7x^3 - 2x^2 + 3 would be represented as {7,-2,0,3}

       Example: x^4 - 4 would be represented as {1,0,0,-4}

       @param coeffs array of coefficients from largest degree down to smallest.
     */
    
    public Polynomial(int [] coeffs) {
	// invoke superclass constructor, i.e. the
	// constructor of ArrayList<Double> with 
	// capacity parameter
  	super(coeffs.length); 
	for (int i=0;i<coeffs.length;i++) {
	    this.add(0,(double) coeffs[i]); 
	}
    }

    /**
       Construct polynomial from double array of coefficients.
       The coefficients are listed in order from highest to lowest degree.
       The degree is the size of the array - 1.


       Example: 7.1x^3 - 2.6x^2 + 3.1 would be represented as {7.1,-2.6, 0.0, 3.1}

       @param coeffs array of coefficients from largest degree down to smallest.
     */

    public Polynomial(double [] coeffs) {
	// invoke superclass constructor, i.e. the
	// constructor of ArrayList<Double> with 
	// capacity at least as large as we need
	
	super(coeffs.length); 
	for (int i=coeffs.length-1;i>=0;i--) {
	    this.add(coeffs[i]); 
	}
    }

    /**
       Return string respresentation of Polynomial.
       
       Leading coefficient has negative sign in front, with no space.
       Other signs have a space on either side.    Coefficients that are ones
       should be omitted.     Coefficients that are within 0.0000001 (i.e. 10^6) of an 
       integer value should omit the .0.    Terms with zero coefficients (to same tolerance)
       should be omitted.

       Examples:<br /> 
       1<br />
       2x - 3<br />
       x^2 - 5x + 6<br />
       -x^7 - 2x^5 + 3x^3 - 4x<br />

       See the source code of PolynomialTest.java for more examples.

       @return string representation of Polynomial
     */
    public String toString() {

	String result="";

	// for loop that steps down from the degree to 0

	for (int i=this.getDegree(); i>=0 ; i-- ) {
	    result += (get(i) + "x^" + i + " ") ;
	}
	    

	return result;
    }


    /** 
	determine whether two polynomials are equal (same degree, same coefficients)
	
	Uses 10^6 as tolerance for double equality.
 
	@param o arbitrary object to test for equality
	@return true if objects are equal, otherwise false
    */

    public boolean equals(Object o) {



	// This is boiler plate code for a equals method in Java
	// Always do this first

	if (o == null)
	    return false;
	if (!(o instanceof Polynomial))
	    return false;

	Polynomial p = (Polynomial) o;

	// @@@ TODO: Check the size of each ArrayList.  
	// If they don't match, return false



	// @@@ TODO: Check each element in the ArrayList
	// If any don't match, return false.
	// Note that you are comparing double values, 
	// so be sure to use a tolerance rather than ==

	final double TOL=0.000001;


	// If you get to the end, and haven't found a reason
	// why they don't match, then they must match.

	return false; // STUB @@@	
	// @@@ RESTORE THIS LATER!!! return true;
	
    }

    /**
       Add two polynomials
       @param p polynomial to add to this polynomial
       @return new Polynomial representing this polynomial plus p
    */
    public Polynomial plus (Polynomial p) {
	// Note that you can't predict the degree in advance.
	// If I add x^2 + 3x + 5  and -x^2 -3x -5, I get zero.
	// So, be careful!

	return new Polynomial (new int [] {-42}); // @@@ STUB!
    }


    /**
       Multiply two polynomials
       @param p polynomial to multiply this polynomial by 
       @return new Polynomial representing this polynomial times p
    */

    public Polynomial times (Polynomial p) {
	// Here, you'll always know the degree for sure
	// the algorithm is similar to multiplying integers
	// by hand (like you did in 3rd or 4th grade)
	
	return new Polynomial (new int [] {-42}); // @@@ STUB!
    }

    /**
       Subtract two polynomials
       @param p polynomial to subtract from this polynomial
       @return new Polynomial representing this polynomial minus p
    */

    public Polynomial minus (Polynomial p) {

	// HINT: This one is easy if you think about the definition
	// of subtraction.  You can just use plus and times
	// and do this with a one liner.

	return new Polynomial (new int [] {-42}); // @@@ STUB!
    }


}