#include <stdio.h>
#include <stdlib.h>


typedef struct node
{
    float coef;      /* coeffecient */
    int exp;       /* exponent */
    struct node *next;
}node;

#define nodealloc (struct node *)malloc(sizeof(struct node)) 

typedef struct node *poly;

/******************POLYNOMIAL FUNCTIONS PROTOTYPE************************/

poly create(void);              /* Create a linked list of polynomials. */
poly creat1(void);             /* for sorting */
void display(poly);
void displayadd(poly);       /* hack for add display */ 
void len(void);
int length(poly);        /* Main length function */
poly add(poly, poly);    /* Main add function  */
void addpoly(void);
poly negate(poly);
void sub(void);

poly empty(int);         /* empty poly list for addition result  */
void coef(void);               /* Coef of a particular power */
void eval(void);
poly sort(poly);               /* Main sort function */
void sort1(void);
void high(void);          /* highest power */
poly mutiply(poly, poly);
void multi(void);
void diff(void);

/* ///////////////////////////////////////// */


/* ///////////////////////////////////////// */
int main()
{
    int choice;
    while(choice!=10)
    {

	printf("\n\nSelect.\n");
	printf("1 : Add two polynomials.\n");
	printf("2 : Subtract two polynomials.\n");
	printf("3 : Multiply polynomials.\n");
	printf("4 : Evaluate.\n");
	printf("5 : Sort the polynomial.\n");
	printf("6 : Find Coefficient of power.\n");
	printf("7 : Length of the polynomial.\n");
	printf("8 : Highest power.\n");
	printf("9 : Nth order difference.\n");
	printf("10: Exit.\n");
	scanf("%i",&choice);
	switch(choice)
	{
	    case 1: addpoly();
		break;
	    case 2: sub();
		break;
	    case 3: multi();
		break;
	    case 4: eval();
		break;
	    case 5: sort1();
		break;
	    case 6: coef();
		break;
	    case 7: len();
		break;
	    case 8: high();
		break;
	    case 9: diff();
		break;
	} /*  switch end */
    }/*  while end  */
    return(0);
}  /* main end */


/******************POLYNOMIAL FUNCTIONS************************/

poly create()
{
    int exp,i;
    float coef;
    poly head=NULL, newnode, temp=NULL;
    
    while(1)
    {
	printf("\nWhat is the degree of Polynomial.\n");
	scanf("%i",&exp);
	if(exp < 0)
	{
	    printf("\nPower should be greater than 0.");
	    continue;
	}
	break;
    }
    
    for(i=0;i<=exp;i++)
    {
	printf("\nEnter the coefficient of x^%i: ",(exp-i));
	scanf("%f",&coef);
	if(!i && !coef)
	{
	    printf("\nCoefficient not allowed.\n");
	    i--;
	    continue;
	}

	if(coef)
	{
	    newnode = nodealloc;  /* Macro */
	    newnode->coef = coef;
	    newnode->exp = (exp-i);
	    newnode->next = NULL;

	    if(head==NULL)
     		temp=head = newnode;
	    else
	    {
		temp->next = newnode;
		temp = newnode;
	    }
	}
    } /* if */
    
    return head;
} /* create */

poly create1()    /* Required for sorting */
{
    int expo,i,number;
    poly first=NULL, newnode, temp;
 error:                                             /* Error checking  */
    printf("\nEnter the number of polynomials.\n"); /* No of polynomials to be entered. */
    scanf("%i",&number);
    if(number<1)
      {
	printf("\nEnter a number greater than 0.\n");
	goto error;
      }
    for(i=0; i<number; i++)
      {
	newnode = nodealloc;             /* Macro */
	newnode->next = NULL;
	printf("Enter the Coefficient.\n");
	scanf("%f",&newnode ->coef);
      experr:
	printf("Enter the Exponent.\n");
	scanf("%d",&expo);
	if(expo<0)
	{
	    printf("\nEnter a number greater than or equal to 0.\n");
	    goto experr;
	}
	newnode->exp=expo;

	if(first==NULL)
	    temp= first=newnode;
	else
	{
	    temp->next = newnode;
	    temp = newnode;
	}
      }  /* for */
    return(first);
}


