// CBigInt003.cpp
// 04/19/2004
// 04/21/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);
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);
};
void driver_CDigit_ConstructorDefault(void);
void driver_CBigInt_insertDigitToLeft(void);
void driver_CBigInt_insertDigitToRight(void);
void driver_CBigInt_Constructor_Rand(void);
void main(void)
{
srand(time(NULL));
//driver_CDigit_ConstructorDefault();
//driver_CBigInt_insertDigitToLeft();
//driver_CBigInt_insertDigitToRight();
driver_CBigInt_Constructor_Rand();
}
//////////////////////////////////////////////////////////////////////
// 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";
}
}
//////////////////////////////////////////////////////////////////////
// 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
// fully contained
// Algorithm0:
// initialize with zeros
// pick a spot randomly so that TEST_DATA[k] would be fully contained
// put the TEST_DATA[k] starting at that point
// Algorithm1:
// initialize with zeros
// k = random(0..TEST_DATA_COUNT-1)
// len = length of TEST_DATA[k]
// spot = rand(0..MAX_DIGITS-len-1]
// for i=0 to len-1 do
// digits[spot+i] = TEST_DATA[k][i]
// end do
/*
int k = rand()%TEST_DATA_COUNT;
//cout << " k = " << k << endl;
int len = strlen(TEST_DATA[k]);
//cout << " len = " << len << endl;
//cout << "from constructor CPosBigInt(char ch) " << TEST_DATA[k] << endl;
for (int j=0; j<=len-1; j++)
if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
return;
int spot = rand()%(MAX_DIGITS-len);
//cout << " spot = " << spot << endl;
for (int i=0; i<=len-1; i++)
_digits[spot+i] = TEST_DATA[k][i];
*/
}
}
//////////////////////////////////////////////////////////////////////
// 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)
{
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)
{
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)
{
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)
{
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)
{
this->initialize();
}
////////////////////////////////////////////////////
////////////////////////////////////////////////////
////////////////////////////////////////////////////
////////////////////////////////////////////////////
ostream & operator << (ostream &bob, const CDigit &d)
{
bob << d._digit;
return bob;
}
void driver_CDigit_ConstructorDefault(void)
{
CDigit d;
cout << d << endl;
}
CDigit::CDigit(void)
{
this->_prev = NULL;
this->_next = NULL;
this->_digit = 0;
}
/*
-------------------------------
driver_CBigInt_Constructor_Rand
-------------------------------
a=bigInt[12]=-225086846884
----------------------------------------------------
b=bigInt[7]=+1234506
----------------------------------------------------
a=bigInt[22]=-5010312076703956123050
----------------------------------------------------
b=bigInt[0]=?
----------------------------------------------------
a=bigInt[42]=-306564934930201592280038886260920079915734
----------------------------------------------------
b=bigInt[1]=-2
----------------------------------------------------
a=bigInt[22]=+0241815914905860267078
----------------------------------------------------
b=bigInt[1]=+0
----------------------------------------------------
a=bigInt[31]=-9619262001608002813394815117201
----------------------------------------------------
b=bigInt[0]=?
----------------------------------------------------
a=bigInt[30]=+167675013444033254978924603153
----------------------------------------------------
b=bigInt[2]=+12
----------------------------------------------------
a=bigInt[29]=+16204788885759040456980940421
----------------------------------------------------
b=bigInt[6]=+123450
----------------------------------------------------
a=bigInt[35]=-32439381511936320168512747960083249
----------------------------------------------------
b=bigInt[7]=+1234506
----------------------------------------------------
a=bigInt[13]=+5250967565607
----------------------------------------------------
b=bigInt[1]=+0
----------------------------------------------------
a=bigInt[32]=+34648537296518939794041853061507
----------------------------------------------------
b=bigInt[1]=+0
----------------------------------------------------
a=bigInt[2]=-27
----------------------------------------------------
b=bigInt[8]=+12345067
----------------------------------------------------
a=bigInt[30]=-534071116997637094560983860406
----------------------------------------------------
b=bigInt[2]=+12
----------------------------------------------------
a=bigInt[5]=-38308
----------------------------------------------------
b=bigInt[3]=+123
----------------------------------------------------
a=bigInt[19]=+9164182760332908224
----------------------------------------------------
b=bigInt[0]=?
----------------------------------------------------
a=bigInt[49]=-8966560733325479400369260415364335498699474087450
----------------------------------------------------
b=bigInt[1]=+1
----------------------------------------------------
a=bigInt[1]=-2
----------------------------------------------------
b=bigInt[3]=+999
----------------------------------------------------
a=bigInt[10]=+6204192830
----------------------------------------------------
b=bigInt[1]=-2
----------------------------------------------------
a=bigInt[38]=-77957478667536603354654936135414590375
----------------------------------------------------
b=bigInt[0]=?
----------------------------------------------------
a=bigInt[47]=+62436363280723338239845922401723431681545282154
----------------------------------------------------
b=bigInt[8]=+12345067
----------------------------------------------------
a=bigInt[15]=-108758477382756
----------------------------------------------------
b=bigInt[3]=+999
----------------------------------------------------
Press any key to continue
*/
|