CBigInt008
[ Home ] [ Up ]

//  CBigInt008.cpp
//  05/03/2004
//  Author: AOU


//////////////////////////////////////////////////////////////////////
// include files
//////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>


//////////////////////////////////////////////////////////////////////
// constants
//////////////////////////////////////////////////////////////////////
const int MAX_DIGITS = 5;  //artificial limit
const int TEST_COUNT = 20;

const int BASE       = 10;

/*
const char *TEST_DATA[] =
  {
  "0", "1", "12", "123", "1234", "123450", "1234506", "12345067",
  "123450670", "1234506708", "1234506708", "Hello", "PSU",
  "9", "99", "999", "9999", "99999", "999999", "9999999",
  "10", "200", "3000", "40000", "500000", "6000000", "70000000",
  "800000000", "9000000000", "1090000000000", "11900000000000",
  "129000000000000", "1390000000000000", "14900000000000000"
  };
*/

const char *TEST_DATA[] =
  {
  "0", "+1", "-2", "12", "123", "1234", "123450", "1234506", "12345067",
  "+0", "++1", "+Hello", "999"
  };

const int TEST_DATA_COUNT = sizeof(TEST_DATA)/sizeof(TEST_DATA[0]);


//////////////////////////////////////////////////////////////////////
// class CDigit
//////////////////////////////////////////////////////////////////////
class CDigit
  {
  private:
    CDigit * _prev;
    CDigit * _next;
    char _digit;
  public:
    CDigit(void);
    CDigit(char d);
    friend class CBigInt;
    friend ostream & operator << (ostream &bob, const CDigit &d);
    friend ostream & operator << (ostream &bob, const CBigInt &bi);
  };


//////////////////////////////////////////////////////////////////////
// class CBigInt
//////////////////////////////////////////////////////////////////////
class CBigInt
  {
  private:
    CDigit * _first;
    CDigit * _last;
    char _sign;
    unsigned long int _size;
    void initialize(void);
  public:
    CBigInt(void);
    bool insertDigitToLeft(char d);     //2004.04.14
    bool insertDigitToRight(char d);    //2004.04.19
    friend ostream & operator << (ostream &bob, const CBigInt &bi);
    void displayR2L(void);
    CBigInt(char ch);
    bool deleteFirstDigit(void);        //2004.04.26
    bool deleteLastDigit(void);         //2004.04.28
    ~CBigInt(void);                     //2004.04.28

    void displayDetails(void);          //2005.05.02
    int deleteAllDigits(void);          //2004.05.02
    int populate(char ch);              //2004.05.02
    int populate(int n, char sign='+'); //2004.05.02

    void displayDetailsAll(void);       //2005.05.03

    int minimize(void);
    bool isValid(void);
    bool operator ==(const CBigInt &bi2);
    bool operator < (const CBigInt &bi2);
    bool operator <= (const CBigInt &bi2);
    bool operator >  (const CBigInt &bi2);
    bool operator >= (const CBigInt &bi2);
    bool operator != (const CBigInt &bi2);


    void displayMinimized(void);
    CBigInt(char d[]);
    void displayScientific(void);

    CBigInt(short int x); // [SHRT_MIN, SHRT_MAX] = [-32767,32767]
    CBigInt(unsigned short int x); // [0, USHRT_MAX] = [0, 65535]
    CBigInt(long int x);   // [LONG_MIN, LONG_MAX] = [-2147483647, 2147483647]
    CBigInt(unsigned long int x);  // [0, ULONG_MAX] = [0, 4294967295]

    void displayWithSeparatorForThousands(void);
    CBigInt(const CBigInt &bi);

    bool deleteLast(int d=1);
    bool deleteFirst(int d=1);

    CBigInt operator +(const CBigInt &y);
    CBigInt operator -(const CBigInt &y);
    CBigInt operator *(const CBigInt &y);
    CBigInt operator %(const CBigInt &y);
    CBigInt operator /(const CBigInt &y);
  };


