bigInt14
[ Home ] [ Up ]

//Date:   2003.12.09
//File:   bigInt14.cpp
//Author: AOU


///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>


/*********************************************************/
/* BEGIN WHAT IS NEW                                     */
/*********************************************************/
/*
**********************************************************
2003.12.09
  CBigInt:
    bool deleteFirst(void); //xx NOT ON FINAL
    bool deleteLast(void);  //xx NOT ON FINAL
    void shiftLeft(void);   //xx NOT ON FINAL
    void shiftRight(void);  //xx NOT ON FINAL

2003.12.08
  CBigInt:
    CBigInt(int n); // modified so as to convert int to big integer
    bool operator     ==  (const CBigInt &bi2) const;  //fixed 
    CBigInt & operator +  (const CBigInt &bi2) const;  //fixed
    bool operator      <  (const CBigInt &bi2) const;  //fixed

2003.12.06
  CBigInt:
    CBigInt(const CBigInt &bi2);
    CBigInt & operator = (const CBigInt &bi2);
    bool operator     ==  (const CBigInt &bi2) const; 
    CBigInt & operator +  (const CBigInt &bi2) const;
    bool operator     !=  (const CBigInt &bi2) const;
    bool operator      <  (const CBigInt &bi2) const;
  
  CDigit:
    bool operator     <  (const CDigit &d2) const;

**********************************************************
2003.12.05
    ~CBigInt(void); //Will

**********************************************************
2003.12.03
    void displayReverse(void) const;
    bool insert2Left(CDigit x);
    
**********************************************************
2003.12.01
    int removeAll(void);
    void populate(int n);

**********************************************************
2003.11.24

**********************************************************
2003.11.14
    CDigit(unsigned int coef, unsigned int expo); 
    CBigInt(void);

**********************************************************
2003.11.12
    bool operator     !=  (const CBigInt &i2) const;
    CDigit(unsigned int coef); 

**********************************************************
2003.11.10
    CDigit(char ch);
    CDigit(const CDigit &d2);
    bool operator     ==  (const CBigInt &i2) const;

*/
/*********************************************************/
/* END WHAT IS NEW                                       */
/*********************************************************/


///////////////////////////////////////////////////////////
//constants
///////////////////////////////////////////////////////////
const unsigned int BASE        = 10;
const unsigned int MIN_VALUE   = 0;
const unsigned int MAX_VALUE   = BASE-1;
const unsigned int MAX_EXPO    = 10;
const unsigned int UNDEFINED   = 911;
const int          MAX_SIZE    = MAX_EXPO+1;
const int          TEST_COUNT  = 40;


///////////////////////////////////////////////////////////
//prototypes
///////////////////////////////////////////////////////////
void driverConstructorDefault_CBigInt(void);
void driverInsert2Right_CBigInt(void);
void driverConstructorN_CBigInt(void);
void driverConstructorCh_CBigInt(void);
void driverRemoveAll_CBigInt(void);
void driverPopulate_CBigInt(void);
void driverInsert2Left_CBigInt(void);
void driverDestructor_CBigInt(void);

void driverConstructorCopy_CBigInt(void);
void driverOperatorAssign_CBigInt(void);
void driverOperatorEqual_CBigInt(void);
void driverOperatorAdd_CBigInt(void);
void driverOperatorNotEqual_CBigInt(void);
void driverOperatorLessThan_CBigInt(void);


void driverDeleteFirst_CBigInt(void);
void driverDeleteLast_CBigInt(void);
void driverShiftLeft_CBigInt(void);
void driverShiftRight_CBigInt(void);


///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void driverConstructorDefault_CDigit(void);
void driverConstructorChar_CDigit(void);
void driverConstructorCopy_CDigit(void);
void driverOperatorEqual_CDigit(void);
void driverOperatorNotEqual_CDigit(void);
void driverConstructorInt_CDigit(void);
void driverConstructorIntExpo_CDigit(void);

void driverOperatorLessThan_CDigit(void);

///////////////////////////////////////////////////////////
//class CDigit
///////////////////////////////////////////////////////////
class CDigit
  {
  private:
    CDigit *_prev;
    unsigned int _coef;
    unsigned int _expo;
    CDigit *_next;
  public:
    CDigit(void); //
    CDigit(char ch);          //2003.11.10
    CDigit(const CDigit &d2); //2003.11.10
    CDigit(unsigned int coef); //
    CDigit(unsigned int coef, unsigned int expo); //

    void display(void) const; //
    void displayAll(void) const; //
    void init(void); //

    bool   operator   == (const CDigit &d2) const;//
    bool   operator   != (const CDigit &d2) const;//
    bool operator     <  (const CDigit &d2) const;//
    bool operator     >  (const CDigit &d2) const;
    bool operator     >= (const CDigit &d2) const;
    bool operator     <= (const CDigit &d2) const;
    CDigit operator   +  (const CDigit &d2) const;
    CDigit operator   *  (const CDigit &d2) const;
    CDigit operator   -  (const CDigit &d2) const;
    CDigit operator   /  (const CDigit &d2) const;
    CDigit & operator =  (const CDigit &d2);

    bool deleteFirst(void);
    bool deleteLast(void);

    friend ostream & operator << (ostream &bob, const CDigit &d2);

    friend class CBigInt;
  };


