// ================================================================
// 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);
}
}