CODL16
[ Home ] [ Up ]

//file: CODL16.cpp
//Author: AOU
//Date 11/19/2004
//C++ .NET

// Ordered Dynamic List

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

    bool copyToArray(char *list[], int &m) const;
    bool loadFromArray(char *list[], int m);
    bool appendFromArray(char *list[], int m);

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)


bool copyToArray(char *list[], int &m) const;
Points:
  copies the contents of a CODL object to an array of strings
  Will assume that memory allocation has been done by the caller
Algorithm:
  m=0
  for each x in *this object
    strcpy(list[m],x)
    m++
    end for
  
  return true


bool loadFromArray(char *list[], int n);
Algorithm:
  empty *this object
  for i=0 to n-1
    result = insert(list[i])
    if result=false then return false
    end for

  return true


bool appendFromArray(char *list[], int n);
Algorithm:
  for i=0 to n-1
    result = insert(list[i])
    if result=false then return false
    end for

  return true

*/


////////////////////////////////////////////////////////
// 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  = 23+1; //no checking of max tring length

char *fileName        = "E:\\csis250.htm";


////////////////////////////////////////////////////////
// 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) const;
    void displayDetails(void) const;
  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) const;
    void displayDetails(void) const;
    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;

    bool saveToSequentialFile(char fName[]) const;
    
    bool loadFromSequentialFile(char fName[]);
    CODL(char fName[]);

    bool hasDistinct(void) const;

    bool saveToDirectFile(char fName[]) const;
    friend bool displaySequentialFromDirectFile(char fName[]);    //could be global
    friend bool displayDirectFromDirectFile(char fName[]);        //could be global
    friend bool displayRandomFromDirectFile(char fName[], int m); //could be global
    bool loadFromDirectFile(char fName[]);
    bool loadRndomFromDirectFile(char fNname[], int m);
  };


////////////////////////////////////////////////////////
// global functions prototypes
////////////////////////////////////////////////////////


////////////////////////////////////////////////////////
// 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_saveToSequentialFile(void);
void test_loadFromSequentialFile(void);
void test_constructorFIle(void);

void test_hasDistinct(void);


void test_saveToDirectFile(void);
void test_displaySequentialFromDirectFile(void);
void test_displayDirectFromDirectFile(void);
void test_displayRandomFromDirectFile(void);
void test_loadFromDirectFile(void);
void test_loadRndomFromDirectFile(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_saveToSequentialFile();
  //test_loadFromSequentialFile();
  //test_constructorFIle();
  //test_hasDistinct();

  //test_saveToDirectFile();
  //test_displaySequentialFromDirectFile();
  //test_displayDirectFromDirectFile();
  //test_displayRandomFromDirectFile();
  //test_loadFromDirectFile();
  test_loadRndomFromDirectFile();
  }


///////////////////////////////////////////////////////
// bool CODL::loadRndomFromDirectFile(char fName[], int m)
///////////////////////////////////////////////////////
/*
bool loadRndomFromDirectFile(char fNname[], int m)
Algorithm:
  empty *this object
  open file
  n = sizeOfFile/(sizeof(CNode)-4)
  for i=0 to n-1
    position filepointer to i*(sizeof(CNode)-4)
    read from the file in temp
    result = this->insert(temp)
    if result=false then return false
    end for

  close file
  return true
*/
bool CODL::loadRndomFromDirectFile(char fName[], int m)
  {
  ifstream inFile(fName, ios::in);
  if (!inFile.is_open())
    return false;

  inFile.seekg(0, ios::end);
  int pos = inFile.tellg();
  int n =  pos/(sizeof(CNode)-4);

  cout << "file size    = " << pos << " bytes" << endl;
  cout << "record size  = " << sizeof(CNode)-4 << endl;
  cout << "record count = " << n << endl;

  this->clearList();

  char temp[MAX_LENGTH];

  if (n >0)
    for (int j=1; j<=m; j++)
      {
      int i = rand()%n;
      inFile.seekg(i*MAX_LENGTH);
      inFile.read(temp, MAX_LENGTH);
      this->insert(temp);
      }

  inFile.close();
  return true;
  }


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

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

    myList.saveToDirectFile(fileName);

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

    int m = rand()%MAX_SIZE;

    yoList.loadRndomFromDirectFile(fileName, m);
    cout << "m = " << m << endl;
    cout << "After yoList.loadRndomFromDirectFile(fileName, m);\n";
    cout << "yoList   = "; yoList.display();

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


