DSortedList07
[ Home ] [ Up ]

//DSortedList07.cpp
//date: 11/18/2002
//author: AOU

//Project#6 Due 11/20/2002

//Dynamic sorted list

////////////////////////////////////////////////////////////
// Include files
////////////////////////////////////////////////////////////
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>


////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
const int MAX_SIZE    = 20; //maximum entries allowed in a list
const int UNDEFINED   = -9999;
const int MAX_VALUE   = 50;
const int TEST_COUNT  = 20;

const int INFINITY    = 32000;


void testInsert(void);
void testConstructorN(void);
void testConstructorChar(void);
void testRemoveAll(void);
void testDestructor(void);

void testAdd(void);  //project#6  Due 11/20/2002
void testDisplayRev(void);

void testShuffle(void);

const int sValues[] = {55, 12, 34, 71, 98, 45, 20};
const int S_SIZE = sizeof(sValues)/sizeof(sValues[0]);

 
////////////////////////////////////////////////////////////
//class CNode
////////////////////////////////////////////////////////////
class CNode
  {
  private:
    int m_key;
    // int age;
    // char name[20];
    // char socsec[10];
    CNode *m_next;
  public:
    CNode(void);        //2002.10.30
    void display(void); //2002.10.30
    CNode(int x);       //2002.11.04
    CNode(char ch);     //2002.11.04
    //...
  friend class CDSortedList;

  friend ostream & operator <<                  //2002.11.13
    (ostream & bob, const CDSortedList &aList); 

  friend ostream & operator <<                  //2002.11.15
    (ostream & bob, const CNode &aNode); 

  };


////////////////////////////////////////////////////////////
//class CDSortedList
////////////////////////////////////////////////////////////
class CDSortedList
  {
  private:
    int m_count;
    CNode *m_first;
    void init(void);  //should only be called by a constructor
  public:
    CDSortedList(void);   //2002.10.30
    void display(void);   //2002.10.30
    bool insert(int x);   //2002.11.04

    CDSortedList(int n);  //2002.11.06
    CDSortedList(char ch);//2002.11.06
    void removeAll(void); //2002.11.08 all except dummy values
    ~CDSortedList(void);  //2002.11.08

    //project#6 Due 11/20/2002
    //Submit well-documented source code and the output
    //The resulting list should be sorted with unique values
    friend void add(const CDSortedList &aList, 
      const CDSortedList &bList, CDSortedList &cList);

    friend ostream & operator <<                  //2002.11.13
      (ostream & bob, const CDSortedList &aList); 

    CNode* addByPos(int pos); //2002.11.15
    void displayRev(void);                        // 2002.11.15
    void shuffle(void);                           // 2002.11.18
    void analyze(void);                           // 2002.11.18
  };


////////////////////////////////////////////////////////////
//void main(void)
////////////////////////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));
  // testInsert();
  //testConstructorN();
  //testConstructorChar();
  //testRemoveAll();
  //testDestructor();
  //testAdd();
  // testDisplayRev();
  testShuffle();
  }


////////////////////////////////////////////////////////////
// void CDSortedList::analyze(void)
////////////////////////////////////////////////////////////
void CDSortedList::analyze(void)
  {
  int countUp=0, countDn=0, countEq=0;

  for (int i=0; i<this->m_count-1; i++)
    {
    CNode *p1, *p2;
    p1 = this->addByPos(i);
    p2 = this->addByPos(i+1);

    if (p1->m_key < p2->m_key) countUp++;
    if (p1->m_key > p2->m_key) countDn++;
    if (p1->m_key == p2->m_key) countEq++;
    }

  cout << "Count Up = " << countUp << endl;
  cout << "Count Dn = " << countDn << endl;
  cout << "Count Eq = " << countEq << endl;
  }


////////////////////////////////////////////////////////////
// void CDSortedList::shuffle(void)
////////////////////////////////////////////////////////////
void CDSortedList::shuffle(void)
  {
  /*
  do the following count*100 times
    randomly pick two elements
    swap their values
  */
  for (int i=0; i<this->m_count*100; i++)
    {
    int pos1, pos2;
    pos1 = rand()%this->m_count;
    pos2 = rand()%this->m_count;

    CNode *p1, *p2;
    p1 = this->addByPos(pos1);
    p2 = this->addByPos(pos2);

    int temp = p1->m_key;
    p1->m_key = p2->m_key;
    p2->m_key = temp;
    }
  }


