CODL07
[ Home ] [ Up ]

//file: CODL07.cpp
//Author: AOU
//Date 10/27/2004

// Ordered Dynamic List

////////////////////////////////////////////////////////
// Assignment 04, Date Assigned 10/22/2004, Due: 10/29/2004
////////////////////////////////////////////////////////
/* 
  Total points 75
  As discussed in the class, implement the following member 
  function and corresponding test functions:

    bool isSorted(void) const;
    void shuffle(void);
    void sortBubble1(void);


Submit the printed form of the following for each function:

(1) Detailed Description      (5 points)
(2) Two Example               (5 points)
(3) Detailed Algorithm        (5 points)
(4) Code                      (5 points)
(5) Output from 10 Test Cases (5 points)

/*

*/
////////////////////////////////////////////////////////
// includes
////////////////////////////////////////////////////////
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


////////////////////////////////////////////////////////
// constants
////////////////////////////////////////////////////////
int const MAX_SIZE    = 10;
char * PLUS_INFINITY  = "zzz"; 
char * MINUS_INFINITY = "$$$"; 
int const TEST_COUNT  = 10;
int const MAX_VALUE   = 10;
int const MAX_LENGTH  = 20+1;


////////////////////////////////////////////////////////
// test data
////////////////////////////////////////////////////////
char *test_data[]=
  {
  "Joe", "Jon", "Bob", "Ken",
  "Zak", "Ann", "Cam", "Alo"
  };

int TEST_SIZE = sizeof(test_data)/sizeof(test_data[0]);


////////////////////////////////////////////////////////
// class CNode
////////////////////////////////////////////////////////
class CNode
  {
  private:
    char key[MAX_LENGTH];
    CNode *next;
  public:
    CNode(void);
    CNode(char value[]);
    void display(void);
    void displayDetails(void);
  friend class CODL;
  friend void swap(CNode &v1, CNode &v2);
  };


////////////////////////////////////////////////////////
// class CODL
////////////////////////////////////////////////////////
class CODL
  {
  private:
    CNode *head;
    int n;
    void init(void);
  public:
    CODL(void);
    void display(void);
    void displayDetails(void);
    bool insert(char x[]);
    CODL(char ch);
    ~CODL(void);
    bool isSorted(void)const;
    CODL(int m);
    CNode * search(char x[]) const;

    CNode * addressOfRandomNode(void) const;
    bool deleteByAddress(CNode *p);

    bool deleteByPosition(int p);
    int deleteByValue(char x[], int c);

  };


////////////////////////////////////////////////////////
// test functions prototypes
////////////////////////////////////////////////////////
void test_insert(void);
void test_isSorted(void);
void test_constructorM(void);
void test_search(void);
void test_constructorR(void);

void test_addressOfRandomNode(void);
void test_swap(void);
void test_deleteByAddress(void);
void test_deleteByPosition(void);
void test_deleteByValue(void);


////////////////////////////////////////////////////////
//void main(void)
////////////////////////////////////////////////////////
void main(void)
  {
  //test_constructorR();
  //test_isSorted();
  //test_constructorM();
  //test_search();
  //test_addressOfRandomNode();
  //test_swap();
  //test_deleteByAddress();
  //test_deleteByPosition();
  test_deleteByValue();
  }


////////////////////////////////////////////////////////
// int CODL::deleteByValue(char x[], int c)
////////////////////////////////////////////////////////
/*
tDeleted=0
while c-->0
  find the address of x and put it in p
  if (call deleteByAddres(p))
      tDeleted++
    else
      break
  wend

return tDeleted
*/
int CODL::deleteByValue(char x[], int c)
  {
  int tDeleted = 0;
  while(c-- > 0)
    {
    CNode *p = this->search(x);
    if (this->deleteByAddress(p))
        tDeleted++;
      else
        break;
    }
  return tDeleted;
  }