///////////////////////////////////////////////////////
// bool CODL::loadFromDirectFile(char fName[])
///////////////////////////////////////////////////////
/*
bool loadFromDirectFile(char fNname[])
Algorithm:
  empty *this object
  open file
  n = sizeOfFile/(sizeof(CNode)-4)
  for i=0 to n-1
    position filepointer to i*(sizeof(CNode)-4)
    read from the file in temp
    result = this->insert(temp)
    if result=false then return false
    end for

  close file
  return true
*/
bool CODL::loadFromDirectFile(char fName[])
  {
  ifstream inFile(fName, ios::in);
  if (!inFile.is_open())
    return false;

  inFile.seekg(0, ios::end);
  int pos = inFile.tellg();
  int n =  pos/(sizeof(CNode)-4);

  cout << "file size    = " << pos << " bytes" << endl;
  cout << "record size  = " << sizeof(CNode)-4 << endl;
  cout << "record count = " << n << endl;

  this->clearList();

  char temp[MAX_LENGTH];

  for (int i=0; i<=n-1; i++)
    {
    inFile.seekg(i*MAX_LENGTH);
    inFile.read(temp, MAX_LENGTH);
    this->insert(temp);
    }

  inFile.close();
  return true;
  }


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

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

    myList.saveToDirectFile(fileName);

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

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

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


////////////////////////////////////////////////////////
// bool displayRandomFromDirectFile(char fName[], int m)
////////////////////////////////////////////////////////
  /*
  open file
  n = sizeOfFile/(sizeof(CNode)-4)

  for j=1 to m
    i = random(0..n-1)
    position filepointer to i*(sizeof(CNode)-4)
    read from the file in temp
    diplay temp
    end for

  close file
  */
bool displayRandomFromDirectFile(char fName[], int m)
  {
  ifstream inFile(fName, ios::in);
  if(!inFile.is_open())
    return false;

  inFile.seekg(0, ios::end);
  int pos = inFile.tellg();
  int n =  pos/(sizeof(CNode)-4);
  cout << "file size    = " << pos << " bytes" << endl;
  cout << "record size  = " << sizeof(CNode)-4 << endl;
  cout << "record count = " << n << endl;

  char temp[MAX_LENGTH];

  cout << "diskFile = {";
  if (n >0)
    for (int j=1; j<=m; j++)
      {
      int i = rand()%n;
      inFile.seekg(i*MAX_LENGTH);
      inFile.read(temp, MAX_LENGTH);
      cout << temp << ' ';
      }

  cout << "}\n";
  inFile.close();
  return true;
  }


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

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

    myList.saveToDirectFile(fileName);
    int m = rand()%(2*MAX_SIZE);

    cout << "After displayRandomFromDirectFile(fileName, m);\n";
    cout << "where m = " << m << endl;

    displayRandomFromDirectFile(fileName, m);
    cout << "========================\n";
    }
  }



////////////////////////////////////////////////////////
// bool displayDirectFromDirectFile(char fName[])
////////////////////////////////////////////////////////
  /*
  void displayDirectFromDirectFile(char fNname[]);
  Algorithm:
    open file
    n = sizeOfFile/(sizeof(CNode)-4)
    for i=0 to n-1
      position filepointer to i*(sizeof(CNode)-4)
      read from the file in temp
      diplay temp
      end for

    close file
  */
