#include <iostream>
#include <algorithm>
using namespace std;
#include "polynomial.h"

//  Implementation of the polynomial class member functions.

Polynomial::Polynomial()
{ }


Polynomial::Polynomial( double a0 )
{
  terms_.push_back( PTerm(a0, 0) );
}

Polynomial::Polynomial( const Polynomial & old )
{
  terms_ = old.terms_;
}


Polynomial::~Polynomial() 
{
}


const Polynomial &
Polynomial::operator = ( const Polynomial & right )
{
  if ( this != &right ) {
    terms_ = right.terms_;
  }
  return *this;
}



double
Polynomial::operator() ( double x ) const
{
  double value = 0.0;
  for ( int i=0; i<terms_.size(); ++i )
    value += terms_[i]( x );
  return value;
}


double 
Polynomial::get_coefficient( int exponent ) const
{
  for ( int i=0; i<terms_.size(); ++i )
    if ( terms_[i].exponent == exponent )
      return terms_[i].coefficient;
  return 0;
}


//  Find the maximum degree.  Start at the largest represented
//  exponent and go down until a term with non-zero exponent is found.
//  Usually, the while loop will have no iterations, but the code does
//  not attempt to reduce the highest degree represented when the
//  coefficient of the highest exponent is assigned 0.

int
Polynomial::max_degree() const
{
  int k = terms_.size()-1;
  while ( k>=0 && terms_[k].coefficient == 0.0 )
    -- k;
  if ( k<0 )
    return -1;
  else
    return terms_[ k ].exponent;
}


//  

void 
Polynomial::assign_coefficient(  double coefficient, int exponent )
{
  int last_sub = terms_.size()-1;
  int k=last_sub;
  while ( k>=0 && terms_[ k ].exponent > exponent ) 
    -- k;
  
  if ( k >= 0 && terms_[ k ].exponent == exponent ) {
    terms_[k].coefficient = coefficient;
  }
  else if ( k == last_sub ) {
    terms_.push_back( PTerm(coefficient, exponent) );
  }
  else {
    terms_.push_back( terms_[last_sub] );
    for ( int i = last_sub-1; i>k; i-- )
      terms_[i+1] = terms_[i];
    terms_[k+1] = PTerm( coefficient, exponent );
  }
}


//  The addition operator implements the design given in the class notes. 

Polynomial operator + ( const Polynomial& f, const Polynomial& g )
{
  Polynomial h;
  int i = 0, j = 0;

  while( i<f.terms_.size() && j<g.terms_.size() ) {
    if ( f.terms_[i].exponent == g.terms_[j].exponent ) {
      h.terms_.push_back( PTerm(f.terms_[i].coefficient + g.terms_[j].coefficient,
				f.terms_[i].exponent ));
      ++ i; 
      ++ j;
    }
    else if ( f.terms_[i].exponent < g.terms_[j].exponent ) {
      h.terms_.push_back( f.terms_[i] );
      ++ i; 
    }
    else {
      h.terms_.push_back( g.terms_[j] );
      ++ j; 
    }
  }
   
  //  Note at most one of these for loops will ever do anything
  //  because the preceding for loop will stop with i==f.terms_.size()
  //  or with j==g.terms_.size() or both.
  for( ; i<f.terms_.size(); ++i ) h.terms_.push_back( f.terms_[i] );
  for( ; j<g.terms_.size(); ++j ) h.terms_.push_back( g.terms_[j] );

  return h;
}


//  Subtraction uses multiplication and addition.  It would be
//  slightly faster to do this directly.

Polynomial operator- (const Polynomial& f, const Polynomial& g)
{
  return f + (-1)*g;
}


//  Multiplication operator for two polynomials...

Polynomial operator * ( const Polynomial & f, const Polynomial & g )
{
  Polynomial h;
  return h;
}

      
//  Multiply a scalar (constant) (on the left) times a polynomial.

Polynomial
operator* (double a, const Polynomial& f)
{
  Polynomial h( f );
  for ( int i=0; i<h.terms_.size(); ++i ) 
    h.terms_[i].coefficient *= a;
  return h;
}


//  Multiply a constant (on the right) times a polynomial.  Just
//  reverse the order of multiplication and use the already written
//  operator.

Polynomial operator* (const Polynomial& f, double a)
{
  return a*f;
}


//  Overloaded output operator.

ostream &
operator << ( ostream & out_str, const Polynomial & poly )
{
  bool first_out = true;
  for ( int i=0; i<poly.terms_.size(); ++i ) {
    double coeff = poly.terms_[i].coefficient;
    int expon = poly.terms_[i].exponent;
    if ( coeff != 0.0 ) {
      if( first_out ) 
	first_out = false;
      else
	out_str << " + ";
      out_str << coeff;
      if ( expon != 0 ) out_str << " x^" << expon;
    }
  }
  if ( first_out ) out_str << 0;
  return out_str;
}