////////////////////////////////////////////////////////
// void test_deleteByValue(void)
////////////////////////////////////////////////////////
void test_deleteByValue(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_deleteByValue\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    CODL myList(m);
    myList.display();

    char x[MAX_LENGTH];
    strcpy(x, test_data[rand()%TEST_SIZE]);

    int c = (rand()%MAX_SIZE)/4;

    cout << "Search and delete " << x << endl;
    cout << "              c = " << c << endl;
    int d = myList.deleteByValue(x, c);

    cout << "Deleted  "  << d << " times\n";

    myList.display();

    cout << "-------------------" << endl;
    }
  }


////////////////////////////////////////////////////////
// bool CODL::deleteByPosition(int p)
////////////////////////////////////////////////////////
/*
valid range is p=1..n 
empty list then return false
if not empty then
  if p is out of range then 
    return false
  else if p is in range then
    convert p to addp
    call deleteByAddress

*/
bool CODL::deleteByPosition(int p)
  {
  if (p<1 || p>n || 0==this->n)
      return false;
    else
      {
      CNode *q = this->head;

      while (p-->0)
        q = q->next;

      return this->deleteByAddress(q);
      }
  }


////////////////////////////////////////////////////////
// void test_deleteByPosition(void)
////////////////////////////////////////////////////////
void test_deleteByPosition(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_deleteByPosition\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    CODL myList(m);
    myList.display();
    myList.displayDetails();

    int p = rand()%MAX_SIZE;

    cout << "p = " << p << endl;

    if (myList.deleteByPosition(p))
        cout << "Success\n";
      else
        cout << "NO success\n";

    cout << "After myList.deleteByPosition(p);\n";

    myList.display();
    myList.displayDetails();

    cout << "-------------------------------" << endl;
    }
  }


////////////////////////////////////////////////////////
// bool CODL::deleteByAddress(CNode *p)
////////////////////////////////////////////////////////
/*
Possibilities

Algorithm0:
if p == null then return false
empty list then return false
non-empty list & bad p then return false
non-empty list & good p then
  find the address of the node left of p in q
  q->next = p->next
  kill p
  n--

Algorithm1:
empty list then return false
non-empty list & bad p then return false
  q = head
  while q!=NULL and q->next != p
    advance q
    wend

  if q == null then return false

non-empty list & good p then
  ' found(find the address of the node left of p in q)
  q->next = p->next
  kill p
  n--

*/
bool CODL::deleteByAddress(CNode *p)
  {
  if (NULL == p)
    return false;

  //empty list then return false
  if (0==this->n)
    return false;

  //non-empty list & bad p then return false
  CNode *q = this->head;
  while ((q!=NULL) && (q->next != p))
    q = q->next;

  if (NULL == q)
    return false;

  //non-empty list & good p then
  //  ' found(find the address of the node left of p in q)
  q->next = p->next;
  delete p;
  n--;

  return true;
  }


////////////////////////////////////////////////////////
// void test_deleteByAddress(void)
////////////////////////////////////////////////////////
void test_deleteByAddress(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_deleteByAddress\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    CODL myList(m);
    myList.display();
    myList.displayDetails();

    CNode *p = myList.addressOfRandomNode();

    if (p!=NULL)
      {
      cout << "Random address "  << p << endl;
      cout << "and at that address is "; p->display();
      }
    else
      cout << "NOT found\n";

    cout << endl;

    myList.deleteByAddress(p);

    cout << "After myList.deleteByAddress(p);\n";

    myList.display();
    myList.displayDetails();

    cout << "-------------------------------" << endl;
    }
  }


////////////////////////////////////////////////////////
// void swap(CNode &v1, CNode &v2)
////////////////////////////////////////////////////////
void swap(CNode &v1, CNode &v2)
  {
  char t[MAX_LENGTH];
  strcpy(t, v1.key);
  strcpy(v1.key, v2.key);
  strcpy(v2.key, t);
  };


