#include <iostream>
//#include <strstream>
#include <string>
#include "osstream.h"
#include "Poly.h"

// PolyStorage *PolyStore = NULL;

extern const string int2string(int);

map_int_to_string * PolyFactor::names = NULL;

llist<PolyTerm *> *garbagePolyTerms;
llist<Poly *> *garbagePolys;
llist<Poly **> *garbagePolyArrays;

Poly * Poly::zero;
Poly * Poly::one;

// Construct the zero and one polynomials and make sure they're permanent. */
void initPolys() {
  garbagePolyTerms = NULL;
  garbagePolys = NULL;
  garbagePolyArrays = NULL;
  Poly::zero = new Poly(0);
  Poly::one = new Poly(1); 
  garbagePolyTerms = NULL;
  garbagePolys = NULL;
  garbagePolyArrays = NULL;
}

#define debug_poly false
// extern bool debug_poly;

/////////////////////////////////////////////////////////////////////////////
// Printing
/////////////////////////////////////////////////////////////////////////////

/* If a variable has an associated name, use that.  Otherwise print
   variables 0 to 25 as 'a' through 'z'.  Print variables above 25 as
   a lowercase letter followed by a numeral.  Print negative numbered
   variables similarly but use uppercase. */
void PolyFactor::print(ostream &os) const
{
  string s;
  if (names != NULL && (s = (*names)[varNum]) != "") {
    os << s;
    return;
  }

  int v = varNum;
  char ch;
  if (v < 0) {
    v = -v - 1;
    ch = 'A' + (v % 26);
  } else ch = 'a' + (v % 26);

  os << ch;
  if (v >= 26)
    os << (v / 26);
}

/* Print term in most stupid way possible:
   e.g., "4 a a b" to mean "4 times a times a times b." */
void PolyTerm::print(ostream &os) const
{
  if (constantp()) {
    os << coefficient;
    return;
  }

  bool needspace = (coefficient != 1);
  if (coefficient == -1) os << '-';
  else if (coefficient != 1) os << coefficient;

  for (list< PolyFactor > :: const_iterator l = factors->begin();
       l != factors->end();
       l++) {
    if (needspace) os << ' ';
    (*l).print(os);
    needspace = true;
  }
}

void Poly::print(ostream &os) const
{
  if (this == NULL || terms == NULL) {
    os << "NULL";
    return;
  }
  bool justStarting = true;
  for (list< const PolyTerm * > :: const_iterator l = terms->begin();
       l != terms->end();
       l++) {
    if (justStarting) justStarting = false;
    else {
      os << ' ';
      if ((*l)->coefficient >= 0) os << "+ ";
    }
    
    (*l)->print(os);
  }
  if (justStarting) os << '0';
}

string Poly::asString() const
{
  ostringstream s;
  print(s);
  return s.str();
}

string PolyTerm::asString() const
{
  ostringstream s;
  print(s);
  return s.str();
}

string PolyFactor::asString() const
{
  ostringstream s;
  print(s);
  return s.str();
}

// generic output routine

string Poly::output(const string sum(const string &a, const string &b),
		    const string product(const string &a, const string &b),
		    string PolyFactor_to_string(PolyFactor f)) const
{
  assert(this != NULL && terms != NULL);
  string result("0");
  for (list< const PolyTerm * > :: const_iterator l = terms->begin();
       l != terms->end();
       l++)
    result = sum(result, (*l)->output(product, PolyFactor_to_string));

  return result;
}

string PolyTerm::output(const string product(const string &a, const string &b),
			string PolyFactor_to_string(PolyFactor f)) const
{
  string result = int2string(coefficient);
  if (!constantp())
    for (list< PolyFactor > :: const_iterator l = factors->begin();
	 l != factors->end();
	 l++)
      result = product(result, PolyFactor_to_string(*l));

  return result;
}

/////////////////////////////////////////////////////////////////////////////
// Utilities, miscellaneous
/////////////////////////////////////////////////////////////////////////////