////////////////////////////////////////////////////////////
// void testShuffle(void)
////////////////////////////////////////////////////////////
void testShuffle(void)
  {
  cout << "testShuffle\n";
  cout << "===========\n";

  for (int i=0; i<TEST_COUNT; i++)
    {
    CDSortedList* myListPtr = new CDSortedList('r');

    cout << *myListPtr;

    myListPtr->analyze();

    cout << "After shuffle\n";

    myListPtr->shuffle();

    cout << *myListPtr;

    myListPtr->analyze();

    delete myListPtr;
    cout << "------------------------\n";
    }
  }


////////////////////////////////////////////////////////////
// void CDSortedList::displayRev(void)
////////////////////////////////////////////////////////////
void CDSortedList::displayRev(void)
  {
  cout << "SortedRevr[" << this->m_count << "]= ";

  for (int i = this->m_count-1; i>=0; i--)
    {
    CNode *q = this->addByPos(i);
    cout << *q;
    }

  cout << endl;
  }
 

////////////////////////////////////////////////////////////
// void testDisplayRev(void)
////////////////////////////////////////////////////////////
void testDisplayRev(void)
  {
  for (int i=0; i<TEST_COUNT; i++)
    {
    CDSortedList myList('r');
    cout << myList;
    myList.displayRev();
    cout << "------------------------\n";
    }
  }


////////////////////////////////////////////////////////////
// CNode* CDSortedList::addByPos(int pos)
////////////////////////////////////////////////////////////
CNode* CDSortedList::addByPos(int pos)
  {
  /*
  Possibilities:
    Empty list
    pos < 0
    pos >= m_count
    pos >=0 and pos <m_count 
  */
  if (this->m_count == 0)
    return NULL;

  if (pos < 0)
    return NULL;

  if (pos >= this->m_count)
    return NULL;

  CNode *p;

  p = this->m_first->m_next;

  while (pos > 0)
    {
    pos--;
    p = p->m_next;
    }

  return p;
  }


////////////////////////////////////////////////////////////
// add
////////////////////////////////////////////////////////////
void add(const CDSortedList &aList, 
  const CDSortedList &bList, CDSortedList &cList)
  {
  //put in c distinct values from a and b
  //a={1, 3, 5, 5}, b={3, 3, 4, 6, 6} then
  //c={1, 3, 4, 5, 6}

  cout << "NOT IMPLEMENTED\n";
  }


////////////////////////////////////////////////////////////
// testAdd
////////////////////////////////////////////////////////////
void testAdd(void)
  {
  cout << "testAdd\n";
  cout << "-------\n";

  int m1 = rand()%(MAX_SIZE/2);
  int m2 = rand()%(MAX_SIZE/2);

  for (int i=0; i<TEST_COUNT; i++)
    {
    CDSortedList aL(m1), bL(m2), cL('r');
    cout << "aL = " << aL;
    cout << "bL = " << bL;
    cout << "cL = " << cL;
    
    add(aL, bL, cL);
    cout << "After add(aL, bL, cL);\n";

    cout << "aL = " << aL;
    cout << "bL = " << bL;
    cout << "cL = " << cL;

    cout <<"=================\n";
    }
  }


////////////////////////////////////////////////////////////
// operator <<
////////////////////////////////////////////////////////////
ostream & operator << (ostream & bob, const CNode &aNode)
  {
  bob << aNode.m_key << ' ';

  return bob;
  }


////////////////////////////////////////////////////////////
// operator <<
////////////////////////////////////////////////////////////
ostream & operator << (ostream & bob, const CDSortedList &aList)
  {
  bob << "SortedList[" << aList.m_count << "]= ";

  CNode *p;

  p = aList.m_first->m_next;

  while (p->m_next != NULL)
    {
    bob << *p;
    p = p->m_next;
    }

  bob << endl;

  return bob;
  }


////////////////////////////////////////////////////////////
// CDSortedList::~CDSortedList(void)
////////////////////////////////////////////////////////////
CDSortedList::~CDSortedList(void)
  {
  cout << "Destructor was called\n";
  CNode *cia1, *cia2;

  cia1 = this->m_first;

  while (cia1 != NULL)
    {
    cia2 = cia1->m_next;
    delete cia1;
    cia1 = cia2;
    }
  }


