COOL007
[ Home ] [ Up ]

//file: COOL007.cpp
//Author: AOU
//Date 09/17/2004


////////////////////////////////////////////////////////
// Assignment 02, Date Assigned 9/13/2004, Due: 9/20/2004
////////////////////////////////////////////////////////
/* 
  As discussed in the class, implement the following member 
  functions and corresponding test functions:

    bool deleteByPos(int p);
    int deleteByValue(int v, int c);

Submit the printed form of the following:

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

Sample output:

*/
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////


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


////////////////////////////////////////////////////////
// constants
////////////////////////////////////////////////////////
int const MAX_SIZE = 10+2;
int const INFINITY = 9999; 
int const TEST_COUNT = 20;
int const MAX_VALUE = 2;

/*
Description:
Example:
Algorithm:
*/

//Problem:  
//  List of values (duplicates allowed) kept in order 
//  with several operations:
//  initialize, insert, delete, modify, search, ...
//Example: 
//  {}, {50}, {25,50}, {25,36,50}, {25,36,50,76},
//  {25,36,50,76}
//Algorithms:


////////////////////////////////////////////////////////
// class COOL
////////////////////////////////////////////////////////
class COOL
  {
  private:
    int a[MAX_SIZE];
    int n;
    void swap(int &v1, int &v2)
      {
      int t = v1;
      v1 = v2;
      v2 = t;
      };

  public:
    COOL(void);
    bool insert(int x);
    void display(void) const;
    bool isSorted(void)const;
    COOL(int m);
    int search(int x) const;
    void search(int x, int &p, int &c) const;
    void shuffle(void);

    void sortBubble1(void);

    bool deleteByPos(int p);
    int deleteByValue(int v, int c);

    void sortBubble2(void);

    friend bool isEqualTo(COOL firstList, COOL secondList);

    bool isEqualTo(COOL secondList);
    bool operator ==(COOL secondList);
  };


////////////////////////////////////////////////////////
// test function prototypes
////////////////////////////////////////////////////////
void test_initialize(void);
void test_constructor(void);
void test_search(void);
void test_search2(void);

void test_shuffle(void);

void test_sortBubble1(void);
void test_sortBubble2(void);

void test_deleteByPos(void);
void test_deleteByValue(void);

void test_isEqualToFriend(void);
void test_isEqualTo(void);
void test_isEqualToOperator(void);


////////////////////////////////////////////////////////
// main
////////////////////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));
  //test_initialize();
  //test_constructor();
  //test_search();
  //test_search2();
  //test_shuffle();
  //test_sortBubble1();
  //test_sortBubble2();
  //test_deleteByPos();
  //test_deleteByValue();

  //test_isEqualToFriend();
  test_isEqualTo();
  //test_isEqualToOperator();
  }


