// CBigInt002.cpp
// 04/12/2004
// Author: AOU
//////////////////////////////////////////////////////////////////////
// include files
//////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
//////////////////////////////////////////////////////////////////////
// constants
//////////////////////////////////////////////////////////////////////
const int MAX_DIGITS = 50; //artificial limit
const int TEST_COUNT = 20;
/*
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", "12", "123", "1234", "123450", "1234506", "12345067"
};
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:
bool insertDigitToLeft(char d);
//bool insertDigitToRight(??);
public:
CBigInt(void);
void display(void);
CBigInt(char d[]);
CBigInt(char code);
void displayMinimized(void);
bool shiftLeft(void);
friend void add(CBigInt x, CBigInt y, CBigInt &z);
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);
friend ostream & operator << (ostream &bob, const CBigInt &bi);
CBigInt(const CBigInt &bi);
friend bool isEqual(const CBigInt &bi1, const CBigInt &bi2);
bool isEqual(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);
bool operator != (const CBigInt &bi2);
bool shiftRight(void);
bool shiftRight(int d);
bool shiftLeft(int d);
CBigInt add(const CBigInt &y);
CBigInt operator +(const CBigInt &y);
};
void driver_CDigit_ConstructorDefault(void);
void driver_CBigInt_insertDigitToLeft(void);
void main(void)
{
driver_CBigInt_insertDigitToLeft();
}
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;
int k = rand()%TEST_COUNT;
for (int j=1; j<=k; j++)
{
bi.insertDigitToLeft('0'+rand()%10);
cout << bi;
}
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;
}
else
{
p->_next = NULL;
p->_next = this->_first;
this->_first = p;
}
this->_size++;
return true;
}
ostream & operator << (ostream &bob, const CBigInt &bi)
{
CDigit *p;
bob << "bigInt[" << bi._size << "]=";
bob << bi._sign;
p = bi._first;
while (p!= NULL)
{
cout << p->_digit;
p = p->_next;
}
bob << endl;
return bob;
}
CBigInt::CBigInt(void)
{
this->_first = NULL;
this->_last = NULL;
this->_size = 0;
this->_sign = '?';
}
////////////////////////////////////////////////////
////////////////////////////////////////////////////
////////////////////////////////////////////////////
////////////////////////////////////////////////////
ostream & operator << (ostream &bob, const CDigit &d)
{
bob << d._digit;
return bob;
}
void driver_CDigit_ConstructorDefault(void)
{
CDigit d;
}
CDigit::CDigit(void)
{
_prev = NULL;
_next = NULL;
_digit = 0;
}
/*
--------------------------------
driver_CBigInt_insertDigitToLeft
--------------------------------
bigInt[0]=?
bigInt[1]=+7
--------------------------------
bigInt[0]=?
bigInt[1]=+0
bigInt[2]=+90
bigInt[3]=+490
bigInt[4]=+8490
bigInt[5]=+88490
bigInt[6]=+288490
bigInt[7]=+4288490
bigInt[8]=+54288490
bigInt[9]=+554288490
bigInt[10]=+1554288490
bigInt[11]=+71554288490
bigInt[12]=+171554288490
bigInt[13]=+1171554288490
bigInt[14]=+51171554288490
--------------------------------
bigInt[0]=?
bigInt[1]=+7
bigInt[2]=+67
--------------------------------
bigInt[0]=?
bigInt[1]=+4
bigInt[2]=+24
bigInt[3]=+324
bigInt[4]=+2324
bigInt[5]=+22324
bigInt[6]=+122324
bigInt[7]=+6122324
bigInt[8]=+86122324
bigInt[9]=+586122324
bigInt[10]=+7586122324
bigInt[11]=+67586122324
--------------------------------
bigInt[0]=?
bigInt[1]=+8
bigInt[2]=+98
bigInt[3]=+298
bigInt[4]=+7298
bigInt[5]=+97298
bigInt[6]=+597298
bigInt[7]=+4597298
bigInt[8]=+34597298
bigInt[9]=+134597298
bigInt[10]=+2134597298
bigInt[11]=+32134597298
--------------------------------
bigInt[0]=?
bigInt[1]=+4
bigInt[2]=+14
bigInt[3]=+114
bigInt[4]=+3114
bigInt[5]=+83114
bigInt[6]=+783114
bigInt[7]=+4783114
bigInt[8]=+24783114
bigInt[9]=+724783114
bigInt[10]=+7724783114
bigInt[11]=+97724783114
bigInt[12]=+397724783114
bigInt[13]=+1397724783114
--------------------------------
bigInt[0]=?
bigInt[1]=+8
bigInt[2]=+68
bigInt[3]=+568
bigInt[4]=+0568
bigInt[5]=+20568
bigInt[6]=+820568
bigInt[7]=+6820568
bigInt[8]=+06820568
bigInt[9]=+206820568
--------------------------------
bigInt[0]=?
bigInt[1]=+8
bigInt[2]=+68
bigInt[3]=+568
bigInt[4]=+0568
--------------------------------
bigInt[0]=?
bigInt[1]=+0
bigInt[2]=+00
bigInt[3]=+600
bigInt[4]=+1600
bigInt[5]=+31600
bigInt[6]=+831600
bigInt[7]=+9831600
bigInt[8]=+39831600
bigInt[9]=+439831600
--------------------------------
bigInt[0]=?
bigInt[1]=+6
bigInt[2]=+06
bigInt[3]=+606
bigInt[4]=+6606
bigInt[5]=+16606
bigInt[6]=+816606
bigInt[7]=+4816606
bigInt[8]=+94816606
bigInt[9]=+694816606
bigInt[10]=+3694816606
bigInt[11]=+73694816606
bigInt[12]=+873694816606
bigInt[13]=+8873694816606
bigInt[14]=+28873694816606
--------------------------------
bigInt[0]=?
bigInt[1]=+1
bigInt[2]=+31
bigInt[3]=+531
bigInt[4]=+9531
bigInt[5]=+89531
bigInt[6]=+489531
bigInt[7]=+0489531
bigInt[8]=+70489531
bigInt[9]=+670489531
--------------------------------
bigInt[0]=?
bigInt[1]=+6
bigInt[2]=+16
bigInt[3]=+516
bigInt[4]=+4516
bigInt[5]=+24516
bigInt[6]=+024516
bigInt[7]=+9024516
bigInt[8]=+79024516
bigInt[9]=+379024516
bigInt[10]=+7379024516
bigInt[11]=+27379024516
bigInt[12]=+627379024516
bigInt[13]=+0627379024516
--------------------------------
bigInt[0]=?
bigInt[1]=+6
--------------------------------
bigInt[0]=?
bigInt[1]=+7
bigInt[2]=+57
bigInt[3]=+457
bigInt[4]=+1457
bigInt[5]=+21457
bigInt[6]=+021457
bigInt[7]=+0021457
bigInt[8]=+10021457
bigInt[9]=+410021457
bigInt[10]=+6410021457
bigInt[11]=+06410021457
bigInt[12]=+706410021457
bigInt[13]=+1706410021457
bigInt[14]=+71706410021457
bigInt[15]=+771706410021457
--------------------------------
bigInt[0]=?
bigInt[1]=+7
bigInt[2]=+37
bigInt[3]=+337
bigInt[4]=+5337
bigInt[5]=+95337
bigInt[6]=+995337
bigInt[7]=+8995337
bigInt[8]=+18995337
bigInt[9]=+818995337
bigInt[10]=+2818995337
bigInt[11]=+62818995337
bigInt[12]=+662818995337
bigInt[13]=+0662818995337
bigInt[14]=+30662818995337
bigInt[15]=+830662818995337
bigInt[16]=+0830662818995337
bigInt[17]=+10830662818995337
--------------------------------
bigInt[0]=?
bigInt[1]=+5
bigInt[2]=+05
--------------------------------
bigInt[0]=?
bigInt[1]=+4
bigInt[2]=+74
bigInt[3]=+874
bigInt[4]=+3874
bigInt[5]=+53874
bigInt[6]=+153874
bigInt[7]=+2153874
bigInt[8]=+02153874
bigInt[9]=+102153874
bigInt[10]=+6102153874
bigInt[11]=+46102153874
bigInt[12]=+046102153874
bigInt[13]=+6046102153874
bigInt[14]=+16046102153874
bigInt[15]=+816046102153874
bigInt[16]=+9816046102153874
bigInt[17]=+89816046102153874
bigInt[18]=+489816046102153874
bigInt[19]=+1489816046102153874
--------------------------------
bigInt[0]=?
bigInt[1]=+3
bigInt[2]=+93
bigInt[3]=+893
bigInt[4]=+8893
bigInt[5]=+08893
bigInt[6]=+808893
bigInt[7]=+7808893
bigInt[8]=+77808893
bigInt[9]=+877808893
bigInt[10]=+3877808893
bigInt[11]=+83877808893
bigInt[12]=+383877808893
bigInt[13]=+7383877808893
bigInt[14]=+17383877808893
--------------------------------
bigInt[0]=?
bigInt[1]=+7
bigInt[2]=+37
bigInt[3]=+437
bigInt[4]=+9437
bigInt[5]=+69437
bigInt[6]=+569437
bigInt[7]=+1569437
bigInt[8]=+01569437
bigInt[9]=+901569437
bigInt[10]=+9901569437
--------------------------------
bigInt[0]=?
bigInt[1]=+8
bigInt[2]=+38
bigInt[3]=+438
bigInt[4]=+8438
bigInt[5]=+48438
bigInt[6]=+948438
bigInt[7]=+9948438
bigInt[8]=+29948438
bigInt[9]=+529948438
bigInt[10]=+5529948438
bigInt[11]=+35529948438
bigInt[12]=+335529948438
bigInt[13]=+3335529948438
bigInt[14]=+73335529948438
bigInt[15]=+473335529948438
bigInt[16]=+3473335529948438
--------------------------------
Press any key to continue
*/
|