// *******************************************************************
//  Last Revised: January 13, 1998
//
// *******************************************************************

#include <iostream.h>
#include <stdlib.h>
#include <ctype.h>
#include <limits.h>
#include "linkbig.h"
#include "apvector.h"

//#define DEBUG

const int BASE = 10;

// author: Owen Astrachan
//
// LBigInts are implemented using a Vector<char> to store
// the digits of a LBigInt
// Currently a number like 5,879 is stored as the vector {9,7,8,5}
// i.e., the least significant digit is the first digit in the vector;
// for example, GetDigit(0) returns 9 and getDigit(3) returns 5.
// All operations on digits should be done using private
// helper functions:
//
// int  GetDigit(k)        -- return k-th digit
// void ChangeDigit(k,val) -- set k-th digit to val
// void AddSigDigit(val)   -- add new most significant digit val
//
// by performing all ops in terms of these private functions we
// make implementation changes simpler
//
// I/O operations are facilitated by the ToString() member function
// which converts a LBigInt to its string (ASCII) representation

LBigInt::LBigInt()
// postcodition: bigint initialized to 0
   : mySign(positive),
     myNumDigits(1)
{
#ifdef DEBUG    
        cout << "default constructor called" << endl;
#endif

    least = most = new Node('0',NULL);	
}

LBigInt::LBigInt(const LBigInt & rhs)
    : mySign(rhs.mySign),
      myNumDigits(rhs.myNumDigits)
{
#ifdef DEBUG    
    cout << "copy constructor called with " << rhs << endl;
#endif

    // copy first digit, then do the rest in a loop
    
    least = most = new Node(rhs.least->info,NULL);
    Node * temp = rhs.least->next;  

    int k; 
    for(k=1; k < myNumDigits; k++)
    {
	most->next = new Node(temp->info,NULL);
	most = most->next;
	temp = temp->next;
    }
}

LBigInt::~LBigInt()
{
#ifdef DEBUG
    cout << "destructor called for " << *this << endl;
#endif

    Node * deadNode = NULL;   // points to node to delete
    Node * traverse = least;  // first node

    while (traverse != NULL)
    {
	deadNode = traverse;
	traverse = traverse->next;
	delete deadNode;
    }
    
    least = most = NULL;      // practice being safe
}

const LBigInt & LBigInt::operator = (const LBigInt & rhs)
{
#ifdef DEBUG
	cout << "assignment operator called with " << rhs << endl;
#endif

    if (this != &rhs)   // avoid copying self
    {
	// copy rhs, starting at least sig digit, using
	// available nodes before allocating any new ones
		
	mySign = rhs.mySign;
		
	Node * rtemp = rhs.least;
	
	most = least;
	most->info = rtemp->info;   // always at least one node
	myNumDigits = 1;
	
	rtemp = rtemp->next;
		
	// use while loop for bug, for loop for working program
		
	while (rtemp != NULL)
	    // for(int k=1; k < rhs.myNumDigits; k++)
	{
	    if (most->next == NULL)
	    {
		most->next = new Node(rtemp->info,NULL);
	    }
	    else
	    {
		most->next->info = rtemp->info;
	    }
	
	    most = most->next;
	    rtemp = rtemp->next;
	    myNumDigits++;
	}
    }
    return *this;
}



LBigInt::LBigInt(int num)
// postcondition: bigint initialized to num
   : mySign(positive),
     myNumDigits(0)
{
    // check if num is negative, change state and num accordingly

#ifdef DEBUG    
    cout << "int constructor called " << num << endl;
#endif   
    if (num < 0)
    {
        mySign = negative;
        num = -1 * num;
    }
    
    // handle least-significant digit of num (handles num == 0)

    least = most = new Node('0',NULL);
    myNumDigits = 1;
    ChangeDigit(0,num % BASE);
    num = num / BASE;

    // handle remaining digits of num

    while (num != 0)
    {
        AddSigDigit(num % BASE);
        num = num / BASE;
    }
}


