#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

class CPoly;

class CTerm // class term
{
  private:
          int m_exp;
          int m_coeff;
          CTerm * m_llink;
          CTerm * m_rlink;
  public:
          CTerm(int, int);
          ~CTerm();
          CTerm operator+(const CTerm &) const;
          CTerm operator-(const CTerm &) const;
          CTerm operator*(const CTerm &) const;
          CTerm & operator=(const CTerm &);

          const int getExp() const;


  /* friend function */
  friend class CPoly;
  friend ostream & operator<<(ostream &ostr, const CTerm & rhs);
  friend ostream & operator<<(ostream &ostr, const CPoly & rhs);

};// end of class term

class CPoly // class polynomial
{
  private:
          CTerm *m_dummy;
          int m_size;

  public:
          CPoly();
          ~CPoly();
          CPoly operator+(const CPoly &) const;
          CPoly operator-(const CPoly &) const;
          CPoly operator*(const CPoly &) const;
          CPoly & operator=(const CPoly &) const;
          void add(const CTerm &);
          CTerm & at(int);
          const int length() const;
          const int degree() const;


  /* friend function */

  friend ostream & operator<<(ostream &ostr, const CPoly & rhs);

};// end of class polynomial

//-------------------------------------------------------------------------------------------------------------------------

CTerm::CTerm(int c = 0, int e = 0) : m_exp(e), m_coeff(c), m_llink(NULL), m_rlink(NULL)
// do nothing
{}

CTerm::~CTerm()
// do nothing
{}

inline CTerm CTerm::operator+(const CTerm &rhs) const
// this function does not check whether addable or not
// it is programmer's responsibility
{
  if(getExp() != rhs.getExp())
  {
    cerr << "undefined addition...  program abort..." << endl;
    abort();
  }

  return  CTerm(m_coeff + rhs.m_coeff, m_exp);
}// end of operator+

inline CTerm CTerm::operator-(const CTerm &rhs) const
// this function does not check whether addable or not
// it is programmer's responsibility
{
  if(getExp() != rhs.getExp())
  {
    cerr << "undefined addition\nprogram abort..." << endl;
    abort();
  }

  return  CTerm(m_coeff - rhs.m_coeff, m_exp);
}// end of operator-

inline CTerm CTerm::operator*(const CTerm &rhs) const
{
   return  CTerm(m_coeff * rhs.m_coeff, m_exp + rhs.m_exp);
}// end of operator*

inline CTerm & CTerm::operator=(const CTerm &rhs)
{
  m_coeff = rhs.m_coeff;
  m_exp = rhs.m_exp;
  return *this;
}// end of operator=

inline const int CTerm:: getExp() const
{
  return m_exp;
}

ostream & operator<<(ostream &ostr, const CTerm & rhs)
{
  ostr << rhs.m_coeff << 'x' << rhs.m_exp;
  return ostr;
}// end of operator<<

//------------------------------------------------------------------------------------------------------------------------------

CPoly::CPoly() : m_size(0)
// create dummy node
{
  m_dummy = new CTerm;
  m_dummy->m_llink = m_dummy->m_rlink = m_dummy; // circular list
}

CPoly:: ~CPoly()
{
  CTerm *delTerm = m_dummy;
  while(m_size)
  {
    CTerm *tmp = delTerm;
    delTerm = delTerm->m_rlink;
    delete tmp;
    m_size--;
  }

  delete delTerm;

/*
  if(m_size)
  {
    cerr << "delete failed... aborting..." << endl;
    abort();
  }
*/
}

CTerm & CPoly:: at(int index)
{
  if(index >= m_size)
  {
    cerr << "array index overflow... aborting...";
    abort();
  }

  CTerm *ptr = m_dummy;

  if(index < m_size/2)
  {
    int count = index + 1; // dummy
    while(count)
    {
      ptr = ptr->m_rlink;
      count--;
    }
    return *ptr;
  }
  else
  {
    int count = m_size - index ;
    while(count)
    {
      ptr = ptr->m_llink;
      count--;
    }
    return *ptr;
  }
}


void CPoly:: add(const CTerm &newTerm)
{
  CTerm *curTerm = m_dummy;

  while(curTerm->m_exp < newTerm.m_exp)
  {
    curTerm = curTerm->m_rlink;

    if(curTerm == m_dummy)
      break;

  }

  if(curTerm->m_exp == newTerm.m_exp)
    curTerm->m_coeff += newTerm.m_coeff;

  else
  {
    CTerm *tmp = new CTerm(newTerm.m_coeff,newTerm.m_exp);
    tmp->m_llink = curTerm;
    tmp->m_rlink = curTerm->m_rlink;
    curTerm->m_rlink->m_llink = tmp;
    curTerm->m_rlink = tmp;
    m_size++;
  }
}

/* for degug */

void dbp(const CPoly &c)
{
  cout << c << endl;
}

//
//

ostream & operator<<(ostream &ostr, const CPoly & rhs)
{
  CTerm *ptr = rhs.m_dummy->m_rlink;
  while(ptr != rhs.m_dummy)
  {
    ostr << *ptr << ' ';
    ptr = ptr->m_rlink;
  }
  return ostr;
}

inline const int CPoly:: length() const
{
  return m_size;
}

inline const int CPoly:: degree() const
{
  return m_dummy->m_rlink->m_exp;
}

CPoly CPoly:: operator+(const CPoly &rhs) const
{
  CPoly res, result , aaa, bbb , ccc;
cout << "WOW" << result.length() << endl;

  CTerm *lhsPtr = m_dummy->m_rlink,
        *rhsPtr = rhs.m_dummy->m_rlink;

  int lLen = this->length(),
      rLen = rhs.length();

  while(lLen && rLen) // not empty
  {
    if(lhsPtr->m_exp == rhsPtr->m_exp)
    {
      if(lhsPtr->m_coeff + rhsPtr->m_coeff) // not zero
      {
        result.add(CTerm(lhsPtr->m_coeff + rhsPtr->m_coeff, lhsPtr->m_exp));
        lhsPtr = lhsPtr->m_rlink;
        rhsPtr = rhsPtr->m_rlink;
        rLen--;
        lLen--;
      }
    }

    else if(lhsPtr->m_exp < rhsPtr->m_exp)
    {
      result.add(*rhsPtr);
      rhsPtr = rhsPtr->m_rlink;
      rLen--;
    }
    else
    {
      result.add(*lhsPtr);
      lhsPtr = lhsPtr->m_rlink;
      lLen--;
    }
  }

  while(lhsPtr != this->m_dummy) // rest of lhs
  {
    result.add(*lhsPtr);
    lhsPtr = lhsPtr->m_rlink;
  }

  while(rhsPtr != rhs.m_dummy) // rest of lhs
  {
    result.add(*rhsPtr);
    rhsPtr = rhsPtr->m_rlink;
  }

  return result;
}




//--------------------------------------------------------------------------------------------------------------------------

int main()
{
  CPoly p1, p2;


  for(int c = 1, e = 1 ; e < 10 ; c++, e++)
  {
    if(e==5)
      p1.add(CTerm(100,8));
   p1.add(CTerm(c,e));
  }

  cout << p1 << endl;
/*
  for(int i = 0 ; i < 11 ; i++)
  {
    cout << p1.at(i) << ' ';
  }
*/
  p2.add(CTerm(1,1));
  p2.add(CTerm(2,4));

  cout << p2 << endl;

  cout << p1 + p2 << "degree: " << (p1 + p2).degree() << endl;

  cout << endl;

  return 0;
}