/**
 * This class represnts a Polynom object.
 * @author (Eyal Oren)
 * @version (2020a, 30.1.2020)
**/
public class Polynom
{
    private PolyNode _head; //Instane variable to point to the Polynom first Node.

    //Constructors:
    /**
     * Creates a new Polynom object.
     */
    public Polynom() //Deafult constructor, assigns the head of the polynom to be null.
    {
        _head = null;
    }

    /**
     * Creates a new Polynom object.
     * @param p, the head of the Polynom to be set.
     */
    public Polynom(PolyNode p) //Constructor to assign a given PolyNode for Polynom head to point at.
    {
        _head = p;
    }

    /**
     * Returns the head of the Polynom.
     * @return the head of the Polynom.
     *
     * Time Complexity O(1)
     * Space Complexity O(1)
     */
    public PolyNode getHead() //Returns the head of the polynom.
    {
        return _head;
    }

    /**
     * Sets the head of the Polynom
     * @param p, the head of the Polynom to be set.
     *
     * Time Complexity O(1)
     * Space Complexity O(1)
     */
    public void setHead(PolyNode p) //Sets the head of the polynom to be the node given in the method.
    {
       _head = p;
    }

    /**
     * Adds a new PolyNode to the Polynom, in the correct place.
     * @param p, the PolyNode to insert.
     * @return the Polynom after instering the new PolyNode.
     *
     * Time Complexity O(n)
     * Space Complexity O(1)
     */
    public Polynom addNode (PolyNode p) //Adds a node to the polynom, keeping the polynom sorted by powers.
    {
        if (this._head == null) //If the polynom is empty of nodes, adding the given node to be the head of the polynom.
        {
            _head = p;
            return this;
        }

        if (p.getPower() > this._head.getPower()) //If the power of the given power is bigger than the head of the polynom, making it the new head.
        {
            p.setNext(_head);
            _head = p;
            return this;
        }

        PolyNode h = _head; //Assigns a pointer to the head of the polynom.

        while (h != null) //Going through all the nodes in the polynom and checking the following terms:
        {
            if (h.getNext() == null) //If the loop reached the end of the polynom, instering the given node as the last node in the polynom.
            {
                if (h.getPower() == p.getPower())        //If the powers are the same, adding the coefficients.
                {
                    h.setCoefficient(h.getCoefficient() + p.getCoefficient());
                }

                else
                {
                    h.setNext(p);  //Otherwise, setting the node recieved in the method to be the last node in the Polynom.
                }
                return this;
            }

            else if (p.getPower() == h.getPower()) //If the polynom contains a node with the same power, adding the given node power to the node that is already in.
            {
                h.setCoefficient(h.getCoefficient() + p.getCoefficient());
                break; //Exiting the loop, considering the instertion has been completed.
            }

            else if (p.getPower() < h.getPower() && p.getPower() > h.getNext().getPower()) //If the given node power is between two adjacent nodes, inserting it before it.
            {
                PolyNode temp = h.getNext(); //Temp pointer to hold.
                h.setNext(p); //Making the given node the next node of the first node.
                p.setNext(temp); //Making the second node as the next of the given node.
                break;  //Exiting the loop, considering the instertion has been completed.
            }

            else
            {
                h = h.getNext(); //If none of the above terms happen, checking the next node to insert at.
            }
        }
        return this;
    }

    /**
     * Multiplies every PolyNode in the Polynom with a given scalar.
     * @param num, the scalar to multiply with.
     * @return the Polynom after multiplication.
     *
     * Time Complexity O(n)
     * Space Complexity O(1)
     */
    public Polynom multByScalar (int num) //Multiplies every PolyNode in the Polynom with a given scalar.
    {
        PolyNode p = _head; //Assigns a pointer to the head of the polynom.
        while (p != null)   //Going through all the nodes in the polynom. and mutiplying their coefficient with the given scalar.
        {
            p.setCoefficient(p.getCoefficient() * num);
            p = p.getNext();
        }
        return this;
    }