static list< const PolyTerm * > * popTerm(list< const PolyTerm * > *terms)
{
  terms->pop_front();
  return terms;
}

static list< const PolyTerm * > * copyTerms(list< const PolyTerm * > *terms)
{
  list < const PolyTerm * > * result = new list < const PolyTerm * > ();
  for (list< const PolyTerm * > :: const_iterator l = terms->begin();
       l != terms->end();
       l++) {
    result->push_back(*l);
  }
  return result;
}


static list< PolyFactor > * copyFactors(list< PolyFactor > *f)
{
  list < PolyFactor > * result = new list < PolyFactor > ();
  for (list< PolyFactor > :: const_iterator l = f->begin();
       l != f->end();
       l++) {
    result->push_back(*l);
  }
  return result;
}

/* Return the constant term of a polynomial. */
int Poly::constantTerm() const
{
  for (list< const PolyTerm * > :: const_iterator l = terms->begin();
       l != terms->end();
       l++)
    if ((*l)->constantp())
      return (*l)->coefficient;

  return 0;
}

/////////////////////////////////////////////////////////////////////////////
// Ordering of PolyTerms
/////////////////////////////////////////////////////////////////////////////

bool PolyTerm::less(const PolyTerm *x) const
{
  list< PolyFactor > :: const_iterator a = factors->begin(),
    b = x->factors->begin();
  
  while (true) {
    if (a == factors->end()) return (b != x->factors->end());
    if (b == x->factors->end()) return false;
    if ((*a).less(*b)) return true;
    if ((*b).less(*a)) return false;
    a++;
    b++;
  }
}

/////////////////////////////////////////////////////////////////////////////
// Negation
/////////////////////////////////////////////////////////////////////////////

const Poly * Poly::negate() const
{
  list< const PolyTerm * > * result = new list< const PolyTerm * >();
  for (list< const PolyTerm * > :: const_iterator l = terms->begin();
       l != terms->end();
       l++) {
    result->push_back((*l)->negate());
  }
  return newPoly(result);
}

/////////////////////////////////////////////////////////////////////////////
// Sums
/////////////////////////////////////////////////////////////////////////////

#define Cons(head, tail) ((result = (tail)), result->push_front(head), result)
static list< const PolyTerm * > * mergeTerms(list< const PolyTerm * > *a,
					     list< const PolyTerm * > *b) 
{
  list< const PolyTerm * > * result;
  if (a->empty())
    return b;
  if (b->empty())
    return a;

  if (a->front()->zerop())
    return mergeTerms(popTerm(a), b);
  if (b->front()->zerop())
    return mergeTerms(popTerm(b), a);

  const PolyTerm *a_front = a->front();
  const PolyTerm *b_front = b->front();
  if (a_front->less(b_front))
    return Cons(a_front, mergeTerms(popTerm(a), b));
  if (b_front->less(a_front))
    return Cons(b_front, mergeTerms(a, popTerm(b)));

  // If we get here, leading terms of a and b have the same factors
  int new_coefficient = a_front->coefficient + b_front->coefficient;
  if (new_coefficient == 0)
    return mergeTerms(popTerm(a), popTerm(b));
  else
    return Cons(newPolyTerm(new_coefficient, a_front->factors),
		mergeTerms(popTerm(a), popTerm(b)));
}
#undef Cons

const Poly * Poly::add(const Poly *p) const
{
  return newPoly(mergeTerms(copyTerms(terms), copyTerms(p->terms)));
}

const Poly * Poly::add(const PolyTerm *t) const
{
  return add(newPoly(t));
}

const Poly * Poly::add(PolyFactor f) const
{
  return add(newPoly(f));
}

/////////////////////////////////////////////////////////////////////////////
// Products
/////////////////////////////////////////////////////////////////////////////

