/* 
This code demostrate how two polynomial can be representaed by
two linked list and then sort and combine them to represent 
a single polynomial

Notes
	No data reading from file
	Data members are public
 	No new list is formed

author	vmtom@iitb.ac.in
date	Tue Sep 20 18:20:31 IST 2005
*/

#include <fstream.h>
#include <math.h>

class term
{
	public:
		int expo;
		float val;
	public:
		term(){expo=0;val=0.0;}
		term(int e,float v)
		{
			expo=e;val=v;
		}
		void printC()
		{
			cout<<val;cout.flush();
			cout<<"x^";cout.flush();
			cout<<expo;cout.flush();
		}
};

class poly
{
	public:
		term* item;
		poly* next;
	public:
		poly(){next=NULL;item=NULL;};

		poly(int i, float f){item = new term(i,f);next=NULL;};

		void setP(poly* n)
		{
			item->expo=n->item->expo;
			item->val=n->item->val;
		}
		void printP()
		{
			if(item==NULL) return;
			item->printC();
		}
};

void main()
{
	int i=0;
	poly* prev1=NULL;
	poly* prev2=NULL;
	poly* lst1=NULL;
	poly* lst2=NULL;
	poly* cur=NULL;
	poly* tmp=NULL;

	// Data for polynomial 2
	//
	int cnt1=5;
	int aval1[5];
	float bval1[5];
	aval1[0]=3; bval1[0]=+4.4;
	aval1[1]=4; bval1[1]=-2.4;
	aval1[2]=4; bval1[2]=-5.4;
	aval1[3]=4; bval1[3]=-4.4;
	aval1[4]=4; bval1[4]=+4.4;

	// Data for polynomial 2
	//
	int cnt2=4;
	int aval2[4];
	float bval2[4];
	aval2[0]=4; bval2[0]=+2.4;
	aval2[1]=3; bval2[1]=-2.4;
	aval2[2]=3; bval2[2]=-3.4;
	aval2[3]=7; bval2[3]=-1.4;

	// Creating polynomial 1
	//
	for(i=0;i<cnt1;i++)
	{	
		cur = new poly(aval1[i],bval1[i]);

		if(lst1==NULL)
		{
			lst1 = cur;
			lst1->setP(cur);
		}
		else if(prev1!=NULL)
		{
			prev1->next=cur;
		}
		prev1=cur;
	 	prev1->setP(cur);
	}

	// Creating polynomial 2
	//
	for(i=0;i<cnt2;i++)
	{	
		cur = new poly(aval2[i],bval2[i]);

		if(lst2==NULL)
		{
			lst2 = cur;
			lst2->setP(cur);
		}
		else if(prev2!=NULL)
		{
			prev2->next=cur;
		}
		prev2=cur;
	 	prev2->setP(cur);
	}

	// Printing polynomial 1
	//
	tmp=lst1;
	cout<<"\nPolynimial 1\t:\t";
	while(tmp!=NULL)
	{
		tmp->printP();
		cout << "+";
		tmp=tmp->next;
	}

	// Printing polynomial 2
	//
	tmp=lst2;
	cout<<"\nPolynimial 2\t:\t";cout.flush();
	while(tmp!=NULL)
	{
		tmp->printP();
		cout << "+";
		tmp=tmp->next;
	}

	// Combining polynomail 1 and 2
	//
	prev1->next=lst2;

	// Printing polynomial 1+2 (unsorted with duplicate terms) 
	//
	tmp=lst1;
	cout<<"\nPolynimial 1,2\t:\t";cout.flush();
	while(tmp!=NULL)
	{
		tmp->printP();
		cout << "+";
		tmp=tmp->next;
	};
		

	//	Finding the maximum power value
	//
	tmp=lst1;
	int maxPow=-1;
	while(tmp!=NULL)
	{
		int j= tmp->item->expo;
		if(j>maxPow)
		{
			maxPow=j;
		}
		tmp=tmp->next;
	};
	cout<<"\nMax exponent\t:\t"<<maxPow;

	//	Sorting and combining coefficients with same exponent
	//
	cout<<"\nPolynimial 1+2\t:\t";cout.flush();
	while(maxPow>-1)
	{
		tmp=lst1;
		float cumCoeff=0.0;
		while(tmp!=NULL)
		{
			int j= tmp->item->expo;
			if(j==maxPow)
				cumCoeff+=tmp->item->val;
			tmp=tmp->next;
		};
		if(fabs(cumCoeff)>0.0)
			cout<<cumCoeff<<"x^"<<maxPow<<" + ";
		maxPow--;
	};

	cout << "\n\n"; cout.flush();
}