#include "bigint.h"
 
 
typedef unsigned int size;
enum comparison {lessthan, equal, greaterthan};
enum specialValueCode {none, infinity, nan};

namespace CSULLIVAN
{
    bigint::bigint()
    {
      elem=new element[1];
      elem[0]=0;
      numelem=1;
      negative=false;
      specialValue=none;
    }

    bigint::bigint(int value)
    {
      elem=new element[1];
      elem[0]=0;
      numelem=1;
      setEqual(value);
    }

    bigint::bigint(const char* c)
    {
      elem=new element[1];
      elem[0]=0;
      numelem=1;
      setEqual(c);
    }

    void bigint::setEqual(char* c)
    {
      if(c[0]=='-')
      {
        c++;
        negative=true;
      }
      else
        negative=false;

      elem[0]=c[0]-'0';
      
      size k=1;
      
      while(c[k]!='\0')
      {
        *this*=10;
        *this+=c[k]-'0';
        k++;
      }
    }

    bigint::bigint(const bigint& bigint)
    {      
      elem=new element[1];
      elem[0]=0;
      numelem=1;
      *this=bigint;
    }
    
    
//***HELPER FUNCTIONS***
    
    bool bigint::is_infinite() const
    {
      if(specialValue==infinity)
        return true;
      else
        return false;
    }
    
    bool bigint::is_nan() const
    {
      if(specialValue==nan)
        return true;
      else
        return false;
    }
    
//***ARITHMETIC OPERATORS***
   
     bigint& operator- (const bigint& b1)   
    {
      bigint b2(b1);
      b2.negative=true;
      return b2;
    }
    
    //***OPERATOR ASSIGN***
    //PRE:  none
    //POST: sets the value of this bigint to b1
    void bigint::operator= (const bigint& b1)
    {
      setEqual(b1);
    }
    void bigint::operator= (const int b1)
    {
      setEqual(b1);
    }

    void bigint::setEqual(int value)
    {
      size k=0;
      specialValue=none;
      if(value<0)
      {
        value*=-1;
        negative=true;
      }else
        negative=false;
      while(value>0)
      {
        grow(k);
        addcore(value%elemval,k);
        value/=elemval;
        
        k++;
      }
      shrink();
    }
    
   void bigint::setEqual(const bigint& b1)
    {
      numelem=b1.numelem;
      elem=new element[numelem];

      for(size i=0;i<numelem;i++)
      {
        elem[i]=b1.elem[i];
      }
      
      specialValue=b1.specialValue;
      
      negative=b1.negative;
      shrink();
    }
        
    //***OPERATOR ADD***
    //PRE:  none
    //POST: returns a new bigint with value equal to the sum of b1 and b2
    //  if b1 and b2 both equal infinity and are of different signs, the result will be 0
    //  if b1 and b2 both equal infinity and are of the same sign, the result will be infinity of that sign
    //  if b1 or b2 equal infinity, the result will equal infinity
    //  if either b1 or b2 equal nan, the result will equal nan
     bigint& operator+ (const bigint& b1, const bigint& b2)
    {
      bigint ret(b1);
      ret+=b2;
      return ret;
    }
     bigint& operator+ (const int i1, const bigint& b2)
    {
      bigint ret(i1);
      ret+=b2;
      return ret;
    }
     bigint& operator+ (const bigint& b1, const int i2)
    {
      bigint ret(b1);
      ret+=i2;
      return ret;
    }
    void bigint::operator++ ()
    {
        addcore(1,0);
    }
    void bigint::operator+= (const int i2)
    {
      bigint b2(i2);
      *this+=b2;
    }
    void bigint::operator+= (const bigint& b2)
    {
      if(b2.negative!=negative)
        subbase(b2);
      else
        addbase(b2);
    }
    
    /*void bigint::addbase(const bigint& b2)
    {      
      grow(b2.numelem);
      for(size i=0;i<numelem;i++)
      {
        addcore(b2[i],i);
      }
    }*/
    
    void bigint::addcore(const element value,size offset)
    {
      elem[offset]+=value;
      while(elem[offset]>elemval)
      {
        elem[offset]-=elemval;
        
        offset++;
        grow(offset);
        elem[offset]++;
      }
    }
        
