//
// polynom.cpp
//
// A program that uses linked lists to represent polynomials
//
// Computer Science S-111, Harvard University
//

#include <iostream.h>
#include "../util/getinput.hpp"


//
// structure for nodes in a linked list that represents a polynomial
// of a single variable.  The assumption is that the nodes will be
// given in increasing order by their exponents, although the code
// below doesn't actually check for this.
//
struct polynom {
    double coeff;
    int expon;
    polynom *next;
};


//
// power - function to compute x^n
//
double
power(double x, int n)
{
    int exp;
    double result;

    // Build up the power: x, x^2, x^4, x^8, ...
    result = x;
    exp = n;
    while (exp > 1) {
	exp = exp / 2;
	result = result * result;
    }

    // If n is odd (and greater than 1), do the extra multiplication now.
    if (n > 1  &&  n % 2 == 1) 
	result = result * x;

    return result;
}

//
// read - reads in a polynomial and stores it in the list 
// pointed to by p
//
void
read(polynom*& p)
{
    double cf;
    int ex;
    
    p = NULL;

    cout << "COEFFICIENT - 0 IF NO MORE TERMS : ";
    cin >> cf;
    if (cf == 0.0)
	return;

    ex = ReadInteger("EXPONENT ");

    p = new polynom;
    p->coeff = cf;
    p->expon = ex;

    // recursively read and build the remaining terms
    read(p->next);
}

//
// write - writes out the polynomial in the list pointed to by p
//
void
write(polynom *p)
{
    while (p != NULL) {
	cout << p->coeff;
	if (p->expon > 0) {
	    if (p->expon == 1)
		cout << "x";
	    else {
		cout << "x^";
		cout << p->expon;
	    }
	}
	cout << " ";

	p = p->next;
	if ((p != NULL) && (p->coeff > 0.0))
	    cout << "+";
    }
}

//
// eval - evaluates the polynomial in p for the specified value of x
//
double
eval(polynom *p, double x)
{
    double pvalue = 0.0;

    if (x != 0.0) {
	while (p != NULL) {
	    pvalue += p->coeff * power(x, p->expon);
	    p = p->next;
	}
    } 

    return pvalue;
}

//
// copy - returns a deep copy of the polynomial pointed to by p
//
polynom *
copy(polynom *p)
{
    if (p == NULL)
	return NULL;
    
    polynom *head = new polynom;
    polynom *temp = head;
    
    while (p != NULL) {
	// Copy the current node.
	temp->coeff = p->coeff;
	temp->expon = p->expon;
	temp->next = NULL;

	//
	// If there's more to come, create the next node
	// of the copy and advance to it.
	//
	if (p->next != NULL) {
	    temp->next = new polynom;
	    temp = temp->next;
	}

	p = p->next;
    }

    return head;
}

//
// add - takes pointers to two polynomials and returns a pointer
// to a new polynomial that is their sum
//
polynom *
add(polynom *p1, polynom *p2)
{
    polynom *head = NULL;
    polynom *tail = NULL;

    while (p1 != NULL || p2 != NULL) {
	// Create a new node.
	polynom *temp = new polynom;

	// Three possible cases:
	if (p2 == NULL || (p1 != NULL  &&  p1->expon < p2->expon)) {
	    //
	    // (1) either p2 is done or p1's term has a smaller exponent,
	    // so the next term is a copy of p1's term and we advance p1
	    //
	    temp->expon = p1->expon;
	    temp->coeff = p1->coeff;
	    p1 = p1->next;
	}
	else if (p1 == NULL || (p2 != NULL  &&  p2->expon < p1->expon)) {
	    //
	    // (2) either p1 is done or p2's term has a smaller exponent,
	    // so the next term is a copy of p2's term and we advance p2
	    //
	    temp->expon = p2->expon;
	    temp->coeff = p2->coeff;
	    p2 = p2->next;
	}
	else {
	    // (3) two terms with equal exponents
	    temp->expon = p1->expon;
	    temp->coeff = p1->coeff + p2->coeff;
	    p1 = p1->next;
	    p2 = p2->next;
	}   

	if (head == NULL) {
	    //
	    // first term of the sum - so we need to keep a
	    // permanent head pointer to it
	    //
	    head = temp;
	    tail = temp;
	}
	else {
	    // link the new node to the previous one
	    tail->next = temp;
	    tail = temp;
	}
    }

    tail->next = NULL;
    return head;
}

//
// mult_by_term - multiply a polynomial by a single term and return a pointer
// to a new polynomial containing the result.
//
polynom *
mult_by_term(polynom *p, polynom *term)
{
    if (p == NULL || term == NULL)
	return NULL;

    polynom *head = new polynom;
    polynom *temp = head;
    
    while (p != NULL) {
	temp->coeff = p->coeff * term->coeff;
	temp->expon = p->expon + term->expon;
	temp->next = NULL;
	
	if (p->next != NULL) {
	    temp->next = new polynom;
	    temp = temp->next;
	}
	
	p = p->next;
    }
    
    return head;
}

//
// mult - multiply two polynomials together and return a pointer
// to a new polynomial containing the result.
//
polynom *
mult(polynom *p1, polynom *p2)
{
    if (p1 == NULL || p2 == NULL)
	return NULL;

    polynom *result = NULL;

    //
    // Note that we have a memory leak here that we're not dealing
    // with, but we would eventually need to address it.
    //
    while (p1 != NULL) {
	result = add(result, mult_by_term(p2, p1));
	p1 = p1->next;
    }
    
    return result;
}


int
main()
{
    polynom *poly1, *poly2, *poly3;
    double x;

    cout << "ENTER YOUR POLYNOMIAL  \n";
    read(poly1);
    write(poly1);
    cout << "\n";

    cout << "\nENTER VALUE FOR x : ";
    cin >> x;
    cout << "VALUE IS " << eval(poly1, x) << "\n";

    cout << "\nENTER YOUR SECOND POLYNOMIAL  \n";
    read(poly2);
    write(poly2);
    cout << "\n";

    cout << "\nENTER VALUE FOR x : ";
    cin >> x;
    cout << "VALUE IS " << eval(poly2, x) << "\n";

    cout << "\nSUM OF FIRST AND SECOND POLYNOMIALS IS \n";
    poly3 = add(poly1, poly2);
    write(poly3);
    cout << "\n";

    cout << "\nENTER VALUE FOR x : ";
    cin >> x;
    cout << "VALUE OF SUM POLY IS " << eval(poly3, x) << "\n";

    // Another memory leak, but we're about to exit anyway!
    cout << "\nPRODUCT OF FIRST AND SECOND POLYNOMIALS IS \n";
    poly3 = mult(poly1, poly2);
    write(poly3);
    cout << "\n";

    cout << "\nENTER VALUE FOR x : ";
    cin >> x;
    cout << "VALUE OF PRODUCT POLY IS " << eval(poly3, x) << "\n";
}


