#ifndef _TITANIUM_POLY_H_
#define _TITANIUM_POLY_H_

#include <string>
#include <list>
#include <limits.h>
#include <AST.h>
#include <cassert>

#ifndef INT_MAX
#define INT_MAX 2147483647
#endif


class Poly;
class PolyTerm;
class PolyFactor;

/////////////////////////////////////////////////////////////////////////////
// Storage management
/////////////////////////////////////////////////////////////////////////////

static inline void freePolys();

static inline PolyTerm *markGarbage(PolyTerm *t);
static inline Poly **markGarbage(Poly **t);
static inline Poly *markGarbage(Poly *t);

static inline PolyTerm *newPolyTerm(list< PolyFactor > *f);
static inline PolyTerm *newPolyTerm(int c, list< PolyFactor > *f);
static inline PolyTerm *newPolyTerm(int i);
static inline PolyTerm *newPolyTerm(PolyFactor f);

static inline Poly * newPoly(const Poly *p);
static inline Poly * newPoly(list< const PolyTerm * > *t);
static inline Poly * newPoly(const PolyTerm *t);
static inline Poly * newPoly(PolyFactor f);
static inline Poly * newPoly(int i);

static inline Poly ** newPolyArray(int i);

typedef map_polyfactor_polyfactor_to_poly derivtable;

/* A variable. */
class PolyFactor {
public:
  int varNum;
  PolyFactor() { varNum = INT_MAX; }
  PolyFactor(int v) { varNum = v; unsetVarName(v); }
  PolyFactor(int v, const string &name) { varNum = v; setVarName(v, name); }
  PolyFactor(char c) {
    if (c >= 'a' && c <= 'z') varNum = c - 'a';
    else if (c >= 'A' && c <= 'Z') varNum = -1 - (c - 'A');
    else varNum = 'z' - 'a';
  }
  bool less(PolyFactor x) const { return varNum < x.varNum; }
  const PolyTerm * mult(const PolyTerm *t) const;
  const Poly * mult(const Poly *p) const;
  const Poly * deriv(PolyFactor v, derivtable d) const;
  void print(ostream &os) const;
  string asString() const;

private:
  static map_int_to_string *names;
  static void setVarName(int v, const string &name) {
    if (names == NULL) names = new map_int_to_string; 
    (*names)[v] = name;
  }
  static void unsetVarName(int v) { if (names != NULL) setVarName(v, ""); }

public:
  static void resetNames() {
    delete names;
    names = NULL;
  }
};

/* A product of an integer coefficient and 0 or more PolyFactors. */
/* Canonical order is that PolyFactors are ordered low to high. */
class PolyTerm : public gc {
public:
  int coefficient;
  list< PolyFactor > *factors;
  PolyTerm(list< PolyFactor > *f) { coefficient = 1; factors = f; }
  PolyTerm(int c, list< PolyFactor > *f) {
    coefficient = c; factors = ((c == 0) ? (new list< PolyFactor > ()) : f);
  }
  PolyTerm(int i) { coefficient = i; factors = new list< PolyFactor > (); }
  PolyTerm(PolyFactor f) {
    coefficient = 1; factors = new list< PolyFactor > (1, f);
  }
  
  PolyFactor asPolyFactor() const {
    assert(coefficient == 1 && factors->size() == 1);
    return factors->front();
  }

  int asInt() const {
    assert(constantp());
    return coefficient;
  }

  int absoluteValue() const {
    assert(constantp());
    return ((coefficient >= 0) ? coefficient : -coefficient);
  }

  bool constantp() const { return factors->empty(); }
  bool zerop() const { return coefficient == 0; }
  bool less(const PolyTerm *) const;
  const PolyTerm * negate() const { return newPolyTerm(-coefficient, factors); }
  const PolyTerm * mult(const PolyTerm *t) const;
  const PolyTerm * mult(int s) const {
    return (s == 1) ? this : mult(newPolyTerm(s));
  }
  const Poly * mult(const Poly *p) const;
  const Poly * deriv(PolyFactor v, derivtable d) const; 
  void print(ostream &os) const;
  string asString() const;
  string output(const string product(const string &a, const string &b),
		string PolyFactor_to_string(PolyFactor f)) const;
};

/* A sum of 1 or more PolyTerms.  (0 is represented as a list of one item.) */
/* Canonical order on terms: sort by leading factor (lowest first).
   Break ties by 2nd factor if 1st factor is equal, etc. */
class Poly : public gc {
public:
  list< const PolyTerm * > *terms;
  Poly() {
    terms = (newPoly(0))->terms;
  }
  Poly(const Poly *p) {
    terms = p->terms;
  }
  Poly(list< const PolyTerm * > *t) {
    terms = (t == NULL || t->empty()) ? (newPoly(0))->terms : t;
  }
  Poly(const PolyTerm *t) {
    terms = new list< const PolyTerm * > (1, t);
  }
  Poly(PolyFactor f) {
    terms = new list< const PolyTerm * > (1, newPolyTerm(f));
  }
  Poly(int i) {
    terms = new list< const PolyTerm * > (1, newPolyTerm(i));
  }

  int asInt() const {
    assert(constantp());
    return terms->front()->asInt();
  }

  int absoluteValue() const {
    assert(constantp());
    return terms->front()->absoluteValue();
  }

  PolyFactor asPolyFactor() const {
    assert(terms->size() == 1);
    return terms->front()->asPolyFactor();
  }

