// CBigInt004.cpp
// 04/26/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 = 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", "-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.27
public:
CBigInt(char d[]);
void display(void);
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);
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);
};
//////////////////////////////////////////////////////////////////////
// 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 main(void)
//////////////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//driver_CDigit_ConstructorDefault();
//driver_CBigInt_insertDigitToLeft();
//driver_CBigInt_insertDigitToRight();
//driver_CBigInt_Constructor_Rand();
driver_CBigInt_deleteFirstDigit();
}
//////////////////////////////////////////////////////////////////////
// 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 << "----------------------------------------------------\n";
CBigInt b('d');
cout << "b=" << b << endl;
b.deleteFirstDigit();
cout << "After b.deleteFirstDigit();\n";
cout << "b=" << b << endl;
cout << "----------------------------------------------------\n";
CBigInt c('z');
cout << "c=" << c << endl;
c.deleteFirstDigit();
cout << "After c.deleteFirstDigit();\n";
cout << "c=" << c << 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;
}
/*
-------------------------------
driver_CBigInt_deleteFirstDigit
-------------------------------
a=bigInt[29]=-42665902528450835602959532219
After a.deleteFirstDigit();
a=bigInt[28]=-2665902528450835602959532219
----------------------------------------------------
b=bigInt[3]=+123
After b.deleteFirstDigit();
b=bigInt[2]=+23
----------------------------------------------------
c=bigInt[0]=?
After c.deleteFirstDigit();
c=bigInt[0]=?
----------------------------------------------------
a=bigInt[29]=+40468274627686007975551186479
After a.deleteFirstDigit();
a=bigInt[28]=+0468274627686007975551186479
----------------------------------------------------
b=bigInt[7]=+1234506
After b.deleteFirstDigit();
b=bigInt[6]=+234506
----------------------------------------------------
c=bigInt[5]=+00100
After c.deleteFirstDigit();
c=bigInt[4]=+0100
----------------------------------------------------
a=bigInt[7]=-3261465
After a.deleteFirstDigit();
a=bigInt[6]=-261465
----------------------------------------------------
b=bigInt[0]=?
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[8]=+00000000
After c.deleteFirstDigit();
c=bigInt[7]=+0000000
----------------------------------------------------
a=bigInt[9]=-218586880
After a.deleteFirstDigit();
a=bigInt[8]=-18586880
----------------------------------------------------
b=bigInt[1]=-2
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[0]=?
After c.deleteFirstDigit();
c=bigInt[0]=?
----------------------------------------------------
a=bigInt[1]=-3
After a.deleteFirstDigit();
a=bigInt[0]=?
----------------------------------------------------
b=bigInt[3]=+999
After b.deleteFirstDigit();
b=bigInt[2]=+99
----------------------------------------------------
c=bigInt[13]=-0000000200000
After c.deleteFirstDigit();
c=bigInt[12]=-000000200000
----------------------------------------------------
a=bigInt[17]=-47361741041345761
After a.deleteFirstDigit();
a=bigInt[16]=-7361741041345761
----------------------------------------------------
b=bigInt[1]=+0
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[15]=+000000001200000
After c.deleteFirstDigit();
c=bigInt[14]=+00000001200000
----------------------------------------------------
a=bigInt[12]=-167762967283
After a.deleteFirstDigit();
a=bigInt[11]=-67762967283
----------------------------------------------------
b=bigInt[3]=+123
After b.deleteFirstDigit();
b=bigInt[2]=+23
----------------------------------------------------
c=bigInt[22]=+0000000001234506700000
After c.deleteFirstDigit();
c=bigInt[21]=+000000001234506700000
----------------------------------------------------
a=bigInt[36]=-184752897262090479220671729308678538
After a.deleteFirstDigit();
a=bigInt[35]=-84752897262090479220671729308678538
----------------------------------------------------
b=bigInt[0]=?
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[7]=+0000000
After c.deleteFirstDigit();
c=bigInt[6]=+000000
----------------------------------------------------
a=bigInt[26]=-02198359523847008348187769
After a.deleteFirstDigit();
a=bigInt[25]=-2198359523847008348187769
----------------------------------------------------
b=bigInt[1]=+0
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[9]=+000120000
After c.deleteFirstDigit();
c=bigInt[8]=+00120000
----------------------------------------------------
a=bigInt[37]=-2664947019504961046759914967496015333
After a.deleteFirstDigit();
a=bigInt[36]=-664947019504961046759914967496015333
----------------------------------------------------
b=bigInt[0]=?
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[14]=+00123450600000
After c.deleteFirstDigit();
c=bigInt[13]=+0123450600000
----------------------------------------------------
a=bigInt[17]=+06283017255335386
After a.deleteFirstDigit();
a=bigInt[16]=+6283017255335386
----------------------------------------------------
b=bigInt[7]=+1234506
After b.deleteFirstDigit();
b=bigInt[6]=+234506
----------------------------------------------------
c=bigInt[6]=+000100
After c.deleteFirstDigit();
c=bigInt[5]=+00100
----------------------------------------------------
a=bigInt[4]=-6335
After a.deleteFirstDigit();
a=bigInt[3]=-335
----------------------------------------------------
b=bigInt[1]=-2
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[11]=+00000000000
After c.deleteFirstDigit();
c=bigInt[10]=+0000000000
----------------------------------------------------
a=bigInt[15]=-175032701291766
After a.deleteFirstDigit();
a=bigInt[14]=-75032701291766
----------------------------------------------------
b=bigInt[1]=-2
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[16]=+0000123450600000
After c.deleteFirstDigit();
c=bigInt[15]=+000123450600000
----------------------------------------------------
a=bigInt[3]=+178
After a.deleteFirstDigit();
a=bigInt[2]=+78
----------------------------------------------------
b=bigInt[8]=+12345067
After b.deleteFirstDigit();
b=bigInt[7]=+2345067
----------------------------------------------------
c=bigInt[18]=+000000000123450670
After c.deleteFirstDigit();
c=bigInt[17]=+00000000123450670
----------------------------------------------------
a=bigInt[20]=+21556468121980138395
After a.deleteFirstDigit();
a=bigInt[19]=+1556468121980138395
----------------------------------------------------
b=bigInt[2]=+12
After b.deleteFirstDigit();
b=bigInt[1]=+2
----------------------------------------------------
c=bigInt[14]=+00000000012000
After c.deleteFirstDigit();
c=bigInt[13]=+0000000012000
----------------------------------------------------
a=bigInt[41]=-07690979047166650553781861279618671996473
After a.deleteFirstDigit();
a=bigInt[40]=-7690979047166650553781861279618671996473
----------------------------------------------------
b=bigInt[7]=+1234506
After b.deleteFirstDigit();
b=bigInt[6]=+234506
----------------------------------------------------
c=bigInt[14]=-00000002000000
After c.deleteFirstDigit();
c=bigInt[13]=-0000002000000
----------------------------------------------------
a=bigInt[25]=-5880232364592058212582968
After a.deleteFirstDigit();
a=bigInt[24]=-880232364592058212582968
----------------------------------------------------
b=bigInt[7]=+1234506
After b.deleteFirstDigit();
b=bigInt[6]=+234506
----------------------------------------------------
c=bigInt[7]=+1234000
After c.deleteFirstDigit();
c=bigInt[6]=+234000
----------------------------------------------------
a=bigInt[48]=+235324261780150249616975379241633406631109349199
After a.deleteFirstDigit();
a=bigInt[47]=+35324261780150249616975379241633406631109349199
----------------------------------------------------
b=bigInt[1]=+0
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[7]=+0999000
After c.deleteFirstDigit();
c=bigInt[6]=+999000
----------------------------------------------------
a=bigInt[8]=-31214323
After a.deleteFirstDigit();
a=bigInt[7]=-1214323
----------------------------------------------------
b=bigInt[1]=+0
After b.deleteFirstDigit();
b=bigInt[0]=?
----------------------------------------------------
c=bigInt[19]=+0000000001234000000
After c.deleteFirstDigit();
c=bigInt[18]=+000000001234000000
----------------------------------------------------
a=bigInt[22]=-8165825246201361660788
After a.deleteFirstDigit();
a=bigInt[21]=-165825246201361660788
----------------------------------------------------
b=bigInt[4]=+1234
After b.deleteFirstDigit();
b=bigInt[3]=+234
----------------------------------------------------
c=bigInt[7]=+0000000
After c.deleteFirstDigit();
c=bigInt[6]=+000000
----------------------------------------------------
Press any key to continue
*/
|