//////////////////////////////////////////////////////////////////////
// driver function prototypes
//////////////////////////////////////////////////////////////////////
void driver_CDigit_ConstructorDefault(void);
void driver_CBigInt_insertDigitToLeft(void);
void driver_CBigInt_insertDigitToRight(void);
void driver_CBigInt_Constructor_Rand(void);

void driver_CBigInt_deleteFirstDigit(void);
void driver_CBigInt_deleteLastDigit(void);
void driver_CBigInt_destructor(void);

void driver_CBigInt_deleteAllDigits(void);
void driver_CBigInt_populate_Rand(void);
void driver_CBigInt_populate_n(void);


//////////////////////////////////////////////////////////////////////
// void main(void)
//////////////////////////////////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));
  //driver_CDigit_ConstructorDefault();
  //driver_CBigInt_insertDigitToLeft();
  //driver_CBigInt_insertDigitToRight();
  //driver_CBigInt_Constructor_Rand();
  //driver_CBigInt_deleteFirstDigit();
  //driver_CBigInt_deleteLastDigit();
  //driver_CBigInt_destructor();

  //driver_CBigInt_deleteAllDigits();
  //driver_CBigInt_populate_Rand();
  driver_CBigInt_populate_n();
  }


//////////////////////////////////////////////////////////////////////
// void CBigInt::displayDetailsAll(void)
//////////////////////////////////////////////////////////////////////
void CBigInt::displayDetailsAll(void)
  {
  cout << "Sign = " << this->_sign << endl;
  cout << "Size = " << this->_size << endl;
  cout << "first= " << this->_first << endl;
  cout << "last = " << this->_last << endl;

  cout << "First2Last  = \n";
  CDigit *p;
  p = this->_first;
  while (p != NULL)
    {
    cout << "@" << p;
    cout << "[" << p->_prev;
    cout << ", " << p->_digit;
    cout << ", " << p->_next;
    cout << "]\n";
    p = p->_next;
    }

  cout << endl;

  cout << "Last2First  = ";
  CDigit *q;
  q = this->_first;
  while (q != NULL)
    {
    cout << q->_digit << ' ';
    q = q->_next;
    }

  cout << endl;
  }