////////////////////////////////////////////////////////
// void test_swap(void)
////////////////////////////////////////////////////////
void test_swap(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_swap\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CNode n1(test_data[rand()%TEST_SIZE]);
    CNode n2(test_data[rand()%TEST_SIZE]);
    n1.displayDetails(); cout << endl;
    n2.displayDetails(); cout << endl;
    swap(n1, n2);
    cout << "After swap(n1, n2);\n";
    n1.displayDetails(); cout << endl;
    n2.displayDetails(); cout << endl;

    cout << endl;
    }
  }


////////////////////////////////////////////////////////
// CNode * CODL::addressOfRandomNode(void) const
////////////////////////////////////////////////////////
/*
if list is empty then 
  return null

pick = rand[1..n]
p = head
while pick > 0
  advance p
  pick--
  wend
*/
CNode * CODL::addressOfRandomNode(void) const
  {
  if (0 == this->n)
    return NULL;

  int pick = rand()%n + 1;
  CNode *p = this->head;

  while (pick-- > 0)
    p = p->next;

  return p;
  }


////////////////////////////////////////////////////////
// void test_addressOfRandomNode(void)
////////////////////////////////////////////////////////
void test_addressOfRandomNode(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_addressOfRandomNode\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    CODL myList(m);
    myList.display();
    myList.displayDetails();

    CNode *p = myList.addressOfRandomNode();

    cout << "Found address "  << p << endl;
    //cout << "and at that address is "; p->display();
    cout << endl;

    cout << endl;
    }
  }


////////////////////////////////////////////////////////
// CNode * CODL::search(char x[]) const
////////////////////////////////////////////////////////
CNode * CODL::search(char x[]) const
  {
  for (CNode *p=head->next; p->next!=NULL; p=p->next)
    {
    if (strcmp(x, p->key)==0) 
        return p;
    if (strcmp(x, p->key)<0)  
        break;
    }

  return NULL;
  }


////////////////////////////////////////////////////////
// void test_search(void)
////////////////////////////////////////////////////////
void test_search(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_search\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    CODL myList(m);
    myList.display();

    char x[MAX_LENGTH];
    strcpy(x, test_data[rand()%TEST_SIZE]);

    cout << "Searching for " << x << endl;
    cout << "Found at "  << myList.search(x) << endl;
    cout << endl;
    }
  }


////////////////////////////////////////////////////////
// CODL::CODL(int m)
////////////////////////////////////////////////////////
//create a list with m values
CODL::CODL(int m)
  {
  init();

  for (int i=1; i<=m; i++)
    {
    int r = rand()%TEST_SIZE;
    this->insert(test_data[r]);
    }
  }


////////////////////////////////////////////////////////
// void test_constructorM(void)
////////////////////////////////////////////////////////
void test_constructorM(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_constructorM\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    CODL myList(m);
    cout << "After CODL myList(" << m << ");\n";
    myList.display();// display(myArray, m);
    }
  }


////////////////////////////////////////////////////////
// bool COOL::isSorted(void)
////////////////////////////////////////////////////////
/*
Description: checks if the list is in order
Example:
Algorithm:
*/
bool CODL::isSorted(void) const
  {
  for (CNode *p=head; p->next!=NULL; p=p->next)
    {
    cout << "(" << p->key << ", " << p->next->key << ")\n";
    if (strcmp(p->key, p->next->key)>0)
      return false;
    }

  return true;
  }


////////////////////////////////////////////////////////
// void test_isSorted(void)
////////////////////////////////////////////////////////
void test_isSorted(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_isSorted\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CODL *myListPtr;
    myListPtr = new CODL('r');
    (*myListPtr).display();

    if(myListPtr->isSorted())
      cout << "List is sorted\n";
    else
      cout << "List is NOT sorted\n";

    delete myListPtr;
    }
  }


