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

#include<iostream>
using namespace std;
#include "polynomial.h"      /* declarations of the class */




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

        /* 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;
}


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

       /* operator<<
	* outputs a current polynomial 
        */


ostream &operator<<(ostream & output, const Polynomial & poly)
{
  Monomial * n;
  
  // The zero polynomial is handled separately
  if (poly.IsZero()) {
    output<<"0";
  }

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

      if (n!=poly.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)
	  output << " + ";
	else
	  output << " - ";
      }


      // 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==poly.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!=poly.list)
	  output << ((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)
	    output << '-';
	  else
	    output << n->coeff;
	}
      }

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

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

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

       /* operator>>
	* 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.
	* If failes to allocate memory, complains to cout
        */

istream &operator>>(istream & input, Polynomial & poly)
{
  float coeff;
  int degree;
  bool res=true, stop=false;

  poly.Init();

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

  if (!res) cout << "Failed to input -- Out of Memory!\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;
}

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

       /* operator>
	* returns true if and only if this polynomial
        * is greater than the argument right
        * Greater than is defined as degree is greater, or,
        * if degrees are equal, highest coefficient is greater.
        * If both degree and coefficient are equal, greater than
        * is determined by the next terms, and so on.
        */
int Polynomial::compCount=0;

bool Polynomial::operator>(const Polynomial & right) const 
{
  compCount++;

  Monomial * p1=list, *p2=right.list;

  while (p1!=NULL && p2!=NULL) {
    // First compare the degrees
    if (p1->degree > p2->degree)
      return true;
    if (p1->degree < p2->degree)
      return false;

    // If the degrees are equal above, then compare the coefficients
    if (p1->coeff > p2->coeff)
      return true;
    if (p1->coeff < p2->coeff)
      return false;

    // If the coefficiets are also equal, go to the next node
    p1 = p1->next;
    p2 = p2->next;
  }

  // we reached the end of one or both lists

  // if p1 is NULL, then it's certainly not greater
  if (p1 == NULL)
    return false;

  // We are now sure that p2 is NULL and p1 is not, so it's greater
  return true;
}

    




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