#ifndef _BIGINT_H
#define _BIGINT_H

// author: Owen Astrachan
// 8/23/95, modified 7/5/96
//          modified 1/5/97
//
// implements an arbitrary precision integer class
// 
// constructors:
//
// LBigInt()            -- default constructor, value of integers is 0
// LBigInt(int n)       -- initialize to value of n (C++ int)
// LBigInt(const apstring & s) -- initialize to value specified by s
//        it is an error if s is an invalid integer, e.g.,
//        "1234abc567".  In this case the bigint value is garbage
//
//
// *****  arithmetic operators:
//
// all arithmetic operators +, -, * are overloaded both
// in form +=, -=, *= and as binary operators
//
// multiplication also overloaded for *= int
// e.g., LBigInt a *= 3 (mostly to facilitate implementation)
//
//  ***** logical operators:
//
// bool operator == (const LBigInt & lhs, const LBigInt & rhs)
// bool operator != (const LBigInt & lhs, const BitInt & rhs)
// bool operator <  (const LBigInt & lhs, const LBigInt & rhs)
// bool operator <= (const LBigInt & lhs, const LBigInt & rhs)
// bool operator >  (const LBigInt & lhs, const LBigInt & rhs)
// bool operator >= (const LBigInt & lhs, const LBigInt & rhs)
//
//  ***** I/O operators:
//
//  void Print()
//        prints value of LBigInt (member function)
//  ostream & operator << (ostream & os, const LBigInt & b)
//        stream operator to print value
//
// istream & operator >> (istream & in, const LBigInt & b)
//        reads whitespace delimited LBigInt from input stream in
//


#include <iostream.h>
#include "apstring.h"            // for strings
#include "apvector.h"            // for sequence of digits


struct Node
{
    char info;
    Node * next;

    Node(char val, Node * link)
	: info(val),
	  next(link)
    { }
};

class LBigInt
{
  public:
    
    LBigInt();                    // default constructor, value = 0
    LBigInt(int);                 // assign an integer value
    LBigInt(const apstring &);    // assign a string
    
    LBigInt(const LBigInt & rhs);
    const LBigInt & operator = (const LBigInt &);
    ~LBigInt();
    
    // operators: arithmetic, relational

    const LBigInt & operator += (const LBigInt &);
    const LBigInt & operator -= (const LBigInt &);
    const LBigInt & operator *= (const LBigInt &);
    const LBigInt & operator *= (int num);
    const LBigInt & operator /= (const LBigInt &);
    const LBigInt & operator /= (int num);
    const LBigInt & operator %= (const LBigInt &);
   
    apstring ToString() const;   // convert to string
    int      ToInt()    const;   // convert to int
    double   ToDouble() const;   // convert to double 

    // facilitate operators ==, <, << without friends

    bool Equal(const LBigInt & rhs)        const;
    bool LessThan(const LBigInt & rhs)     const;
    void Print(ostream & os)              const;

  private:
    
    // other helper functions

    bool IsNegative()  const;    // return true iff number is negative
    bool IsPositive()  const;    // return true iff number is positive
    int NumDigits()    const;    // return # digits in number
    
    int GetDigit(int k) const;
    void AddSigDigit(int value);
    void ChangeDigit(int k, int value);

    void Normalize();
    void DivideHelp(const LBigInt & lhs, const LBigInt & rhs,
                        LBigInt & quotient, LBigInt & remainder);

    // private state/instance variables

    enum Sign{positive,negative};
    Sign mySign;				 // is number positive
						 // or negative
    Node * least;  // least significant digit
    Node * most;   // most significant digit  

    int myNumDigits;			 // stores # of digits of number 
};

// free functions

ostream & operator <<(ostream &, const LBigInt &);
istream & operator >>(istream &, LBigInt &);

LBigInt operator +(const LBigInt & lhs, const LBigInt & rhs);
LBigInt operator -(const LBigInt & lhs, const LBigInt & rhs);
LBigInt operator *(const LBigInt & lhs, const LBigInt & rhs);
LBigInt operator *(const LBigInt & lhs, int num);
LBigInt operator *(int num, const LBigInt & rhs);
LBigInt operator /(const LBigInt & lhs, const LBigInt & rhs);
LBigInt operator /(const LBigInt & lhs, int num);
LBigInt operator %(const LBigInt & lhs, const LBigInt & rhs);

bool operator == (const LBigInt & lhs, const LBigInt & rhs);
bool operator <  (const LBigInt & lhs, const LBigInt & rhs);
bool operator != (const LBigInt & lhs, const LBigInt & rhs);
bool operator >  (const LBigInt & lhs, const LBigInt & rhs);
bool operator >= (const LBigInt & lhs, const LBigInt & rhs);
bool operator <= (const LBigInt & lhs, const LBigInt & rhs);


#endif   // _BIGINT_H not defined