///////////////////////////////////////////////////////////
//class CBigInt
///////////////////////////////////////////////////////////
class CBigInt
  {
  private:
    CDigit *_first;
    CDigit *_last;
    unsigned int _count;
  public:
    CBigInt(void); //
    CBigInt(char ch); //
    CBigInt(int n); //    modified so as to convert int to big integer
    CBigInt(const CBigInt &bi2); //

    ~CBigInt(void); //Will

    void display(void) const; //
    void displayAll(void) const; //
    void init(void); //
    bool insert2Right(CDigit x); //
    bool insert2Left(CDigit x); //
    int  removeAll(void); //
    void populate(int n); //
    void displayReverse(void) const; //
    bool isSorted(void) const;
    void shuffle(void);
    void sortBubble(void);
    void minimize(void);
    bool removeAtAddress(CDigit *p);
    int removeLeadingBlanks(void);
    int removeLeadingZeros(void);
    
    CBigInt & operator = (const CBigInt &bi2); //

    bool operator     ==  (const CBigInt &bi2) const; //
    bool operator     !=  (const CBigInt &bi2) const; //
    bool operator      <  (const CBigInt &bi2) const; //
    bool operator      <= (const CBigInt &bi2) const;
    bool operator      >  (const CBigInt &bi2) const;
    bool operator      >= (const CBigInt &bi2) const;
    CBigInt & operator +  (const CBigInt &bi2) const; //
    CBigInt & operator *  (const CBigInt &bi2) const;
    CBigInt & operator -  (const CBigInt &bi2) const;
    CBigInt & operator /  (const CBigInt &bi2) const;

    friend ostream & operator << (ostream &bob, const CBigInt &bi);

    bool hasDistinct(void) const;
    
    bool deleteAtPos(int p);

    bool deleteFirst(void); //xx NOT ON FINAL
    bool deleteLast(void);  //xx NOT ON FINAL
    void shiftLeft(void);   //xx NOT ON FINAL
    void shiftRight(void);  //xx NOT ON FINAL
  };


///////////////////////////////////////////////////////////
//main
///////////////////////////////////////////////////////////
void main(void)
  {
  //srand(time(NULL));

  //driverConstructorDefault_CBigInt();
  //driverInsert2Right_CBigInt();
  //driverConstructorN_CBigInt(); //modified
  //driverConstructorCh_CBigInt();
  //driverRemoveAll_CBigInt();
  //driverPopulate_CBigInt();
  //driverInsert2Left_CBigInt();
  //driverDestructor_CBigInt();

  //driverConstructorCopy_CBigInt();
  //driverOperatorAssign_CBigInt();
  //driverOperatorEqual_CBigInt();
  //driverOperatorAdd_CBigInt();
  //driverOperatorNotEqual_CBigInt();
  //driverOperatorLessThan_CBigInt();

  //driverDeleteFirst_CBigInt();
  //driverDeleteLast_CBigInt();
  //driverShiftLeft_CBigInt();
  driverShiftRight_CBigInt();

  ////////////////////////////////////
  ////////////////////////////////////

  //driverConstructorDefault_CDigit();

  //driverConstructorChar_CDigit();
  //driverConstructorCopy_CDigit();
  //driverOperatorEqual_CDigit();
  //driverOperatorNotEqual_CDigit();
  //driverConstructorInt_CDigit();
  //driverConstructorIntExpo_CDigit();

  //driverOperatorLessThan_CDigit();

  }