    /**
     * Adds the given Polynom in the method, to this Polynom.
     * @param other, the Polynom to add to this Polynom.
     * @return this Polynom after adding the given Polynom to it.
     *
     * Time Complexity O(n)
     * Space Complexity O(n)
     */
    public Polynom addPol (Polynom other)
    {
        if (other._head == null) //If the polynom recived in the method is empty, returning this polynom.
        {
            return this;
        }

        if (this._head == null) //If this polynom is empty, assigning this polynom to be the polynom recived and returning it.
        {
            this._head = new PolyNode(other._head);
            return this;
        }

        PolyNode h = other._head;      //Pointer to the other polynom head.
        PolyNode origin = this._head;  //Pointer to this polynom head.

        if (h.getPower() > origin.getPower())   //If the power of the other head is bigger than the head of this head, inserting it as the new head.
        {
            PolyNode temp = new PolyNode(h);  //New node for the node to insert.
            h = h.getNext();
            temp.setNext(origin);             //Inserting the specific node in the polynom that has been reciived, between the two nodes.
            this._head = temp;
            origin = this._head;
        }

        while (h != null)                               //Going through every node in the other polynom
        {
           while (origin != null)                       //Checking in this polynom, where to enter the specific node of the other polynom.
           {
               if (origin.getNext() == null)            //If we have reached to the end of this polynom:
               {
                   PolyNode temp = h;
                   h = h.getNext();
                   if (origin.getPower() == temp.getPower()) //If the powers are equal, adding the coefficients.
                   {
                       origin.setCoefficient(origin.getCoefficient() + temp.getCoefficient());
                       origin.setNext(temp.getNext());
                   }
                   else
                   {
                       origin.setNext(temp); //Otherwise, setting the specific node to be the last node in the Polynom at the moment.
                   }
                   break;
               }

               else if (h.getPower() < origin.getPower() && h.getPower() > origin.getNext().getPower()) //If the power of the other node is just between two powers of this polynom, inserting it between them.
               {
                  PolyNode temp = new PolyNode(h); //New node for the node to insert.
                  temp.setNext(origin.getNext());
                  origin.setNext(temp);
                  h = h.getNext();
               }

               else if (h.getPower() == origin.getPower())  //If the other node power is equal to this power, adding it's power to this power.
               {
                   origin.setCoefficient(origin.getCoefficient() + h.getCoefficient());
                   h = h.getNext();
               }


               else
               {
                   origin = origin.getNext(); //If none of the above reached, moving the origin pointer one node further.
               }
           }
        }
        return this;
    }
    /**
     * Multiplies the given Polynom with this Polynom.
     * @param other, the Polynom to multiply this Polynom with.
     * @return this Polynom after multiplying it with the given Polynom.
     */
    public Polynom multPol (Polynom other)
    {
        if (other == null || other._head == null) //If the given Polynom or it's head are null, returning this Polynom.
        {
            return this;
        }

        if (this._head == null) //If this Polynom doesnt point on any vaild nodes, returning this Polynom.
        {
            return this;
        }

        Polynom p = new Polynom();     //Creating new Polynom to hold the multiplied nodes.

        //Assigning pointers to each Polynom head: ש
        PolyNode origin = this._head;
        PolyNode r = other._head;

        while (origin != null) //Going through all the nodes in this Polynom
        {
            while (r != null) //GOing through all the nodes in the given Polynom, for each Node in this polynom.
            {
                PolyNode toAdd = new PolyNode(origin.getPower() + r.getPower(), origin.getCoefficient() * r.getCoefficient()); //Creating a new Node, which is the product of multiplying 2 nodes.
                p.addNode(toAdd); //Adding the node to the temporary Polynom, with the method to sort the nodes.
                r = r.getNext();
            }
            if (r == null) //If the 2nd Polynom has reached it's end, pointing it back to the head. to multiply the next origin node with this Polynom nodes.
            {
                r = other._head;
            }
            origin = origin.getNext(); //After the iteration, moving the origin node to be the next one.
        }
        this.setHead(p._head);  //Setting this Polynom head to be the temporary Polynom head.
        return this;
    }

    /**
     * Returns the differential Polynom of this Polynom.
     * @return the differential Polynom of this Polynom.
     *
     *  Time Complexity O(n)
     *  Space Complexity O(1)
     */
    public Polynom differential() //Returns the differential Polynom of this Polynom.
    {
       PolyNode p = _head; //Assigns a pointer to the head of this Polynom.

       while (p != null) //Going through each node in the Polyonm, to differante it.
       {
           if (p.getPower() == 0) //If the power of a node is 0, setting it's coefficient to be 0.
           {
               p.setCoefficient(0);
               p = p.getNext();
           }

           else if (p.getPower() == 1) //If the power of a node is 1, setting it's power to be 0.
           {
               p.setPower(0);
               p = p.getNext();
           }

           else //Otherise using the basic differential formula.
           {
               p.setCoefficient(p.getCoefficient() * p.getPower());
               p.setPower(p.getPower() - 1);
               p = p.getNext();
           }
       }
       return this;
    }
    /**
     * Returns a String that represents this Polynom.
     * @return a String that represnts this Polynom.
     *
     * Time Complexity O(n)
     * Space Complexity O(1)
     */
    public String toString()
    {
        if (_head == null)
        {
            return ""; //If the Polynom is empty, returning an empty string.
        }

        String str = "";
        boolean isFirst = true;
        PolyNode p = _head;
        while (p != null)             //Going through all the nodes in the Polyonm.
        {
            if (p.getCoefficient() != 0) //Adding a node only if it's coefficient is not zero.
            {
                if (isFirst)  //If it's the first node, won't add a '+' sign.
                {
                    str += p;
                    isFirst = false; //The first node has been added.
                }

                else
                {
                    if (p.getCoefficient() > 0)  //If it's not the first node.
                    {
                        str += "+" + p;
                    }
                    else
                    {
                        str += p;
                    }
                }
            }
            p = p.getNext();
        }
        return str;
    }
//End of class Polynom.
}