list< PolyFactor > * PolyFactor_mult(PolyFactor t, list< PolyFactor > *factors)
{
  if (debug_poly) {
    cout << "Multiplied factor ";
    t.print(cout);
    cout << " by list of factors ";
    (newPolyTerm(factors))->print(cout);
    cout << " to get: ";
  }

  list< PolyFactor > * result = copyFactors(factors);
  list< PolyFactor > :: iterator l = result->begin();
  while (l != result->end() && (*l).less(t)) l++;
  result->insert(l, t);

  if (debug_poly) {
    (newPolyTerm(result))->print(cout);
    cout << '\n';
  }

  return result;
}

const PolyTerm * PolyTerm::mult(const PolyTerm *t) const
{
  list < PolyFactor > * resultFactors = copyFactors(t->factors);
  for (list< PolyFactor > :: const_iterator l = factors->begin();
       l != factors->end();
       l++) {
    resultFactors = PolyFactor_mult((*l), resultFactors);
  }

  const PolyTerm *result = newPolyTerm(coefficient * t->coefficient,
				       resultFactors);

  if (debug_poly) {
    cout << "Multiplied term ";
    print(cout);
    cout << " by term ";
    t->print(cout);
    cout << " to get: ";
    result->print(cout);
    cout << '\n';
  }

  return result;
}

const Poly * Poly::mult(const Poly *p) const
{
  const Poly *result = newPoly();
  for (list< const PolyTerm *> :: const_iterator l = terms->begin();
       l != terms->end();
       l++)
    for (list< const PolyTerm *> :: const_iterator k = p->terms->begin();
	 k != p->terms->end();
	 k++)
      result = result->add((*l)->mult(*k));
  
  if (debug_poly) {
    cout << "Multiplied poly ";
    print(cout);
    cout << " by poly ";
    p->print(cout);
    cout << " to get: ";
    result->print(cout);
    cout << '\n';
  }

  return result;
}

const Poly * Poly::mult(const PolyTerm *t) const
{
  return mult(newPoly(t));
}

const Poly * Poly::mult(PolyFactor f) const
{
  return mult(newPoly(f));
}

const PolyTerm * PolyFactor::mult(const PolyTerm *t) const
{
  return t->mult(newPolyTerm(*this));
}

const Poly * PolyFactor::mult(const Poly *p) const
{
  return p->mult(*this);
}

const Poly * PolyTerm::mult(const Poly *p) const
{
  return p->mult(this);
}

/////////////////////////////////////////////////////////////////////////////
// Differentiation
/////////////////////////////////////////////////////////////////////////////

const Poly * Poly::deriv(PolyFactor v, derivtable d) const
{
  const Poly *result = Poly::zero;
  for (list< const PolyTerm *> :: const_iterator k = terms->begin();
       k != terms->end();
       k++) {
    const Poly *x = (*k)->deriv(v, d);
    if (x == NULL) return NULL;
    result = result->add(x);
  }
  return result;
}

const Poly * PolyTerm::deriv(PolyFactor v, derivtable d) const
{
  if (factors == NULL || factors->size() == 0) return Poly::zero;

  const Poly * const c = newPoly(coefficient);

  /* Compute derivative of each factor */
  list< const Poly * > r;
  for (list< PolyFactor > :: const_iterator j = factors->begin();
       j != factors->end();
       j++) {
    const Poly *x = (*j).deriv(v, d);
    if (x == NULL) return NULL;
    else r.push_back(x);
    cout << "Derivative of factor ";
    (*j).print(cout);
    cout << " is ";
    x->print(cout);
    cout << '\n';
  }

  /* apply product rule */
  const Poly *result = Poly::zero;
  for (int l = 0, n = r.size(); l < n; l++) {
    const Poly *f = c;
    list< PolyFactor > :: const_iterator fk = factors->begin();
    list< const Poly * > :: const_iterator rk = r.begin();
    for (int k = 0; k < n; k++, fk++, rk++)
      if (l == k) f = f->mult(*rk);
      else f = f->mult(*fk);

    result = result->add(f);
    cout << "Added ";
    f->print(cout);
    cout << " to result\n";
  }
  result->print(cout);
  cout << " is result\n";
  return result;
}

const Poly * PolyFactor::deriv(PolyFactor v, derivtable d) const
{
  return d[varNum][v.varNum];
}