/*
 *Daniel Tabuenca
 *###-##-3128
 *Login: dtabuenc
 *Lab section 23
 *Assignment 1
 *Due April 28, Friday, 11:59pm, 2000
 */


#include <stdio.h>
#include <string.h>
#include "polynomial.h"

#define BUFFERSIZE 80

istream &operator>>(istream &in, Polynomial &poly)
	{
	if (!poly.terms.empty())
		{
		cerr<<"Polynomial already initialized!\n";
		return in;
		}
	/*Buffer for reading in file*/
	char buffer[BUFFERSIZE];

	/*Character for storing trailing 
	 *bracket to check for valid expression.
	 */
	char bracket;

	/*variable to store polynomials
	 *we read from the file.
	 */
	PolyTerm newTerm;
	
	/*Loop forever*/
	for(;;)
		{
		/*Stop if no more lines to read*/
		
		in.getline(buffer,80);
		
		if(in.eof())
			{
			cerr<<"No valid Polynomial line found!\n";
			return in;
			}
		/*Stop if we found what looks like a polynomial
		 *This is a simple regular expression search for 
		 *any string surrounded by brackets. See the
		 *sscanf man page for more details
		 */
		if(sscanf(buffer, " [ %[^]] %c",buffer,&bracket)==2)
			{
			
			if(bracket==']')
				break;
			else
				continue;		
			}
		}

	/*Keep reading in terms until we find no comma*/
	for(;;)
		{
		if(sscanf(buffer, " %f ( %f )", &(newTerm.base), &(newTerm.exp))<2)
			{
			cerr<< "Malformed input!\n";
			return in;
			}
			
		/*Add the term to the linked list*/
		poly.terms.push_back(newTerm);
		
		/*Shrink the string down to what is after 
		 *the next comma. If there is no next comma 
		 *then there is no next element and we are
		 *done.
		 */
		if(sscanf(buffer, " %*f ( %*f ) , %[^a-Z]", buffer)!=1)
			{
			/*We are done inputting new terms so
			 *sort the list just for fun and then
			 *return.
			 */
			poly.terms.sort();	

			/*Also simplify the polynomial
			 *so all other algorithms will
			 *run faster.
			 */
			poly.simplify();
			return in;
			}
		}		
		
	}

/*Outputs the polynomial in specified format*/
ostream &operator<<(ostream &out, Polynomial &poly)
	{
	/*Check if we have terms in the polynomial*/
	if(poly.terms.empty())
		{
		cerr<<"Attempt to print uninitialize Polynomial\n";
		return out;
		}

	/*Set of iterators to traverse the linked
	 *list. The begin and end operator
	 *are just for speed to avoid a function
	 *call every time we need to check if 
	 *we are at the beginning or end.
	 */	
	TermListIterator term;
	TermListIterator begin=poly.terms.begin();
	TermListIterator end=poly.terms.end();

	/*We start with the open bracket*/
	out << "[";

	/*Go through the entire list printing each term*/
	for(term=poly.terms.begin(); term!=end; term++)
		{
		/*Don't output the comma the first time*/
		if(term!=begin)
			out <<", ";
		out << *term;
		}
	/*End with a bracket*/
	out << "]";
	return out;
	}

/*Simplify assumes it has been given
 *a sorted list of terms and goes through
 *efficiently combining like terms.
 */
void Polynomial::simplify()
	{
	TermListIterator currTerm;
	TermListIterator nextTerm;
	TermListIterator begin=terms.begin();
	TermListIterator end=terms.end();

	/*Set the first two terms to be checked*/
	currTerm=begin;
	nextTerm=begin;
	nextTerm++;

	/*We will go through the whole list*/
	while(nextTerm!=end)
		{
		/*If the exponent match we can combine them*/
		if( (*currTerm).exp == (*nextTerm).exp )
			{
			/*Add the base of the current one
			 *to the base of the next one*/
			*nextTerm+= *currTerm;

			/*We can now delete the current one
			 *(the return value is the iterator
			 *following the deleted one so we don't
			 *have to increment currTerm.
			 */
			currTerm=terms.erase(currTerm);

			/*Move the next iterator up one too.
			 */
			nextTerm++;
			continue;
			}

		/*We didn't find any match so move both
		 *up by one and try again.
		 */
		currTerm++;
		nextTerm++;
		}
	
	}
		
	