LBigInt::LBigInt(const apstring & s)
// precondition: s consists of digits only, optionally preceded by + or -
// postcondition: bigint initialized to integer represented by s
//                if s is not a well-formed LBigInt (e.g., contains non-digit
//                characters) then an error message is printed and abort called
  : mySign(positive),
    myNumDigits(0)
{
    int k;
    int limit = 0;


#ifdef DEBUG    
    cout << "string constructor called s = " << s << endl;
#endif   

    least = most = new Node('0',NULL);   // start with zero for default
    
    if (s.length() == 0)
    {
        return;
    }
    if (s[0] == '-')
    {
        mySign = negative;
        limit = 1;
    }
    if (s[0] == '+')
    {
        limit = 1;
    }
    // start at least significant digit
    
    ChangeDigit(0,s[s.length()-1]);

    for(k=s.length() - 2; k >= limit; k--)
    {
        if (! isdigit(s[k]))
        {
            cerr << "badly formed LBigInt value = " << s << endl;
            abort();
        }
        AddSigDigit(s[k]-'0');
    }
    Normalize();
}


const LBigInt & LBigInt::operator -=(const LBigInt & rhs)
// postcondition: returns value of bigint - rhs after subtraction
{
    int diff;
    int borrow = 0;

    int k;
    int len = NumDigits();

    if (this == &rhs)         // subtracting self?
    {
        *this = 0;
        return *this;
    }

    // signs opposite? then lhs - (-rhs) = lhs + rhs

    if (IsNegative() != rhs.IsNegative())
    {
        *this +=(-1 * rhs);
        return *this;
    }
    // signs are the same, check which number is larger
    // and switch to get larger number "on top" if necessary
    // since sign can change when subtracting
    // examples: 7 - 3 no sign change,     3 - 7 sign changes
    //          -7 - (-3) no sign change, -3 -(-7) sign changes
    if (IsPositive() && (*this) < rhs ||
        IsNegative() && (*this) > rhs)
    {
        *this = rhs - *this;
      if (IsPositive()) mySign = negative;
      else              mySign = positive;   // toggle sign
        return *this;
    }
    // same sign and larger number on top

    for(k=0; k < len; k++)
    {
        diff = GetDigit(k) - rhs.GetDigit(k) - borrow;
        borrow = 0;
        if (diff < 0)
        {
            diff += 10;
            borrow = 1;
        }
        ChangeDigit(k,diff);
    }
    Normalize();
    return *this;
}

const LBigInt & LBigInt::operator +=(const LBigInt & rhs)
// postcondition: returns value of bigint + rhs after addition
{

    int sum;
    int carry = 0;

    int k;
    int len = NumDigits();         // length of larger addend

    if (this == &rhs)              // to add self, multiply by 2
    {
      *this *= 2;
      return *this;
    }

    if (rhs == 0)                   // zero is special case
    {
   return *this;
    }

    if (IsPositive() != rhs.IsPositive())    // signs not the same, subtract
    {
        *this -= (-1 * rhs);
        return *this;
    }

    // process both numbers until one is exhausted

    if (len < rhs.NumDigits())
    {
        len = rhs.NumDigits();
    }
    for(k=0; k < len; k++)
    {
        sum = GetDigit(k) + rhs.GetDigit(k) + carry;
        carry = sum / BASE;
        sum = sum % BASE;

        if (k < myNumDigits)
        {
            ChangeDigit(k,sum);
        }
        else
        {
            AddSigDigit(sum);
        }
    }
    if (carry != 0)
    {
        AddSigDigit(carry);
    }
    return *this;
}

LBigInt operator +(const LBigInt & lhs, const LBigInt & rhs)
// postcondition: returns a bigint whose value is lhs + rhs
{
    LBigInt result(lhs);
    result += rhs;
    return result;
}

LBigInt operator -(const LBigInt & lhs, const LBigInt & rhs)
// postcondition: returns a bigint whose value is lhs + rhs
{
    LBigInt result(lhs);
    result -= rhs;
    return result;
}

void LBigInt::Print(ostream & os) const
// postcondition: LBigInt inserted onto stream os
{
    os << ToString();
}

apstring LBigInt::ToString() const
// postcondition: returns string equivalent of LBigInt
{
    int k;
    int len = NumDigits();
    apstring s = "";

    if (IsNegative())
    {
        s = '-';
    }
    for(k=len-1; k >= 0; k--)
    {
        s += char('0'+GetDigit(k));
    }
    return s;
}

