#ifndef _bigint_H
#define _bigint_H

//include linked list stack
#include "stack.h"
#include <string>

class bigint{
 // class interface 
   
   private:
     stack<int> holder;  // holds characters in large integer        
     
     
      
    public:
      void normalize(); 
      bigint();
      bigint(string x);
      bigint & operator =(const bigint & x); // overload assignment op
      
       // default constructor
       
        
       friend bigint operator+(const bigint & x, const bigint & y); 
       friend bigint operator-(const bigint & x, const bigint & y); 
       friend bigint operator/(const bigint & x, const bigint & y); 
       friend bigint operator*(const bigint & x, const bigint & y);
        friend bigint operator%(const bigint & x, const bigint & y);
       /*
        Pre : All overloaded operators receive two bigint classes
        Post: Perfroms addition, subtraction, division, multiplication
              respectively       
       */
       
              
 friend bool operator<(const bigint & x, const bigint & y);
 friend bool operator>(const bigint & x, const bigint & y);
 friend bool operator<=(const bigint & x, const bigint & y);
 friend bool operator>=(const bigint & x, const bigint & y);
 friend bool operator==(const bigint & x, const bigint & y);
 friend bool operator!=(const bigint & x, const bigint & y);     
       /*
        Pre : All overloaded operators receive two bigint classes
        Post: Performs relational operator
       */
       
                    
       
       // friend output operators
       friend istream& operator>>(istream & input, bigint & x); 
       friend ostream& operator<<(ostream & output, const bigint& x); 
       // overloaded streams operators for input/output 

};



bigint :: bigint()
{
  // default constructor;
  //sets default to zero
  
    
  
}
bigint::bigint(string x)
{      
         int len = x.length();
	for(int i = 0; i < len;i++)
	{
		int num = int(x[i]) - int('0');
		holder.push(num);
	}
}
void bigint :: normalize()
{
  // reversed stack after reading in and +,-,/,*
 stack<int>temp1,temp2;

 while (!holder.isempty())
  temp1.push(holder.pop()); 
  
  while (!temp1.isempty())
  temp2.push(temp1.pop());
   
 while (!temp2.isempty())
  holder.push(temp2.pop());
 


}


bigint & bigint :: operator =(const bigint & x)
{
   
   // get rid of what is already in lvalue  
   int t2;
   while(!holder.isempty())
       t2= holder.pop();
   
   //make temp stack, x is const
   stack<int>temp = x.holder;
   
   //transfer  
   while(!temp.isempty())
    {
       holder.push(temp.pop());
    } 
   
   //reverse order  
   normalize();  

   // return object
   return *this;
}



bigint operator+(const bigint & x, const bigint & y) 
{
  // adds two bigints together 
  int carryover=0;   // if addition is more than 10, holds 1..else 0
  bigint addtemp;  // holds addition
  stack<int>xtemp = x.holder;
  stack<int>ytemp = y.holder; 
  
  stack<int>mover;
  
 
  
  //if y is greater than x;
  if(x.holder.getsize() < y.holder.getsize())
    {
      //empty out xtemp so you can put zeros for placement
      while(!xtemp.isempty())
        mover.push(xtemp.pop()); 
        
      for(int loop = 0; loop < y.holder.getsize() - x.holder.getsize(); loop++)
         xtemp.push(0);
           
      while(!mover.isempty())
        xtemp.push(mover.pop()); 
    } 
  
  //if x is greater than y;
  if(x.holder.getsize() > y.holder.getsize())
    {
      //empty out xtemp so you can put zeros for placement
      while(!ytemp.isempty())
        mover.push(ytemp.pop()); 
        
      for(int loop = 0; loop < x.holder.getsize() - y.holder.getsize(); loop++)
         ytemp.push(0);
           
      while(!mover.isempty())
        ytemp.push(mover.pop()); 
    }
  
  int xtp, ytp;
  
  // addition
  while(xtemp.getsize() > 0)
    {
      xtp = xtemp.pop(); ytp = ytemp.pop();
            
            
      addtemp.holder.push((carryover + xtp + ytp)%10);
      carryover = (carryover + xtp + ytp)/10;
    } 
  
  if(carryover == 1)
      addtemp.holder.push(1); 
    
  addtemp.normalize();
  
  return addtemp;
   
 }
  

///////////////////////////subtraction//////////////////////////////

    
bigint operator-(const bigint & x, const bigint & y) 
{ 
 // adds two bigints together 
  int carryover=0;   // if addition is more than 10, holds 1..else 0
  bigint subtemp;  // holds addition
  stack<int>xtemp = x.holder;
  stack<int>ytemp = y.holder; 
  stack<int>mover;
  int intx, inty;
  
  if(x < y)
    { cout << "CANNOT DO SUBTRACTION, lval < rval ";
      exit(1); }
  
  
  //make both stacks same size;
  if(x.holder.getsize() != y.holder.getsize())
    {
      //empty out xtemp so you can put zeros for placement
      while(!ytemp.isempty())
        mover.push(ytemp.pop()); 
        
      for(int loop = 0; loop < x.holder.getsize() - y.holder.getsize(); loop++)
         ytemp.push(0);
           
      while(!mover.isempty())
        ytemp.push(mover.pop()); 
    } 
  
  
  
  
  
 while(!xtemp.isempty())
    {
      intx = xtemp.pop();
      inty = ytemp.pop();   
          
        
      // if y greater than x
      if(intx >= inty) 
        subtemp.holder.push(intx - inty);
      else
       {
        // if y value is less than x value... must take one 
        //      from the next place over
        
        int tempholder = xtemp.pop();
        
        // takes from the next up
        tempholder--;
        xtemp.push(tempholder);
        
        // give 10 to one below
        intx+=10;
       
        // push new onto stack
        subtemp.holder.push(intx - inty);
        //cout << intx - inty << endl;
       }   
        
      
    }// end while 
   
   int leadzeros; 
  while(subtemp.holder.stacktop() == 0 && subtemp.holder.getsize() > 1)
  {        
      leadzeros = subtemp.holder.pop();
  }
  
  subtemp.normalize();
   
  
  
  return subtemp;
  } // end first if
  
 