///////////////////////////////////////////////////////////
// void driverShiftRight_CBigInt(void)
///////////////////////////////////////////////////////////
void driverShiftRight_CBigInt(void)
  {
  cout << "------------------------\n";
  cout << "driverShiftRight_CBigInt\n";
  cout << "------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r');

    cout << "bi1 = "; bi1.display(); cout << endl;

    bi1.shiftRight();
    cout << "After shifting right one digit\n";
    cout << "bi1 = "; bi1.display(); cout << endl;
    
    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// void CBigInt::shiftRight(void)
///////////////////////////////////////////////////////////
/*
if undefined or equal to zero then 
    return
  else only one digit
    replace it with zero
    return
  else
    decrease expo of each digit by one
    delete right-most digit
  end if
*/
void CBigInt::shiftRight(void)
  {
  if (NULL==this->_first)
      return;
    else if (this->_first==this->_last && this->_first->_coef==0)
      return;
    else if (this->_first==this->_last)
      {
      this->_first->_coef=0;
      return;
      }
    else
      {
      CDigit *p = this->_first;
      while (p!=NULL)
        {
        p->_expo--;
        p=p->_next;
        }
      this->deleteLast();
      }
  }


///////////////////////////////////////////////////////////
// void driverShiftLeft_CBigInt(void)
///////////////////////////////////////////////////////////
void driverShiftLeft_CBigInt(void)
  {
  cout << "-----------------------\n";
  cout << "driverShiftLeft_CBigInt\n";
  cout << "-----------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r');

    cout << "bi1 = "; bi1.display(); cout << endl;

    bi1.shiftLeft();
    cout << "After shifting left one digit\n";
    cout << "bi1 = "; bi1.display(); cout << endl;
    
    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// void CBigInt::shiftLeft(void)
///////////////////////////////////////////////////////////
/*
if undefined or equal to zero then 
    return
  else
    increase expo of each digit by one
    insert to right zero digit
  end if
*/
void CBigInt::shiftLeft(void)
  {
  if (NULL==this->_first)
      return;
    else if (this->_first==this->_last && this->_first->_coef==0)
      return;
    else
      {
      CDigit *p = this->_first;
      while (p!=NULL)
        {
        p->_expo++;
        p=p->_next;
        }
      CDigit digit(0,0);
      this->insert2Right(digit);
      }
  }


///////////////////////////////////////////////////////////
// void driverDeleteLast_CBigInt(void)
///////////////////////////////////////////////////////////
void driverDeleteLast_CBigInt(void)
  {
  cout << "------------------------\n";
  cout << "driverDeleteLast_CBigInt\n";
  cout << "------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r');

    cout << "bi1 = "; bi1.display(); cout << endl;

    while(bi1.deleteLast())
      {
      cout << "After deleting the last digit\n";
      cout << "bi1 = "; bi1.display(); cout << endl;
      }
    
    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CBigInt::deleteLast(void)
///////////////////////////////////////////////////////////
/*
if empty then 
    return false
  else
    if only one node then
        remove it
        set first and last to null
        set count to 0
      else
        set second to last node's next to null
        set last to second to last node
        delete the last node
        decrease count
      end if
    return true
  end if

*/
bool CBigInt::deleteLast(void)
  {
  if (NULL==this->_first)
      return false;
    else
      {
      if (this->_first==this->_last)
          {
          delete this->_first;
          this->_first=this->_last=NULL;
          this->_count=0;
          }
        else
          {
          CDigit *p=this->_last;
          this->_last=this->_last->_prev;
          this->_last->_next=NULL;
          delete p;
          this->_count--;
          }
      return true;
      }
  }


///////////////////////////////////////////////////////////
// void driverDeleteFirst_CBigInt(void)
///////////////////////////////////////////////////////////
void driverDeleteFirst_CBigInt(void)
  {
  cout << "-------------------------\n";
  cout << "driverDeleteFirst_CBigInt\n";
  cout << "-------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r');

    cout << "bi1 = "; bi1.display(); cout << endl;

    while(bi1.deleteFirst())
      {
      cout << "After deleting the first digit\n";
      cout << "bi1 = "; bi1.display(); cout << endl;
      }
    
    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CBigInt::deleteFirst(void)
///////////////////////////////////////////////////////////
/*
if empty then 
    return false
  else
    if only one node then
        remove it
        set first and last to null
        set count to 0
      else
        set second node's prev to null
        set first to second node
        delete the first node
        decrease count
      end if
    return true
  end if

*/
bool CBigInt::deleteFirst(void)
  {
  if (NULL==this->_first)
      return false;
    else
      {
      if (this->_first==this->_last)
          {
          delete this->_first;
          this->_first=this->_last=NULL;
          this->_count=0;
          }
        else
          {
          CDigit *p=this->_first;
          this->_first=this->_first->_next;
          this->_first->_prev=NULL;
          delete p;
          this->_count--;
          }
      return true;
      }
  }


///////////////////////////////////////////////////////////
// void driverOperatorLessThan_CBigInt(void)
///////////////////////////////////////////////////////////
void driverOperatorLessThan_CBigInt(void)
  {
  cout << "------------------------------\n";
  cout << "driverOperatorLessThan_CBigInt\n";
  cout << "------------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r'), bi2('r');

    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;

    cout << ((bi1<bi2) ? "bi1 is less than bi2\n":"bi1 is NOT less than bi2\n");
    cout << ((bi2<bi1) ? "bi2 is less than bi1\n":"bi2 is NOT less than bi1\n");

    bi1 = bi2;
    
    cout << endl;
    cout << "After bi1 = bi2;\n";
    
    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;

    cout << ((bi1<bi2) ? "bi1 is less than bi2\n":"bi1 is NOT less than bi2\n");

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CBigInt::operator < (const CBigInt &bi2) const
///////////////////////////////////////////////////////////
/*
expo1 = exponent of the most significant digit of bi1
expo2 = exponent of the most significant digit of bi2
if expo1 < expo2 then {500, 1000} 
    return true
  else if expo1 > expo2 then {1000, 500}
    return false
  else if expo1 == expo2 then {541, 529}
    for digits from left to right
      if digit1 < digit2 then 
        return true
      if difit1 > digit2 then 
        return false
      end for
    return false

*/
bool CBigInt::operator < (const CBigInt &bi2) const
  {
  //takes care of undefined integers
  if (NULL==this->_first || NULL==bi2._first)
    return false;

  // expo1 = exponent of the most significant digit of bi1
  
  CDigit *p1=this->_first;
  while (p1!=this->_last && p1->_coef==0)
    p1=p1->_next;

  int expo1 = p1->_expo;

  // expo2 = exponent of the most significant digit of bi2
  CDigit *p2=bi2._first;
  while (p2!=bi2._last && p2->_coef==0)
    p2=p2->_next;

  int expo2 = p2->_expo;

  // if expo1 < expo2 then {500, 1000} return true
  if (expo1 < expo2)
    return true;

  //   else if expo1 > expo2 then {1000, 500} return false
  if (expo1 > expo2)
    return false;

  //   else if expo1 == expo2 then {541, 529}
  while (p1!=NULL) 
    {
    if (p1->_coef < p2->_coef)
      return true;
    if (p1->_coef > p2->_coef)
      return false;
    p1=p1->_next;
    p2=p2->_next;
    }
  return false;
  }


///////////////////////////////////////////////////////////
// void driverOperatorNotEqual_CBigInt(void)
///////////////////////////////////////////////////////////
void driverOperatorNotEqual_CBigInt(void)
  {
  cout << "------------------------------\n";
  cout << "driverOperatorNotEqual_CBigInt\n";
  cout << "------------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r'), bi2('r');

    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;

    cout << ((bi1!=bi2) ? "bi1 is NOT equal to bi2\n":"bi1 is equal to bi2\n");

    bi1 = bi2;
    
    cout << "After bi1 = bi2;\n";
    
    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;

    cout << ((bi1!=bi2) ? "bi1 is NOT equal to bi2\n":"bi1 is equal to bi2\n");

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CBigInt::operator != (const CBigInt &bi2) const
///////////////////////////////////////////////////////////
bool CBigInt::operator != (const CBigInt &bi2) const
  {
  return !(*this==bi2);
  }


///////////////////////////////////////////////////////////
// void driverOperatorAdd_CBigInt(void)
///////////////////////////////////////////////////////////
void driverOperatorAdd_CBigInt(void)
  {
  cout << "-------------------------\n";
  cout << "driverOperatorAdd_CBigInt\n";
  cout << "-------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r'), bi2('r'), bi3('r');

    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;
    cout << "bi3 = "; bi3.display(); cout << endl;

    bi3 = bi1 + bi2;
    
    cout << endl;
    cout << "After bi3 = bi1 + bi2;\n";
    
    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;
    cout << "bi3 = "; bi3.display(); cout << endl;

    bi1 = bi2;
    bi3 = bi1 + bi2;
    
    cout << endl;
    cout << "After bi1 = bi2; and \n";
    cout << "After bi3 = bi1 + bi2;\n";
    
    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;
    cout << "bi3 = "; bi3.display(); cout << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CBigInt & CBigInt::operator + (const CBigInt &bi2) const
///////////////////////////////////////////////////////////
CBigInt & CBigInt::operator + (const CBigInt &bi2) const
  {
  //what if addition creates extra digit to the left
  CBigInt *pbi = new CBigInt;
  //knowing location of million dollars is safer than having million dollars in pocket
  
  //does not work if one or both number(s) undefined (fixed)

  if (NULL==this->_first || NULL==bi2._first)
    return *pbi;

  unsigned int carry = 0;
  unsigned int expo  = 0;
  unsigned int sum;

  CDigit *p1=this->_last;
  CDigit *p2=bi2._last;
  
  while (p1!=NULL || p2!=NULL)
    {
    if (p1!=NULL && p2!=NULL)
      sum = p1->_coef + p2->_coef;
    else if (p1!=NULL)
      sum = p1->_coef;
    else if (p2!=NULL)
      sum = p2->_coef;

    sum = sum + carry;
    carry = sum/BASE;
    sum = sum%BASE;

    CDigit digit(sum, expo);
    pbi->insert2Left(digit);

    expo++;

    if (p1!=NULL)
      p1 = p1->_prev;
    if (p2!=NULL)
      p2 = p2->_prev;

    }
  
  //what if addition creates extra digit to the left (fixed)
  //take care of carry>0
  if (carry>0)
    {
    CDigit digit(carry, expo);
    pbi->insert2Left(digit);
    }

  return *pbi;
  }


///////////////////////////////////////////////////////////
// void driverOperatorEqual_CBigInt(void)
///////////////////////////////////////////////////////////
void driverOperatorEqual_CBigInt(void)
  {
  cout << "---------------------------\n";
  cout << "driverOperatorEqual_CBigInt\n";
  cout << "---------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r'), bi2('r');

    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;

    cout << ((bi1==bi2) ? "bi1 is equal to bi2\n":"bi1 is NOT equal to bi2\n");

    bi1 = bi2;
    
    cout << "After bi1 = bi2;\n";
    
    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;

    cout << ((bi1==bi2) ? "bi1 is equal to bi2\n":"bi1 is NOT equal to bi2\n");

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CBigInt::operator == (const CBigInt &i2) const
///////////////////////////////////////////////////////////
bool CBigInt::operator == (const CBigInt &i2) const
  {
  //possibilities
  //one or both undefined
  //one had leading zero and other did not

  CDigit *p1, *p2;

  p1 = this->_first;
  p2 = i2._first; 

  //if both are undefined
  if (NULL==p1 && NULL==p2)
    return true;

  //if one is undefined
  if (NULL==p1 || NULL==p2) 
    return false;

  //advance p1 and p2 to most significant digits except value is 0
  while (p1!=this->_last && 0==p1->_coef)
    p1 = p1->_next;

  while (p2!=i2._last && 0==p2->_coef)
    p2 = p2->_next;

  //if most siginificant digits don't have same weight
  if (p1->_expo != p2->_expo)
    return false;

  //compare digit by digit
  while (p1 != NULL)
    {
    if (*p1 != *p2)
      return false;
    
    p1 = p1->_next;
    p2 = p2->_next;
    }

  return true;
  }


///////////////////////////////////////////////////////////
// void driverOperatorAssign_CBigInt(void)
///////////////////////////////////////////////////////////
void driverOperatorAssign_CBigInt(void)
  {
  cout << "----------------------------\n";
  cout << "driverOperatorAssign_CBigInt\n";
  cout << "----------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi1('r'), bi2('r'), bi3('r');

    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;
    cout << "bi3 = "; bi3.display(); cout << endl;

    bi1 = bi2 = bi3;
    cout << "After bi1 = bi2 = bi3;\n";
    
    cout << "bi1 = "; bi1.display(); cout << endl;
    cout << "bi2 = "; bi2.display(); cout << endl;
    cout << "bi3 = "; bi3.display(); cout << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CBigInt & CBigInt::operator = (const CBigInt &i2)
///////////////////////////////////////////////////////////
CBigInt & CBigInt::operator = (const CBigInt &i2)
  {
  this->removeAll();

  CDigit *p = i2._first;
  while (p!=NULL)
    {
    this->insert2Right(*p);
    p = p->_next;
    }

  return *this;
  }


///////////////////////////////////////////////////////////
// void driverConstructorCopy_CBigInt(void)
///////////////////////////////////////////////////////////
void driverConstructorCopy_CBigInt(void)
  {
  cout << "-----------------------------\n";
  cout << "driverConstructorCopy_CBigInt\n";
  cout << "-----------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt *p1 = new CBigInt('r');

    cout << "*p1 = "; (*p1).display(); cout << endl;
    
    CBigInt *p2 = new CBigInt(*p1);

    cout << "*p2 = "; (*p2).display(); cout << endl;

    delete p1;
    delete p2;

    cout << "......................." << endl;

    }
  }


///////////////////////////////////////////////////////////
// CBigInt::CBigInt(const CBigInt &bi2)
///////////////////////////////////////////////////////////
CBigInt::CBigInt(const CBigInt &bi2)
  {
  this->init();

  CDigit *p = bi2._first;
  while (p!=NULL)
    {
    this->insert2Right(*p);
    p = p->_next;
    }

  return;
  }


///////////////////////////////////////////////////////////
// void driverDestructor_CBigInt(void)
///////////////////////////////////////////////////////////
void driverDestructor_CBigInt(void)
  {
  cout << "----------------------\n";
  cout << "driverDestructor_CBigInt\n";
  cout << "----------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt *p = new CBigInt('r');

    cout << "*p = ";
    (*p).display();
    cout << endl;
    
    delete p;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CBigInt::~CBigInt(void)
///////////////////////////////////////////////////////////
CBigInt::~CBigInt(void)
  {
  //cout << "Destructor was called\n";
  this->removeAll();
  }


///////////////////////////////////////////////////////////
// void driverInsert2Left_CBigInt(void)
///////////////////////////////////////////////////////////
void driverInsert2Left_CBigInt(void)
  {
  cout << "--------------------\n";
  cout << "driverInsert2Left_CBigInt\n";
  cout << "--------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi;
    cout << "bi = ";
    bi.display();
    cout << endl;

    CDigit d('r');
    cout << "d = ";
    d.display();
    cout << endl;

    bi.insert2Left(d);
    cout << "bi = ";
    bi.display();
    cout << endl;

    CDigit d2('r');
    cout << "d2 = ";
    d2.display();
    cout << endl;

    bi.insert2Left(d2);
    cout << "bi = ";
    bi.display();
    cout << endl;
    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CBigInt::insert2Left(CDigit x)
///////////////////////////////////////////////////////////
/*
p = address of new digit
copy into this digit coef and expo from x

if bigInt is empty then
    first = p
    last  = p
    count = 1
  else
    make new node point to first node
    make first node point to new node
    set first = p
    count++
  end if
*/
bool CBigInt::insert2Left(CDigit x)
  {
  CDigit *p;

  p = new CDigit;
  if (NULL == p)
    return false;

  p->_coef = x._coef;
  p->_expo = x._expo;

  if (NULL == this->_first)
    {
    this->_first = this->_last = p;
    this->_count = 1;
    }
  else
    {
    p->_next = this->_first;
    this->_first->_prev = p;
    this->_first = p;
    this->_count++;
    }

  return true;
  }


///////////////////////////////////////////////////////////
// void CBigInt::displayReverse(void) const
///////////////////////////////////////////////////////////
void CBigInt::displayReverse(void) const
  {
  CDigit *p;

  p = _last;

  while (p!=NULL)
    {
    p->display();
    p = p->_prev;
    }
  }


///////////////////////////////////////////////////////////
// void driverPopulate_CBigInt(void)
///////////////////////////////////////////////////////////
void driverPopulate_CBigInt(void)
  {
  cout << "----------------------\n";
  cout << "driverPopulate_CBigInt\n";
  cout << "----------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi('r');
    cout << "bi = ";
    bi.display();
    cout << endl;
    bi.displayReverse();
    cout << endl;
    bi.displayAll();
    cout << endl;

    int n = rand()%MAX_SIZE;

    bi.populate(n);

    cout << "After bi.populate(" << n << ");\n";

    cout << "bi = ";
    bi.display();
    cout << endl;
    bi.displayReverse();
    cout << endl;
    bi.displayAll();
    cout << endl;

    cout << "......................." << endl;

    }

  }



///////////////////////////////////////////////////////////
// void CBigInt::populate(int n)
///////////////////////////////////////////////////////////
/*
Populates an existing big integer
remove all digits
insert n digits
*/
void CBigInt::populate(int n)
  {
  this->removeAll();
  for (int i=n-1; i>=0; i--)
    {
    unsigned int coef = rand()%(MAX_VALUE-MIN_VALUE+1)+MIN_VALUE;
    unsigned int expo = i;
    CDigit d(coef, expo);
    this->insert2Right(d);
    }
  }


///////////////////////////////////////////////////////////
// void driverRemoveAll_CBigInt(void)
///////////////////////////////////////////////////////////
void driverRemoveAll_CBigInt(void)
  {
  cout << "-----------------------\n";
  cout << "driverRemoveAll_CBigInt\n";
  cout << "-----------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi('r');
    cout << "bi = ";
    bi.display();
    cout << endl;
    bi.displayAll();
    cout << endl;

    int removed = bi.removeAll();

    cout << "After removing " << removed << endl;

    cout << "bi = ";
    bi.display();
    cout << endl;
    bi.displayAll();
    cout << endl;

    cout << "......................." << endl;
    }
  }



///////////////////////////////////////////////////////////
// int CBigInt::removeAll(void)
///////////////////////////////////////////////////////////
/*
Removes all the nodes and 
  returns the number of nodes removed

Algorthm:
  removed=0
  t1=t2=first
  while t2<>null
    t2=t2->next
    delete t1
    removed++
    t1=t2
    wend
  first=last=null
  count=0
*/
int CBigInt::removeAll(void)
  {
  int removed=0;
  CDigit *t1, *t2;
  t1=t2=_first;
  while (t2 != NULL)
    {
    t2=t2->_next;
    delete t1;
    removed++;
    t1=t2;
    }

  this->init();
  return removed;
  }


///////////////////////////////////////////////////////////
// void driverConstructorCh_CBigInt(void)
///////////////////////////////////////////////////////////
void driverConstructorCh_CBigInt(void)
  {
  cout << "---------------------------\n";
  cout << "driverConstructorCh_CBigInt\n";
  cout << "---------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi('r');
    cout << "bi = ";
    bi.display();
    cout << endl;
    bi.displayAll();
    cout << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CBigInt::CBigInt(char ch)
///////////////////////////////////////////////////////////
CBigInt::CBigInt(char ch)
  {
  this->init();

  if ('r'==ch || 'R'==ch)
    {
    int n = rand()%(MAX_SIZE+1);
    for (int i=n-1; i>=0; i--)
      {
      unsigned int coef = rand()%(MAX_VALUE-MIN_VALUE+1)+MIN_VALUE;
      unsigned int expo = i;
      CDigit d(coef, expo);
      this->insert2Right(d);
      }
    }
  }


///////////////////////////////////////////////////////////
// void driverConstructorN_CBigInt(void)
///////////////////////////////////////////////////////////
void driverConstructorN_CBigInt(void)
  {
  cout << "--------------------\n";
  cout << "driverConstructorN_CBigInt\n";
  cout << "--------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    int n = rand();
    cout << "n=" << n << endl;
    CBigInt bi(n);
    cout << "bi = ";
    bi.display();
    cout << endl;
    bi.displayAll();

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CBigInt::CBigInt(int n)
///////////////////////////////////////////////////////////
//creates a big integer from integer n
/*
expo = 0
do
  coef = n%BASE
  n = n/BASE
  digit = (coef, expo)
  insert2Right digit into bi
  expo++
  while n>0

*/
CBigInt::CBigInt(int n)
  {
  this->init();

  unsigned int expo = 0;
  unsigned int coef;

  do
    {
    coef = n%BASE;
    n = n/BASE;
    CDigit digit(coef, expo);
    this->insert2Left(digit);
    expo++;
    }
    while (n>0);
  }


///////////////////////////////////////////////////////////
// void CBigInt::init(void)
///////////////////////////////////////////////////////////
void CBigInt::init(void)
  {
  _first = NULL;
  _last  = NULL;
  _count = 0;
  }


///////////////////////////////////////////////////////////
// void driverInsert2Right_CBigInt(void)
///////////////////////////////////////////////////////////
void driverInsert2Right_CBigInt(void)
  {
  cout << "--------------------\n";
  cout << "driverInsert2Right_CBigInt\n";
  cout << "--------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi;
    cout << "bi = ";
    bi.display();
    cout << endl;

    CDigit d('r');
    cout << "d = ";
    d.display();
    cout << endl;

    bi.insert2Right(d);
    cout << "bi = ";
    bi.display();
    cout << endl;

    CDigit d2('r');
    cout << "d2 = ";
    d2.display();
    cout << endl;

    bi.insert2Right(d2);
    cout << "bi = ";
    bi.display();
    cout << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CBigInt::insert2Right(CDigit x)
///////////////////////////////////////////////////////////
/*
p = address of new digit
copy into this digit coef and expo from x

if bigInt is empty then
    first = p
    last  = p
    count = 1
  else
    make new node point to last node
    make last node point to new node
    set last = p
    count++
  end if
*/
bool CBigInt::insert2Right(CDigit x)
  {
  CDigit *p;

  p = new CDigit;
  if (NULL == p)
    return false;

  p->_coef = x._coef;
  p->_expo = x._expo;

  if (NULL == this->_first)
    {
    this->_first = this->_last = p;
    this->_count = 1;
    }
  else
    {
    p->_prev = this->_last;
    this->_last->_next = p;
    this->_last = p;
    this->_count++;
    }

  return true;
  }


///////////////////////////////////////////////////////////
// void CBigInt::display(void) const
///////////////////////////////////////////////////////////
void CBigInt::display(void) const
  {
  int blanks = MAX_SIZE - this->_count + 1;
  while (blanks > 0)
    {
    blanks--;
    cout << ' ';
    }

  CDigit *p;

  p = _first;

  while (p!=NULL)
    {
    p->display();
    p = p->_next;
    }
  }


///////////////////////////////////////////////////////////
// void CBigInt::displayAll(void) const
///////////////////////////////////////////////////////////
/*
p = first
do while p<>null
  diplay the digit at p
  advance p
  end while
*/
void CBigInt::displayAll(void) const
  {
  CDigit *p;
  p = _first;
  while (p!=NULL)
    {
    p->displayAll();
    p = p->_next;
    cout << endl;
    }
  }


///////////////////////////////////////////////////////////
// void driverConstructorDefault_CBigInt(void)
///////////////////////////////////////////////////////////
void driverConstructorDefault_CBigInt(void)
  {
  cout << "--------------------------------\n";
  cout << "driverConstructorDefault_CBigInt\n";
  cout << "--------------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CBigInt bi;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CBigInt::CBigInt(void)
///////////////////////////////////////////////////////////
CBigInt::CBigInt(void)
  {
  this->init();
  }


///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
//*******************************************************//
//*******************************************************//
//*******************************************************//
//*******************************************************//
//*******************************************************//
//*******************************************************//
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////
// void driverOperatorLessThan_CDigit(void)
///////////////////////////////////////////////////////////
void driverOperatorLessThan_CDigit(void)
  {
  cout << "-----------------------------\n";
  cout << "driverOperatorLessThan_CDigit\n";
  cout << "-----------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CDigit d1('r');
    CDigit d2('r');
    CDigit d3(d1);

    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;
    cout << "d2="; d2.display(); cout << endl;
    cout << "d2="; d2.displayAll(); cout << endl;
    cout << "d3="; d3.display(); cout << endl;
    cout << "d3="; d3.displayAll(); cout << endl;

    cout << ((d1 < d2)? "d1 is less than d2\n": "d1 is NOT less than d2\n");
    cout << ((d1 < d3)? "d1 is less than d3\n": "d1 is NOT less than d3\n");
    cout << ((d2 < d3)? "d2 is less than d3\n": "d2 is NOT less than d3\n");

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CDigit::operator < (const CDigit &d2) const
///////////////////////////////////////////////////////////
/*
compares only the coef data member and not the expo
*/
bool CDigit::operator < (const CDigit &d2) const
  {
  return (this->_coef < d2._coef);
  }


///////////////////////////////////////////////////////////
// void driverConstructorIntExpo_CDigit(void)
///////////////////////////////////////////////////////////
void driverConstructorIntExpo_CDigit(void)
  {
  cout << "------------------------------\n";
  cout << "driverConstructorIntExpo_CDigit\n";
  cout << "------------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    unsigned int x = rand()%(MAX_VALUE+5-(MIN_VALUE)+1) + MIN_VALUE;
    unsigned int e = rand()%(MAX_EXPO+5);

    cout << "After CDigit d1(" << x << ", " << e << ");\n";

    CDigit d1(x, e);

    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CDigit::CDigit(unsigned int coef, unsigned int expo)
///////////////////////////////////////////////////////////
CDigit::CDigit(unsigned int coef, unsigned int expo)
  {
  if (coef<=MAX_VALUE && coef>=MIN_VALUE)
      _coef = coef;
    else if (coef>MAX_VALUE)
      _coef = MAX_VALUE;
    else if (coef<MIN_VALUE)
      _coef = MIN_VALUE;

  if (expo<=MAX_EXPO && expo>=0)
      _expo = expo;
    else if (expo<0)
      _expo = 0;
    else if (expo>MAX_EXPO)
      _expo = MAX_EXPO;

  this->init();
  }


///////////////////////////////////////////////////////////
// void driverConstructorInt_CDigit(void)
///////////////////////////////////////////////////////////
void driverConstructorInt_CDigit(void)
  {
  cout << "---------------------------\n";
  cout << "driverConstructorInt_CDigit\n";
  cout << "---------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    unsigned int x = rand()%(MAX_VALUE+5-(MIN_VALUE)+1) + MIN_VALUE;

    cout << "After CDigit d1(" << x << ");\n";

    CDigit d1(x);

    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// CDigit::CDigit(unsigned int coef)
///////////////////////////////////////////////////////////
CDigit::CDigit(unsigned int coef)
  {
  if (coef<=MAX_VALUE && coef>=MIN_VALUE)
      _coef = coef;
    else if (coef>MAX_VALUE)
      _coef = MAX_VALUE;
    else if (coef<MIN_VALUE)
      _coef = MIN_VALUE;

  _expo = 0;
  this->init();
  }


///////////////////////////////////////////////////////////
// void driverOperatorNotEqual_CDigit()
///////////////////////////////////////////////////////////
void driverOperatorNotEqual_CDigit()
  {
  cout << "-----------------------------\n";
  cout << "driverOperatorNotEqual_CDigit\n";
  cout << "-----------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CDigit d1('r');
    CDigit d2('r');
    CDigit d3(d1);

    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;
    cout << "d2="; d2.display(); cout << endl;
    cout << "d2="; d2.displayAll(); cout << endl;
    cout << "d3="; d3.display(); cout << endl;
    cout << "d3="; d3.displayAll(); cout << endl;

    if(d1 != d2)
      cout << "Digits d1 & d2 Are NOT Equal" << endl;
    else
      cout << "Digits d1 & d2 Are Equal" << endl;

    if(d1 != d3)
      cout << "Digits d1 & d3 Are NOT Equal" << endl;
    else
      cout << "Digits d1 & d3 Are Equal" << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CDigit::operator != (const CDigit &d2) const
///////////////////////////////////////////////////////////
bool CDigit::operator != (const CDigit &d2) const
  {
  //return !(this->_coef == d2._coef && this->_expo == d2._expo);
  return !(*this == d2);
  }


///////////////////////////////////////////////////////////
// void driverOperatorEqual_CDigit(void)
///////////////////////////////////////////////////////////
void driverOperatorEqual_CDigit(void)
  {
  cout << "--------------------------\n";
  cout << "driverOperatorEqual_CDigit\n";
  cout << "--------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CDigit d1('r');
    CDigit d2('r');
    CDigit d3(d1);

    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;
    cout << "d2="; d2.display(); cout << endl;
    cout << "d2="; d2.displayAll(); cout << endl;
    cout << "d3="; d3.display(); cout << endl;
    cout << "d3="; d3.displayAll(); cout << endl;

    if(d1 == d2)
      cout << "Digits d1 & d2 Are Equal" << endl;
    else
      cout << "Digits d1 & d2 Are NOT Equal" << endl;

    if(d1 == d3)
      cout << "Digits d1 & d3 Are Equal" << endl;
    else
      cout << "Digits d1 & d3 Are NOT Equal" << endl;

    cout << "......................." << endl;
    }
  }


///////////////////////////////////////////////////////////
// bool CDigit::operator == (const CDigit &d2) const
///////////////////////////////////////////////////////////
bool CDigit::operator == (const CDigit &d2) const
  {
  return (this->_coef == d2._coef && this->_expo == d2._expo);
  }


///////////////////////////////////////////////////////////
// void CDigit::init(void)
///////////////////////////////////////////////////////////
void CDigit::init(void)
  {
  this->_prev = NULL;
  this->_next = NULL;
  }


///////////////////////////////////////////////////////////
// void driverConstructorCopy_CDigit(void)
///////////////////////////////////////////////////////////
void driverConstructorCopy_CDigit(void)
  {
  cout << "----------------------------\n";
  cout << "driverConstructorCopy_CDigit\n";
  cout << "----------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CDigit d1('r');
    CDigit d2(d1);
    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;
    cout << "d2="; d2.display(); cout << endl;
    cout << "d2="; d2.displayAll(); cout << endl;
    cout << "...................\n";
    }
  }


///////////////////////////////////////////////////////////
// CDigit::CDigit(const CDigit &d2)
///////////////////////////////////////////////////////////
CDigit::CDigit(const CDigit &d2)
  {
  this->_coef = d2._coef;
  this->_expo = d2._expo;
  this->init();
  }


///////////////////////////////////////////////////////////
// void driverConstructorChar_CDigit(void)
///////////////////////////////////////////////////////////
void driverConstructorChar_CDigit(void)
  {
  cout << "----------------------------\n";
  cout << "driverConstructorChar_CDigit\n";
  cout << "----------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CDigit d1('r'), d2('r');
    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;
    cout << "d2="; d2.display(); cout << endl;
    cout << "d2="; d2.displayAll(); cout << endl;
    cout << "...................\n";
    }
  }


///////////////////////////////////////////////////////////
// CDigit::CDigit(char ch)
///////////////////////////////////////////////////////////
CDigit::CDigit(char ch)
  {
  if ('r'==ch || 'R'==ch)
      {
      this->_coef = rand()%(MAX_VALUE-MIN_VALUE+1)+MIN_VALUE;
      this->_expo = rand()%MAX_EXPO;
      this->init();
      }
    else
      {
      this->_coef = UNDEFINED;
      this->_expo = UNDEFINED;
      this->init();
      }
  }



///////////////////////////////////////////////////////////
// void driverConstructorDefault_CDigit(void)
///////////////////////////////////////////////////////////
void driverConstructorDefault_CDigit(void)
  {
  cout << "-------------------------------\n";
  cout << "driverConstructorDefault_CDigit\n";
  cout << "-------------------------------\n";
  for (int i=1; i<=TEST_COUNT; i++)
    {
    CDigit d1, d2;
    cout << "d1="; d1.display(); cout << endl;
    cout << "d1="; d1.displayAll(); cout << endl;
    cout << "d2="; d2.display(); cout << endl;
    cout << "d2="; d2.displayAll(); cout << endl;
    cout << "...................\n";
    }
  }


///////////////////////////////////////////////////////////
// void CDigit::displayAll(void) const
///////////////////////////////////////////////////////////
void CDigit::displayAll(void) const
  {
  cout << '@' << this << "=";
  cout << '[' << this->_prev << ' ';
  cout << this->_coef << ' ';
  cout << this->_expo << ' ';
  cout << this->_next << ']';
  }


///////////////////////////////////////////////////////////
// void CDigit::display(void) const
///////////////////////////////////////////////////////////
void CDigit::display(void) const
  {
  cout << this->_coef;
  }


///////////////////////////////////////////////////////////
// CDigit::CDigit(void)
///////////////////////////////////////////////////////////
CDigit::CDigit(void)
  {
  this->_coef = UNDEFINED;
  this->_expo = UNDEFINED;
  this->init();
  }