class Poly {
  /* Instance Fields */
  private Term terms;

  /* Constructors */
  public Poly(){terms = new Term();};
  public Poly(int e, double c){terms = new Term(e,c);};
  public Poly(Term t){terms = t;};
  /* Instance methods */

  public int degree(){return terms.degree();};
  public double lead(){return terms.lead();};

  public void InsertTerm(Term t){
/* This takes a single term and inserts it into the polynomial.  At the end
all representation decisions about polynomials must still hold.  There must
be only one term for each possible exponent, there should be no term with a
zero coefficient and the exponents must be in decreasing order. */
      if (t.lead() == 0) return; //do nothing if the term is = 0
      if (t.degree() > this.terms.degree()){
          //if the term belongs at the beginning of the poly:
          if (this.terms.degree() != 0 || this.terms.lead() != 0) {
              Term temp = new Term(t.degree(), t.lead());
              temp.SetNext(this.terms);
              this.terms = temp;
          }
          else { //There could be a single first term w/ degree and coef 0 (if
                 //the Poly was just created, and with no parameters)
              this.terms = t; //Get rid of the 0/0 term
          }
      }
      else { //in normal cases, just use the Term insert()
          this.terms.insert(t.degree(), t.lead());
      }
}
  
  public void add(Poly p){
    /* The polynomial p is unchanged but this polynomial is altered. */
    Term foo = p.terms;
    while (foo != null) {this.InsertTerm(foo); foo = foo.GetNext();}};

  public double eval(double x){//Evaluates the polynomial at the value x.

    if (terms == null) return 0.0;
    else {
      double result = 0.0;
      Term foo = terms;
      while (foo != null) {result += foo.eval(x); foo = foo.GetNext();}
      return result;}};
      
  /* Static (Class) Methods */
  public static void display(Poly p){
    if (p.terms == null) System.out.println("[]");
    else System.out.println(p.terms);};   
  
  public static Poly add2(Poly p, Poly q){ 
    /* The two polynomials are unaltered. */
    Poly result = clone(p);
    result.add(q);
    return result; };

  public static Poly clone(Poly p){
    /* Makes a new copy of the polynomial. */
    Term foo = p.terms;
    Term rear = null, result = null, temp = null;
    if (foo == null) return new Poly();
    else {
      result = new Term(foo.degree(), foo.lead());
      rear = result;
      foo = foo.GetNext();
      while (foo != null) {
      temp = new Term(foo.degree(),foo.lead());
      rear.SetNext(temp);
      rear = temp;
      foo = foo.GetNext();}
      return new Poly(result);}};

  private static Poly mtp(Poly p, Term t){
 //Returs polynomial p multiplied by term t
      Poly product = new Poly();
      Term temp = p.terms;
      while (temp != null) { //loop through the terms of p
          product.InsertTerm(new Term(temp.degree() + t.degree(), temp.lead() + t.lead()));
            //multiply each term by t
          temp = temp.GetNext();
      }
      return product;
  }
  
  private static void mtp(Poly p, Term t, Poly existingPoly){
 //Inserts polynomial p multiplied by term t into into polynomial existingPoly
      Term temp = p.terms;
      while (temp != null) { //loop through the terms of p
          existingPoly.InsertTerm(new Term(temp.degree() + t.degree(), temp.lead() * t.lead()));
            //multiply each term by t
          temp = temp.GetNext();
      }
  }

  public static Poly multiply(Poly p, Poly q){
 //Multiplies two polynomials, returns the result
      Poly product = new Poly();
      Term temp = q.terms;
      while (temp!=null) { //loop through the terms of q
          Poly.mtp(p, temp, product); //use this form of mtp to "insert as you go"
            //multiply the term by all the terms in p using mtp
          temp = temp.GetNext();
      }
      return product;
  }

  public static Poly diff(Poly p){
  //Returns the derivative of polynomial p
      Poly deriv = new Poly();
      Term temp = p.terms;
      while (temp != null){
          deriv.InsertTerm(new Term(temp.degree() - 1, temp.lead()*temp.degree()));
            //standard exponent/chain rule
          temp = temp.GetNext();
      }
      return deriv;
  }
    
    public static void main(String[] args){
   
/* You can test this code by using the main method below, which outputs
everything to the screen.  Your diskette should contain all the classfiles
generated so that we can verify that the output produced is as specified.
*/  
       Poly p = new Poly(5,3.0);
       p.InsertTerm(new Term(3,2.0));
       p.InsertTerm(new Term(0,-2.0));
       display(p);
       double y = p.eval(2.0);
       System.out.println(y);
    
       Poly q = new Poly(0,2.5);
       q.InsertTerm(new Term(1,2.0));
       q.InsertTerm(new Term(2,3.0));
       q.InsertTerm(new Term(7,5.0));
       Poly r = multiply(p,q);
       System.out.println("The product of the polynomials:");
       display(p);
       System.out.println("and");
       display(q);
       System.out.println("is:");
       display(r);
       System.out.println("The sum of the polynomials:");
       display(p);
       System.out.println("and:");
       display(q);
       System.out.println("is:");
       q.add(p);
       display(q);
    };
}