// HW5.cpp : 定義主控台應用程式的進入點。
//
#include <iostream>
using namespace std;

#define MAX_TERMS 10 /*size of terms array*/

class PolynomialTerm {
public:
	int coef;
	int expo;
};                                                                          /////

class ArrayPolynomial {                                        /////
public:                                                                  /////
	PolynomialTerm terms[MAX_TERMS]; /////

	void clear() /////
	{
		for (int i = 0; i < MAX_TERMS; i++) {
			terms[i].coef = 0;
			terms[i].expo = 0;
		}

		return;
	}

	void inputTerms(int coef, int expo) /////
	{
		for (int i = 0; i < MAX_TERMS; i++) {
			if (terms[i].coef == 0) {
				if (coef != 0) {
					terms[i].coef = coef;
					terms[i].expo = expo;
					return;
				}
			}
			else if (terms[i].expo == expo) {
				if (coef == 0) {
					for (int j = i; j < MAX_TERMS - 1; j++) {
						terms[j] = terms[j + 1];
					}
					terms[MAX_TERMS - 1].coef = 0;
					return;
				}
				else {
					terms[i].coef = coef;
					return;
				}
			}
			else if (terms[i].expo < expo) {
				if (coef != 0) {
					for (int j = MAX_TERMS - 1; j > i; j--)
						terms[j] = terms[j - 1];

					terms[i].coef = coef;
					terms[i].expo = expo;
					return;
				}
			}
		}
	}

	void addArrayBasedPoly(ArrayPolynomial& a, ArrayPolynomial& b) /////
	{
		clear();
		int starta = 0, startb = 0, startd = 0;
		while (starta < MAX_TERMS && startb < MAX_TERMS) {
			if (a.terms[starta].coef == 0 && b.terms[startb].coef == 0)
				break;

			if (a.terms[starta].expo > b.terms[startb].expo) {
				inputTerms(a.terms[starta].coef, a.terms[starta].expo);
				startd++; starta++;
			}
			else if (a.terms[starta].expo < b.terms[startb].expo) {
				inputTerms(b.terms[startb].coef, b.terms[startb].expo);
				startd++; startb++;
			}
			else {
				int sum = a.terms[starta].coef + b.terms[startb].coef;
				if (sum != 0) {
					inputTerms(sum, a.terms[starta].expo);
					startd++;
				}
				starta++; startb++;
			}
		}

		return;
	}

	void reverseArrayBasedPoly() /////
	{
		int start = 0;
		int end = MAX_TERMS - 1;

		while (start < end) {
			if (terms[end].coef != 0) { 
				PolynomialTerm temp = terms[start]; 
				terms[start] = terms[end]; 
				terms[end] = temp; 
				start++;
			}
			end--;
		}

		return;
	}

	void printArrayBasedPoly() /////
	{
		if (terms[0].coef == 0)
			return;

		if (terms[0].expo == 0)
			std::cout << terms[0].coef;
		else
			std::cout << terms[0].coef << "X^" << terms[0].expo;

		for (int i = 1; i < MAX_TERMS; i++) {
			if (terms[i].coef == 0)
				return;

			if (terms[i].expo == 0)
				std::cout << " + " << terms[i].coef;
			else
				std::cout << " + " << terms[i].coef << "X^" << terms[i].expo;
		}

		return;
	}

	int compute(int x)
	{
		int sum = 0;
		for (int i = 0; i < MAX_TERMS; i++) {
			int termvalue = 1;
			for (int j = 0; j < terms[i].expo; j++)
				termvalue *= x;
			
			sum += terms[i].coef * termvalue;
		}
		
		return sum;
	}
};

class LinkedPolynomialTerm {
public:
	int coef;
	int expo;
	LinkedPolynomialTerm* nextTermPtr; /////
};                                                                  /////

class LinkPolynomial {                                /////
public:                                                          /////
	LinkedPolynomialTerm* polynomialTermPtr = nullptr; /////

	void clear() /////
	{
		LinkedPolynomialTerm* tmpPtr;

		while (polynomialTermPtr != nullptr) {
			tmpPtr = polynomialTermPtr;
			polynomialTermPtr = polynomialTermPtr->nextTermPtr;
			delete tmpPtr;
		}

		return;
	}