//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_populate_n(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_populate_n(void)
  {
  cout << "-------------------------\n";
  cout << "driver_CBigInt_populate_n\n";
  cout << "-------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CBigInt a;
    int n;

    n = -1;

    a.populate(n);
    cout << "After a.populate(" << n << ");\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '+');
    cout << "After a.populate(" << n << ", '+');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '-');
    cout << "After a.populate(" << n << ", '-');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '*');
    cout << "After a.populate(" << n << ", '*');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    n = 0;

    a.populate(n);
    cout << "After a.populate(" << n << ");\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '+');
    cout << "After a.populate(" << n << ", '+');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '-');
    cout << "After a.populate(" << n << ", '-');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '*');
    cout << "After a.populate(" << n << ", '*');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";
    
    n = rand()%TEST_COUNT;

    a.populate(n);
    cout << "After a.populate(" << n << ");\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '+');
    cout << "After a.populate(" << n << ", '+');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '-');
    cout << "After a.populate(" << n << ", '-');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";

    a.populate(n, '*');
    cout << "After a.populate(" << n << ", '*');\n";
    cout << "a=" << a << endl;
    a.displayDetails();
    a.displayDetailsAll();
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// int CBigInt::populate(int n, char sign)
//////////////////////////////////////////////////////////////////////
int CBigInt::populate(int n, char sign)
  {
  this->deleteAllDigits();

  //if ((!(sign == '+' || sign == '-')) || (n<=0))
  if ((sign != '+' && sign != '-') || (n<=0))
    {
    this->_sign = '?';
    return this->_size;
    }

  this->_sign = sign;

  for (int i=1; i<=n; i++)
    {
    char c;
    c = '0' + rand()%10;
    this->insertDigitToRight(c);
    }

  return this->_size;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_populate_Rand(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_populate_Rand(void)
  {
  cout << "----------------------------\n";
  cout << "driver_CBigInt_populate_Rand\n";
  cout << "----------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CBigInt a;
    a.populate('r');
    cout << "a=" << a << endl;
    a.displayDetails();
    cout << "----------------------------------------------------\n";

    CBigInt b;
    b.populate('d');
    cout << "b=" << b << endl;
    b.displayDetails();
    cout << "----------------------------------------------------\n";

    CBigInt c;
    c.populate('z');
    cout << "c=" << c << endl;
    c.displayDetails();
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// int CBigInt::populate(char ch)
//////////////////////////////////////////////////////////////////////
int CBigInt::populate(char ch)
  {
  this->deleteAllDigits();

  if ('r' == ch)
      {
      int digCount = 1 + rand()%(MAX_DIGITS);

      if (rand()%2 == 1)
          this->_sign = '+';
        else
          this->_sign = '-';

      for (int i=1; i<=digCount; i++)
        {
        char c;
        c = '0' + rand()%10;
        this->insertDigitToRight(c);
        }

      return this->_size;
      }

  if ('d' == ch)
    {
    int k   = rand()%TEST_DATA_COUNT;

    int len = strlen(TEST_DATA[k]);

    if ('+' == TEST_DATA[k][0] || '-' == TEST_DATA[k][0])
        {
        this->_sign = TEST_DATA[k][0];

        for (int j=1; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return this->_size;
            }

        for (int i=1; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);

        return this->_size;
        }
      else
        {
        this->_sign = '+';

        for (int j=0; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return this->_size;
            }

        for (int i=0; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);

        return this->_size;
        }

    }

  if ('z' == ch)
    {
    int k   = rand()%TEST_DATA_COUNT;

    int len = strlen(TEST_DATA[k]);

    if ('+' == TEST_DATA[k][0] || '-' == TEST_DATA[k][0])
        {
        this->_sign = TEST_DATA[k][0];

        for (int j=1; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return this->_size;
            }

        for (int i=1; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);

        return this->_size;
        }
      else
        {
        this->_sign = '+';

        for (int j=0; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return this->_size;
            }

        for (int i=0; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);

        return this->_size;
        }

    int zL = rand()%10;
    for (int i=1; i<=zL; i++)
      this->insertDigitToLeft('0');

    int zR = rand()%10;
    for (i=1; i<=zR; i++)
      this->insertDigitToRight('0');

    return this->_size;
    }

  return this->_size;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_deleteAllDigits(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_deleteAllDigits(void)
  {
  cout << "------------------------------\n";
  cout << "driver_CBigInt_deleteAllDigits\n";
  cout << "------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CBigInt *pa;
    pa = new CBigInt('d');
    cout << "*pa=" << *pa << endl;

    pa->displayDetails();
    pa->deleteAllDigits();

    cout << "\nAfter pa->deleteAllDigits();\n\n";

    cout << "*pa=" << *pa << endl;
    pa->displayDetails();

    delete pa;
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// int CBigInt::deleteAllDigits(void)
//////////////////////////////////////////////////////////////////////
int CBigInt::deleteAllDigits(void)
  {
  int n = 0;
  while (this->_first != NULL)
    {
    this->deleteLastDigit();
    n++;
    }

  this->_sign = '?';
  return n;
  }


//////////////////////////////////////////////////////////////////////
// void CBigInt::displayDetails(void)
//////////////////////////////////////////////////////////////////////
void CBigInt::displayDetails(void)
  {
  cout << "Sign = " << this->_sign << endl;
  cout << "Size = " << this->_size << endl;
  cout << "first= " << this->_first << endl;
  cout << "last = " << this->_last << endl;

  cout << "First2Last  = ";
  CDigit *p;
  p = this->_first;
  while (p != NULL)
    {
    cout << p->_digit << ' ';
    p = p->_next;
    }

  cout << endl;

  cout << "Last2First  = ";
  CDigit *q;
  q = this->_last;
  while (q != NULL)
    {
    cout << q->_digit << ' ';
    q = q->_prev;
    }

  cout << endl;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_destructor(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_destructor(void)
  {
  cout << "-------------------------\n";
  cout << "driver_CBigInt_destructor\n";
  cout << "-------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CBigInt *pa;
    pa = new CBigInt('d');
    cout << "*pa=" << *pa << endl;

    delete pa;
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// CBigInt::~CBigInt(void)
//////////////////////////////////////////////////////////////////////
/*
while there is a digit in this number
  delete it
*/
CBigInt::~CBigInt(void)
  {
  cout << "Destructor called ";
  int n = this->deleteAllDigits();
  cout << n << " digits destroyed\n";
  }


//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_deleteLastDigit(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_deleteLastDigit(void)
  {
  cout << "------------------------------\n";
  cout << "driver_CBigInt_deleteLastDigit\n";
  cout << "------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CBigInt a('r');
    cout << "a=" << a << endl;
    a.deleteLastDigit();
    cout << "After a.deleteLastDigit();\n";
    cout << "a=" << a << endl;
    cout << "a="; a.displayR2L(); cout << endl;
    cout << "----------------------------------------------------\n";

    CBigInt b('d');
    cout << "b=" << b << endl;
    b.deleteLastDigit();
    cout << "After b.deleteLastDigit();\n";
    cout << "b=" << b << endl;
    cout << "b="; b.displayR2L(); cout << endl;
    cout << "----------------------------------------------------\n";

    CBigInt c('z');
    cout << "c=" << c << endl;
    c.deleteLastDigit();
    cout << "After c.deleteLastDigit();\n";
    cout << "c=" << c << endl;
    cout << "c="; c.displayR2L(); cout << endl;
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CBigInt::deleteLastDigit(void)
//////////////////////////////////////////////////////////////////////
/*
Description:
  Deletes the last digit

Algorithm:
Possibilities:
size 0, 1, >1
if size = 0 then 
    return false
  else if size =1
    delete the digit
    first=last=null
    size=0
    sign=?
    return true
  else
    delete the last digit, and change pointers
    size--
    return true
  end if
\
*/
bool CBigInt::deleteLastDigit(void)
  {
  if (0==this->_size)
      return false;
    else if (1==this->_size)
      {
      delete this->_first;
      this->_first = this->_last = NULL;
      this->_size = 0;
      this->_sign = '?';
      return true;
      }
    else
      {
      CDigit *p;
      p = this->_last;
      this->_last = this->_last->_prev;
      this->_last->_next = NULL;
      delete p;
      this->_size--;
      return true;
      }
  }


//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_deleteFirstDigit(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_deleteFirstDigit(void)
  {
  cout << "-------------------------------\n";
  cout << "driver_CBigInt_deleteFirstDigit\n";
  cout << "-------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CBigInt a('r');
    cout << "a=" << a << endl;
    a.deleteFirstDigit();
    cout << "After a.deleteFirstDigit();\n";
    cout << "a=" << a << endl;
    cout << "a="; a.displayR2L(); cout << endl;
    cout << "----------------------------------------------------\n";

    CBigInt b('d');
    cout << "b=" << b << endl;
    b.deleteFirstDigit();
    cout << "After b.deleteFirstDigit();\n";
    cout << "b=" << b << endl;
    cout << "b="; b.displayR2L(); cout << endl;
    cout << "----------------------------------------------------\n";

    CBigInt c('z');
    cout << "c=" << c << endl;
    c.deleteFirstDigit();
    cout << "After c.deleteFirstDigit();\n";
    cout << "c=" << c << endl;
    cout << "c="; c.displayR2L(); cout << endl;
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CBigInt::deleteFirstDigit(void)
//////////////////////////////////////////////////////////////////////
/*
Description:
  Deletes the first digit

Algorithm:
Possibilities:
size 0, 1, >1
if size = 0 then 
    return false
  else if size =1
    delete the digit
    first=last=null
    size=0
    sign=?
    return true
  else
    delete the first digit, and change first
    size--
    return true
  end if
\
*/
bool CBigInt::deleteFirstDigit(void)
  {
  if (0==this->_size)
      return false;
    else if (1==this->_size)
      {
      delete this->_first;
      this->_first = this->_last = NULL;
      this->_size = 0;
      this->_sign = '?';
      return true;
      }
    else
      {
      CDigit *p;
      p = this->_first;
      this->_first = this->_first->_next;
      this->_first->_prev = NULL;
      delete p;
      this->_size--;
      return true;
      }
  }


//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_Constructor_Rand(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_Constructor_Rand(void)
  {
  cout << "-------------------------------\n";
  cout << "driver_CBigInt_Constructor_Rand\n";
  cout << "-------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CBigInt a('r');
    cout << "a=" << a << endl;
    cout << "----------------------------------------------------\n";

    CBigInt b('d');
    cout << "b=" << b << endl;
    cout << "----------------------------------------------------\n";

    CBigInt c('z');
    cout << "c=" << c << endl;
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(char ch)
//////////////////////////////////////////////////////////////////////
/*
Purpose:   A constructor to create a random big integer
Examples:  CPosBigInt x('r'); could give x=667621
Algorithm:
  initialize all digits with zeros
  set leadingZeros to a random number between 0 and MAX_DIGITS;
  do the following for i=leadingZeros to MAX_DIGITS-1
    d = random integer between 0 and 9
    c = random character betwwe '0' to '9' using d 
    digits[i] = c
    end do
*/
CBigInt::CBigInt(char ch)
  {
  this->initialize();

  if ('r' == ch)
      {
      int digCount = 1 + rand()%(MAX_DIGITS);

      if (rand()%2 == 1)
          this->_sign = '+';
        else
          this->_sign = '-';

      for (int i=1; i<=digCount; i++)
        {
        char c;
        c = '0' + rand()%10;
        this->insertDigitToRight(c);
        //_digits[i] = c;//insert to left or right
        }
      }

  if ('d' == ch)
    {
    int k   = rand()%TEST_DATA_COUNT;

    int len = strlen(TEST_DATA[k]);

    /*
    if the first character is sign then
        get the sign and process the rest of the digits
      else
        set the sign as +
        process all the digits
      end if

    */
    if ('+' == TEST_DATA[k][0] || '-' == TEST_DATA[k][0])
        {
        this->_sign = TEST_DATA[k][0];

        for (int j=1; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return;
            }

        for (int i=1; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);
        }
      else
        {
        this->_sign = '+';

        for (int j=0; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return;
            }

        for (int i=0; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);
        }

    }

  if ('z' == ch)
    {
    // create a random big integer from test data 
    // with lots of leading and trailing zeros
    // Algorithm0:
    //   initialize 
    //   k = random[0..TEST_DATA_COUNT)
    //   insert digits from TEST_DATA[k]
    //   insert random zeros to the left
    //   insert random zeros to the right

    int k   = rand()%TEST_DATA_COUNT;

    int len = strlen(TEST_DATA[k]);

    /*
    if the first character is sign then
        get the sign and process the rest of the digits
      else
        set the sign as +
        process all the digits
      end if

    */
    if ('+' == TEST_DATA[k][0] || '-' == TEST_DATA[k][0])
        {
        this->_sign = TEST_DATA[k][0];

        for (int j=1; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return;
            }

        for (int i=1; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);
        }
      else
        {
        this->_sign = '+';

        for (int j=0; j<=len-1; j++)
          if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
            {
            this->_sign = '?';
            return;
            }

        for (int i=0; i<=len-1; i++)
          this->insertDigitToRight(TEST_DATA[k][i]);
        }

    int zL = rand()%10;
    for (int i=1; i<=zL; i++)
      this->insertDigitToLeft('0');

    int zR = rand()%10;
    for (i=1; i<=zR; i++)
      this->insertDigitToRight('0');

    }
  }


//////////////////////////////////////////////////////////////////////
// void CBigInt::initialize(void)
//////////////////////////////////////////////////////////////////////
/*
Initializes a big integer with zeros
*/
void CBigInt::initialize(void)
  {
  this->_sign  = '?';
  this->_size  = 0;
  this->_first = NULL;
  this->_last  = NULL;
  }



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

    int k = rand()%TEST_COUNT;
    for (int j=1; j<=k; j++)
      {
      bi.insertDigitToRight('0'+rand()%10);
      cout << bi << endl;
      bi.displayR2L(); cout << endl;
      cout << endl;
      }
    cout << "--------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CBigInt::insertDigitToRight(char d)
//////////////////////////////////////////////////////////////////////
/*
Inserts a node based on digit d to the left
of big integer.
Examples:
  Given: "", 5 => "<-5->"
  Given: "<-5->", 6 => "<-5-><-6->"

Algorithm0:
  Create a node based on the value of d
  insert that node to the left
  update the size

Algorithm0:
  //Create a node based on the value of d
  p = new CDigit
  next of p = NULL
  digit at p = d

  //insert that node to the right
  if no digit in the big integer
      prev of p = NULL
      first = p
      last = p
    else
      prev of p is last
      next of last = p
      last = p

  update the size
    size++
*/
bool CBigInt::insertDigitToRight(char d)
  {
  CDigit * p;

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

  if ('?'==this->_sign)
    this->_sign = '+';//correction

  p->_next = NULL;
  p->_digit = d;

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

  return true;
  }


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

    int k = rand()%TEST_COUNT;
    for (int j=1; j<=k; j++)
      {
      bi.insertDigitToLeft('0'+rand()%10);
      cout << bi << endl;
      bi.displayR2L(); cout << endl;
      cout << endl;
      }
    cout << "--------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CBigInt::insertDigitToLeft(char d)
//////////////////////////////////////////////////////////////////////
/*
Inserts a node based on digit d to the left
of big integer.
Examples:
  Given: "", 5 => "<-5->"
  Given: "<-5->", 6 => "<-6-><-5->"

Algorithm0:
  Create a node based on the value of d
  insert that node to the left
  update the size

Algorithm0:
  //Create a node based on the value of d
  p = new CDigit
  prev of p = NULL
  digit at p = d

  //insert that node to the left
  if no digit in the big integer
      next of p = NULL
      first = p
      last = p
    else
      next of p is first
      first = p

  update the size
    size++
*/
bool CBigInt::insertDigitToLeft(char d)
  {
  CDigit * p;

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

  p->_prev = NULL;
  p->_digit = d;

  if (this->_size == 0)
      {
      this->_sign = '+';
      p->_next = NULL;
      this->_first = p;
      this->_last = p;
      this->_size = 1;
     }
    else
      {
      p->_next = this->_first;
      this->_first->_prev = p;
      this->_first = p;
      this->_size++;
      }

  return true;
  }


//////////////////////////////////////////////////////////////////////
// void CBigInt::displayR2L(void)
//////////////////////////////////////////////////////////////////////
void CBigInt::displayR2L(void)
  {
  CDigit *p;

  cout << "bigInt[" << this->_size << "]=";


  p = this->_last;
  while (p != NULL)
    {
    cout << p->_digit;
    p = p->_prev;
    }
  
  cout << this->_sign;

  }


//////////////////////////////////////////////////////////////////////
// ostream & operator << (ostream &bob, const CBigInt &bi)
//////////////////////////////////////////////////////////////////////
ostream & operator << (ostream &bob, const CBigInt &bi)
  {
  CDigit *p;

  bob << "bigInt[" << bi._size << "]=";

  bob << bi._sign;

  p = bi._first;
  while (p != NULL)
    {
    bob << p->_digit;
    p = p->_next;
    }
  
  return bob;
  }


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


////////////////////////////////////////////////////
////////////////////////////////////////////////////
////////////////////////////////////////////////////
// ostream & operator << (ostream &bob, const CDigit &d)
////////////////////////////////////////////////////
ostream & operator << (ostream &bob, const CDigit &d)
  {
  bob << d._digit;
  return bob;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CDigit_ConstructorDefault(void)
//////////////////////////////////////////////////////////////////////
void driver_CDigit_ConstructorDefault(void)
  {
  CDigit d;
  cout << d << endl;
  }


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

/*
*/