int LBigInt::ToInt() const
// precondition: INT_MIN <= self <= INT_MAX
// postcondition: returns int equivalent of self
{
    int result = 0;
    int k;
    if (INT_MAX < *this) return INT_MAX;
    if (*this < INT_MIN) return INT_MIN;

    for(k=NumDigits()-1; k >= 0; k--)
    {
        result = result * 10 + GetDigit(k);
    }
    if (IsNegative())
    {
        result *= -1;
    }
    return result;
}

double LBigInt::ToDouble() const
// precondition: DBL_MIN <= self <= DLB_MAX
// postcondition: returns double equivalent of self
{
    double result = 0.0;
    int k;
    for(k=NumDigits()-1; k >= 0; k--)
    {
        result = result * 10 + GetDigit(k);
    }
    if (IsNegative())
    {
        result *= -1;
    }
    return result;
}

ostream & operator <<(ostream & out, const LBigInt & big)
// postcondition: big inserted onto stream out
{
    big.Print(out);
    return out;
}

istream & operator >> (istream & in, LBigInt & big)
// postcondition: big extracted from in, must be whitespace delimited
{
    apstring s;
    in >> s;
    big = LBigInt(s);
    return in;
}

bool operator == (const LBigInt & lhs, const LBigInt & rhs)
// postcondition: returns true if lhs == rhs, else returns false
{
    return lhs.Equal(rhs);
}

bool LBigInt::Equal(const LBigInt & rhs) const
// postcondition: returns true if self == rhs, else returns false
{

    if (NumDigits() != rhs.NumDigits() || IsNegative() != rhs.IsNegative())
    {
        return false;
    }
    // assert: same sign, same number of digits;

    int k;
    int len = NumDigits();
    for(k=0; k < len; k++)
    {
        if (GetDigit(k) != rhs.GetDigit(k)) return false;
    }

    return true;
}

bool operator != (const LBigInt & lhs, const LBigInt & rhs)
// postcondition: returns true if lhs != rhs, else returns false
{
    return ! (lhs == rhs);
}

bool operator < (const LBigInt & lhs, const LBigInt & rhs)
// postcondition: return true if lhs < rhs, else returns false
{
    return lhs.LessThan(rhs);
}

bool LBigInt::LessThan(const LBigInt & rhs) const
// postcondition: return true if self < rhs, else returns false
{
    // if signs aren't equal, self < rhs only if self is negative

    if (IsNegative() != rhs.IsNegative())
    {
        return IsNegative();
    }

    // if # digits aren't the same must check # digits and sign

    if (NumDigits() != rhs.NumDigits())
    {
        return (NumDigits() < rhs.NumDigits() && IsPositive()) ||
               (NumDigits() > rhs.NumDigits() && IsNegative());
    }

    // assert: # digits same, signs the same

    int k;
    int len = NumDigits();

    for(k=len-1; k >= 0; k--)
    {
        if (GetDigit(k) < rhs.GetDigit(k)) return IsPositive();
        if (GetDigit(k) > rhs.GetDigit(k)) return IsNegative();
    }
    return false;      // self == rhs
}

bool operator > (const LBigInt & lhs, const LBigInt & rhs)
// postcondition: return true if lhs > rhs, else returns false
{
    return rhs < lhs;
}

bool operator <= (const LBigInt & lhs, const LBigInt & rhs)
// postcondition: return true if lhs <= rhs, else returns false
{
    return lhs == rhs || lhs < rhs;
}
bool operator >= (const LBigInt & lhs, const LBigInt & rhs)
// postcondition: return true if lhs >= rhs, else returns false
{
    return lhs == rhs || lhs > rhs;
}

void LBigInt::Normalize()
// postcondition: all leading zeros removed
{
    int k;
    int len = NumDigits();
    for(k=len-1; k >= 0; k--)        // find a non-zero digit
    {
        if (GetDigit(k) != 0) break;
        myNumDigits--;               // "chop" off zeros
    }
    if (k < 0)    // all zeros
    {
        myNumDigits = 1;
        mySign = positive;
        most = least;
    }
    else
    {
        most = least;
        for(k=0; k < myNumDigits; k++)
        {
            most = most->next;
        }
    }
}


