bigInt09
[ Home ] [ Up ]

//Date:   2003.12.01
//File:   bigInt09.cpp
//Author: AOU


///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>


/*********************************************************/
/* BEGIN WHAT IS NEW                                     */
/*********************************************************/
/*

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 driverInsert_CBigInt(void);
void driverConstructorN_CBigInt(void);
void driverConstructorCh_CBigInt(void);

void driverRemoveAll_CBigInt(void);
void driverPopulate_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);

    void display(void) const; //
    void displayAll(void) const; //
    void init(void); //
    bool insert(CDigit x); //
    int removeAll(void); //
    void populate(int n); //
    bool isSorted(void) const;
    void shuffle(void);
    void sortBubble(void);

    CBigInt & operator = (const CBigInt &i2);

    bool operator     ==  (const CBigInt &i2) const;//2003.11.10
    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();
  //driverInsert_CBigInt();
  //driverConstructorN_CBigInt();
  //driverConstructorCh_CBigInt();
  //driverRemoveAll_CBigInt();
  driverPopulate_CBigInt();

  ////////////////////////////////////
  ////////////////////////////////////

  //driverConstructorDefault_CDigit();

  //driverConstructorChar_CDigit();
  //driverConstructorCopy_CDigit();
  //driverOperatorEqual_CDigit();
  //driverOperatorNotEqual_CDigit();
  //driverConstructorInt_CDigit();
  //driverConstructorIntExpo_CDigit();
  }


///////////////////////////////////////////////////////////
// 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.displayAll();
    cout << endl;

    cout << "After populate " << endl;

    int n = rand()%MAX_SIZE;

    bi.populate(n);

    cout << "bi = ";
    bi.display();
    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->insert(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->insert(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
  insert 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->insert(d);
    }


  }

void CBigInt::init(void)
  {
  _first = NULL;
  _last  = NULL;
  _count = 0;
  }
///////////////////////////////////////////////////////////
// void driverInsert_CBigInt(void)
///////////////////////////////////////////////////////////
void driverInsert_CBigInt(void)
  {
  cout << "--------------------\n";
  cout << "driverInsert_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.insert(d);
    cout << "bi = ";
    bi.display();
    cout << endl;

    CDigit d2('r');
    cout << "d2 = ";
    d2.display();
    cout << endl;

    bi.insert(d2);
    cout << "bi = ";
    bi.display();
    cout << endl;
    cout << "......................." << endl;

    }

  }


///////////////////////////////////////////////////////////
// bool CBigInt::insert(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::insert(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();
  }