CODL05*
[ Home ] [ Up ]

//file: CODL05.cpp
//Author: AOU
//Date 10/22/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[]=
  {
  "John", "James", "Bob", "Karen",
  "Zack", "Ann", "Camry", "Alero"
  };

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


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


////////////////////////////////////////////////////////
// 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 main(void)
////////////////////////////////////////////////////////
void main(void)
  {
  //test_constructorR();
  //test_isSorted();
  //test_constructorM();
  cout << "rand() = " << rand() << endl;
  //test_search();
  test_addressOfRandomNode();
  }


////////////////////////////////////////////////////////
// bool CODL::deleteByAddress(CNode *p)
////////////////////////////////////////////////////////
/*
List is empty
p pointed node does not belong to the list
p == NULL
p pointed node does belong to the list

*/
bool CODL::deleteByAddress(CNode *p)
  {
  return true;
  }


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

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