const LBigInt & LBigInt::operator *=(int num)
// postcondition: returns num * value of LBigInt after multiplication
{
    int carry = 0;
    int product;               // product of num and one digit + carry
    int k;
    int len = NumDigits();

    if (0 == num)              // treat zero as special case and stop
    {
        *this = 0;
        return *this;
    }

    if (BASE < num|| num < 0)        // handle pre-condition failure
    {
        *this *= LBigInt(num);
        return *this;
    }

    if (1 == num)              // treat one as special case, no work
    {
        return *this;
    }

    for(k=0; k < len; k++)     // once for each digit
    {
        product = num * GetDigit(k) + carry;
        carry = product/BASE;
        ChangeDigit(k,product % BASE);
    }

    while (carry != 0)         // carry all digits
    {
        AddSigDigit(carry % BASE);
        carry /= BASE;
    }
    return *this;
}


LBigInt operator *(const LBigInt & a, int num)
// postcondition: returns a * num
{
    LBigInt result(a);
    result *= num;
    return result;
}

LBigInt operator *(int num, const LBigInt & a)
// postcondition: returns num * a
{
    LBigInt result(a);
    result *= num;
    return result;
}


const LBigInt & LBigInt::operator *=(const LBigInt & rhs)
// postcondition: returns value of bigint * rhs after multiplication
{
    // uses standard "grade school method" for multiplying

   if (IsNegative() != rhs.IsNegative())
   {
      mySign = negative;
   }
   else
   {
      mySign = positive;
   }

    LBigInt self(*this);                        // copy of self
    LBigInt sum(0);                             // to accumulate sum
    int k;
    int len = rhs.NumDigits();                 // # digits in multiplier

    for(k=0; k < len; k++)
    {
       sum += self * rhs.GetDigit(k);          // k-th digit * self
       self *= 10;                             // add a zero
    }
    *this = sum;
    return *this;
}

LBigInt operator *(const LBigInt & lhs, const LBigInt & rhs)
// postcondition: returns a bigint whose value is lhs * rhs
{
    LBigInt result(lhs);
    result *= rhs;
    return result;
}

int LBigInt::NumDigits() const
// postcondition: returns # digits in LBigInt
{
    return myNumDigits;
}

int LBigInt::GetDigit(int k) const
// precondition: 0 <= k < NumDigits()
// postcondition: returns k-th digit
//                (0 if precondition is false)
//                Note: 0th digit is least significant digit
{
    Node * temp;
    
    if (0 <= k && k < NumDigits())
    {
	temp = least;
	int lcv;
	for(lcv = 0; lcv < k; lcv++)
	{
	    temp = temp->next;
	}
		
	return temp->info - '0';
    }    
    return 0;
}

void LBigInt::ChangeDigit(int k, int value)
// precondition: 0 <= k < NumDigits()
// postcondition: k-th digit changed to value
//                Note: 0th digit is least significant digit
{
    Node * temp;
    
    if (0 <= k && k < NumDigits())
    {
	temp = least;
	int lcv;
	for(lcv = 0; lcv < k; lcv++)
	{
	    temp = temp->next;
	}
	temp->info = char('0'+value);
    }
    else
    {
        cerr << "error changeDigit " << k << " " << myNumDigits << endl;
    }
}

void LBigInt::AddSigDigit(int value)
// postcondition: value added to LBigInt as most significant digit
//                Note: 0th digit is least significant digit
{
    most->next = new Node(char(value+'0'),NULL);
    most = most->next;
    myNumDigits++;
}

bool LBigInt::IsNegative() const
// postcondition: returns true iff LBigInt is negative
{
    return mySign == negative;
}

bool LBigInt::IsPositive() const
// postcondition: returns true iff LBigInt is positive
{
   return mySign == positive;
}


void LBigInt::DivideHelp(const LBigInt & lhs, const LBigInt & rhs,
                        LBigInt & quotient, LBigInt & remainder)
