DSortedList10
[ Home ] [ Up ]

//DSortedList10.cpp
//date: 12/02/2002
//author: AOU


//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) const; //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

    // extra credit 01
    friend void sub(const CDSortedList &aList, 
      const CDSortedList &bList, CDSortedList &cList);
    //c = a - b

    // extra credit 02
    friend void addMultiple(const CDSortedList aList[], int listCount, 
      CDSortedList &mList);

    bool isEmpty(void) const; 
    bool operator ==(CDSortedList list2); 
    bool operator !=(CDSortedList list2); 
    int getCount(void); 
    int getAt(int p);
    bool remove(int x);
    int searchBinary(int x) const;
    int searchBinaryLM(int x) const;
    void sortInsertion1(void);
   
  };


////////////////////////////////////////////////////////////
//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 != NULL)
    {
    if (x < p->m_key)
      return 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";

  CDSortedList myList('c');
  cout << myList;
  for (int j=0; j<S_SIZE; j++)
    {
    int x = sValues[j];
    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;

    x = sValues[j]+1;
    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";

  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(-INFINITY);
  CNode *p2 = new CNode(+INFINITY);

  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) const
  {
  cout << this->m_key << " "; 
  }


/*
testSearch
==========
SortedList[7]= 12 20 34 45 55 71 98
55 is in the list at 0x00320B38
56 is not in the list
12 is in the list at 0x00320B70
13 is not in the list
34 is in the list at 0x00320BA8
35 is not in the list
71 is in the list at 0x00320BE0
72 is not in the list
98 is in the list at 0x00320C18
99 is not in the list
45 is in the list at 0x00320C50
46 is not in the list
20 is in the list at 0x00320C88
21 is not in the list
-------------------
SortedList[0]=
45 is not in the list
-------------------
Destructor was called
SortedList[1]= 28
47 is not in the list
38 is not in the list
-------------------
Destructor was called
SortedList[2]= 21 34
4 is not in the list
1 is not in the list
31 is not in the list
-------------------
Destructor was called
SortedList[3]= 21 22 30
46 is not in the list
37 is not in the list
35 is not in the list
4 is not in the list
-------------------
Destructor was called
SortedList[4]= 0 18 45 49
1 is not in the list
19 is not in the list
13 is not in the list
31 is not in the list
14 is not in the list
-------------------
Destructor was called
SortedList[5]= 6 14 21 27 47
18 is not in the list
36 is not in the list
29 is not in the list
18 is not in the list
9 is not in the list
27 is in the list at 0x00320D68
-------------------
Destructor was called
SortedList[6]= 0 11 19 23 31 46
45 is not in the list
9 is not in the list
7 is not in the list
17 is not in the list
1 is not in the list
5 is not in the list
25 is not in the list
-------------------
Destructor was called
SortedList[7]= 1 15 16 25 35 40 44
44 is in the list at 0x00320E10
2 is not in the list
31 is not in the list
19 is not in the list
36 is not in the list
33 is not in the list
44 is in the list at 0x00320E10
8 is not in the list
-------------------
Destructor was called
SortedList[8]= 5 19 26 29 35 42 47 48
10 is not in the list
22 is not in the list
18 is not in the list
20 is not in the list
26 is in the list at 0x00320EB8
47 is in the list at 0x00320DA0
43 is not in the list
16 is not in the list
4 is not in the list
-------------------
Destructor was called
SortedList[9]= 0 17 18 19 23 34 38 39 42
26 is not in the list
3 is not in the list
29 is not in the list
22 is not in the list
20 is not in the list
10 is not in the list
40 is not in the list
8 is not in the list
7 is not in the list
4 is not in the list
-------------------
Destructor was called
Destructor was called
Press any key to continue
*/