CODL03
[ Home ] [ Up ]

//file: CODL03.cpp
//Author: AOU
//Date 10/18/2004

// Ordered Dynamic Lisr
////////////////////////////////////////////////////////
// includes
////////////////////////////////////////////////////////
#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>



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

char *test_data[]=
  {
  "John", "James", "Bob", "Karen",
  "Zack", "Ann", "Camry", "Alero"
  };
int TEST_SIZE = sizeof(test_data)/sizeof(test_data[0]);


void test_constructorR(void );


class CNode
  {
  private:
    char key[MAX_LENGTH];
    CNode *next;
  public:
    CNode(void)
      {
      strcpy(key, "");
      next = NULL;
      };

    CNode(char value[])
      {
      strcpy(key, value);
      next = NULL;
      };
    void display(void)
      {
      cout << key;
      }
  friend class CODL;
  };


class CODL
  {
  private:
    CNode *head;
    int n;
    void 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;
      }
  public:
    CODL(void)
      {
      init();
      }
    void display(void)
      {
      cout << "List[" << n << "] = ";
      CNode *p = head;
      while (p != NULL)
        {
        p->display();
        cout << ' ';
        p = p->next;
        }
      
      cout << endl;
      }
    bool insert(char x[]);

    CODL(char ch);
    ~CODL(void);
  };

void test_insert(void);

void main(void)
  {
  test_constructorR();
  }


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)
  {
  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[])
  {
  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();
    }

  }