// ================================================================
// FILE:    Poly.cpp
//
// AUTHORS: Giang, Cam  #4975
//          Hsu, Yee    #8748
//          Lin, Jacky  #5230
//
// USAGE COMMENTS:
//      In UNIX     --  % make
//                  --  % Poly < PolyData.txt
//
// LIBRARIES:
//      iostream.h  --  For stream input/output
//      Term.h      --  To access class Term where declared
//      Poly.h      --  To access class Poly where declared
//
// FUNCTIONS/METHODS DEFINED:
//      Poly                --  Poly default constructor
//      ~Poly               --  Poly default destructor
//
//      void InsertTerm     --  Append new term to link list
//
//      Poly operator =     --  To assign a poly to a poly
//      Poly operator +     --  To add polynomials
//      Poly operator -     --  To subtract polynomials
//      Poly operator *     --  To multiply polynomials
//      Poly operator ^     --  To multiply polynomial to itself
//
//      friend operator *           --  Multiply polynomial
//      friend ostream& operator << --  Output a polynomial
//      friend istream& operator >> --  Input  a polynomial
//
//      void RecAdd     -- Recursively add polynomials
//      void RecSub     -- Recursively subtract polynomials 
//      void RecMul     -- Recursively multiply polynomials
// ================================================================

#include <iostream.h>
#include "Term.h"
#include "Poly.h"

// ================================================================
// IDENTIFIER:  Poly()
//
// COMMENTS:    Poly default constructor.
//              Assigns the head pointer to NULL.
// ================================================================

Poly::Poly() : head(NULL) {}

// ================================================================
// IDENTIFIER:  Poly(const Poly& p)
//
// PRE:         An integer that needs to be cast to a polynomial
//
// INPUT PARAM: int nCoeff  --  An integer soon becoming a poly
//
// POST:        An integer cast into a polynomial
//
// CALLS:       InsertTerm  --  Appends the integer as a
//                              polynomial to the link list
//
// COMMENTS:    Poly overloaded constructor with one argument.
//              Creates a polynomial of 1 term.
// ================================================================

Poly::Poly(const int nCoeff)
{
    head = NULL;
    InsertTerm(nCoeff, 0);
}

// ================================================================
// IDENTIFIER:  Poly(const int nCoeff1, const int nCoeff2)
//
// PRE:         Two integer that needs to be cast to a polynomial
//
// INPUT PARAM: int nCoeff1 --  An integer soon becoming a poly
//              int nCoeff2 --  An integer soon becoming a poly
//
// POST:        Two integer cast into a polynomial
//
// CALLS:       InsertTerm  --  Appends the integer as a
//                              polynomial to the link list
//
// COMMENTS:    Poly overloaded constructor with two argument.
//              Creates a polynomial of 2 term.
// ================================================================

Poly::Poly(const int nCoeff1, const int nCoeff2)
{
    head = NULL;
    InsertTerm(nCoeff1, 1);
    InsertTerm(nCoeff2, 0);
}

// ================================================================
// IDENTIFIER:  Poly(const Poly& p)
//
// PRE:         A Polynomial that needs to be copied
//
// INPUT PARAM: Poly& p --  A reference polynomial
//
// POST:        A polynomial is copied
//
// COMMENTS:    Poly copy constructor.
//              Makes a deep copy of a polynomial.
// ================================================================

Poly::Poly(const Poly& p)
{
    if (p.head == NULL)
        head = NULL;
    else
    {   
        //copy the head
        head = new Term;
        head->nCoeff = p.head->nCoeff;
        head->nExp = p.head->nExp;

        pTerm newptr = head;
        pTerm oldptr = p.head->next;

        //copy the rest of the list
        while (oldptr != NULL)
        {
            newptr->next = new Term;
            newptr = newptr->next;
            newptr->nCoeff = oldptr->nCoeff;
            newptr->nExp = oldptr->nExp;
            oldptr = oldptr->next;
        }
        newptr->next = NULL;
    }
}

// ================================================================
// IDENTIFIER:  ~Poly()
//
// PRE:         A polynomial that needs to be destroyed
//
// POST:        A polynomial deleted and memory is returned
//              back to the system.
//
// COMMENTS:    Poly default destructor.
//              Destroys the polynomial link list to
//              prevent memory leak.
// ================================================================

Poly::~Poly()
{
    pTerm curr = head;

    while (head != NULL)
    {
        head = head->next;
        delete curr;
        curr = head;
    }
}