////////////////////////////////////////////////////////
// bool COOL::operator ==(COOL secondList)
////////////////////////////////////////////////////////
bool COOL::operator ==(COOL secondList)
  {
  if ((0==n) && (0==secondList.n))
    return true;
  else if (n != secondList.n)
    return false;
  else
    for (int i=0; i<=n-1; i++)
      if (a[i] != secondList.a[i]) 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;
    COOL myList(m);
    myList.display();

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

    //if (isEqualTo(myList, yourList))
    //if (myList.isEqualTo(yourList))
    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 (isEqualTo(myList, yourList))
    //if (myList.isEqualTo(yourList))
    if (myList == yourList)
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";

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


////////////////////////////////////////////////////////
// bool COOL::isEqualTo(COOL secondList)
////////////////////////////////////////////////////////
bool COOL::isEqualTo(COOL secondList)
  {
  if ((0==n) && (0==secondList.n))
    return true;
  else if (n != secondList.n)
    return false;
  else
    for (int i=0; i<=n-1; i++)
      if (a[i] != secondList.a[i]) return false;

  return true;
  }


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

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

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

    //if (isEqualTo(myList, yourList))
    if (myList.isEqualTo(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 (isEqualTo(myList, yourList))
    //if (myList == yourList)
    if (myList.isEqualTo(yourList))
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";


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


////////////////////////////////////////////////////////
// bool isEqualTo(COOL firstList, COOL secondList)
////////////////////////////////////////////////////////
/*
Description:
Example:
Algorithm:
  if both lists are empty then
    return true
  else if their sizes are different then
    return false
  else
    for i=0 to n-1
      if firstList.a[i] <> secondList.a[i] 
         then return false
      end for
  end if

  return true

*/
bool isEqualTo(COOL firstList, COOL secondList)
  {
  if ((0==firstList.n) && (0==secondList.n))
    return true;
  else if (firstList.n != secondList.n)
    return false;
  else
    for (int i=0; i<=firstList.n-1; i++)
      if (firstList.a[i] != secondList.a[i]) return false;

  return true;
  }


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

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

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

    if (isEqualTo(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 (isEqualTo(myList, yourList))
    //if (myList == yourList)
        cout << "Lists are equal\n";
      else
        cout << "Lists are NOT equal\n";


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


////////////////////////////////////////////////////////
// bool COOL::deleteByPos(int p)
////////////////////////////////////////////////////////
/*
Description: 
Example:
 [-inf,20, 30, 40, +inf], 0 =>nothing
 [-inf,20, 30, 40, +inf], 1 =>[-inf, 30, 40, +inf]
 [-inf,20, 30, 40, +inf], 3 =>[-inf,20, 30, +inf]
Algorithm:
 n=2, p<0, p=0, p=n-1 =>nothing
 p=1..n-2
   shift values to left starting at p+1
   
*/
bool COOL::deleteByPos(int p)
  {
  //supply the code that works
  return true;
  }


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

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

    int p = rand()%(MAX_SIZE+1);
    cout << "Trying to delete value at position " << p << endl;
    if (myList.deleteByPos(p))
      cout << "deleteByPos was successful\n";
    else
      cout << "deleteByPos was NOT successful\n";

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


////////////////////////////////////////////////////////
// int COOL::deleteByValue(int v, int c)
////////////////////////////////////////////////////////
/*
Description:
Example:
 [-inf,20,30,40,40,+inf], 20,5 =>[-inf,30,40,40,+inf], 1
 [-inf,20,30,40,40,+inf], 40,5 =>[-inf,20,30,+inf], 2
 [-inf,20,30,40,40,+inf], 40,1 =>[-inf,20,30,40,+inf], 1
Algorithm:

*/
int COOL::deleteByValue(int v, int c)
  {
  //supply the code that works
  return 0;
  }


////////////////////////////////////////////////////////
// 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;
    COOL myList(m);
    myList.display();

    int v = rand()%(MAX_VALUE+1);
    int c = rand()%MAX_SIZE;

    cout << "Trying to delete "  << c << " copies of value " << v << endl;

    int deleted = myList.deleteByValue(v, c);

    if (deleted > 0)
        {
        cout << "deleteByValue was successful\n";
        cout << "Deleted "  << deleted << "copies of value " << v << endl;
        }
      else
        cout << "deleteByValue was NOT successful\n";

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


////////////////////////////////////////////////////////
// void COOL::sortBubble2(void);
////////////////////////////////////////////////////////
/*
do the following
  sorted = true
  check the list left to right
    if a bad pair found swap, set sorted to false
  while not sorted
*/
void COOL::sortBubble2(void)
  {
  bool sorted;
  do 
    {
    sorted = true;
    for (int j=0; j<=n-1; j++)
      {
      if (a[j] > a[j+1]) 
        {
        swap(a[j], a[j+1]);
        sorted = false;
        }
      }
    }
    while (!sorted);
  }


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

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

    myList.shuffle();
    cout << "After shuffle\n";
    myList.display();

    myList.sortBubble2();
    cout << "After sortBubble2\n";
    myList.display();

    if (myList.isSorted())
        cout << "List is sorted\n";
      else
        cout << "List is NOT sorted\n";
    cout << "------------------------\n";
    }
  }


////////////////////////////////////////////////////////
// void COOL::sortBubble1(void);
////////////////////////////////////////////////////////
/*
-99,1, 2, 3, 4, 5,+99
for i = 1 to n-1
  for j=0 to n-2
    if a[i] > a[i+1] then 
        swap a[i], a[i+1]
    end for
  end for
*/
void COOL::sortBubble1(void)
  {
  for (int i = 1; i<=n-1; i++)
    {
    for (int j=0; j<=n-2; j++)
      {
      if (a[j] > a[j+1]) 
          swap(a[j], a[j+1]);
      }
    }
  }


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

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

    myList.shuffle();
    cout << "After shuffle\n";
    myList.display();

    myList.sortBubble1();
    cout << "After sortBubble1\n";
    myList.display();

    if (myList.isSorted())
        cout << "List is sorted\n";
      else
        cout << "List is NOT sorted\n";
    cout << "------------------------\n";
    }
  }

  
////////////////////////////////////////////////////////
// void COOL::shuffle(void)
////////////////////////////////////////////////////////
/*
Description:
  shuffles/scramble/unsort/re-organize/shake
Example:
  [-99, 12, 24, 24 99]=>[-99, 24, 12, 24 99] 
Algorithm:
 randomly pick two values and swap
 delete a value randomly while building another sequentially
 split the list into two sublists and merge them randomly
 randomly pick a value and swap it with the first value
   do the following n*n
     p = random value between 1 and n-2
     swap a[1] with a[p]
*/
void COOL::shuffle(void)
  {
  if (n<=3)
    return;

  for (int i=1; i<=n*n; i++)
    {
    int p = 1 + rand()%(n-2);
    swap(a[1],a[p]);
    }
  }


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

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

    myList.shuffle();
    cout << "After shuffle\n";
    myList.display();

    cout << endl;
    }
  }

  
