CODL12
[ Home ] [ Up ]

//file: CODL12.cpp
//Author: AOU
//Date 11/05/2004
//C++ .NET

// 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>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <fstream>
using namespace std;


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

char *fileName        = "F:\\csis250.html";


////////////////////////////////////////////////////////
// test data
////////////////////////////////////////////////////////
char *test_data[]=
  {
  "Joe", "Jon", "Bob", "Ken",
  "Zak", "Ann", "Cam", "Alo",
  "You", "Sue", "Hay", "Rik",
  "Ben", "Tom", "His", "Her"
  };

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;
    bool has(char x[]) const;
    CNode * addressOfRandomNode(void) const;
    bool deleteByAddress(CNode *p);
    bool deleteByPosition(int p);
    int deleteByValue(char x[], int c);

    bool operator ==(const CODL &s2) const;
    int clearList(void);
    CODL & operator =(const CODL &s2);

    CODL(const CODL &aList);
    bool operator !=(const CODL &s2) const;

    bool isEmpty(void) const;
    bool operator <(const CODL &s2) const;

    void save(char fName[]);
    void load(char fName[]);
    CODL(char fName[]);

    bool hasDistinct(void) const;
  };


////////////////////////////////////////////////////////
// test functions prototypes
////////////////////////////////////////////////////////
void test_insert(void);
void test_isSorted(void);
void test_constructorM(void);
void test_search(void);
void test_has(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 test_isEqualToOperator(void);
void test_isNotEqualToOperator(void);
void test_assignOperator(void);

void test_constructorCopy(void);

void test_OperatorLessThan(void);
void test_save(void);
void test_load(void);
void test_ConstructorFIle(void);

void test_hasDistinct(void);

////////////////////////////////////////////////////////
//void main(void)
////////////////////////////////////////////////////////
void main(void)
  {
  srand((unsigned int)time(NULL));
  //test_constructorR();
  //test_isSorted();
  //test_constructorM();
  //test_search();
  //test_has();
  //test_addressOfRandomNode();
  //test_swap();
  //test_deleteByAddress();
  //test_deleteByPosition();
  //test_deleteByValue();
  //test_isEqualToOperator();
  //test_isNotEqualToOperator();
  //test_assignOperator();
  //test_constructorCopy();

  //test_OperatorLessThan();
  //test_save();
  //test_load();
  //test_ConstructorFIle();
  test_hasDistinct();
  }

/*
p = head->next
while p->next != NULL
  if p->key == p->next->key then
    return false
  advance p
  wend

return true
*/
bool CODL::hasDistinct(void) const
  {
  CNode *p = this->head->next;

  while (p->next != NULL)
    {
    if (strcmp(p->key,p->next->key) == 0)
      return false;
    p = p->next;
    }

  return true;
  }

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

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CODL myList('r');
    cout << "myList   = "; myList.display();

    if (myList.hasDistinct())
        cout << "Values are distinct\n";
      else
        cout << "Values are NOT distinct\n";

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



///////////////////////////////////////////////////////
// CODL::CODL(char fName[])
///////////////////////////////////////////////////////
CODL::CODL(char fName[])
  {
  this->init();
  this->load(fName);
  }


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

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CODL myList('r');
    cout << "myList   = "; myList.display();

    myList.save(fileName);

    CODL yoList(fileName);

    cout << "After CODL yoList(fileName);\n";
    cout << "yoList   = "; yoList.display();

    if (myList == yoList)
        cout << "Constructor was a success\n";
      else
        cout << "Constructor was NOT a success\n";

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



///////////////////////////////////////////////////////
// void CODL::load(char fName[])
///////////////////////////////////////////////////////
void CODL::load(char fName[])
  {
  ifstream inFile(fName, ios::in);

  this->clearList();

  char temp[MAX_LENGTH];

  while (inFile >> temp)
    {
    this->insert(temp);
    }

  inFile.close();
  }


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

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CODL myList('r');
    cout << "myList   = "; myList.display();

    myList.save(fileName);

    CODL yoList('r');
    cout << "After CODL yoList('r');\n";
    cout << "yoList   = "; yoList.display();

    yoList.load(fileName);
    cout << "After yoList.load(fileName);\n";
    cout << "yoList   = "; yoList.display();

    if (myList == yoList)
        cout << "Load was a success\n";
      else
        cout << "Load was NOT a success\n";
    cout << "------------------------\n";
    }
  }


////////////////////////////////////////////////////////
//void CODL::save(char fName[])
////////////////////////////////////////////////////////
void CODL::save(char fName[])
{
ofstream outFile(fName, ios::out);

CNode *p = this->head->next;
while (p->next != NULL)
  {
  outFile << p->key << endl;
  p = p->next;
  }

outFile.close();
}


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

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CODL myList('r');
    cout << "myList   = "; myList.display();

    myList.save(fileName);
    cout << "------------------------\n";
    }
  }