// ================================================================
// IDENTIFIER:  InsertTerm(const int nCoeff, const int nExp)
//
// PRE:         An coefficient and exponent that needs to be
//              cast into a term and append to the link list    
//
// INPUT PARAM: int nCoeff  --  Coefficient integer
//              int nExp    --  Exponent integer
//
// POST:        A new term appended to the link list.
//
// COMMENTS:    Creates a new term and appends it to the link list.
//              The new term consist a coefficient, an exponent,
//              and a pointer to NULL. All integers are valid
//              coefficient except 0.
// ================================================================

void Poly::InsertTerm(const int nCoeff, const int nExp)
{
    if (nCoeff != 0)
    {       
        pTerm curr = new Term;

        curr->nCoeff = nCoeff;
        curr->nExp = nExp;
        curr->next = NULL;
    
        if (head == NULL)
            head = curr;
        else
        {
            pTerm walker = head;

            while (walker->next != NULL)
                walker = walker->next;

            walker->next = curr;
        }
    }
}

// ================================================================
// IDENTIFIER:  operator=(const Poly& p)
//
// PRE:         A polynomial that needs to be assigned to another
//              polynomial.
//
// INPUT PARAM: Poly& p --  A reference polynomial
//
// POST:        A polynomial assigned to this poly object.
//
// RETURN:      *this   --  this object for concatenation
//
// COMMENTS:    Poly overloaded = operator.
//              The = operator is overloaded so that assigment
//              may be used for polynomials. It copies a poly to
//              a poly if it doesn't already exist.
// ================================================================

Poly Poly::operator=(const Poly& p)
{
    if (this != &p)
    {
        //prevents memory leak;
        this->~Poly();

        if (p.head == NULL)
            head = NULL;
        else
        {   
            //copies the head of the list
            head = new Term;
            head->nCoeff = p.head->nCoeff;
            head->nExp = p.head->nExp;

            pTerm newptr = head;
            pTerm oldptr = p.head->next;

            //copy the rest of the list
            while (oldptr != NULL)
            {
                newptr->next = new Term;
                newptr = newptr->next;
                newptr->nCoeff = oldptr->nCoeff;
                newptr->nExp = oldptr->nExp;
                oldptr = oldptr->next;
            }
            newptr->next = NULL;
        }
    }
    return *this;
}

// ================================================================
// IDENTIFIER:  operator+(const Poly& p)
//
// PRE:         Two polynomials that need to be added
//
// INPUT PARAM: Poly& p --  A reference polynomial
//
// POST:        A polynomial from two polynomials added
//
// CALLS:       RecAdd  --  Performs addition recursively
//
// RETURN:      pp  --  The polynomial after addition
//
// COMMENTS:    Poly overloaded + operator.
//              The + operator is overloaded so that polynomials
//              may perform addition.
// ================================================================

Poly Poly::operator+(const Poly& p)
{
    Poly pp;
    RecAdd(head, p.head, pp);
    return pp;
}

// ================================================================
// IDENTIFIER:  operator-(const Poly& p)
//
// PRE:         Two polynomials that need to be subtracted
//
// INPUT PARAM: Poly& p --  A reference polynomial
//
// POST:        A polynomial from two polynomials subtracted
//
// CALLS:       RecSub  --  Performs subtraction recursively
//
// RETURN:      pp  --  The polynomial after subtraction
//
// COMMENTS:    Poly overloaded - operator.
//              The - operator is overloaded so that polynomials
//              may perform subtraction.
// ================================================================

Poly Poly::operator-(const Poly& p)
{
    Poly pp;
    RecSub(head, p.head, pp);
    return pp;
}

// ================================================================
// IDENTIFIER:  operator*(const Poly& p)
//
// PRE:         Two polynomials that need to be multiplied
//
// INPUT PARAM: Poly& p --  A reference polynomial
//
// POST:        A polynomial from two polynomials multiplied
//
// CALLS:       RecMul  --  Performs multiplication recursively
//
// RETURN:      pp  --  The polynomial after multiplication
//
// COMMENTS:    Poly overloaded * operator.
//              The * operator is overloaded so that polynomials
//              may perform multiplication.
// ================================================================

Poly Poly::operator*(const Poly& p)
{
    Poly pp;
    RecMul(head, p.head, pp);
    return pp;
}

