DSortedList08
[ Home ] [ Up ]

//DSortedList08.cpp
//date: 11/25/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);

void testSortBubble(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 sortBubble(void);                        //2002.11.25
    bool isSorted(void) const;                    //2002.11.25
  };


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


////////////////////////////////////////////////////////////
// void CDSortedList::sortBubble(void)
////////////////////////////////////////////////////////////
void CDSortedList::sortBubble(void)
  {
  if (this->m_count <= 1)
    return;

  int temp;
  CNode *ip;
  bool sorted = false;

  while (!sorted)
    {
    sorted = true;
    for (ip = this->m_first->m_next; ip->m_next->m_next != NULL; ip = ip->m_next)
      {
      if (ip->m_key > ip->m_next->m_key)
        {
        temp = ip->m_key;
        ip->m_key = ip->m_next->m_key;
        ip->m_next->m_key = temp;
        sorted = false;
        }
      } 
    }
  }


////////////////////////////////////////////////////////////
// isSorted(void)
////////////////////////////////////////////////////////////
bool CDSortedList::isSorted(void) const
  {
  if (this->m_count <= 1)
    return true;

  for (CNode*ip = this->m_first->m_next; ip->m_next->m_next != NULL; ip = ip->m_next)
    if (ip->m_key > ip->m_next->m_key)
    return false;

  return true;
  }


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

  for (int i=1; i<=10; i++)
    {
    CDSortedList myList('r');

    cout << "Original list\n";
    cout << myList;
    if (myList.isSorted())
        cout << "List is SORTED\n";
      else
        cout << "List is NOT SORTED\n";

    myList.shuffle();
    cout << "Shuffled list\n";
    cout << myList;
    if (myList.isSorted())
        cout << "List is SORTED\n";
      else
        cout << "List is NOT SORTED\n";

    myList.sortBubble();
    cout << "After sortBubble\n";
    cout << myList;
    if (myList.isSorted())
        cout << "List is SORTED\n";
      else
        cout << "List is NOT SORTED\n";

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

////////////////////////////////////////////////////////////
// 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:
testSortBubble
==============
Original list
SortedList[19]= 2 2 8 9 16 17 17 27 27 27 30 35 36 37 41 41 43 44 45
List is SORTED
Shuffled list
SortedList[19]= 30 27 16 37 45 44 35 8 27 36 2 43 2 41 27 41 17 17 9
List is NOT SORTED
After sortBubble
SortedList[19]= 2 2 8 9 16 17 17 27 27 27 30 35 36 37 41 41 43 44 45
List is SORTED
-------------------
Destructor was called
Original list
SortedList[0]=
List is SORTED
Shuffled list
SortedList[0]=
List is SORTED
After sortBubble
SortedList[0]=
List is SORTED
-------------------
Destructor was called
Original list
SortedList[11]= 2 3 4 6 6 14 22 29 44 46 48
List is SORTED
Shuffled list
SortedList[11]= 29 14 4 6 48 6 46 3 44 22 2
List is NOT SORTED
After sortBubble
SortedList[11]= 2 3 4 6 6 14 22 29 44 46 48
List is SORTED
-------------------
Destructor was called
Original list
SortedList[2]= 4 30
List is SORTED
Shuffled list
SortedList[2]= 30 4
List is NOT SORTED
After sortBubble
SortedList[2]= 4 30
List is SORTED
-------------------
Destructor was called
Original list
SortedList[0]=
List is SORTED
Shuffled list
SortedList[0]=
List is SORTED
After sortBubble
SortedList[0]=
List is SORTED
-------------------
Destructor was called
Original list
SortedList[0]=
List is SORTED
Shuffled list
SortedList[0]=
List is SORTED
After sortBubble
SortedList[0]=
List is SORTED
-------------------
Destructor was called
Original list
SortedList[0]=
List is SORTED
Shuffled list
SortedList[0]=
List is SORTED
After sortBubble
SortedList[0]=
List is SORTED
-------------------
Destructor was called
Original list
SortedList[4]= 3 39 42 49
List is SORTED
Shuffled list
SortedList[4]= 49 42 3 39
List is NOT SORTED
After sortBubble
SortedList[4]= 3 39 42 49
List is SORTED
-------------------
Destructor was called
Original list
SortedList[15]= 0 5 5 9 13 14 16 17 17 22 24 28 35 35 45
List is SORTED
Shuffled list
SortedList[15]= 35 14 17 0 5 16 5 35 28 13 17 24 22 45 9
List is NOT SORTED
After sortBubble
SortedList[15]= 0 5 5 9 13 14 16 17 17 22 24 28 35 35 45
List is SORTED
-------------------
Destructor was called
Original list
SortedList[10]= 14 22 23 24 29 33 40 42 44 50
List is SORTED
Shuffled list
SortedList[10]= 42 14 40 22 50 24 29 33 23 44
List is NOT SORTED
After sortBubble
SortedList[10]= 14 22 23 24 29 33 40 42 44 50
List is SORTED
-------------------
Destructor was called
Press any key to continue
*/