////////////////////////////////////////////////////////
// void COOL::search(int x, int &p, int &c)
////////////////////////////////////////////////////////
/*
Description: searches for copies of x in the list,
  in p returns the position, in c returns the number 
  of copies of x starting at p.
Example:
  [-99, 12, 24, 24, 24, 45, 50, 60, 75, 99], 24 
    => 2, 3
    => at positions 2, 3, 4
Algorithm:
*/
void COOL::search(int x, int &p, int &c) const
  {
  /*
  Code to be replaced
  p=1;
  c=3;
  */
  for (int i=1; i<=n-2; i++)
    {
    if (x == a[i]) 
        {
        p=i;
        c=1;
        for (int j=i+1; j<=n-2; j++)
          {
          if (x==a[j])
              c++;
            else
              return;
          }
        return;
        }

    if (x < a[i])  
        break;
    }

  c=0;
  p=-1;
  }




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

  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    COOL myList(m);
    myList.display();
    int x = rand()%(MAX_VALUE +1);
    cout << "Searching for " << x << endl;
    int p, c;

    myList.search(x, p, c);

    cout << "Found "  << c << " copies of " << x << " starting at position " << p << endl;

    cout << "In other words, " << x << " was found at positions ";
    for (int j=p; j<=p+c-1; j++)
      cout << j << ' ';

    cout << endl << endl;

    }
  }

  
////////////////////////////////////////////////////////
// int COOL::search(int x)
////////////////////////////////////////////////////////
/*
Description: searches for the first value x in the list 
  and returns the position if found else returns -1
Example:
  [-99, 12, 24, 45, 50, 60, 75, 99], 24 => 2
  [-99, 12, 24, 45, 50, 60, 75, 99], 25 => -1
Algorithm:
  for i=1 to n-2
    if x = a[i] then 
        return i
    if x < a[i] then 
        exit loop
    end for

  return -1

*/
int COOL::search(int x) const
  {
  for (int i=1; i<=n-2; i++)
    {
    if (x == a[i]) 
        return i;
    if (x < a[i])  
        break;
    }

  return -1;
  }