	void inputLinkTerms(int coef, int expo) /////
	{
		LinkedPolynomialTerm* tmpPtr;

		tmpPtr = new LinkedPolynomialTerm;
		tmpPtr->coef = coef;
		tmpPtr->expo = expo;
		tmpPtr->nextTermPtr = nullptr;

		LinkedPolynomialTerm* current = polynomialTermPtr;
		LinkedPolynomialTerm* prev = nullptr;
		if (coef == 0) {
			while (current != nullptr) {
				if (current->expo == expo) {
					if (current == polynomialTermPtr) { //如果要刪除的節點是第一個
						polynomialTermPtr = current->nextTermPtr;  //第一個往後移
						delete current;
						return;
					}
					else {
						prev->nextTermPtr = current->nextTermPtr;
						delete current;
						return;
					}
				}
				else {
					if (current->nextTermPtr == nullptr)
						break;
					else {
						prev = current;
						current = current->nextTermPtr;
					}
				}
			}
		}
		else {
			if (polynomialTermPtr == nullptr) {
				polynomialTermPtr = tmpPtr;
				return;
			}
			else {
				while (current != nullptr && current->expo > expo) {
					prev = current;
					current = current->nextTermPtr;
				}
				if (current == nullptr)
					prev->nextTermPtr = tmpPtr;
				else {
					if (current->expo == expo)
						current->coef = coef;
					else {
						tmpPtr->nextTermPtr = current;
						if (prev != nullptr)
							prev->nextTermPtr = tmpPtr;
						else
							polynomialTermPtr = tmpPtr;  //插在第一個
					}
				}
			}
			return;
		}
	}

	void addLinkBasedPoly(LinkPolynomial& aPol, LinkPolynomial& bPol) {
		/////
		clear();
		LinkedPolynomialTerm* aterm = aPol.polynomialTermPtr;
		LinkedPolynomialTerm* bterm = bPol.polynomialTermPtr;
		LinkedPolynomialTerm* current = nullptr;
		LinkedPolynomialTerm* dterm = nullptr;

		while (aterm != nullptr || bterm != nullptr) {
			LinkedPolynomialTerm* tmpptr = new LinkedPolynomialTerm;
			tmpptr->nextTermPtr = nullptr;

			if (aterm != nullptr && bterm != nullptr) {
				if (aterm->expo == bterm->expo) {
					tmpptr->coef = aterm->coef + bterm->coef;
					tmpptr->expo = aterm->expo;
					aterm = aterm->nextTermPtr;
					bterm = bterm->nextTermPtr;
				}
				else if (aterm->expo > bterm->expo) {
					tmpptr->coef = aterm->coef;
					tmpptr->expo = aterm->expo;
					aterm = aterm->nextTermPtr;
				}
				else {
					tmpptr->coef = bterm->coef;
					tmpptr->expo = bterm->expo;
					bterm = bterm->nextTermPtr;
				}
			}

			else if (aterm != nullptr) {
				tmpptr->coef = aterm->coef;
				tmpptr->expo = aterm->expo;
				aterm = aterm->nextTermPtr;
			}
			else if (bterm != nullptr) {
				tmpptr->coef = bterm->coef;
				tmpptr->expo = bterm->expo; 
				bterm = bterm->nextTermPtr;
			}
			if (tmpptr->coef != 0) {
				if (dterm == nullptr)
					dterm = tmpptr;
				else
					current->nextTermPtr = tmpptr;

				current = tmpptr;
			}
		}
		polynomialTermPtr = dterm;
	}


	void reverseLinkBasedPoly() /////
	{
		/////
		if (polynomialTermPtr == nullptr || polynomialTermPtr->nextTermPtr == nullptr)
			return;
		
		LinkedPolynomialTerm* prev = nullptr;
		LinkedPolynomialTerm* current = polynomialTermPtr;
		LinkedPolynomialTerm* preceding = polynomialTermPtr->nextTermPtr;

		while (preceding != nullptr) {
			current->nextTermPtr = prev;  // 把current->next轉向
			prev = current;				  // prev往後移
			current = preceding;		  // current往後移
			preceding = preceding->nextTermPtr;	// preceding往後移
		}

		current->nextTermPtr = prev;  //current為最後一個節點，將current->next轉向
		polynomialTermPtr = current;  //更新polynomialTermPtr為current

		return;
	}

	void printLinkBasedPoly()                                                            /////
	{
		LinkedPolynomialTerm* termPtr = polynomialTermPtr; /////

		if (termPtr == nullptr)
			return;

		if (termPtr->expo == 0)
			cout << termPtr->coef;
		else
			cout << termPtr->coef << "X^" << termPtr->expo;

		termPtr = termPtr->nextTermPtr;

		while (termPtr != nullptr) {
			if (termPtr->coef == 0)
				return;

			if (termPtr->expo == 0)
				cout << " + " << termPtr->coef;
			else
				cout << " + " << termPtr->coef << "X^" << termPtr->expo;

			termPtr = termPtr->nextTermPtr;
		}

		return;
	}

