//Date: 2003.12.05
//File: bigInt11.cpp
//Author: AOU
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
/*********************************************************/
/* BEGIN WHAT IS NEW */
/*********************************************************/
/*
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 = 25;
///////////////////////////////////////////////////////////
//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 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);
///////////////////////////////////////////////////////////
//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);
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); //
CBigInt(const CBigInt &i2); //***
~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);
CBigInt & operator = (const CBigInt &i2); //***
bool operator == (const CBigInt &i2) const; //***
bool operator != (const CBigInt &i2) const;
bool operator < (const CBigInt &i2) const;
bool operator <= (const CBigInt &i2) const;
bool operator > (const CBigInt &i2) const;
bool operator >= (const CBigInt &i2) const;
CBigInt operator + (const CBigInt &i2) const; //***
CBigInt operator * (const CBigInt &i2) const; //***
CBigInt operator - (const CBigInt &i2) const;
CBigInt operator / (const CBigInt &i2) const;
friend ostream & operator << (ostream &bob, const CBigInt &bi);
bool hasDistinct(void) const;
bool deleteAtPos(int p);
};
///////////////////////////////////////////////////////////
//main
///////////////////////////////////////////////////////////
void main(void)
{
//srand(time(NULL));
//driverConstructorDefault_CBigInt();
//driverInsert2Right_CBigInt();
//driverConstructorN_CBigInt();
//driverConstructorCh_CBigInt();
//driverRemoveAll_CBigInt();
//driverPopulate_CBigInt();
//driverInsert2Left_CBigInt();
driverDestructor_CBigInt();
////////////////////////////////////
////////////////////////////////////
//driverConstructorDefault_CDigit();
//driverConstructorChar_CDigit();
//driverConstructorCopy_CDigit();
//driverOperatorEqual_CDigit();
//driverOperatorNotEqual_CDigit();
//driverConstructorInt_CDigit();
//driverConstructorIntExpo_CDigit();
}
///////////////////////////////////////////////////////////
// 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)
{
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++)
{
CBigInt bi(5);
cout << "bi = ";
bi.display();
cout << endl;
bi.displayAll();
cout << endl;
cout << "......................." << endl;
}
}
//creates a big integer with n digits
/*
for i=n-1 to 0 step -1
d = random digit with expo i
insert2Right d into bi
end for
*/
CBigInt::CBigInt(int n)
{
this->init();
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 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
{
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 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 driverOperatorEqual_CDigit()
{
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();
}
|