import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.ListIterator;

public class Polynomial {

    LinkedList<PolynomialTerm> aPoly;
    ArrayList<PolynomialTerm> adding = new ArrayList<PolynomialTerm>();
     ArrayList<PolynomialTerm> mult = new ArrayList<PolynomialTerm>();
     ArrayList<PolynomialTerm> store = new ArrayList<PolynomialTerm>();
     ArrayList<PolynomialTerm> store2 = new ArrayList<PolynomialTerm>();
    
   
    

    Polynomial()
    {
      this.aPoly  = new LinkedList<PolynomialTerm>();
    }

    
Polynomial (int[] data)
     {
           this.aPoly = new LinkedList<PolynomialTerm>();
          for(int i =0; i<data.length; i = i+2)
          {

              PolynomialTerm term = new PolynomialTerm(data[i],data[i+1]);
              addTerm(term);
          }
 


  
    
			
     }

public boolean isZero()
    {
       if(this.aPoly.isEmpty())
         {
        return true;
         }

      return false;
   }


public Polynomial copy()

    {
         ListIterator<PolynomialTerm> iter = aPoly.listIterator();
        int [] parameter = new int[aPoly.size()*2];
        

        for(int i = 0 ;i< aPoly.size(); i++)
            {
                PolynomialTerm temp = iter.next();

                parameter[i] = temp.exponent;
                parameter[i+1] = temp.coefficient;
            }

        return new Polynomial(parameter);
    }
public Polynomial plus(Polynomial two)
    {
      Polynomial addition  = new Polynomial();

      PolynomialTerm maxOne = getMax(this);
      PolynomialTerm maxTwo = getMax(two);

      Polynomial two1 = two.copy();
      Polynomial this1 = this.copy();
     

    if(this.aPoly.isEmpty()&& two.aPoly.isEmpty())
    {
        for(PolynomialTerm i : adding)
        {
            addition.addTerm(i);
        }
        adding.clear();

         for(PolynomialTerm i : store)
             {
                 this.addTerm(i);
             }

         store.clear();
          for(PolynomialTerm e : store2)
             {
                 two.addTerm(e);
             }
          store2.clear();
        return addition;
    }

 else if(maxOne.exponent == maxTwo.exponent)
       {
       PolynomialTerm nuevo = new PolynomialTerm(maxOne.exponent,maxTwo.coefficient+maxOne.coefficient);
       adding.add(nuevo);
           two.aPoly.remove(maxTwo);
           store2.add(maxTwo);
          this.aPoly.remove(maxOne);
          store.add(maxOne);
           return this.plus(two);
       }


 else if (maxOne.exponent > maxTwo.exponent)
       {
           adding.add(maxOne);
           this.aPoly.remove(maxOne);
           store.add(maxOne);
          return this.plus(two);
       }

 else  
       
           adding.add(maxTwo);
           two.aPoly.remove(maxTwo);
           store.add(maxTwo);
          return this.plus(two);
       

 
     
    } 







public Polynomial times(Polynomial two)
    {
     Polynomial multiplication  = new Polynomial();
      PolynomialTerm first = new PolynomialTerm();


     ListIterator<PolynomialTerm> list = this.aPoly.listIterator();
      ListIterator<PolynomialTerm> list2 = two.aPoly.listIterator();


    if(list.hasNext())
     {
          first = list.next();
         
     }



         if(this.aPoly.isEmpty() )
         {
             
           
             for(PolynomialTerm i : mult)
             {
                 multiplication.addTerm(i);
                 
             }

            mult.clear();

             for(PolynomialTerm i : store)
             {
                 this.addTerm(i);
             }
             store.clear();
             return simplify(multiplication);
         }

       else
           this.aPoly.remove(first);
           store.add(first);
           while(list2.hasNext())
           {
               PolynomialTerm next = list2.next();
               mult.add(new PolynomialTerm(first.exponent + next.exponent,first.coefficient * next.coefficient));
           }

    return times(two);
    }
public void addTerm(PolynomialTerm term)
    {

            ArrayList<PolynomialTerm> temp = new ArrayList<PolynomialTerm>();
            PolynomialTerm max =new PolynomialTerm (0,0);

            aPoly.addFirst(term);

          for(PolynomialTerm i : aPoly)
            {
                temp.add(i);
            }
          aPoly.clear();


        while(!temp.isEmpty())
        {

          for(PolynomialTerm j : temp)
            {
                if(max.exponent< j.exponent)
                {
                    max = j;
                  
                }
            }
        
          temp.remove(max);
          aPoly.addLast(max);
          max =new PolynomialTerm (0,0);

         
    }
      
         
    }

public Polynomial times(PolynomialTerm term)
    {
             Polynomial aTerm = new Polynomial();
             aTerm.addTerm(term);

             return this.times(aTerm);
    }


public int value(int x)
        {
                  int value =0;

                  for(PolynomialTerm i : this.aPoly)
                  {
                      value += Math.pow(x, i.exponent)*i.coefficient;
                  }

                  return value;
       }
// helper methods


public Polynomial simplify(Polynomial term)
    {



       for(PolynomialTerm e : term.aPoly)
       {        
               
          for(PolynomialTerm i : term.aPoly)
          {
              if((i.exponent == e.exponent) &&(!i.equals(e)))
              {
                  term.aPoly.remove(i);
                  term.aPoly.remove(e);

                  term.addTerm(new PolynomialTerm(i.exponent, e.coefficient+i.coefficient));
                  return term;
              }
          }
              
        }
       return term;
    }

public PolynomialTerm getMax(Polynomial one)
    {
          PolynomialTerm max = new PolynomialTerm(0,0);
       for(PolynomialTerm i : one.aPoly)
       {
           if(max.exponent < i.exponent)
           {
               max = i;
           }

          
       }
       return max;
    }


public PolynomialTerm addTerm(PolynomialTerm one, PolynomialTerm two)
    {
      return new PolynomialTerm(one.exponent, one.coefficient+ two.coefficient);
    }
public String toString()
    {
          String image = "";

          for(PolynomialTerm j : this.aPoly)
          {
              image += "( " + j.exponent + "," + j.coefficient + ")";
          }
          return image;
    }
}