////////////////////////////////////////////////////////////
// void testDestructor(void)
////////////////////////////////////////////////////////////
void testDestructor(void)
  {
  cout << "testDestructor\n";
  cout << "==============\n";

  CDSortedList *mp1 = new CDSortedList('c');
  mp1->display();
  delete mp1;

  cout << "-----------------\n";

  for (int i=0; i<TEST_COUNT; i++)
    {
    CDSortedList *mp1 = new CDSortedList('r');
    mp1->display();
    delete mp1;
    cout << "-----------------\n";
    }
  }


////////////////////////////////////////////////////////////
// void CDSortedList::removeAll(void)
////////////////////////////////////////////////////////////
void CDSortedList::removeAll(void)
  {
  CNode *cia1, *cia2;

  cia1 = this->m_first;

  while (cia1 != NULL)
    {
    cia2 = cia1->m_next;
    delete cia1;
    cia1 = cia2;
    }

  this->init();
  }


////////////////////////////////////////////////////////////
// void testRemoveAll(void)
////////////////////////////////////////////////////////////
void testRemoveAll(void)
  {
  cout << "testRemoveAll\n";
  cout << "=============\n";

  CDSortedList myList('c');
  myList.display();
  myList.removeAll();
  myList.display();

  cout << "-----------------\n";

  for (int i=0; i<TEST_COUNT; i++)
    {
    CDSortedList myList('r');
    myList.display();
    myList.removeAll();
    myList.display();
    cout << "-----------------\n";
    }
  }


////////////////////////////////////////////////////////////
// void CDSortedList::init(void)
////////////////////////////////////////////////////////////
void CDSortedList::init(void)
  {
  CNode *p1 = new CNode;
  CNode *p2 = new CNode;

  this->m_first = p1;
  p1->m_next = p2;
  p2->m_next = NULL;

  p1->m_key = -INFINITY;
  p2->m_key = +INFINITY;

  this->m_count = 0;
  }


////////////////////////////////////////////////////////////
// CDSortedList::CDSortedList(char ch)
////////////////////////////////////////////////////////////
CDSortedList::CDSortedList(char ch)
  {
  this->init();

  if (('r' == ch) || ('R' == ch))
    {
    //insert random number of random values to the list
    int n = rand()%(MAX_SIZE+1);

    for (int i=0; i<n; i++)
      this->insert(rand()%(MAX_VALUE+1));
    }

  if (('c' == ch) || ('C' == ch))
    {
    //insert random number of random values to the list

    for (int i=0; i<S_SIZE; i++)
      this->insert(sValues[i]);
    }

  }


////////////////////////////////////////////////////////////
// void testConstructorChar(void)
////////////////////////////////////////////////////////////
void testConstructorChar(void)
  {
  cout << "testConstructorChar\n";
  cout << "===================\n";

  CDSortedList myList('c');
  myList.display();
  cout << "-----------------\n";

  for (int i=0; i<TEST_COUNT; i++)
    {
    CDSortedList myList('r');
    myList.display();
    cout << "-----------------\n";
    }
  }


////////////////////////////////////////////////////////////
// CDSortedList::CDSortedList(int n)
////////////////////////////////////////////////////////////
CDSortedList::CDSortedList(int n)
  {
  this->init();

  //insert n random values to the list
  for (int i=0; i<n; i++)
    this->insert(rand()%(MAX_VALUE+1));

  }


////////////////////////////////////////////////////////////
// void testConstructorN(void)
////////////////////////////////////////////////////////////
void testConstructorN(void)
  {
  cout << "testConstructorN\n";
  cout << "================\n";

  for (int i=0; i<TEST_COUNT; i++)
    {
    CDSortedList myList(rand()%MAX_SIZE);
    myList.display();
    }
  }


////////////////////////////////////////////////////////////
// bool CDSortedList::insert(int x)
////////////////////////////////////////////////////////////
bool CDSortedList::insert(int x)
  {
  if (this->m_count >= MAX_SIZE)
    return false;

  CNode *p, *p1, *p2;

  p = new CNode(x);
  if (NULL == p) 
    return false;

  p1 = this->m_first;
  p2 = p1->m_next;

  while(true)
    {
    if ((x >= p1->m_key) && (x <= p2->m_key))
      {
      p1->m_next = p;
      p->m_next = p2;
      this->m_count++;
      return true;
      }
    else
      {
      p1 = p1->m_next;
      p2 = p1->m_next;
      }
    }
  }