////////////////////////////////////////////////////////
// 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;
    COOL myList(m);
    myList.display();
    int x = rand()%(MAX_VALUE +1);
    cout << "Searching for " << x << endl;
    cout << "Found at "  << myList.search(x) << endl;
    }
  }


////////////////////////////////////////////////////////
// COOL::COOL(int m)
////////////////////////////////////////////////////////
//create a list with m values
COOL::COOL(int m)
  {
  n = 2;
  a[0] = -INFINITY;
  a[1] = +INFINITY;
  for (int i=2; i<=MAX_SIZE-1; i++)
    a[i] = 0;

  for (i=1; i<=m; i++)
    {
    int x = rand()%(MAX_VALUE+1);
    insert(x);
    }
  }


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

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


////////////////////////////////////////////////////////
// bool COOL::isSorted(void)
////////////////////////////////////////////////////////
// bool isSorted(int a[], int n)
/*
Description: checks if the list is in order
Example:
Algorithm:
*/
bool COOL::isSorted(void) const
  {
  for (int i=0; i<=n-2; i++)
    if (a[i] > a[i+1])
      return false;

  return true;
  }


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

  COOL myList;

  for (int i=1; i<=TEST_COUNT/TEST_COUNT; i++)
    {
    //myList.initialize(); //initialize(myArray, m);
    myList.display();// display(myArray, m);
    int j, x;
    for (j=1; j<=TEST_COUNT; j++)
      {
      x = rand()%(MAX_VALUE+1);
      myList.insert(x); //insert(myArray, m, x);
      myList.display(); //display(myArray, m);
      if (myList.isSorted()) //(isSorted(myArray, m))
        cout << "List is in order\n";
      else
        cout << "List is NOT in order\n";
      }
    }
  }


////////////////////////////////////////////////////////
// COOL::COOL(void)
////////////////////////////////////////////////////////
/*
Description:
Initializes the list of values by setting n=0, and
a[0..MAX_SIZE-1] = 0;
Algorithm:
  n = 2
  a[0] = -INFINITY
  for i=1 to MAX_SIZE-2
    a[i] = 0;

  a[MAX_SIZE-1] = +INFINITY
*/
COOL::COOL(void)
  {
  n = 2;
  a[0] = -INFINITY;
  a[1] = +INFINITY;
  for (int i=2; i<=MAX_SIZE-1; i++)
    a[i] = 0;

  }


////////////////////////////////////////////////////////
// bool COOL::insert(int x)
////////////////////////////////////////////////////////
/*
Description: inserts x into the list and maintains the order
Example: 
  {}, {50}, {25,50}, {25,36,50}, {25,36,50,76},
  {25,36,50,76}
Algorithm0:
  Case0: list is full

  Case1: x goes to empty list

  x Case3: x > all the values in the list
  x Case2: x < all the values in the list
  Case4: x goes between two values and handle duplicates

Algorithm1:
  m = n
  s1: if (x >= a[m-1]) then
      a[m] = x
      n++
      exit function
    else
      a[m] = a[m-1]
      m--
      goto s1


Algorithm2:
  m = n
  while x < a[m-1])
    a[m] = a[m-1]
    m--
    wend

  a[m] = x
  n++

*/
bool COOL::insert(int x)
  {
  if (n >= MAX_SIZE)
    return false;

  int m = n;

  while (x < a[m-1])
    {
    a[m] = a[m-1];
    m--;
    }

  a[m] = x;
  n++;
  return true;
  }


////////////////////////////////////////////////////////
// void COOL::display(void)
////////////////////////////////////////////////////////
/*
Description:
Algorithm:
*/
void COOL::display(void) const
  {
  cout << "COOL[" << n-2 << "] = [";
  for (int i=0; i<=n-1; i++)
    cout << a[i] << ' ';

  cout << "]\n";
  }