// ================================================================
// IDENTIFIER:  operator^(const int nExp)
//
// PRE:         A polynomial that needs to be raised to a power
//
// INPUT PARAM: int nExp    --  An exponent of a polynomial
//
// POST:        A polynomial raised to the power of an exponent
//
// RETURN:      pp  --  The polynomial after exponentiation
//
// ALGORITHM:   Create a base polynomial with coefficient 1.
//              For nExp loops, multiply the base polynomial to
//              the passing polynomial (*this) and stores it back
//              to itself. The multiplication will call the
//              overloaded * to perform polynomials recursively.
//
// COMMENTS:    Poly overloaded ^ operator.
//              The ^ operator is overloaded so that a polynomial
//              may perform exponentiation.
// ================================================================

Poly Poly::operator^(const int nExp)
{
    Poly pp(1);

    for (int i = 0; i < nExp; i++)
        pp = pp * *this;

    return pp;
}

// ================================================================
// IDENTIFIER:  operator*(const int nNum, const Poly& p)
//
// PRE:         A polynomial that needs to be multiplied to an int
//
// INPUT PARAM: int nNum    --  An integer to be multiplied to poly
//              Poly& p     --  A reference polynomial
//
// POST:        A polynomial multiplied by an integer
//
// RETURN:      pp  --  The polynomial after multiplication
//
// ALGORITHM:   Create a polynomial with coefficient nNum.
//              nNum is cast from an integer to a polynomial.
//              Multiply the polynomial with the passing
//              polynomial p. The multiplication is done by calling
//              the * operator to perform multiplication of two
//              polynomials.
//
// COMMENTS:    Ordinary overloaded * operator.
//              The * operator is overloaded so that a polynomial
//              may be multiplied to an integer.
// ================================================================

Poly operator*(const int nNum, const Poly& p)
{
    Poly pp(nNum);
    pp = pp * p;
    return pp;
}

// ================================================================
// IDENTIFIER:  operator<<(ostream& out, const Poly& p)
//
// PRE:         A polynomial stored in a link list waiting to be
//              streamed to output using standard cout.
//
// INPUT PARAM: ostream& out    --  Standard cout stream
//              Poly& p         --  A reference polynomial
//
// POST:        All terms in the link list is displayed
//              algebraically on standard output
//
// RETURN:      out     --  For concatenation
//
// ALGORITHM:   If the polynomial doesn't exist, output 0.
//              Otherwise, run through the list and display each
//              term. Do not display the exponent if it carries 1,
//              and do not display the coefficient if it carries 1.
//              Move the pointer down the list, display + if the
//              coefficient is positive but display - if negative
//              first by negating the coefficient. Repeat through
//              until the end of the list.
//
// COMMENTS:    Ordinary overloaded << operator.
//              The << operator is overloaded so that
//              polynomials stored in the link list may be
//              output to the screen.
// ================================================================

ostream& operator<<(ostream& out, const Poly& p)
{
    pTerm curr = p.head;

    if (curr == NULL)
        out<<0;
    else
    {
        while (curr != NULL)
        {
            if (curr->nExp == 0)
                out<<curr->nCoeff;
            else if (curr->nExp == 1)
            {
                //do not display the coefficient if it is 1
                if (curr->nCoeff != 1)
                    out<<curr->nCoeff <<"X";
                else
                    out<<"X";
            }
            else
            {
                //do not display the coefficient if it is 1
                if (curr->nCoeff != 1)
                    out<<curr->nCoeff  <<"X^" <<curr->nExp;
                else
                    out<<"X^" <<curr->nExp;
            }

            curr = curr->next;

            //display the sign of the coefficient
            if (curr != NULL)
            {
                if (curr->nCoeff > 0)
                    out<<" + ";
                else
                {
                    //change coefficient from - to + and output -
                    out<<" - ";
                    curr->nCoeff = -(curr->nCoeff);
                }
            }
        }
    }
    return out;
}

// ================================================================
// IDENTIFIER:  operator>>(istream& in, Poly& p)
//
// PRE:         Data available to be read as a polynomial and
//              then stored to a link list
//
// INPUT PARAM: istream& in     --  Standard cin stream
//              Poly& p         --  A reference polynomial
//
// POST:        All data read will be stored in a link list
//
// CALLS:       InsertTerm      --  Inserts a coefficient
//                                  and exponent to the link list
//
// RETURN:      in  --  For concatenation
//
// ALGORITHM:   Delete any existing polynomials. Take input
//              character left paren (. Loop and take integer
//              inputs while ignoring all whitespaces. Insert
//              the coefficient and a fake exponent to the link
//              list. Coefficient with 0 will be ignored by the
//              InsertTerm() function. Loop until all integers are
//              read and right paren ) is captured. The exponent
//              is entered starting with 0 and incrementing by 1
//              every integer is read. When all integer is read,
//              decrement the exponent by 1 then run through the
//              link list correcting all the exponents by
//              subtracting current exponent to the previous one
//              entered. When all this is done, the link list
//              will have a sparse representation of the polynomial
//              with correct coefficient and exponents.
//
// COMMENTS:    Ordinary overloaded >> operator.
//              The >> operator is overloaded so that
//              data may be read and stored in a link list.
// ================================================================

