using namespace std;
#include "bignum.h"
#include "poly.h"
#include "utilio.h"

/********************
  IO operations
********************/

ostream& putnum(ostream& f, const RAT& x, int d, bool showsign) {
    if (showsign)
	if (x > 0)
	    f << " + ";
	else 
	    f << " - ";
    else
	if (x < 0)
	    f << "-";
    if (x != 1 && x != -1 || d == 0)
	if (x > 0)
	    f << x;
	else
	    f << -x;
    if (d > 0) {
	f << "t";
	if (d > 1)
	    f << "^" << d;
    }
    return f;
}    

ostream& operator<<(ostream& f, const poly& z) {
    if (z.zero())
	return f << "0";
    int k;
    for(k=0; z.numer[k] == 0; k++);
    int startk = k;
    RAT out;
    for(; k<= z.deg(); k++) {
	if (z.numer[k] == 0)
	    continue;
	putnum(f,fraction(out,z.numer[k],z.denom),k,k>startk);
    }
    return f;
}

/*
reads a polynomial in the same format as produced by <<
scanning stops at eof, or newline (read) or any unexpected character 
(not read) c

does not increase maxdeg
*/
istream& operator>>(istream& f, poly& z) {
    int c;
    bool first_term = true;
    int sign;
    RAT r;
    int p;

    poly w(z.maxdeg());

    z = 0;
    while(true) {
	switch(c = skipspace(f)) {
	case EOF:
	    return f;
	case '\n':
	    return f;
	case '+':
	    sign = 1;
	    break;
	case '-':
	    sign = -1;
	    break;
	default:
	    sign = 1;
	    f.unget();
	    if(!first_term)
		return f;
	}
	if(first_term) {
	    first_term = false;
	}
//  	cerr << "c#1 = " << c << " (" << (char)c << ")\n";
	c = skipspace(f);
//  	cerr << "c#2 = " << c << " (" << (char)c << ")\n";
	assert(isdigit(c) || c == 't');
	if(isdigit(c)) {
	    INT a,b;
	    f.unget();
	    f >> a;
	    c = skipspace(f);
//  	    cerr << "c#3 = " << c << " (" << (char)c << ")\n";
	    if (c == '/') {
		f >> b;
		c = skipspace(f);
//  		cerr << "c#4 = " << c << " (" << (char)c << ")\n";
	    }
	    else {
		b = 1;
	    }
	    fraction(r,a,b);
	    r.canonicalize();
//  	    cerr << "r = " << r << "\n";
	}
	else 
	    r = 1;
	r *= sign;
	if (c == 't') {
	    c = f.get();
	    if (c == '^')
		f>>p;
	    else {
		f.unget();
		p = 1;
	    }
	}
	else {
	    f.unget();
	    p = 0;
	}
	assert(p>=0 && p<=w.maxdeg());
	w = 0;
	w.set_numer(p,r.get_num());
	w.denom *= r.get_den();
	z += w;
    }
}

/********************
  more complicated and/or rare member functions
********************/

void poly::set_maxdeg(int n) {
    assert(n >= -1);
    if (n==maxd)
	return;
    numer.resize(n+1);
    if (n<maxd) {
	if(n<deg())
	    setdeg(n);
    }
    else 
	for(int k = n; k>maxd; k--)
	    numer[k] = 0;
    maxd = n;
}
 
poly& poly::reduce() {
    INT GCD;
    GCD = denom;
    for (int k=0; k<=deg(); k++)
	gcd(GCD,GCD,numer[k]);
    if(GCD != 1) {
	for(int k=0; k<=deg(); k++)
	    numer[k] /= GCD;
	denom /= GCD;
    }
    return *this;
}

bool poly::fixdenom(const INT& D) {
    assert(D>0);
    INT GCD;
    gcd(GCD,denom,D);
    INT x;
    x = denom/GCD;
    if(x!=1) {
	vector<RAT> V(deg()+1);
	for(int k=0; k<=deg(); k++) {
	    fraction(V[k],numer[k],x);
	    if(V[k].get_den() != 1)
		return false;
	}
	for(int k=0; k<=deg(); k++)
	    numer[k] = V[k];
    }
    x = D/GCD;
    *this *= x;
    denom = D;
    return true;
}