////////////////////////////////////////////////////////
// CODL::~CODL(void)
////////////////////////////////////////////////////////
CODL::~CODL(void)
  {
  cout << "Destructor\n";
  CNode *q, *p = head;
  while (p!= NULL)
    {
    // eating pizza
    q = p->next;
    delete p;
    p = q;
    }
  }


////////////////////////////////////////////////////////
// CODL::CODL(char ch)
////////////////////////////////////////////////////////
CODL::CODL(char ch)
  {
  init();
  if ('r' == ch)
    {
    int m = rand()%MAX_SIZE;
    for (int i=1; i<=m; i++)
      {
      int r = rand()%TEST_SIZE;
      this->insert(test_data[r]);
      }
    }
  }


////////////////////////////////////////////////////////
// void test_constructorR(void)
////////////////////////////////////////////////////////
void test_constructorR(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_constructorR\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CODL *myListPtr;
    myListPtr = new CODL('r');
    //myListPtr->display();
    delete myListPtr;

    //myList.display();
    }
  }


////////////////////////////////////////////////////////
// bool CODL::insert(char x[])
////////////////////////////////////////////////////////
bool CODL::insert(char x[])
  {
  if (n >= MAX_SIZE)
    return false;

  CNode *p;
  p = new CNode(x);

  CNode *q;
  
  q = head;

  //while (q->next->key <= x)
  while (strcmp(q->next->key, x) <= 0)
    q = q->next;

  p->next = q->next;
  q->next = p;
  n++;
  return true;
  }


////////////////////////////////////////////////////////
// void test_insert(void)
////////////////////////////////////////////////////////
void test_insert(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_insert\n";
  cout << "+++++++++++++++++++++++++++++++\n";

  CODL myList;
  myList.display();

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int r = rand()%TEST_SIZE;
    myList.insert(test_data[r]);
    myList.display();
    }
  }


////////////////////////////////////////////////////////
// CODL::CODL(void)
////////////////////////////////////////////////////////
CODL::CODL(void)
  {
  init();
  }


////////////////////////////////////////////////////////
// void CODL::init(void)
////////////////////////////////////////////////////////
void CODL::init(void)
  {
  CNode *p, *q;
  p = new CNode(MINUS_INFINITY);
  q = new CNode(PLUS_INFINITY);
  head = p;
  p->next = q;
  q->next = NULL;
  n = 0;
  }


////////////////////////////////////////////////////////
// void CODL::displayDetails(void)
////////////////////////////////////////////////////////
void CODL::displayDetails(void)
  {
  cout << "List[" << n << "] = ";
  cout << "head = " << head << endl;

  CNode *p = head;
  while (p != NULL)
    {
    p->displayDetails();
    cout << endl;
    p = p->next;
    }
  
  cout << endl;
  }


////////////////////////////////////////////////////////
// void CODL::display(void)
////////////////////////////////////////////////////////
void CODL::display(void)
  {
  cout << "List[" << n << "] = ";
  CNode *p = head;
  while (p != NULL)
    {
    p->display();
    cout << ' ';
    p = p->next;
    }
  
  cout << endl;
  }


////////////////////////////////////////////////////////
//CNode::CNode(void)
////////////////////////////////////////////////////////
CNode::CNode(void)
  {
  strcpy(key, "");
  next = NULL;
  };


////////////////////////////////////////////////////////
// CNode::CNode(char value[])
////////////////////////////////////////////////////////
CNode::CNode(char value[])
  {
  strcpy(key, value);
  next = NULL;
  };


////////////////////////////////////////////////////////
// void CNode::displayDetails(void)
////////////////////////////////////////////////////////
void CNode::displayDetails(void)
  {
  cout << "at " << this << " [";
  cout << key << ", ";
  cout << next << "]";
  }


////////////////////////////////////////////////////////
// void CNode::display(void)
////////////////////////////////////////////////////////
void CNode::display(void)
  {
  cout << key;
  }