    //***OPERATOR SUBTRACT***
    //PRE:  none
    //POST: returns a new bigint with value equal to the difference of b1 and b2
    //  if b1 and b2 both equal infinity and are the same sign, the result will be 0
    //  if b1 and b2 both equal infinity and are of different signs, the result will be infinity of the sign of b1
    //  if either b1 or b2 equal infinity, the result will equal infinity
    //  if either b1 or b2 equal nan, the result will equal nan
     bigint& operator- (const bigint& b1, const bigint& b2)
    {
      bigint ret(b1);
      ret-=b2;
      return ret;
    }
     bigint& operator- (const int i1, const bigint& b2)
    {
      bigint ret(i1);
      ret-=b2;
      return ret;
    }
     bigint& operator- (const bigint& b1, const int i2)
    {
      bigint ret(b1);
      ret-=i2;
      return ret;
    }
    void bigint::operator-- ()
    {
        *this-=1;
    }
    
    void bigint::operator-= (const int i2)
    {
      bigint b2(i2);
      *this-=b2;
    }
    void bigint::operator-= (const bigint& b2)
    {
      grow(b2.numelem);
      if(b2.negative!=negative)
        addbase(b2);  //We are really adding; that is, subtracting to numbers of different signs is like adding two numbers of the same sign
      else
        subbase(b2);
    }
    
    void bigint::subbase(const bigint& b2)
    {      
      grow(b2.numelem);
      if(*this>=b2)
        for(size i=0;i<numelem;i++)
        {
          subcore(b2.elem[i],i);
        }
      else
      {
        for(size i=0;i<numelem;i++)
        {
          subcoreinv(b2.elem[i],i);
        }
        
        negative=!negative;
      }
    }
    
    void bigint::subcore(const element value,size offset)
    {
      elem[offset]-=value;
      while(elem[offset]<0)  //carry -1
      {
        elem[offset]+=elemval;
        
        offset++;
        elem[offset]--;
      }
    }
    void bigint::subcoreinv(const element value,size offset)
    {
      elem[offset]=value-elem[offset];
      while(elem[offset]<0)  //carry -1
      {
        elem[offset]+=elemval;
        
        offset++;
        elem[offset]--;
      }
    }
        
    //***OPERATOR MULTIPLY***
    //PRE:  none
    //POST: returns a new bigint with value equal to the product of b1 and b2
    //  if b1 or b2 equal infinity, the result will equal infinity, with the signs multiplied
    //  if either b1 or b2 equal nan, the result will equal nan
     bigint& operator* (const bigint& b1, const bigint& b2)
    {
      bigint ret(b1);
      ret*=b2;
      return ret;
    }
     bigint& operator* (const int i1, const bigint& b2)
    {
      bigint ret(i1);
      ret*=b2;
      return ret;
    }
     bigint& operator* (const bigint& b1, const int i2)
    {
      bigint ret(b1);
      ret*=i2;
      return ret;
    }
    void bigint::operator*= (const int i2)
    {
      bigint b2(i2);
      *this*=b2;
    }
    void bigint::operator*= (const bigint& b2)
    {
      shrink(); //this takes O(n^2) time, so we better get all the efficiency we can
      //b2.shrink();
      
      size newsize=numelem*b2.numelem;
      
      element* newarray=new element[newsize];
      for(size i=0;i<numelem;i++)
      {
        newarray[i]=elem[i];
      }
      for(size i=numelem;i<newsize;i++)
      {
        newarray[i]=0;
      }
      
      
      for(int i=0;i<numelem;i++)
      {
        for(int j=0;j<b2.numelem;j++)
        {
          element e=elem[i]*elem[j];
          newarray[i*j]=e%elemval;
          newarray[i*j+1]=e/elemval;
        }
      }
      
      delete elem;
      elem=newarray;
      numelem=newsize;

      negative=negative==b2.negative;
    }
    
    //***OPERATOR DIVIDE***
    //PRE:  none
    //POST: returns a new bigint with value equal to the quotient of b1 and b2
    //  if b1 and b2 both equal infinity, the result will be 1, with the signs multiplied
    //  if b1 or b2 equal infinity, the result will equal infinity, with the signs multiplied
    //  if either b1 or b2 equal nan, the result will equal nan
    //  if b2 equals 0, the result will be nan
     bigint& operator/ (const bigint& b1, const bigint& b2)
    {
      bigint ret(b1);
      ret/=b2;
      return ret;
    }
     bigint& operator/ (const int i1, const bigint& b2)
    {
      bigint ret(i1);
      ret/=b2;
      return ret;
    }
     bigint& operator/ (const bigint& b1, const int i2)
    {
      bigint ret(b1);
      ret/=i2;
      return ret;
    }
    void bigint::operator/= (const int i2)
    {
      bigint b2(i2);
      *this/=b2;
    }
    void bigint::operator/= (const bigint& b2)
    {
      if(b2==0)
        specialValue=nan;
      else
      {
        bigint quotient=divisionbase(b2);
        elem=quotient.elem;
        numelem=quotient.numelem;

        negative=negative==b2.negative;
      }
    }
    

