DSortedList05
[ Home ] [ Up ]

//DSortedList05.cpp
//date: 11/13/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

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); 
  };


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


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

 
////////////////////////////////////////////////////////////
// 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 CDSortedList &aList)
  {
  bob << "SortedList[" << aList.m_count << "]= ";

  CNode *p;

  p = aList.m_first;

  while (p != NULL)
    {
    p->display();
    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:
testDestructor
==============
List[7] =
[0x00321138 -32000 0x003211E0]
[0x003211E0 12 0x00322A50]
[0x00322A50 20 0x00321218]
[0x00321218 34 0x003212C0]
[0x003212C0 45 0x003211A8]
[0x003211A8 55 0x00321250]
[0x00321250 71 0x00321288]
[0x00321288 98 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[5] =
[0x00321138 -32000 0x003211A8]
[0x003211A8 4 0x00321288]
[0x00321288 17 0x00321218]
[0x00321218 18 0x003211E0]
[0x003211E0 21 0x00321250]
[0x00321250 33 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[5] =
[0x00321138 -32000 0x003211E0]
[0x003211E0 16 0x003211A8]
[0x003211A8 16 0x00321250]
[0x00321250 17 0x00321218]
[0x00321218 19 0x00321288]
[0x00321288 34 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[9] =
[0x00321138 -32000 0x00321250]
[0x00321250 11 0x00321288]
[0x00321288 13 0x003211E0]
[0x003211E0 13 0x00322A88]
[0x00322A88 17 0x003212C0]
[0x003212C0 17 0x003211A8]
[0x003211A8 17 0x00321218]
[0x00321218 27 0x00322AC0]
[0x00322AC0 44 0x00322A50]
[0x00322A50 50 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[6] =
[0x00321138 -32000 0x00321288]
[0x00321288 14 0x003211E0]
[0x003211E0 17 0x00321250]
[0x00321250 22 0x00321218]
[0x00321218 32 0x003211A8]
[0x003211A8 43 0x003212C0]
[0x003212C0 50 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[2] =
[0x00321138 -32000 0x003211A8]
[0x003211A8 28 0x003211E0]
[0x003211E0 38 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[1] =
[0x00321138 -32000 0x003211A8]
[0x003211A8 36 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[10] =
[0x00321138 -32000 0x00322A88]
[0x00322A88 2 0x003212C0]
[0x003212C0 5 0x003211A8]
[0x003211A8 5 0x00322AC0]
[0x00322AC0 15 0x00322A50]
[0x00322A50 21 0x00322AF8]
[0x00322AF8 27 0x00321250]
[0x00321250 28 0x003211E0]
[0x003211E0 34 0x00321288]
[0x00321288 41 0x00321218]
[0x00321218 45 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[3] =
[0x00321138 -32000 0x00321218]
[0x00321218 22 0x003211E0]
[0x003211E0 35 0x003211A8]
[0x003211A8 39 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[9] =
[0x00321138 -32000 0x00322AC0]
[0x00322AC0 10 0x003212C0]
[0x003212C0 17 0x00322A88]
[0x00322A88 18 0x00321218]
[0x00321218 23 0x00321288]
[0x00321288 27 0x00321250]
[0x00321250 27 0x003211E0]
[0x003211E0 32 0x003211A8]
[0x003211A8 46 0x00322A50]
[0x00322A50 48 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[8] =
[0x00321138 -32000 0x00321288]
[0x00321288 1 0x00321218]
[0x00321218 3 0x00322A50]
[0x00322A50 14 0x003212C0]
[0x003212C0 16 0x003211E0]
[0x003211E0 23 0x00321250]
[0x00321250 26 0x00322A88]
[0x00322A88 28 0x003211A8]
[0x003211A8 37 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[5] =
[0x00321138 -32000 0x003211A8]
[0x003211A8 17 0x00321250]
[0x00321250 19 0x00321288]
[0x00321288 33 0x003211E0]
[0x003211E0 34 0x00321218]
[0x00321218 35 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[2] =
[0x00321138 -32000 0x003211E0]
[0x003211E0 5 0x003211A8]
[0x003211A8 6 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[3] =
[0x00321138 -32000 0x003211A8]
[0x003211A8 5 0x00321218]
[0x00321218 14 0x003211E0]
[0x003211E0 35 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[3] =
[0x00321138 -32000 0x003211A8]
[0x003211A8 2 0x003211E0]
[0x003211E0 29 0x00321218]
[0x00321218 32 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[2] =
[0x00321138 -32000 0x003211E0]
[0x003211E0 14 0x003211A8]
[0x003211A8 42 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[8] =
[0x00321138 -32000 0x00321288]
[0x00321288 2 0x003211E0]
[0x003211E0 3 0x00322A50]
[0x00322A50 14 0x00322A88]
[0x00322A88 22 0x00321218]
[0x00321218 34 0x003211A8]
[0x003211A8 35 0x00321250]
[0x00321250 45 0x003212C0]
[0x003212C0 47 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[5] =
[0x00321138 -32000 0x003211E0]
[0x003211E0 6 0x00321218]
[0x00321218 13 0x00321250]
[0x00321250 21 0x00321288]
[0x00321288 32 0x003211A8]
[0x003211A8 48 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[5] =
[0x00321138 -32000 0x00321218]
[0x00321218 4 0x003211A8]
[0x003211A8 27 0x003211E0]
[0x003211E0 29 0x00321288]
[0x00321288 37 0x00321250]
[0x00321250 40 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[2] =
[0x00321138 -32000 0x003211A8]
[0x003211A8 37 0x003211E0]
[0x003211E0 39 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
List[4] =
[0x00321138 -32000 0x003211E0]
[0x003211E0 3 0x00321250]
[0x00321250 19 0x003211A8]
[0x003211A8 24 0x00321218]
[0x00321218 45 0x00321170]
[0x00321170 32000 0x00000000]

Destructor was called
-----------------
Press any key to continue
*/