void testInsert(void)
  {
  cout << "testInsert\n";
  cout << "==========\n";

  CDSortedList myList;
  myList.display();

  for (int i=0; i<10; i++)
    {
    int x = rand()%MAX_VALUE;
    myList.insert(x);
    cout << "After inserting " << x << endl;
    myList.display();
    }
  }


////////////////////////////////////////////////////////////
//void CDSortedList::display(void)
////////////////////////////////////////////////////////////
void CDSortedList::display(void)
  {
  cout << "List[" << this->m_count << "] = \n";
  CNode *p;

  p = this->m_first;

  while (p != NULL)
    {
    p->display();
    p = p->m_next;
    cout << endl;
    }

  cout << endl;
  }


////////////////////////////////////////////////////////////
//CDSortedList::CDSortedList(void)
////////////////////////////////////////////////////////////
CDSortedList::CDSortedList(void)
  {
  /*
  create two nodes 
    one pointed to by p1, 
    other pointed to by p2

  make first point to p1
  make p1 point to p2
  make p2 point to nothing

  put -infin in p1 node
  put +infin in p2 node

  set count = 0
  */
  this->init();
  }


////////////////////////////////////////////////////////////
// CNode::CNode(char ch)
////////////////////////////////////////////////////////////
CNode::CNode(char ch)
  {
  if (('r' == ch) || ('R' == ch))
      {
      this->m_key = rand()%(MAX_VALUE+1);
      this->m_next = NULL;
      }
    else
      {
      this->m_key = UNDEFINED;
      this->m_next = NULL;
      }
  }


////////////////////////////////////////////////////////////
// CNode::CNode(int x)
////////////////////////////////////////////////////////////
CNode::CNode(int x)
  {
  this->m_key = x;
  this->m_next = NULL;
  }


////////////////////////////////////////////////////////////
//CNode::CNode(void)
////////////////////////////////////////////////////////////
CNode::CNode(void)
  {
  this->m_key = UNDEFINED;
  this->m_next = NULL;
  }


////////////////////////////////////////////////////////////
//void CNode::display(void)
////////////////////////////////////////////////////////////
void CNode::display(void)
  {
  //cout << "["; 
  //cout << this << " "; 
  cout << this->m_key << " "; 
  //cout << this->m_next << "] ";
  }