void display(poly head)
{
    if(!head)
	return;
    printf("\n%gx^%d ",head->coef, head->exp);
    head = head->next;
    while(head)
    {
	if(head->coef < 0)
	{
	    printf("- %gx^%d ",-(head->coef),head->exp);
	}
	else
	{
	    printf("+ %gx^%d ",head->coef,head->exp);
	}
	head = head->next;
    }
    printf("\n");
} /* display */


void addpoly(void)
{
    poly poly1, poly2, result;
    poly1=sort(poly1=create());
    
    display(poly1);
    poly2=sort(poly2=create());
    
    display(poly2);

    result=add(poly1,poly2);
    display(result);
}


poly add(poly one, poly two)
{
    int flag;
    poly polynode=NULL,current=NULL,newnode;
    
    while(one && two)
    {
	flag=0;
	while(one && two && one->exp > two->exp) /* err if anyone has ended */
	{
	  newnode = nodealloc;
	  newnode->coef = one->coef;
	  newnode->exp = one->exp;
	  newnode->next = NULL;
	  /* /////////////// */
	  if(current)
	    current->next = newnode;
	  one = one->next;
	  current = newnode;
	  if(!polynode)
	    polynode = newnode;
	  flag=1;
        }
      while(one && two && two->exp > one->exp)
        {
	  newnode = nodealloc;
	  newnode->coef = two->coef;
	  newnode->exp = two->exp;
	  newnode->next = NULL;
	  if(current)
	    current->next = newnode;
	  two = two->next;
	  current = newnode;
	  if(!polynode)
	    polynode = newnode;
	  flag=1;
        }

	  /* //////////// */
      if(flag)
	  continue;

      if(one->coef + two->coef)
        {
	  newnode = nodealloc;
	  newnode->coef = one->coef + two->coef;
	  newnode->exp = one->exp;
	  newnode->next = NULL;
	  if(current)
	    current->next = newnode;
	  if(!polynode)
	    polynode = newnode;
	  current = newnode;
        }
      one = one->next;
      two = two->next;

    }
	  /* //////////// */

  if(one)
    {
      if(current)
	current->next = one;
      else
	  return(one); 	  /*	return one; */
    }
  if(two)
    {
      if(current)
	current->next = two;
      else
	  return(two);
    }

  /*  return polynode; */
  return(polynode);

} /* End add */


poly negate(poly list)
{
    poly temp=list;
    while(list)
    {
	list->coef= -(list->coef);
	list= list->next;
    }
    
    return(temp);
}

void sub(void)
{
    
    poly poly1, poly2, result;
    poly1=sort(poly1=create());
    
    display(poly1);
    poly2=sort(poly2=create());
    
    display(poly2);
    
    poly2=negate(poly2);      /* negate the second poly and add */

    result=add(poly1,poly2);
    display(result);
    

} /* end sub */


poly multiply(poly list1, poly list2)
{
    poly tempa, tempb= list2, result=NULL, temp=NULL,newnode, current;
    int exp;
    float coef;

    while(tempb)
    {
	tempa=list1;
	temp= NULL;
	current = NULL;

	while(tempa)
	{
	    exp = tempa->exp + tempb->exp;
	    coef = tempa->coef * tempb->coef;
	    newnode = nodealloc;
	    newnode->next = NULL;
	    newnode->coef = coef;
	    newnode->exp = exp;

	    if(current)
		current->next = newnode;
	    current=newnode;
	    if(!temp)
		temp=newnode;

	    tempa = tempa->next;
	} /*  inner */

	result=add(result,temp);
	tempb = tempb->next;


    } /*  outer */
    return(result);
} /* end multply */


void multi(void)
{
    poly list1,list2, result;
    list1=create();

    list2=create();

    result=multiply(list1, list2);
    result=sort(result);
    display(result);
} /* end multi */