/*Add two polynomials returning a pointer to a newly
 *created polynomial.
 */
Polynomial *Polynomial::operator+(Polynomial &oldPoly)
	{
	Polynomial *newPoly= new Polynomial;
	Polynomial *oldBackup= new Polynomial;
	TermListIterator copyer;
	/*We first copy one of the polynomials to what will
	 *be the final result.
	 */
	for(copyer=terms.begin(); copyer!=terms.end();copyer++)
		{
		newPoly->terms.push_back(*copyer);
		}

	/*Back up the other one so it won't get erased*/
	for(copyer=oldPoly.terms.begin(); copyer!=oldPoly.terms.end();copyer++)
		{
		oldBackup->terms.push_back(*copyer);
		}

	/*Merge the two sorted lists*/

	 newPoly->terms.merge(oldBackup->terms);

	/*Combine like terms*/
	newPoly->simplify();

	/*clean up memory*/
	delete oldBackup;

	return newPoly;
	}	

/*Multiply an entire polynomial by a single term,
 *returning a new polynomail.
 */
Polynomial *Polynomial::operator*(PolyTerm &oldTerm)	
	{
	Polynomial *newPoly=new Polynomial;
	PolyTerm newTerm;
	TermListIterator currTerm;
	TermListIterator end=terms.end();

	/*We add to the new list each element of the 
	 *old list multiplied by the term.
	 */
	for(currTerm=terms.begin(); currTerm!=end;currTerm++)
		{
		newTerm= *currTerm;
		newTerm*=oldTerm;
		newPoly->terms.push_back(newTerm);
		}
	return newPoly;
	}

/*Multiply two polynomials, returning the new polynomial
 *as a pointer.
 */
Polynomial *Polynomial::operator*(Polynomial &oldPoly)
	{
	/*First figure out the smaller polynomial (less
	 *terms) in order to speed up the algorithm.
	 */
	Polynomial *bigger, *smaller;
	if(this->terms.size()>oldPoly.terms.size())
		{
		bigger=this;
		smaller=&oldPoly;
		}
	else
		{
		bigger=&oldPoly;
		smaller=this;
		}

	/*For each term in the small polynomial we will create a new polynomial
	 *so allocate an array of Polynomial Pointers for this purpose.
	 */
	Polynomial **mergeArray=new (Polynomial *)[smaller->terms.size()];

	/*Iterators to go through two polynomials*/
	TermListIterator smallIter,bigIter;

	/*Temporary holding place for term processing*/
	PolyTerm newTerm;

	int i=0;
	/*For each term in the smaller polynomial*/
	for(smallIter=smaller->terms.begin();smallIter!=smaller->terms.end();smallIter++)
		{
		/*Create a new polynomial*/
		mergeArray[i]=new Polynomial;
		/*For each term in the bigger polnomial*/
		for(bigIter=bigger->terms.begin();bigIter!=bigger->terms.end();bigIter++)
			{
			/*Get the term*/
			newTerm = *bigIter;

			/*Multiply by the term in the smaller 
			 *poly.
			 */
			newTerm *= *smallIter;
			/*Add the result to the new polynomial*/
			mergeArray[i]->terms.push_back(newTerm);
			}
		i++;
		}
	/*Create the actual new polynomial we will return.
	 */
	Polynomial *newPoly=new Polynomial;
	/*Set it equal to the first Polynomial in the array*/
	*newPoly=*mergeArray[0];

	/*Delete first polynomial from the array*/
	delete mergeArray[0];

	/*go through the array of polynomials (i is used from
	 *above as it contains the size of the array.
	 */
	for(int j=1; j<i; j++)
		{
		/*Merge the terms of the array to the new 
		 *Polynomial.
		 */
		newPoly->terms.merge(mergeArray[j]->terms);

		/*Delete each term as we don't need it anymosr*/
		delete mergeArray[j];
		}
	/*Delete the entire array*/
	delete [] mergeArray;
	/*Combine like terms*/
	newPoly->simplify();
	return newPoly;
		

	}