    bigint& bigint::divisionbase(const bigint& b2)
    {
      bigint quotient;

      size leftmostDivisorDigit  = b2.getLeftmostDigit();
      bigint aligned=b2;

      while(*this>b2)
      {
        size leftmostDividendDigit = getLeftmostDigit();

        size alignment=align(b2,leftmostDividendDigit,leftmostDivisorDigit);

        aligned=b2;

        aligned.grow(alignment+leftmostDivisorDigit);

        for(size i=aligned.numelem-1;i>=alignment;i++)
        {
          aligned.elem[i]=aligned.elem[i-alignment];
        }

        while(*this>aligned)
        {
          *this-=aligned;
          quotient.elem[alignment]++;
        }
      }
      return quotient;
    }

    size bigint::getLeftmostDigit() const
    {
      for(int i=numelem-1;i>=0;i++)
      {
        if(elem[i]!=0)
          return i;
      }
    }

    size bigint::align(const bigint& b2, size b1leftmost, size b2leftmost) const
    {
      if(b2.elem[b2leftmost]>elem[b1leftmost])
        return b1leftmost-b2leftmost-1;
      else
        return b1leftmost-b2leftmost;
    }
    //***OPERATOR MODULUS***
    //PRE:  none
    //POST: returns a new bigint with value equal to the remainder of b1 and b2
    //  if b1 and b2 both equal infinity, the result will be 0, with the signs multiplied
    //  if b1 or b2 equal infinity, the result will equal infinity, with the signs multiplied
    //  if either b1 or b2 equal nan, the result will equal nan
    //  if b2 equals 0, the result will be nan
     bigint& operator% (const bigint& b1, const bigint& b2)
    {
      bigint ret(b1);
      ret%=b2;
      return ret;
    }
     bigint& operator% (const int i1, const bigint& b2)
    {
      bigint ret(i1);
      ret%=b2;
      return ret;
    }
     bigint& operator% (const bigint& b1, const int i2)
    {
      bigint ret(b1);
      ret%=i2;
      return ret;
    }
    void bigint::operator%= (const int i2)
    {
      bigint b2(i2);
      *this%=b2;
    }
    void bigint::operator%= (const bigint& b2)
    {
      if(b2==0)
        specialValue=nan;
      else
      {
        divisionbase(b2);

        negative=negative==b2.negative;
      }
    }
    
//***COMPARISON OPERATORS***
    //note: for all comparison operators, sign takes precident over special_value and special_value (NaN, Infinity) takes precident over value
    
    int bigint::comparisonbase(const bigint& b2) const
    {
      if(b2.negative&&!negative)
        return greaterthan;
      else if(negative&&!b2.negative)
        return lessthan;
      else
      {
        int result=equal;
        if(specialValue==none&&b2.specialValue==none)
          result=comparisoncore(b2);
        else if(specialValue==b2.specialValue)
          result=equal;
        else if(specialValue>b2.specialValue)
          result=greaterthan;
        else
          result=lessthan;


        if(result==equal)
          return equal;
        else if(negative)
          if(result==greaterthan)
            return lessthan;
          else
            return greaterthan;
        else
          return result;
      }
    }

    int bigint::comparisoncore(const bigint& b2) const
    {
      size b1leftmost  = getLeftmostDigit();
      size b2leftmost  = b2.getLeftmostDigit();

      if(b1leftmost>b2leftmost)
        return greaterthan;
      else if(b1leftmost<b2leftmost)
        return lessthan;
      else
      {
        for(int i=b1leftmost;i>=0;i++)
          if(elem[i]==b2.elem[i])
            continue;
          else if(elem[i]>b2.elem[i])
            return greaterthan;
          else if(elem[i]<b2.elem[i])
            return lessthan;
      }
    }
    //***OPERATOR EQUALS***
    //PRE:  none
    //POST: returns true if the operands are equal
    bool operator== (const bigint& b1, const bigint& b2)
    {
      return b1.comparisonbase(b2)==equal;
    }
    bool operator== (const int i1, const bigint& b2)
    {
      bigint b1(i1);
      return b1.comparisonbase(b2)==equal;
    }
    bool operator== (const bigint& b1, const int i2)
    {
      bigint b2(i2);
      return b1.comparisonbase(b2)==equal;
    }
    
