//Implementation of the poly1 class.  This class was implemented with the idea
//that dynamic arrays would be included in future versions.
//Please see poly0.h for full documentation
//
// Written by:  Dan Macumber macumber@colorado.edu
// TA: Tye Ratton, Monday 3:00
//
/////////////////////////////////////////////////////////////////////////////

#include <fstream>  //provides ostream for << operater
#include <cstdlib>  
#include <cassert>  //provides assert to check preconditions
#include <cmath>    //provides pow
#include <climits>  //provides UINT_MAX
#include <algorithm>//provides fill_n
#include "poly0.h"  //the polynomial class header
 
using namespace std; 
using namespace main_savitch_3;

//MEMBER FUNCTIONS OF THE POLYNOMIAL CLASS

//The Default Constructor.  This will create a polynomial with all coefficient
//equal to zero, if the constructor is called with other arguments the
//polynomial can initially have one term with degree and a coefficient.

polynomial::polynomial(double c, unsigned int exponent)
{
    assert(exponent<=MAX_EX);
    clear();
    current_degree=0;
    assign_coef(c, exponent);
}
    
// MODIFICATION MEMBER FUNCTIONS for the polynomial class

//This function will add a term to an existing term.  For example if the
//polynomial has an x^2 term then this function can add another term 2x^2,
//giving 3x^2.

void polynomial::add_to_coef(double amount, unsigned int exponent)
{
    assert(exponent<=MAX_EX);
    assign_coef(amount+coefficient(exponent), exponent);
}

//This function will replace whatever term was in the original polynomial with 
//a new term.

void polynomial::assign_coef(double coefficient, unsigned int exponent)
{
    assert(exponent<=MAX_EX);
    coef[exponent]=coefficient;

    //check to see if the degree has changed.  IMPORTANT this is the only
    //function which is allowed to directly change the degree, all other
    //function do so by calling this function
    
    if(exponent>current_degree && coefficient!=0)
	current_degree=exponent;
    else if(current_degree==exponent && coefficient==0 && current_degree!=0)
    {
	if(previous_term(current_degree)==UINT_MAX)
	    current_degree=0;
	else
	    current_degree=previous_term(current_degree);
    }
	
}

//This function will reset all the terms in the polynomial to zero.
void polynomial::clear( )
    
{
    fill_n(coef, CAPACITY, 0.0);
    current_degree=0;
}

// CONSTANT MEMBER FUNCTIONS for the polynomial class

//This function returns the coefficient of a term, if the exponent is
//greater than allowed, the function returns zero.
double polynomial::coefficient(unsigned int exponent) const
    
{
    if(exponent>MAX_EX)
	return 0.0;
    else
	return coef[exponent];
}

//This function returns the first derivative of the polynomial.

polynomial polynomial::derivative( ) const
{
    polynomial dx;
    unsigned int n=next_term(0);
	    
    while(n!=0)
    {
	dx.assign_coef((n)*coefficient(n), n-1);
	n=next_term(n);
    }
    
    return dx;
}

//This function returns the polynomials value at some x value.

double polynomial::eval(double x) const
{
    double sum=0;
    unsigned int n=0;

    do
    {
	sum+=coefficient(n)*pow((long double)x, (int)n);
	n=next_term(n);
    }while(n!=0);

    return sum;
}

//This function will return the power of the next greatest term to e.
//For instance in the polynomial x^2 + 3x^3, if e is 2 then the next power is
//3.

unsigned int polynomial::next_term(unsigned int e) const
{
    unsigned int n;
	    
    if(e<degree())
    {
	for(n=e+1; n<=degree(); n++)
	    if(coefficient(n)!=0.0)
		return n;
    }
    
    return 0; 
}


//This function will return the power of the previous term to e.
//For instance in the polynomial x^2 + 3x^3, if e is 3 then the previous
//power is 2.

unsigned int polynomial::previous_term(unsigned int e) const
{
    unsigned int n=e;

    if(e==0)
	return UINT_MAX;
    
    do
    {
	if(n>degree())
	    return degree();
	n--;
	if(coefficient(n)!=0.0)
	    return n;
    }while(n>0);
	    
    return UINT_MAX;
}


namespace main_savitch_3
{
    
// NON-MEMBER BINARY OPERATORS for the polynomial Class
    
    //This function defines what it means to subtract two polynomials.
    
    polynomial operator -(const polynomial& p1, const polynomial& p2)
	{
	    polynomial difference=p1;
	    unsigned int n=0;
	  
	    do
	    {
		difference.assign_coef(difference.coefficient(n)
				       -p2.coefficient(n),n);
		n=p2.next_term(n);
	    }while(n!=0);
		
	    return difference;
	}

    //This function defines what it means to add two polynomials.
    
    polynomial operator +(const polynomial& p1, const polynomial& p2)
	{
	    polynomial sum=p1;
	    unsigned int n=0;

	    do
	    {
		sum.assign_coef(sum.coefficient(n)+p2.coefficient(n),n);
		n=p2.next_term(n);
	    }while(n!=0);

	    return sum;
	}

    //This function defines what it means to multiply two polynomials.
    