	int compute(int x)
	{
		int sum = 0;
		LinkedPolynomialTerm* termPtr = polynomialTermPtr;
		while (termPtr != nullptr) {
			int termvalue = 1;
			for (int i = 0; i < termPtr->expo; i++)
				termvalue *= x;

			sum += termPtr->coef * termvalue;
			termPtr = termPtr->nextTermPtr;
		}
		
		return sum;
	}
};

int main()
{
	ArrayPolynomial a, b, d;                                                              /////
	LinkPolynomial aPol, bPol, dPol;                                             /////

	int coef, expo, x;

	// aPtr = bPtr = dPtr = nullptr; /////

	while (1) {
		a.clear(); b.clear(); d.clear();                                    /////
		// aPtr->clear(aPtr); bPtr->clear(bPtr); dPtr->clear(dPtr); /////


		for (int i = 0; i < MAX_TERMS; i++) {
			cout << "\ninput a's coefficient and exponent: ";
			cin >> coef >> expo;

			if (expo == 0 && coef == 0)
				break;

			a.inputTerms(coef, expo);             /////
			aPol.inputLinkTerms(coef, expo); /////
		}

		cout << "\n\na = ";
		a.printArrayBasedPoly();     /////
		cout << "\na = ";
		aPol.printLinkBasedPoly(); /////
		cout << "\n";

		for (int i = 0; i < MAX_TERMS; i++) {
			cout << "\ninput b's coefficient and exponent: ";
			cin >> coef >> expo;

			if (expo == 0 && coef == 0)
				break;

			b.inputTerms(coef, expo);             /////
			bPol.inputLinkTerms(coef, expo); /////
		}

		cout << "\n\nb = ";
		b.printArrayBasedPoly();      /////

		cout << "\nb = ";
		bPol.printLinkBasedPoly(); /////

		cout << "\n";

		// d =a + b, where a, b, and d are polynomials

		d.addArrayBasedPoly(a, b); /////
		cout << "\na + b = ";
		d.printArrayBasedPoly();     /////

		dPol.addLinkBasedPoly(aPol, bPol); /////
		cout << "\na + b = ";
		dPol.printLinkBasedPoly();               /////

		cout << "\n";

		d.reverseArrayBasedPoly(); /////
		cout << "\nreversed d = ";
		d.printArrayBasedPoly();     /////

		dPol.reverseLinkBasedPoly(); /////
		cout << "\nreversed d = ";
		dPol.printLinkBasedPoly();               /////

		cout << "\n";

		cout << "\ninput X: ";
		cin >> x;

		cout << "\nd = ";
		cout << d.compute(x);      //////

		cout << "\nd = ";
		cout << dPol.compute(x); //////

		cout << "\n";

		aPol.clear(); bPol.clear(); dPol.clear(); /////
	}

	return 0;
}

/*
測資1:
0 5 3 0 7 1 1 1 -2 2 2 2 3 3 0 2 4 4 0 0
a = 4X^4 + 3X^3 + 1X^1 + 3
-3 0 0 7 8 1 -1 1 3 2 -2 2 -3 3 0 2 -4 4 0 0
b = -4X^4 + -3X^3 + -1X^1 + -3
a + b =

測資2:
7 3 2 5 1 7 4 8 2 3 5 5 1 0 0 3 0 0
a = 4X^8 + 1X^7 + 5X^5 + 1
2 5 -5 5 1 3 3 7 5 0 8 0 0 3 0 0
b = 3X^7 + -5X^5 + 8
a + b = 4X^8 + 4X^7 + 9

測資3:
8 8 7 7 6 6 3 3 4 4 5 5 2 0 1 9 0 0
a = 1X^9 + 8X^8 + 7X^7 + 6X^6 + 5X^5 + 4X^4 + 3X^3 + 2
-8 8 -7 7 -6 6 0 8 8 0 -8 8 9 9 0 0
b = 9X^9 + -8X^8 + -7X^7 + -6X^6 + 8
a + b = 10X^9 + 5X^5 + 4X^4 + 3X^3 + 10

測資4:
3 0 7 2 2 2 7 4 0 1 4 5 -8 9 -4 3 0 0
a = -8X^9 + 4X^5 + 7X^4 + -4X^3 + 2X^2 + 3
5 2 0 3 -5 2 -2 9 7 0 6 3 0 3 -7 4 2 1 0 0
b = -2X^9 + -7X^4 + -5X^2 + 2X^1 + 7
a + b = -10X^9 + 4X^5 + -4X^3 + -3X^2 + 2X^1 + 10

測資5:
0 9 0 7 0 3 0 1 2 0 0 0
a = 2
5 4 8 9 0 2 0 0
b = 8X^9 + 5X^4
a + b = 8X^9 + 5X^4 + 2
*/