istream& operator>>(istream& in, Poly& p)
{
    char ch = '\0';
    int nExp = 0, nCoeff = 0;

    // destroy existing Poly to accept new Poly
    p.~Poly();

    //ignore '('
    in>>ch;

    while (in.peek() != ')')
    {
        //skip whitespace otherwise read coefficient input
        if (in.peek() == ' ')
            in.ignore();
        else
        {
            //takes input and inserts coefficient
            //and fake exponent to the list
            in>>nCoeff;
            p.InsertTerm(nCoeff, nExp++);
        }
    }

    //ignore ')'
    in>>ch;

    //undo last exponent increment
    nExp--;

    pTerm curr = p.head;

    //run through the list correcting each exponent
    while (curr != NULL)
    {
        curr->nExp = nExp - curr->nExp;
        curr = curr->next;
    }
    return in;
}

// ================================================================
// IDENTIFIER:  RecAdd(pTerm t1, pTerm t2, Poly& p)
//
// PRE:         Two polynomials that needs to be added
//              term by term
//
// INPUT PARAM: pTerm t1    --  First term of object poly
//              pTerm t2    --  First term of passing poly
//              Poly& p     --  Reference polynomial with will be
//                              the result from addition
//
// POST:        The polynomial p from recursive addition
//
// CALLS:       InsertTerm      --  Inserts a coefficient
//                                  and exponent to the link list
//              RecAdd          --  Calls itself recursively to
//                                  perform addition term by term
//
// RETURN:      NONE    --  However, p is the true return value as
//                          p is both an argument and final value
//                          from passing by reference
//
// ALGORITHM:   Do nothing if both heads of the two polynomial
//              are empty. If first head t1 is empty. Insert the
//              head of t2 in the list; otherwise, insert the head
//              of t1. If t1's exponent is greater than t2's
//              exponent, insert t1's content in the list;
//              otherwise, if t2's exponent is greater, insert t2's
//              content. If both term have equal exponent value,
//              add the coefficient of the two terms and insert
//              the result to the list with its exponent. On each
//              of those case, update its corresponding term
//              pointer then call RecAdd again to perform each
//              addition of the polynomial term by term
//              recursively.
//
// COMMENTS:    The RecAdd() method performs term by term addition
//              of two polynomials recursively. The result p is
//              passed and returned by reference.
// ================================================================

void Poly::RecAdd(pTerm t1, pTerm t2, Poly& p)
{
    if(t1 != NULL || t2 != NULL)
    {
        if (t1 == NULL)
        {
            //insert t2 content if t1 is empty
            p.InsertTerm(t2->nCoeff, t2->nExp);
            t2 = t2->next;
        }
        else if (t2 == NULL)
        {
            //insert t1 content if t2 is empty
            p.InsertTerm(t1->nCoeff, t1->nExp);
            t1 = t1->next;
        }
        else
        {
            if (t1->nExp > t2->nExp)
            {
                //t1's exponent greater, so insert t1's content
                p.InsertTerm(t1->nCoeff, t1->nExp);
                t1 = t1->next;
            }
            else if (t1->nExp < t2->nExp)
            {
                //t2's exponent greater, so insert t2's content
                p.InsertTerm(t2->nCoeff, t2->nExp);
                t2 = t2->next;
            }
            else
            {
                //same exponent, insert added coefficient
                p.InsertTerm(t1->nCoeff + t2->nCoeff, t1->nExp);
                t1 = t1->next;
                t2 = t2->next;
            }
        }
        RecAdd(t1, t2, p);
    }
}