bool displayDirectFromDirectFile(char fName[])
  {
  ifstream inFile(fName, ios::in);
  if (!inFile.is_open())
    return false;

  inFile.seekg(0, ios::end);
  int pos = inFile.tellg();
  int n =  pos/(sizeof(CNode)-4);

  cout << "file size    = " << pos << " bytes" << endl;
  cout << "record size  = " << sizeof(CNode)-4 << endl;
  cout << "record count = " << n << endl;

  char temp[MAX_LENGTH];

  cout << "diskFile = {";
  for (int i=0; i<=n-1; i++)
    {
    inFile.seekg(i*MAX_LENGTH);
    inFile.read(temp, MAX_LENGTH);
    cout << temp << ' ';
    }

  cout << "}\n";
  inFile.close();
  return true;
  }


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

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

    myList.saveToDirectFile(fileName);

    displayDirectFromDirectFile(fileName);
    cout << "========================\n";
    }
  }


////////////////////////////////////////////////////////
// bool displaySequentialFromDirectFile(char fName[])
////////////////////////////////////////////////////////
  /*
  void displaySequentialFromDirectFile(char fNname[]);
  Algorithm:
    open file
    n = sizeOfFile/(sizeof(CNode)-4)
    for i=0 to n-1
      position filepointer to i*(sizeof(CNode)-4)
      read from the file in temp
      diplay temp
      end for

    close file
  */
bool displaySequentialFromDirectFile(char fName[])
  {
  ifstream inFile(fName, ios::in);
  if (!inFile.is_open())
    return false;

  char temp[MAX_LENGTH];

  inFile.read(temp, MAX_LENGTH);

  cout << "diskFile = {";
  while (!inFile.eof())
    {
    cout << temp << ' ';
    inFile.read(temp, MAX_LENGTH);
    }

  cout << "}" << endl;
  inFile.close();
  return true;
  }


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

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

    myList.saveToDirectFile(fileName);

    displaySequentialFromDirectFile(fileName);
    cout << "========================\n";
    }
  }


////////////////////////////////////////////////////////
// bool saveToDirectFile(char fName[]) const
////////////////////////////////////////////////////////
  /*
  Algorithm:
    open file
    p = head->next
    while p->next != NULL
      write to file p->key
      advance p
      wend

    close file
    end algorithm
  */
bool CODL::saveToDirectFile(char fName[]) const
  {
  ofstream outFile(fName, ios::binary);
  if (!outFile.is_open())
    return false;
  
  CNode *p = this->head->next;

  while (p->next != NULL)
    {
    outFile.write(p->key, sizeof(CNode)-4);
    p = p->next;
    }

  outFile.close();
  return true;
  }


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

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

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


////////////////////////////////////////////////////////
// bool CODL::hasDistinct(void) const
////////////////////////////////////////////////////////
/*
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->loadFromSequentialFile(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.saveToSequentialFile(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";
    }
  }


///////////////////////////////////////////////////////
// bool CODL::loadFromSequentialFile(char fName[])
///////////////////////////////////////////////////////
bool CODL::loadFromSequentialFile(char fName[])
  {
  ifstream inFile(fName, ios::in);
  if (!inFile.is_open())
    return false;

  this->clearList();

  char temp[MAX_LENGTH];

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

  inFile.close();
  return true;
  }


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

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

    myList.saveToSequentialFile(fileName);

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

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

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


////////////////////////////////////////////////////////
//bool CODL::saveToSequentialFile(char fName[])
////////////////////////////////////////////////////////
bool CODL::saveToSequentialFile(char fName[]) const
  {
  ofstream outFile(fName, ios::out);
  if (!outFile.is_open())
    return false;

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

  outFile.close();
  return true;
  }


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

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

    myList.saveToSequentialFile(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)
  //ignore -inf and +inf from 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)
  //does not delete -inf and +inf
  {
  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)
  {
  this->init();

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

  while (m-- > 0)
    {
    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)
  {
  this->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) const
  {
  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) const
  {
  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) const
  {
  cout << "at " << this << " [";
  cout << key << ", ";
  cout << next << "]";
  }


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