DSortedList09
[ Home ] [ Up ]

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

void testSearch(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

    CNode * search (int x);                       //2002.11.28
  };


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


////////////////////////////////////////////////////////////
// CNode * CDSortedList::search (int x)
////////////////////////////////////////////////////////////
CNode * CDSortedList::search (int x)
  {
  if (this->m_count == 0)
    return NULL;
  CNode *p;
  p = this->m_first->m_next;
  while (p->m_next->m_next != NULL)
    {
    if (x == p->m_key)
      return p;
    p = p->m_next;
    }

  return NULL;
  }


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

  for (int i=1; i<=10; i++)
    {
    CDSortedList myList(i-1);
    cout << myList;
    for (int j=1; j<=i; j++)
      {
      int x = rand()%(MAX_VALUE+1);
      CNode *p = myList.search(x);
      if (NULL == p)
          cout << x << " is not in the list\n";
        else
          cout << x << " is in the list at " << p << endl;
      }
    cout << "-------------------\n";
    }
  }


////////////////////////////////////////////////////////////
// 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:
testSearch
==========
SortedList[0]=
17 is not in the list
-------------------
Destructor was called
SortedList[1]= 1
29 is not in the list
2 is not in the list
-------------------
Destructor was called
SortedList[2]= 29 48
2 is not in the list
3 is not in the list
9 is not in the list
-------------------
Destructor was called
SortedList[3]= 20 36 44
44 is not in the list
3 is not in the list
20 is in the list at 0x003211E0
44 is not in the list
-------------------
Destructor was called
SortedList[4]= 14 37 45 47
34 is not in the list
36 is not in the list
44 is not in the list
49 is not in the list
50 is not in the list
-------------------
Destructor was called
SortedList[5]= 7 11 31 32 38
49 is not in the list
0 is not in the list
37 is not in the list
5 is not in the list
50 is not in the list
39 is not in the list
-------------------
Destructor was called
SortedList[6]= 15 22 25 34 39 45
13 is not in the list
2 is not in the list
39 is in the list at 0x00321250
21 is not in the list
23 is not in the list
31 is not in the list
10 is not in the list
-------------------
Destructor was called
SortedList[7]= 10 11 14 21 29 35 39
18 is not in the list
39 is not in the list
35 is in the list at 0x00321288
33 is not in the list
39 is not in the list
49 is not in the list
21 is in the list at 0x00321250
5 is not in the list
-------------------
Destructor was called
SortedList[8]= 7 18 20 23 23 26 36 44
11 is not in the list
42 is not in the list
15 is not in the list
26 is in the list at 0x003211E0
13 is not in the list
2 is not in the list
48 is not in the list
10 is not in the list
26 is in the list at 0x003211E0
-------------------
Destructor was called
SortedList[9]= 3 4 17 24 32 36 37 39 45
20 is not in the list
3 is in the list at 0x00322A50
8 is not in the list
43 is not in the list
14 is not in the list
36 is in the list at 0x00322A88
12 is not in the list
14 is not in the list
4 is in the list at 0x00321218
37 is in the list at 0x003211A8
-------------------
Destructor was called
Press any key to continue
*/