// ================================================================
// IDENTIFIER:  RecSub(pTerm t1, pTerm t2, Poly& p)
//
// PRE:         Two polynomials that needs to be subtracted
//              term by term
//
// INPUT PARAM: pTerm t1    --  First term of object poly
//              pTerm t2    --  First term of passing poly
//              Poly& p     --  Reference polynomial with will be
//                              the result from subtraction
//
// POST:        The polynomial p from recursive subtraction
//
// CALLS:       InsertTerm      --  Inserts a coefficient
//                                  and exponent to the link list
//              RecSub          --  Calls itself recursively to
//                                  perform subtraction term by
//                                  term
//
// RETURN:      NONE    --  However, p is the true return value as
//                          p is both an argument and final value
//                          from passing by reference
//
// ALGORITHM:   Do nothing if both heads of the two polynomial
//              are empty. If first head t1 is empty. Insert the
//              head of t2 in the list with its coefficient negated;
//              otherwise, insert the head of t1. If t1's exponent
//              is greater than t2's exponent, insert t1's content
//              in the list; otherwise, if t2's exponent is greater,
//              insert t2's content with negated coefficent. If
//              both term have equal exponent value, subtract the
//              coefficient of the two terms t1 - t2 and insert
//              the result to the list with its exponent. On each
//              of those case, update its corresponding term
//              pointer then call RecSub again to perform each
//              subtraction of the polynomial term by term
//              recursively.
//
// COMMENTS:    The RecSub method performs term by term subtraction
//              of two polynomials recursively. The result p is
//              passed and returned by reference.
// ================================================================

void Poly::RecSub(pTerm t1, pTerm t2, Poly& p)
{
    if (t1 != NULL || t2 != NULL)
    {
        if (t1 == NULL) 
        {
            //negate t2's coefficient and insert if t1 is empty
            p.InsertTerm(-(t2->nCoeff), t2->nExp);
            t2 = t2->next;
        }
        else if (t2 == NULL) 
        {
            //insert t1 content if t2 is empty
            p.InsertTerm(t1->nCoeff, t1->nExp);
            t1 = t1->next;
        }
        else
        {
            if (t1->nExp > t2->nExp)
            {
                //t1's exponent greater, so insert t1's content
                p.InsertTerm(t1->nCoeff, t1->nExp);
                t1 = t1->next;
            }
            else if (t1->nExp < t2->nExp)
            {
                //t2's exponent greater, insert t2's coeff negate
                p.InsertTerm(-(t2->nCoeff), t2->nExp);
                t2 = t2->next;
            }
            else
            {
                //same exponent, insert subtracted coefficient
                p.InsertTerm(t1->nCoeff - t2->nCoeff, t1->nExp);
                t1 = t1->next;
                t2 = t2->next;
            }
        }
        RecSub(t1, t2, p);
    }
}

// ================================================================
// IDENTIFIER:  RecMul(pTerm t1, pTerm t2, Poly& p)
//
// PRE:         Two polynomials that needs to be multiplied
//              term by term
//
// INPUT PARAM: pTerm t1    --  First term of object poly
//              pTerm t2    --  First term of passing poly
//              Poly& p     --  Reference polynomial with will be
//                              the result from multiplication
//
// POST:        The polynomial p from recursive multiplication
//
// CALLS:       InsertTerm      --  Inserts a coefficient
//                                  and exponent to the link list
//              RecMul          --  Calls itself recursively to
//                                  perform multiplication term by
//                                  term
//
// RETURN:      NONE    --  However, p is the true return value as
//                          p is both an argument and final value
//                          from passing by reference
//
// ALGORITHM:   Do nothing if 2nd polynomials head t2 is empty
//              (base case). Copy 1st poly's head to another
//              pointer pt. While pt (1'st poly's head) is not
//              empty, insert a term with the coefficient from
//              both head's multiplied and the exponents from
//              each term added. Update pt's pointer and keep
//              inserting until pt is empty. Add the new
//              polynomial after the multiplication of each
//              to passing polynomial p and stores it back to
//              itself. The adding of two polynomials is done
//              recusively by calling the overloaded + operator.
//              Call RecMul again by passing the head of t1,
//              the next pointer of t2, and the original poly p.
//              Keep calling RecMul until the base case is reached.
//
//
// COMMENTS:    The RecMul method performs term by term
//              multiplicably of two polynomials recursively.
//              The result p is passed and returned by reference.
// ================================================================

void Poly::RecMul(pTerm t1, pTerm t2, Poly& p)
{
    Poly pp;
    pTerm pt = t1;

    if (t2 != NULL)
    {
        while (pt != NULL)
        {
            //insert with multiplied coefficients and added exponents
            pp.InsertTerm(t2->nCoeff * pt->nCoeff, t2->nExp + pt->nExp);
            pt = pt->next;
        }
        p = p + pp;
        RecMul(t1, t2->next, p);
    }
}