/*
 *        File: polynomial.cpp
 *        Author: Leonid Reyzin
 *        Date:  March 2003
 *        Class: CS112B1
 * --------------------------------------------------------------------
 */

#include "polynomial.h"      /* declarations of the class */


#include<iostream>
using namespace std;


/*------------------------------------------------------------*/

        /* Monomial::Monomial()  constructor
        *  Initializes a Monomial to point to NULL
        */

Monomial::Monomial()
{
  next  = NULL;
}

/*------------------------------------------------------------*/

        /* Monomial::Monomial(newitem, newnext)  constructor
        *  Initializes a Monomial to contain newitem and point
	*  to newnext
        */
Monomial::Monomial(int newdegree, float newcoeff, Monomial * newnext)
{
  degree = newdegree;
  coeff = newcoeff;
  next = newnext;
}


/*------------------------------------------------------------*/

        /* Polynomial::Polynomial  constructor
        * creates a polynomial and initializes it to 0
        */

Polynomial::Polynomial()
{
  list = NULL;
}

/*------------------------------------------------------------*/

        /* Polynomial::~Polynomial  destructor
        *  frees up the memory taken up by a polynomial
        */
Polynomial::~Polynomial()
{
  Init();
}

/*------------------------------------------------------------*/

       /* Polynomial::Init:
        * Empties and re-initializes a polynomial to 0
        */
bool Polynomial::Init()
{
  Monomial * newlist;

  while (list != NULL) {
    newlist = list->next;
    delete list;
    list = newlist;
  }
  list=NULL;
  return true;
}

/*------------------------------------------------------------*/

       /* Polynomial::IsZero:
        * checks whether a polynomial is zero.
        */
bool Polynomial::IsZero() const
{
  return (list==NULL);
}

/*------------------------------------------------------------*/

       /* Polynomial::AddMonomial:
	* Adds a monomial to a polynomial
        * returns true if successful, false if out of memory
        */

bool Polynomial::AddMonomial(int degree, float coeff)
{
  Monomial *newnode, *biggernode, *smallernode=NULL;


  if (coeff==0.0) // Nothing to do
    return true;
  
  // Find the location where to insert.  At the end of this loop,
  // biggernode will point to the node at or after the insertion point
  // (or NULL if insertion is at the end of the list), while smallernode
  // will point to the node before the insertion point
  // (or NULL if insertion is at the beginnig of the list)
  for (biggernode = list; biggernode != NULL; biggernode = biggernode->next) {
    if (biggernode->degree <= degree)
      break;
    smallernode = biggernode;
  }

  // If the degree of bigger node is the same as degree, we simply
  // add two coeeficients without creating a new node
  if (biggernode!=NULL && biggernode->degree == degree) {
    biggernode->coeff+=coeff;

    // It's possible that this addition produced a zero coefficient,
    // in which case the node must be removed
    if (biggernode->coeff==0.0) {
      if (smallernode == NULL)
        list = biggernode->next;
      else 
	smallernode->next = biggernode->next;

      delete biggernode;
    }

  }

  // Create a new node and insert it before biggernode
  else {

    newnode = new Monomial(degree, coeff, biggernode);

    if (newnode == NULL)
      return false;

    if (smallernode == NULL)  // special case: insertion at the beginning
      list = newnode;
    else                      // general case
      smallernode->next = newnode;
  }
  return true;
}


/*------------------------------------------------------------*/

       /* Polynomial::Print
	* Pretty prints the current polynomial
        */
void Polynomial::Print () const
{
  Monomial * n;
  
  // The zero polynomial is handled separately
  if (IsZero()) {
    cout<<"0";
  }

  else {
    for (n=list; n!=NULL; n=n->next) {

      if (n!=list) {
        // If this is not the first monomial, we need to put the
        // + or - that goes between monomials
        // For the first one, however, the + or - must be handled
        // differently, because no + is output if its positive,
        // and the - goes without spaces if it's negative
	if (n->coeff>0)
	  cout << " + ";
	else
	  cout << " - ";
      }


      // Now we need to output the coefficient
      // This happens only if it's not equal to 1 or -1, in which case
      // the + or the - minus we output above already takes care of it
      // However, there are two special cases: the -1 at the beginning
      // of the polynomial must still be output as -, and the last
      // coefficient is always output, even if it's 1
      if((n->coeff != 1.0 && (n->coeff != -1.0 || n==list)) || n->degree == 0) {
	
	// If this is not the first coefficent, then + or - is already
        // taken care of above, so simply output the absolute value
	if (n!=list)
	  cout << ((n->coeff>0) ? n->coeff : -n->coeff);

	// If it is the first coefficient, then we output it the way it is
	// unless it is -1, in which case we just output - without spaces.
	else {
          if (n->coeff==-1.0)
	    cout << '-';
	  else
	    cout << n->coeff;
	}
      }

      // Now output x unless the degree is 0
      if (n->degree>0)
	cout<<"x";

      // Now output the degree unless it is 0 or 1
      if (n->degree>1)
	cout<<"^"<<n->degree;
    }
  }
}

/*------------------------------------------------------------*/

       /* Polynomial::Print
	* Inputs the current polynomial
	* The format is a sequence of pairs coeff degree
	* followed by 0 0 to show end.  
	* For example 4 3 2 1 0 0 
	* means 4x^3 + 2x.
	* Returns false if fails to allocate memory, true otherwise.
        */

bool Polynomial::Input()
{
  float coeff;
  int degree;
  bool res=true, stop=false;

  Init();

  do {
    cin >> coeff;
    cin >> degree;
    if (coeff==0.0 && degree==0) 
      stop = true;
    else
      res=AddMonomial(degree, coeff);
  } while (!stop && res);

  return res;
}

/*------------------------------------------------------------*/

       /* operator>>
	* inputs a current polynomial using Polynomial::Input
	* in case Input returns false, complains to cout
        */

istream &operator>>(istream & input, Polynomial & poly)
{
  if (!poly.Input()) cout << "Failed to input!\n";
  return input;
}



/*------------------------------------------------------------*/

       /* swap
	* swaps the values of two polynomials
	* without using a third polynomial (which could cause
	* memory havoc, because the third polynomial would
	* have to be destroyed, and destructor would deallocate memory
	* that is still being used by one of the two polynomials)
        */

int Polynomial::swapCount=0;

void swap(Polynomial & p1, Polynomial & p2) {
  Polynomial::swapCount++; 
  Monomial * temp=p1.list; 
  p1.list=p2.list; 
  p2.list=temp;
}



/* ----------- END OF FILE: polynomial.cpp ---------- */