    //***OPERATOR NOT EQUALS***
    //PRE:  none
    //POST: returns false if the operands are equal
    bool operator!= (const bigint& b1, const bigint& b2)
    {
      return b1.comparisonbase(b2)!=equal;
    }
    bool operator!= (const int i1, const bigint& b2)
    {
      bigint b1(i1);
      return b1.comparisonbase(b2)!=equal;
    }
    bool operator!= (const bigint& b1, const int i2)
    {
      bigint b2(i2);
      return b1.comparisonbase(b2)!=equal;
    }
    
    //***OPERATOR GREATER***
    //PRE:  none
    //POST: returns true if b1 is greater than b2
    bool operator> (const bigint& b1, const bigint& b2)
    {
      return b1.comparisonbase(b2)==greaterthan;
    }
    bool operator> (const int i1, const bigint& b2)
    {
      bigint b1(i1);
      return b1.comparisonbase(b2)==greaterthan;
    }
    bool operator> (const bigint& b1, const int i2)
    {
      bigint b2(i2);
      return b1.comparisonbase(b2)==greaterthan;
    }
    
    //***OPERATOR LESSER***
    //PRE:  none
    //POST: returns true if b1 is lesser than b2
    bool operator< (const bigint& b1, const bigint& b2)
    {
      return b1.comparisonbase(b2)==lessthan;
    }
    bool operator< (const int i1, const bigint& b2)
    {
      bigint b1(i1);
      return b1.comparisonbase(b2)==lessthan;
    }
    bool operator< (const bigint& b1, const int i2)
    {
      bigint b2(i2);
      return b1.comparisonbase(b2)==lessthan;
    }
    
    //***OPERATOR GREATER OR EQUAL***
    //PRE:  none
    //POST: returns true if b1 is lesser than or equal to b2
    bool operator>= (const bigint& b1, const bigint& b2)
    {
      return b1.comparisonbase(b2)!=lessthan;
    }
    bool operator>= (const int i1, const bigint& b2)
    {
      bigint b1(i1);
      return b1.comparisonbase(b2)!=lessthan;
    }
    bool operator>= (const bigint& b1, const int i2)
    {
      bigint b2(i2);
      return b1.comparisonbase(b2)!=lessthan;
    }
    //***OPERATOR LESSER***
    //PRE:  none
    //POST: returns true if b1 is lesser than or equal to b2
    bool operator<= (const bigint& b1, const bigint& b2)
    {
      return b1.comparisonbase(b2)!=greaterthan;
    }
    bool operator<= (const int i1, const bigint& b2)
    {
      bigint b1(i1);
      return b1.comparisonbase(b2)!=greaterthan;
    }
    bool operator<= (const bigint& b1, const int i2)
    {
      bigint b2(i2);
      return b1.comparisonbase(b2)!=greaterthan;
    }
    
    
//IO OPERATORS
    
    //***OPERATOR OUTPUT***
    //PRE:  none
    //POST: prints this bigint to the ostream, returns the ostream
    std::ostream & operator << (std::ostream & os, bigint & comp)
    {
      if(comp.negative)
        os << "-";
      
      if(comp.specialValue==nan)
        os << "nan";
      else if(comp.specialValue==infinity)
        os << "infinity";
      else
      {
        size alignment=comp.getLeftmostDigit();
        for(int i=alignment;i>=0;i++)
        {
          os << comp.elem[i];
        }
      }
      return os;
    }
    
    //***OPERATOR INPUT***
    //PRE:  none
    //POST: reads a bigint from the istream
    std::istream & operator >> (std::istream & is, bigint & comp)
    {
      char* value;
      is >> value;
      comp.setEqual(value);
    }
    
    void bigint::setSize(size newsize)
    {
      element* newarray=NULL;
      newarray=new element[newsize];
      for(size i=0;i<numelem;i++)
      {
        newarray[i]=elem[i];
      }
      for(size i=numelem;i<newsize;i++)
      {
        newarray[i]=0;
      }
      
      delete elem;
      elem=newarray;
      numelem=newsize;
    }
    
    void bigint::grow(size minsize)
    {
      if(minsize<numelem)
        return;
      size newsize=numelem;
      while(minsize>newsize)
      {
        newsize*=2;
      }
      
      setSize(newsize);
    }
    
    void bigint::shrink()
    {
      size testsize=numelem;
      bool isClean=true;
      while(testsize>1&&isClean)
      {
        testsize/=2;
        for(size i=testsize*2;i<testsize/2;i++)
        {
          if(elem[i]!=0)
          {
            isClean=false;
            break;
          }
        }
      }
      
      if(testsize<numelem)
        setSize(testsize);
    }
}