    polynomial operator *(const polynomial& p1, const polynomial& p2)
	{
	    assert(p1.degree()+p2.degree()<=polynomial::MAX_EX);

	    polynomial multiple;

	    unsigned int n=0;
	    unsigned int m=0;

	    do
	    {
		do
		{
		    multiple.assign_coef(p1.coefficient(n)*p2.coefficient(m)+
					 multiple.coefficient(n+m), n+m);
		    m=p2.next_term(m);
		    
		}while(m!=0);
		
		n=p1.next_term(n);
		
	    }while(n!=0);

	    return multiple;
	}

    // NON-MEMBER OUTPUT FUNCTIONS for the polynomial Class

    //This function defines what it means to output a polynomial to a stream.
    //Most importantly it formats the output so it is easily understandable
    //by a user.
    
    ostream& operator << (ostream& out, const polynomial& p)
	{
	    unsigned int i = p.degree( );
	    double number;
	    
	    do
	    {
		// Get the coefficient:
		number = p.coefficient(i);

		if(i==p.degree() && number<0)
		    out << "-";
		else if(number<0)
		    out << " - ";
		else if(number>0 && i!=p.degree())
		    out << " + ";

		number = fabs(number);

		if(number!=1.0 || i==0)
		    out << number;

		if(i>1)
		    out << "x^" << i;
		if(i==1)
		    out << "x";

		i = p.previous_term(i);

	    }   while (i != UINT_MAX);

	    return out;     //return the output stream
	}

    // NON MEMBER FUNCTIONS

    //GIF functionality by Micheal Main main@colorado.edu
    
    void write_gif_header128(
	ostream& out,
	int width,
	int height,
	const char color_table[128][3]
	)
	{
	    // GIF signature and screen descriptor:
	    out.write("GIF87a", 6);         // GIF signature
	    out.put(width & 0xFF);          // Low byte of screen width
	    out.put((width >> 8) & 0xFF);   // High byte of screen width
	    out.put(height & 0xFF);         // Low byte of screen width
	    out.put((height >> 8) & 0xFF);  // High byte of screen width
	    out.put(0xE6);                  // 7-bits per pixel
	    out.put(0);                     // Background color
	    out.put(0);                     // Zero marks end of screen descriptor
	    
	    // Color table:
	    out.write(color_table[0], 128*3);
	    
	    // Image descriptior:
	    out.put(',');                   // Image separator character
	    out.write("\0\0\0\0", 4);       // Image starts at 0,0
	    out.put(width & 0xFF);          // Low byte of image width
	    out.put((width >> 8) & 0xFF);   // High byte of image width
	    out.put(height & 0xFF);         // Low byte of image width
	    out.put((height >> 8) & 0xFF);  // High byte of image width
	    out.put('\0');                  // Non-interleaved image
	    
	    // Code size (with 128 colors, pixels are 7 bits each).
	    out.put('\7'); // Code size (7-bit data for each pixel).
	}
    
    void make_gif(
	const polynomial& p,
	const char filename[ ],
	double low_x,
	double high_x,
	double low_y,
	double high_y
	)
	{
	    enum color { BLACK = 0, DARKGRAY, LIGHTGRAY, RED, GREEN };
	    const char COLOR_TABLE[128][3] = {
		{'\000', '\000', '\000' },  // BLACK
		{'\100', '\100', '\100' },  // DARKGRAY
		{'\300', '\300', '\300' },  // LIGHTGRAY
		{'\250', '\000', '\000' },  // RED
		{'\000', '\250', '\000' }   // GREEN
	    };
	    
	    const int SIZE  = 300; // Gif map width and height
	    
	    double delta_x = (high_x - low_x) / (SIZE - 1);
	    double delta_y   = (high_y - low_y) / (SIZE - 1);
	    bool vertical_axis, horizontal_axis;
	    int row, column;
	    double current_x, current_y;
	    double nearness;
	    double value[SIZE];
	    char color;
	    
	    // Check that the file opened okay and write the front information to the file.
	  
	    ofstream gif(filename, ios::out|ios::binary);
	    assert(gif);
	    
	    write_gif_header128(gif, SIZE, SIZE, COLOR_TABLE);
	    
	    // Compute the value of the function at each column
	    for (column = 0; column < SIZE; column++)
		value[column] = p.eval(low_x + column * delta_x);
	    
	    // Write the pixel data for the picture
	    for (row = SIZE-1; row >= 0; --row)
	    {
		current_y = low_y + row * delta_y;
		horizontal_axis = (delta_y >= current_y) && (current_y > -delta_y);
		for (column = 0; column < SIZE; ++column)
		{
		    if ((column % 5) == 0)
		    {
			gif.put('\6');
			gif.write("\200", 1); // Start code for 8-bit codes
		    }
		    current_x = low_x + column * delta_x;
		    vertical_axis = (delta_x >= current_x) && (current_x > -delta_x);
		    nearness = current_y - value[column];
		    if ((delta_y >= nearness) && (nearness >= -delta_y))
			color = BLACK;
		    else if (vertical_axis || horizontal_axis)
			color = DARKGRAY;
		    else if ((current_y < value[column]) && (current_y >= 0))
			color = GREEN;
		    else if ((current_y > value[column]) && (current_y < 0))
			color = RED;
		    else
			color = LIGHTGRAY;
		    
		    gif.put(color);
		}
	    }
	    
	    // Write the GIF ending and close the file
	    gif.put('\1');      // Block byte count
	    gif.put('\201');    // End code for 8-bit codes
	    gif.put('\0');      // Data Terminator
	    gif.put('\73');     // GIF File Terminator
	    gif.close( );
	    
	}

}