void eval(void)
{
    int val,pow=1,expo,i,result,ans=0;
    poly list;
    list=create();
    list=sort(list);
    printf("\nEnter the value of x.\n");
    scanf("%i",&val);
    while(list!=NULL)
    {
	expo=list->exp;
	for(i=0;i<expo; i++)   /* To get the exponent x^n  */
	    pow= pow * val; 
   
	result= pow * list->coef;
	pow=1;
	ans=ans+result;
	
	list= list->next;

    } /* main while */
    printf("\nAns - %i\n",ans);
}  /* end eval */


poly sort(poly first)      /* Insertion sort */ 
{
    if(first==NULL)
	printf("\nEmpty.\n");
    else
    {
	poly nextnode=first;
	poly curr=first,tmp;
	int ex,co;
	while(nextnode)
	{
	    tmp=nextnode->next;
	    while(tmp)
	    {
		if((curr->exp) < (tmp->exp))
		{
		    ex=curr->exp;
		    co=curr->coef;
		    curr->exp=tmp->exp;
		    curr->coef=tmp->coef;
		    tmp->exp=ex;
		    tmp->coef=co;
		} /*  if end */
		tmp=tmp->next;

	    } /*  inner while */
	    nextnode=nextnode->next;
	    curr=curr->next;

	} /* outer  while  */
    } /*  else */
    return(first);
} /* sort */

void sort1()
{
    poly listsort;
    listsort=create1();
    printf("Polynomial before sorting.\n");
    display(listsort);

    listsort=sort(listsort);
    printf("\n\nPolynomial after sorting.\n\n");
    display(listsort);
      
} /* sort end */


void coef()  /* coef of particular power */
{
    int pow;
    poly list;
    list=create();
    list=sort(list);
    printf("\nEnter power whose coefficent you want.\n");
    scanf("%i",&pow);
    while(list!=NULL)
    {
	if((list->exp)==pow)
	{
	    printf("\nCoefficient of power %i is %g.\n",pow,list->coef);
	    return;
	}
	list=list->next;
    }
    printf("\nCoefficient of power %i does not exist.\n",pow);
} /* end Coef */




int length(poly first)
{
    int count=0;
    while(first!=NULL)
    {
	count++;
	first = first -> next;
    }
    return(count);
}

void len()
{
    poly list;
    list=create();
    list=sort(list);
    printf("The length of the polynomial is %i\n",length(list));
}


void high()
{
    poly list;
    list=create();
    if(!list)
    {
	printf("\nPolynomial empty.\n"); 
	return;
    }
    else
    {
	list=sort(list);
	printf("\nHighest power is %i.\n",list->exp);    
	return;
    }
}


void diff(void)   /* nth order difference */
{
    int order;
    poly diff,diff1;

    diff=sort(diff=create());
    diff1=diff;
    display(diff);
 orderr:
    printf("\nDifferentiation of order - ");
    scanf("%i",&order);
    if(order<1)
    {
	printf("\nThe order should be greater than 0.\n");
	goto orderr;
    }
    
    if(order>=length(diff1))
    {
	printf("\n0\n");
	return;
    }

    while(order)
    {
	diff=diff1;
/* Check if nodes next exists if yes is the power greater than 0 */
	while(diff && diff->next->next && diff->next->exp!=0)
	{
	    if(diff->exp)
	    {
	    diff->coef=diff->coef * diff->exp;
	    diff->exp=(diff->exp - 1);
	    diff=diff->next;
	    }  
	} /*  inner */
	if(diff->next)
	{
	    diff->coef=diff->coef * diff->exp;
	    diff->exp=(diff->exp - 1);
	    diff->next=NULL;
	} /* if */
	else
	{
	    diff->coef=0;
	    diff->exp=0;
	    diff->next=NULL;
	    display(diff1);
	    return;
	}
	
	order--;
    } /* outer */
    display(diff1);
    return;
} /* end diff */