/*
SAMPLE RUN:
testShuffle
===========
SortedList[6]= 9 32 32 34 40 45
Count Up = 4
Count Dn = 0
Count Eq = 1
After shuffle
SortedList[6]= 34 9 32 32 45 40
Count Up = 2
Count Dn = 2
Count Eq = 1
Destructor was called
------------------------
SortedList[2]= 10 39
Count Up = 1
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[2]= 39 10
Count Up = 0
Count Dn = 1
Count Eq = 0
Destructor was called
------------------------
SortedList[18]= 3 6 12 16 23 24 28 31 31 34 39 41 47 47 47 48 50 50
Count Up = 13
Count Dn = 0
Count Eq = 4
After shuffle
SortedList[18]= 50 12 3 16 41 31 28 31 39 47 6 24 50 34 47 47 48 23
Count Up = 9
Count Dn = 7
Count Eq = 1
Destructor was called
------------------------
SortedList[14]= 3 3 6 7 9 10 15 27 28 29 29 30 36 43
Count Up = 11
Count Dn = 0
Count Eq = 2
After shuffle
SortedList[14]= 3 9 43 6 29 15 10 36 28 7 3 27 29 30
Count Up = 7
Count Dn = 6
Count Eq = 0
Destructor was called
------------------------
SortedList[13]= 8 11 12 17 17 25 25 37 38 45 46 48 49
Count Up = 10
Count Dn = 0
Count Eq = 2
After shuffle
SortedList[13]= 38 48 12 17 37 17 25 8 49 46 45 11 25
Count Up = 6
Count Dn = 6
Count Eq = 0
Destructor was called
------------------------
SortedList[13]= 4 11 13 17 18 22 27 30 37 42 45 50 50
Count Up = 11
Count Dn = 0
Count Eq = 1
After shuffle
SortedList[13]= 30 42 13 4 22 50 18 11 17 37 45 50 27
Count Up = 7
Count Dn = 5
Count Eq = 0
Destructor was called
------------------------
SortedList[0]=
Count Up = 0
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[0]=
Count Up = 0
Count Dn = 0
Count Eq = 0
Destructor was called
------------------------
SortedList[9]= 5 6 7 16 23 23 36 46 49
Count Up = 7
Count Dn = 0
Count Eq = 1
After shuffle
SortedList[9]= 36 5 16 7 23 6 49 46 23
Count Up = 3
Count Dn = 5
Count Eq = 0
Destructor was called
------------------------
SortedList[2]= 14 33
Count Up = 1
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[2]= 33 14
Count Up = 0
Count Dn = 1
Count Eq = 0
Destructor was called
------------------------
SortedList[8]= 12 16 17 19 21 32 36 40
Count Up = 7
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[8]= 32 17 12 16 21 40 19 36
Count Up = 4
Count Dn = 3
Count Eq = 0
Destructor was called
------------------------
SortedList[10]= 5 8 14 14 20 23 30 30 32 40
Count Up = 7
Count Dn = 0
Count Eq = 2
After shuffle
SortedList[10]= 23 40 20 30 14 30 5 32 14 8
Count Up = 4
Count Dn = 5
Count Eq = 0
Destructor was called
------------------------
SortedList[11]= 3 3 5 5 19 19 27 28 33 45 48
Count Up = 7
Count Dn = 0
Count Eq = 3
After shuffle
SortedList[11]= 3 33 5 19 28 48 19 45 5 3 27
Count Up = 6
Count Dn = 4
Count Eq = 0
Destructor was called
------------------------
SortedList[0]=
Count Up = 0
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[0]=
Count Up = 0
Count Dn = 0
Count Eq = 0
Destructor was called
------------------------
SortedList[20]= 0 3 3 6 9 12 14 20 22 22 24 30 31 38 39 43 46 48 50 50
Count Up = 16
Count Dn = 0
Count Eq = 3
After shuffle
SortedList[20]= 30 22 24 0 46 9 39 50 31 22 48 50 38 12 3 43 20 3 6 14
Count Up = 9
Count Dn = 10
Count Eq = 0
Destructor was called
------------------------
SortedList[8]= 1 7 7 17 32 32 33 49
Count Up = 5
Count Dn = 0
Count Eq = 2
After shuffle
SortedList[8]= 17 32 1 7 7 33 32 49
Count Up = 4
Count Dn = 2
Count Eq = 1
Destructor was called
------------------------
SortedList[16]= 0 2 7 18 18 20 23 30 31 34 35 40 41 42 45 49
Count Up = 14
Count Dn = 0
Count Eq = 1
After shuffle
SortedList[16]= 18 20 42 49 35 31 7 30 34 18 40 23 0 2 45 41
Count Up = 8
Count Dn = 7
Count Eq = 0
Destructor was called
------------------------
SortedList[14]= 5 9 11 11 19 20 24 27 28 31 32 43 46 50
Count Up = 12
Count Dn = 0
Count Eq = 1
After shuffle
SortedList[14]= 11 24 27 43 20 46 50 9 5 11 31 28 19 32
Count Up = 8
Count Dn = 5
Count Eq = 0
Destructor was called
------------------------
SortedList[6]= 3 5 10 27 37 43
Count Up = 5
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[6]= 43 3 37 27 5 10
Count Up = 2
Count Dn = 3
Count Eq = 0
Destructor was called
------------------------
SortedList[16]= 1 3 10 11 12 13 16 19 22 32 35 40 43 44 45 47
Count Up = 15
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[16]= 32 43 45 40 35 16 12 10 22 13 44 3 19 47 1 11
Count Up = 7
Count Dn = 8
Count Eq = 0
Destructor was called
------------------------
SortedList[10]= 6 8 10 18 26 29 39 41 47 49
Count Up = 9
Count Dn = 0
Count Eq = 0
After shuffle
SortedList[10]= 10 47 26 29 39 6 8 41 18 49
Count Up = 6
Count Dn = 3
Count Eq = 0
Destructor was called
------------------------
Press any key to continue
*/