// postcondition: quotient = lhs / rhs
//                remainder = lhs % rhs     
{
    if (lhs < rhs)             // integer division yields 0
    {                          // so avoid work and return
        quotient = 0;        
        remainder = lhs;
        return;
    }
    else if (lhs == rhs)       // again, avoid work in special case
    {
        quotient = 1;
        remainder = 0;
        return;
    }
    
    LBigInt dividend(lhs);      // make copies because of const-ness
    LBigInt divisor(rhs);
    quotient = remainder = 0;
    int k,trial;
    int zeroCount = 0;

    // pad divisor with zeros until # of digits = dividend
    
    while (divisor.NumDigits() < dividend.NumDigits())
    {
        divisor *= 10;
        zeroCount++;
    }

    // if we added one too many zeros chop one off
    
    if (divisor > dividend)
    {
        divisor /= 10;
        zeroCount--;
    }


    // algorithm: make a guess for how many times dividend part
    // goes into divisor, adjust the guess, subtract out and repeat
    
    int divisorSig = divisor.GetDigit(divisor.NumDigits()-1);
    int dividendSig;
    LBigInt hold;    
    for(k=0; k <= zeroCount; k++)
    {
        dividendSig = dividend.GetDigit(dividend.NumDigits()-1);
        trial =
            (dividendSig*10 + dividend.GetDigit(dividend.NumDigits()-2))
            /divisorSig;
        
        if (BASE <= trial)   // stay within base
        {
            trial = BASE-1;
        }
        while ((hold = divisor * trial) > dividend)
        {
            trial--;
        }

        // accumulate quotient by adding digits to quotient
        // and chopping them off of divisor after adjusting dividend
        
        quotient *= 10;
        quotient += trial;
        dividend -= hold;
        divisor /= 10;       
        divisorSig = divisor.GetDigit(divisor.NumDigits()-1);        
    }
    remainder = dividend;
}

const LBigInt & LBigInt::operator /=(const LBigInt & rhs)
// postcondition: return LBigInt / rhs after modification
{
    LBigInt quotient,remainder;
    bool resultNegative = (IsNegative() != rhs.IsNegative());
    mySign = positive;      // force myself positive
    
    // DivideHelp does all the work
    
    if (rhs.IsNegative())
    {
        DivideHelp(*this,-1*rhs,quotient,remainder);
    }
    else
    {
        DivideHelp(*this,rhs,quotient,remainder);       
    }
    *this = quotient;
    mySign = resultNegative ? negative : positive;
    Normalize();
    return *this;
}

LBigInt operator / (const LBigInt & lhs, const LBigInt & rhs)
// postcondition: return lhs / rhs
{
    LBigInt result(lhs);
    result /= rhs;
    return result;
}

const LBigInt & LBigInt::operator /=(int num)
// precondition: 0 < num < BASE     
// postcondition: returns LBigInt/num after modification
{
    int carry = 0;
    int quotient;
    int k;
    int len = NumDigits();

    if (num > BASE)     // check precondition
    {
        return operator /= (LBigInt(num));
    }
    if (0 == num)       // handle division by zero 
    {
        cerr << "division by zero error" << endl;
		abort();
    }
    else
    {
        for(k=len-1; k >= 0; k--)  // once for each digit
        {
            quotient = (10*carry + GetDigit(k));
            carry = quotient % num;
            ChangeDigit(k, quotient / num);
        }
    }
    Normalize();
    return *this;
}

LBigInt operator /(const LBigInt & a, int num)
// postcondition: returns a / num     
{
    LBigInt result(a);
    result /= num;
    return result;
}

LBigInt operator %(const LBigInt & lhs, const LBigInt & rhs)
// postcondition: returns lhs % rhs     
{
    LBigInt result(lhs);
    result %= rhs;
    return result;
}


const LBigInt & LBigInt::operator %=(const LBigInt & rhs)
// postcondition: returns LBigInt % rhs after modification     
{
    LBigInt quotient,remainder;
    bool resultNegative = (IsNegative() != rhs.IsNegative());
    
    // DivideHelp does all the work
    
    if (rhs.IsNegative())
    {
        DivideHelp(*this,-1 * rhs,quotient,remainder);
    }
    else
    {
        DivideHelp(*this,rhs,quotient,remainder);       
    }
    *this = remainder;
    mySign = resultNegative ? negative : positive;   
    return *this;
}