bigint operator/(const bigint & x, const bigint & y)
{
  
  // CANNOT DIVIDE BY ZERO
  bigint zero;
  zero.holder.push(0);  
  
  if(y == zero)
  {
    cout << "ERROR, cannot divide by zero"; 
    exit(1);
  }
  
  //cannot do negative numbers
  
  // Variable declaration
  bigint tx, ty;
  bigint counter;
  bigint one;
  
  counter.holder.push(0);
  
  // incrementer
  one.holder.push(1);
  
  // assign y to ty, y is constant
  tx = x;
  
  // returns integer value of 
  while(tx>=y)
  {
    tx = tx - y;
    counter = counter + one;
  }
  
   
  
  
  // if x is > ty
  if(counter.holder.getsize() == 0) counter.holder.push(0);
  
  // return quotient
  return counter;

}



bigint operator%(const bigint & x, const bigint & y)
{
  
   
   return  x-((x/y)*y);

}
              
 
 bool operator<(const bigint & x, const bigint & y)
 {
   //variable declaration
  bigint tx, ty;
  bool flag = false;
 
  tx = x; ty = y;
 
  if(x.holder.getsize() < y.holder.getsize()) return true;
  if(x.holder.getsize() > y.holder.getsize()) return false;
  
  
  tx.normalize();
  ty.normalize();
   
 
  
  while(!tx.holder.isempty())
  { 
    int yy = ty.holder.pop(), xx = tx.holder.pop();
    //cout << xx << " " << yy <<endl;
    if(xx < yy)
       return true;
    if(xx > yy)
       return false; 
  }
  
  return false; 
 }
 
 
 
 
  
  
bool operator>(const bigint & x, const bigint & y)
{
   //variable declaration
  bigint tx = x, ty = y;
  bool flag = false;
 
  if(x.holder.getsize() > y.holder.getsize()) return true;
  if(x.holder.getsize() < y.holder.getsize()) return false;
  
   tx.normalize();
   ty.normalize();
  
  
   
  // if both are same length
  while(!tx.holder.isempty())
  { 
    int yy = ty.holder.pop(), xx = tx.holder.pop();
    
    if(xx < yy)
       return false;
    if(xx > yy)
       return true;     
 
 }
  return false;


}
     
bool operator<=(const bigint & x, const bigint & y)
{

 //variable declaration
  bigint tx, ty;
  bool flag = true;
 
  tx = x; ty = y;
  
  tx.normalize();
  ty.normalize();
  
  
  // if greater or less than in length, determine 
  if(x.holder.getsize() < y.holder.getsize()) return true;
  if(x.holder.getsize() > y.holder.getsize()) return false;
  
  // else, if equal size number, compair components
  while(!tx.holder.isempty())
  { 
    int yy = ty.holder.pop(), xx = tx.holder.pop();
    
    if(xx < yy)
       return true;
    
    if( xx > yy ) return false;
    
    if(xx!=yy) flag = false;
  
  }
  
  return flag;

}




bool operator>=(const bigint & x, const bigint & y)
{
//variable declaration
  bigint tx, ty;
  bool flag = true;
 
  tx = x; ty = y;
  
  tx.normalize();
  ty.normalize();
  
    
  // if greater or less than in length, determine 
  if(x.holder.getsize() > y.holder.getsize()) return true;
  if(x.holder.getsize() < y.holder.getsize()) return false;
  
  // else, if equal size number, compair components
  while(!tx.holder.isempty())
  { 
    int yy = ty.holder.pop(), xx = tx.holder.pop();
    
    if(xx > yy)
       return true;
    
    if(xx!=yy)
      flag = false;
  
    if(xx < yy) return false;
  }
  
  return flag;


}


bool operator==(const bigint & x, const bigint & y)
{

 //variable declaration
  bigint tx, ty;
  bool flag = false;
 
  tx = x; ty = y;
  
  // if greater or less than in length, determine 
  if(x.holder.getsize() != y.holder.getsize()) return false;
   
  // else, if equal size number, compair components
  while(!tx.holder.isempty())
  { 
    int yy = ty.holder.pop(), xx = tx.holder.pop();
    
    if(xx != yy)
       return false;
  }
  
  return true;

}     
     
     
     
     
 bool operator!=(const bigint & x, const bigint & y)    
 {
 
 
 //variable declaration
  bigint tx, ty;
  bool flag = false;
 
  tx = x; ty = y;
  
  // if greater or less than in length, determine 
  if(x.holder.getsize() != y.holder.getsize()) return true;
   
  // else, if equal size number, compair components
  while(!tx.holder.isempty())
  { 
    int yy = ty.holder.pop(), xx = tx.holder.pop();
    
    if(xx != yy)
       return true;
  }
  
  return false;
 
 
 
 
 }





                    
       
       // friend output operators
       
       
istream& operator >> (istream & input, bigint & x)
{
   char temp;
   
   input.get(temp);
    
  while(temp != '\n')
  {
    // turn character into int
    x.holder.push(int(temp) - 48);
    input.get(temp);  
  }

 // return for linkage purposes
 return input;     
}     
     
ostream& operator<<(ostream & output, const bigint& x)
{
  
 bigint temp = x;
 temp.normalize();
  
  while(!temp.holder.isempty())
     output << temp.holder.pop();
  
 return output;

}     
     
     
     
     
     

     
#endif