  bool constantp() const {
    return terms->size() == 1 && terms->front()->constantp();
  }
  bool zerop() const {
    return terms->size() == 1 && terms->front()->zerop();
  }
  bool equalp(const Poly *p) const {
    return sub(p)->zerop();
  }
  int constantTerm() const;
  const Poly * deriv(PolyFactor v, derivtable d) const;
  const Poly * mult(PolyFactor) const;
  const Poly * mult(const PolyTerm *) const;
  const Poly * mult(const Poly *) const;
  const Poly * mult(int s) const {
    return (s == 0) ? zero : ((s == 1) ? this : mult(newPolyTerm(s)));
  }
  const Poly * add(int a) const {
    return (a == 0) ? this : add(newPolyTerm(a));
  }
  const Poly * add(PolyFactor) const;
  const Poly * add(const PolyTerm *) const;
  const Poly * add(const Poly *) const;
  const Poly * sub(const Poly *p) const { return add(p->negate()); }
  const Poly * negate() const;

  void print(ostream &os) const;
  string asString() const;
  string 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;

  static Poly * zero;
  static Poly * one;
};

static inline string stringify(const Poly *p) {
  return (p == NULL) ? string("NULL") : p->asString();
}

static inline const Poly *safeAdd(const Poly *a, const Poly *b) {
  return (a == NULL || b == NULL) ? (const Poly *) NULL : a->add(b);
}

static inline const Poly *safeMult(const Poly *a, const Poly *b) {
  return (a == NULL || b == NULL) ? (const Poly *) NULL : a->mult(b);
}


/////////////////////////////////////////////////////////////////////////////
// Storage management
/////////////////////////////////////////////////////////////////////////////

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

static inline void freePolys() {
  int i = 0, j = 0, k = 0;
  while (garbagePolyTerms != NULL) {
    delete garbagePolyTerms->front();
    garbagePolyTerms = garbagePolyTerms->free();
    i++;
  }
  while (garbagePolys != NULL) {
    delete garbagePolys->front();
    garbagePolys = garbagePolys->free();
    j++;
  }
  while (garbagePolyArrays != NULL) {
    delete[] garbagePolyArrays->front();
    garbagePolyArrays = garbagePolyArrays->free();
    k++;
  }
  /* cout << "Freed " << i << " PolyTerms, " << j << " Polys, and " <<
       k << " Poly arrays." << endl; */
}

static inline PolyTerm *markGarbage(PolyTerm *t) {
  garbagePolyTerms = cons(t, garbagePolyTerms);
  return t;
}

static inline Poly **markGarbage(Poly **t) {
  garbagePolyArrays = cons(t, garbagePolyArrays);
  return t;
}

static inline Poly *markGarbage(Poly *t) {
  garbagePolys = cons(t, garbagePolys);
  return t;
}

static inline PolyTerm *newPolyTerm(list< PolyFactor > *f) {
  return markGarbage(new PolyTerm(f));
}
static inline PolyTerm *newPolyTerm(int c, list< PolyFactor > *f) {
  return markGarbage(new PolyTerm(c, f));
}
static inline PolyTerm *newPolyTerm(int i) {
  return markGarbage(new PolyTerm(i));
}
static inline PolyTerm *newPolyTerm(PolyFactor f) {
  return markGarbage(new PolyTerm(f));
}

static inline Poly * newPoly() {
  return markGarbage(new Poly());
}
static inline Poly * newPoly(const Poly *p) {
  return markGarbage(new Poly(p));
}
static inline Poly * newPoly(list< const PolyTerm * > *t) {
  return markGarbage(new Poly(t));
}
static inline Poly * newPoly(const PolyTerm *t) {
  return markGarbage(new Poly(t));
}
static inline Poly * newPoly(PolyFactor f) {
  return markGarbage(new Poly(f));
}
static inline Poly * newPoly(int i) {
  return markGarbage(new Poly(i));
}

static inline Poly ** newPolyArray(int i) {
  return markGarbage(new Poly * [i]);
}

/* Given that PolyStorage, below, is commented out, I made PolyTerm and Poly
   inherit from gc.  Polys and PolyTerms will be garbage collected. */
#if 0
/* For reasons I don't understand, my attempt to use BufferPools
   led to crashes inside calls to the standard template library (STL). */
/////////////////////////////////////////////////////////////////////////////
// Storage management for the above types.
/////////////////////////////////////////////////////////////////////////////

/* In our usage there will be at most one PolyStorage instance extant
at at time.  The new operator for Poly (and PolyTerm?) will allocate
storage from the BufferPools in that one PolyStorage instance.
Storage is released by making calls on the BufferPools or by simply
deleting the PolyStorage object. */

class PolyStorage {
public:
  BufferPool< sizeof(Poly) > PolyHeap;
  // BufferPool< sizeof(PolyTerm) > PolyTermHeap;
};

extern PolyStorage *PolyStore;

inline void resetPolyStorage()
{
  delete PolyStore;
  PolyStore = NULL;
}

inline void *Poly::operator new(size_t size)
{
  assert(size == sizeof(Poly));
  if (PolyStore == NULL)
    PolyStore = new PolyStorage();
  return PolyStore->PolyHeap.alloc();
}

inline void Poly::operator delete(void *buffer, size_t size)
{
  assert(size == sizeof(Poly));
  PolyStore->PolyHeap.release(buffer);
}

inline void *PolyTerm::operator new(size_t size)
{
  assert(size == sizeof(PolyTerm));
  if (PolyStore == NULL)
    PolyStore = new PolyStorage();
  return PolyStore->PolyTermHeap.alloc();
}

inline void PolyTerm::operator delete(void *buffer, size_t size)
{
  assert(size == sizeof(PolyTerm));
  PolyStore->PolyTermHeap.release(buffer);
}
#endif // 0

#endif /* _TITANIUM_POLY_H_ */