////////////////////////////////////////////////////////
// bool CODL::operator <(const CODL &s2) const
////////////////////////////////////////////////////////
bool CODL::operator <(const CODL &s2) const
/*
Algorithm0:
if s1 and s2 are empty then return true
if s1 is empty then return true
if s2 is empty and s1 is not empty then return false
for each x in s1 do the following
  if x is not in s2 then
    return false
  end for

if s1 is empty then return true
if s1 and s2 are empty then return true
if s2 is empty and s1 is not empty then return false
for each x in s1 do the following
  if x is not in s2 then
    return false
  end for
  
*/
  {
  if (this->isEmpty())
    return true;
    
  if (this->isEmpty() && s2.isEmpty())
    return true;

  if (!this->isEmpty() && s2.isEmpty())
    return false;

  CNode *p = this->head->next;
  while (p->next != NULL)
    {
    if (!s2.has(p->key))
      return false;

    p = p->next;
    }
  
  return true;
  }


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

  for (int i=1; i<=TEST_COUNT; i++)
    {
    CODL myList('r');
    CODL yourList('r');
    cout << "myList   = "; myList.display();
    cout << "yourList = "; yourList.display();

    if (myList < yourList)
        cout << "myList is < yourList\n";
      else
        cout << "myList is NOT < yourList\n";

    if (yourList < myList)
        cout << "yourList is < myList \n";
      else
        cout << "yourList is NOT < myList \n";

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


////////////////////////////////////////////////////////
// bool CODL::isEmpty(void) const
////////////////////////////////////////////////////////
bool CODL::isEmpty(void) const
  {
  return (this->n == 0);
  }


////////////////////////////////////////////////////////
// CODL::CODL(const CODL &s2)
////////////////////////////////////////////////////////
CODL::CODL(const CODL &s2)
  {
  this->init();
  //*this = aList;
  for (CNode *p = s2.head->next; p->next!=NULL; p=p->next)
    this->insert(p->key);
  }


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

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

    if (myList == yourList)
        cout << "Lists are  equal\n";
      else
        cout << "Lists are NOT equal\n";

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


////////////////////////////////////////////////////////
// CODL &CODL::operator =(const CODL &s2)
////////////////////////////////////////////////////////
/*
clear the first list
for each value x in the s2
  insert x in the first list 
*/
CODL & CODL::operator =(const CODL &s2)
  {
  this->clearList();
  for (CNode *p = s2.head->next; p->next!=NULL; p=p->next)
    this->insert(p->key);

  return *this;
  }


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

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

    m = rand()%MAX_SIZE;
    CODL yourList(m);
    yourList.display();

    m = rand()%MAX_SIZE;
    CODL hitList(m);
    hitList.display();

    if (myList == yourList)
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";

    cout << "After myList = yourList;\n";

    myList = (yourList = hitList);
    myList.display();
    yourList.display();
    hitList.display();

    if (myList == yourList)
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";

    if (myList == hitList)
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";

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


////////////////////////////////////////////////////////
// int CODL::clearList(void)
////////////////////////////////////////////////////////
/*
Deletes all but the dummy nodes
*/
int CODL::clearList(void)
  {
  int tDeleted = 0;

  CNode *q, *p = head->next;
  while (p->next!= NULL)
    {
    // eating pizza
    q = p->next;
    delete p;
    tDeleted++;
    p = q;
    }

  head->next = p;
  this->n = 0;
  return tDeleted;
  }


////////////////////////////////////////////////////////
// bool CODL::operator ==(const CODL s2) const
////////////////////////////////////////////////////////
bool CODL::operator ==(const CODL &s2) const
  {
  if ((0==this->n) && (0==s2.n))
    return true;
  else if (n != s2.n)
    return false;
  else
    for (CNode *p1=this->head, *p2=s2.head; p1!=NULL; p1=p1->next, p2=p2->next)
      if (strcmp(p1->key,p2->key)!=0) 
        return false;

  return true;
  }


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

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

    m = rand()%MAX_SIZE;
    CODL yourList(m);
    yourList.display();

    if (myList == yourList)
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";

    cout << "After myList = yourList;\n";

    /*
    myList = yourList;
    myList.display();
    yourList.display();

    if (myList == yourList)
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";
    */

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


////////////////////////////////////////////////////////
// bool CODL::operator !=(const CODL s2) const
////////////////////////////////////////////////////////
bool CODL::operator !=(const CODL &s2) const
  {
  return !(*this==s2);
  }


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

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

    m = rand()%MAX_SIZE;
    CODL yourList(m);
    yourList.display();

    if (myList != yourList)
        cout << "Lists are NOT equal\n";
      else
        cout << "Lists are equal\n";

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


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


////////////////////////////////////////////////////////
// bool CODL::has(char x[]) const
////////////////////////////////////////////////////////
bool CODL::has(char x[]) const
  {
  if (this->search(x) == NULL)
    return false;
  else
    return true;
  }


////////////////////////////////////////////////////////
// void test_has(void)
////////////////////////////////////////////////////////
void test_has(void)
  {
  cout << "+++++++++++++++++++++++++++++++\n";
  cout << "test_has\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;
    if (myList.has(x))
      cout << x << " is in the list\n";
    else
      cout << x << " is NOT in the list\n";

    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->next;
  cout << '{';
  while (p->next != 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;
  }