COOL016
[ Home ] [ Up ]

// Date:   2005/10/21
// Author: AOU
// File:   COOL016.cpp

#include<iostream>
using namespace std;

/*
Description:
Examples:
Algorithms:
Code:
Output:
*/
/*
maintain Ordered Dense List, allow duplicate values
Operations:
  create (COOL myList; )
  populate (myList.populate(1,10);)
  populate (myList.populate(20);)
  populate (myList.populate("myList.dat");)
  shuffle (myList.shuffle();)
  insert  (myList.insert(45);)
  deleteByValue  (myList.delete(45);)
  display  (a.display();)
  deleteAll
  sort
  sum (a = myList.sum();)
  
*/
int const MAX_SIZE  =  10;
int const UNDEFINED = -6;
int const MIN_VALUE =  1;
int const MAX_VALUE =  9;
int const INFINITY  =  9999;
int const TEST_COUNT=  MAX_SIZE+10;


class COOL
  {
  private:
    int a[MAX_SIZE+2];
    int n;
    void swap(int &x, int &y);
  public:
    COOL(void);
    COOL(int n);

    void display(void) const;
    int insert(int x);
    int populate(int m);

    int populate(int n1, int n2); 
    //Project#2 with a test function
    //random values between n1 and n2
    //returns number of values added

    void shuffle(void);
    void sortBubble1(void);
    void sortBubble2(void); //p03
	  void displayDistinct(void) const; //p04
    void displayDistinctWithCounts(void) const; //p05

    friend bool isEqual(const COOL &list1, const COOL &list2);
    bool isEqual(const COOL &list2) const;
    bool operator ==(const COOL &list2) const;

    bool operator !=(const COOL &list2) const;


    int sum(void) const;
  private:
    void init(void);
  public:
    COOL(char ch); //r=>random, d=>distinct
    bool has(int x) const;
    int operator +(void) const;

    COOL(const COOL &aList);
    COOL & operator = (const COOL &aList);
    friend void merge(const COOL &aList, const COOL &bList, COOL &cList);//p06
    //cList should not have duplicate values due 10/21/2005

    bool deleteByPos(int p);

    int populate(char *fileName);


    int deleteByValue(int p);
    int deleteByValueAll(int p);
    int deleteByValueN(int p, int n);
    int deleteByValueLast(int p);
  };

//bool isEqual(const COOL &list1, const COOL &list2);

void test_insert(void);
void test_populate(void);
void test_shuffle(void);
void test_sortBubble1(void);
void test_sortBubble2(void);
void test_constructorN(void);
void test_isEqualFriend(void);
void test_isEqual(void);
void test_operator_isEqual(void);
void test_operator_isNotEqual(void);
void test_sum(void);
void test_constructorChar(void);
void test_has(void);
void test_operatorUniPlus(void);
void test_constructorCopy(void);
void test_operator_assign(void);
void test_mergeFriend(void);
void test_deleteByPos(void);


void main ()
  {
  //test_insert();
  //test_populate();
  //test_shuffle();
  //test_sortBubble1();
  //test_sortBubble2();
  //test_constructorN();
  //test_isEqualFriend();
  //test_isEqual();
  //test_operator_isEqual();
  //test_operator_isNotEqual();
  //test_sum();
  //test_constructorChar();
  //test_has();
  //test_operatorUniPlus();
  //test_constructorCopy();
  //test_operator_assign();
  //test_mergeFriend();
  test_deleteByPos();
  /*
  int a=4, b=5,c=6;
  cout << "a= " << a << endl;
  cout << "b= " << b << endl;
  cout << "c= " << c << endl;
  cout << "b=c" << (b=c) << endl;
  cout << "b= " << b << endl;
  a=(b=c);
  cout << endl;
  cout << "a= " << a << endl;
  cout << "b= " << b << endl;
  cout << "c= " << c << endl;
  */

 }

void test_deleteByPos(void)
  {
  cout << "--------------------\n";
  cout << "test_deleteByPos\n";
  cout << "--------------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL myList('r');

    myList.display();

    int p = -1 + rand()%(MAX_SIZE+1 - -1 + 1);

    cout << p << endl;

    bool result = myList.deleteByPos(p);

    myList.display();

    if (result)
      cout << "delete by position was a success\n";
    else
      cout << "delete by position was NOT a succes\n";

    cout << "........................\n";
    }

  }


/*
bool COOL::deleteByPos(int p)
Description:
  delete a value from a given valid position 
Example:
  {-inf, 5, 6, 9, +inf}, 2 => {-inf, 5, 9, +inf}, true
  {-inf, 5, 6, 9, +inf}, 0 => {-inf, 5, 6, 9, +inf}, false
  {-inf, 5, 6, 9, +inf}, 4 => {-inf, 5, 6, 9, +inf}, false
  {-inf, 5, 6, 9, +inf}, 9 => {-inf, 5, 6, 9, +inf}, false
  {-inf, 5, 6, 9, +inf},-9 => {-inf, 5, 6, 9, +inf}, false
Algorithm0:
  if p <= 0 or >= n-1 then 
    return false
  else
    delete the value at position p by shifting values to the left
    decrease n by 1
    return true
  end if

Algorithm1:
  if p <= 0 or >= n-1 then 
    return false
  else
    //delete the value at position p by shifting values to the left
    for i=p to n-2 step 1
      a[i] = a[i+1]
      end for
    a[n-1] = UNDEFINED
    decrease n by 1
    return true
  end if
*/
bool COOL::deleteByPos(int p)
  {
  if ((p <= 0) || (p >= n-1)) 
    return false;
  else
    //delete the value at position p by shifting values to the left
    {
    for (int i=p; i<=n-2; i++)
      a[i] = a[i+1];

    a[n-1] = UNDEFINED;
    n--;
    return true;
    }
  }


void test_mergeFriend(void)
  {
  cout << "----------------\n";
  cout << "test_mergeFriend\n";
  cout << "----------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL aList('r'), bList('r'), cList('r');
    aList.display();
    bList.display();
    cList.display();

    merge(aList, bList, cList);

    cout << "After merge(aList, bList, cList);\n";

    aList.display();
    bList.display();
    cList.display();

    cout << "........................\n";
    }

  }

/*
  merge(const COOL &aList, const COOL &bList, COOL &cList)
  Algorithm
  clear cList
  for each value x in aList do the following
    if x is not in cList then 
      insert x into cList
      end if
    end for

  for each value x in bList do the following
    if x is not in cList then 
      insert x into cList
      end if
    end for

*/
void merge(const COOL &aList, const COOL &bList, COOL &cList)
  {
  cout << "MISSING CODE\n";
  }




COOL & COOL::operator = (const COOL &aList)
  {
  cout << "Did you just call me?\n";

  for (int i=0; i<=MAX_SIZE+1; i++)
    this->a[i] = aList.a[i];

  this->n = aList.n;

  return *this;
  }


void test_operator_assign(void)
  {
  cout << "--------------------\n";
  cout << "test_operator_assign\n";
  cout << "--------------------\n";

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

    COOL yourList('r');
    yourList.display();

    COOL hisList('r');
    hisList.display();

    myList = yourList = hisList;

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

    myList.display();
    yourList.display();
    hisList.display();

    if (myList == yourList)
      cout << "myList == yourList\n";
    else
      cout << "myList != yourList\n";


    cout << "........................\n";
    }

  }



void test_constructorCopy(void)
  {
  cout << "--------------------\n";
  cout << "test_constructorCopy\n";
  cout << "--------------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL myList('r');

    myList.display();

    COOL yourList(myList);
    yourList.display();

    if (myList == yourList)
      cout << "myList == yourList\n";
    else
      cout << "myList != yourList\n";


    cout << "........................\n";
    }

  }



COOL::COOL(const COOL &aList)
  {
  cout << "You just called copy constructor\n";
  for (int i=0; i<=MAX_SIZE+1; i++)
    this->a[i] = aList.a[i];

  this->n = aList.n;
  }


void test_has(void)
  {
  cout << "--------------------\n";
  cout << "test_has\n";
  cout << "--------------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL myList('r');

    myList.display();

    int x = MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1);

    cout << x << endl;

    if (myList.has(x))
      cout << "has it\n";
    else
      cout << "DOES NOT have it\n";

    cout << "........................\n";
    }

  }


bool COOL::has(int x) const
  {
  if (2 == this->n)
    return false;

  for (int i=1; i<=this->n-2; i++)
    if (this->a[i] == x)
      return true;

  return false;
  }


void test_constructorChar(void)
  {
  cout << "--------------------\n";
  cout << "test_constructorChar\n";
  cout << "--------------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL myList('d');

    myList.display();

    COOL yourList('x');

    yourList.display();

    cout << "........................\n";
    }

  }


COOL::COOL(char ch)
  {
  init();

  if ('r' == ch)
    {
    int n = rand()%(MAX_SIZE+1);
    this->populate(n);
    }
  else if ('d' == ch)
    {
    //supply the missing code
    }
  }


void test_operatorUniPlus(void)
  {
  cout << "------------------------\n";
  cout << "test_operatorUniPlus\n";
  cout << "------------------------\n";

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

    myList.display();

    cout << "myList.sum() = " <<  +myList << endl;

    cout << "........................\n";
    }
  }


int COOL::operator +(void) const
  {
  int result = 0;
  for (int i=1; i<=n-2; i++)
    result = result + a[i];

  return result;
  }



void test_sum(void)
  {
  cout << "------------------------\n";
  cout << "test_sum\n";
  cout << "------------------------\n";

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

    myList.display();

    cout << "myList.sum() = " << myList.sum() << endl;

    cout << "........................\n";
    }
  }


int COOL::sum(void) const
  {
  int result = 0;
  for (int i=1; i<=n-2; i++)
    result = result + a[i];

  return result;
  }


void test_operator_isNotEqual(void)
  {
  cout << "------------------------\n";
  cout << "test_operator_isNotEqual\n";
  cout << "------------------------\n";

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

    int m = rand()%MAX_SIZE;
    COOL yourList(m);

    myList.display();
    yourList.display();

    if (myList.operator !=(yourList))
      cout << "myList is NOT equal to yourList\n";
    else
      cout << "myList is equal to yourList\n";

    cout << "myList = yourList;\n";
    myList = yourList;
    myList.display();
    yourList.display();

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


    cout << "........................\n";
    }
  }


bool COOL::operator !=(const COOL &list2) const
  {
  return !(*this == list2);
  /*
  if (*this == list2)
    return false;
  else
    return true;
  */
  /*
  if (n != list2.n)
    return true;

  if (n <= 2)
    return false;

  for (int i=0; i<=n-1; i++)
    if (a[i] != list2.a[i])
      return true;

  return false;
  */
  }


void test_operator_isEqual(void)
  {
  cout << "------------\n";
  cout << "test_operator_isEqual\n";
  cout << "------------\n";

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

    int m = rand()%MAX_SIZE;
    COOL yourList(m);

    myList.display();
    yourList.display();

    if (myList.operator ==(yourList))
      cout << "myList is equal to yourList\n";
    else
      cout << "myList is NOT equal to yourList\n";

    cout << "myList = yourList;\n";
    myList = yourList;
    myList.display();
    yourList.display();

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


    cout << "........................\n";
    }
  }


bool COOL::operator ==(const COOL &list2) const
  {
  if (n != list2.n)
    return false;

  if (n <= 2)
    return true;

  for (int i=0; i<=n-1; i++)
    if (a[i] != list2.a[i])
      return false;

  return true;
  }


void test_isEqual(void)
  {
  cout << "------------\n";
  cout << "test_isEqual\n";
  cout << "------------\n";

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

    int m = rand()%MAX_SIZE;
    COOL yourList(m);

    myList.display();
    yourList.display();

    if (myList.isEqual(yourList))
      cout << "myList is equal to yourList\n";
    else
      cout << "myList is NOT equal to yourList\n";

    cout << "myList = yourList;\n";
    myList = yourList;
    myList.display();
    yourList.display();

    if (myList.isEqual(yourList))
      cout << "myList is equal to yourList\n";
    else
      cout << "myList is NOT equal to yourList\n";


    cout << "........................\n";
    }
  }


bool COOL::isEqual(const COOL &list2) const
  {
  if (n != list2.n)
    return false;

  if (n <= 2)
    return true;

  for (int i=0; i<=n-1; i++)
    if (a[i] != list2.a[i])
      return false;

  return true;
  }


void test_isEqualFriend(void)
  {
  cout << "------------------\n";
  cout << "test_isEqualFriend\n";
  cout << "------------------\n";

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

    int m = rand()%MAX_SIZE;
    COOL yourList(m);

    myList.display();
    yourList.display();

    if (isEqual(myList, yourList))
      cout << "myList is equal to yourList\n";
    else
      cout << "myList is NOT equal to yourList\n";

    cout << "myList = yourList;\n";
    myList = yourList;
    myList.display();
    yourList.display();

    if (isEqual(myList, yourList))
      cout << "myList is equal to yourList\n";
    else
      cout << "myList is NOT equal to yourList\n";


    cout << "........................\n";
    }
  }


bool isEqual(const COOL &list1, const COOL &list2)
  {
  if (list1.n != list2.n)
    return false;

  if (list1.n <= 2)
    return true;

  for (int i=0; i<=list1.n-1; i++)
    if (list1.a[i] != list2.a[i])
      return false;

  return true;
  }


void test_constructorN(void)
  {
  cout << "-----------------\n";
  cout << "test_constructorN\n";
  cout << "-----------------\n";

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

    myList.display();

    cout << "........................\n";
    }
  }


COOL::COOL(int n)
  {
  //a[0] = -INFINITY;
  //a[1] = +INFINITY;

  //for (int i=2; i<=MAX_SIZE+1; i++)
  //  a[i] = UNDEFINED;

  //this->n = 2;

  this->init();

  this->populate(n);
  }


/*
Description: 
  displays distinct values from the list
Examples:
  [-inf, 1, 1, 1, 2, 5, 5, +inf] => 
   -inf  1
   1     3
   2     1
   5     2
   +inf  1

Algorithms0:
  print the first value
  do the following for the rest of the values
    if the next value != value printed 
      print next value, prinedValue=nextValue

    
Algorithms0:
  i=0
  x=a[i]
  print x
  do the following for i=1 to n-1
    if a[i] != x then
       x = a[i]
       print x
       end if
    end do



Code:
Output:
*/
void COOL::displayDistinctWithCounts(void) const //p04
  {
  /*
  */
  }
/*
Description: 
  displays distinct values from the list
Examples:
  [-inf, 1, 1, 1, 2,+inf] => -inf, 1, 2, +inf
Algorithms0:
  print the first value
  do the following for the rest of the values
    if the next value != value printed 
      print next value, prinedValue=nextValue

    
Algorithms0:
  i=0
  x=a[i]
  print x
  do the following for i=1 to n-1
    if a[i] != x then
       x = a[i]
       print x
       end if
    end do



Code:
Output:
*/
void COOL::displayDistinct(void) const //p04
  {
  }


void test_sortBubble2(void)
  {
  cout << "------------\n";
  cout << "test_sortBubble2\n";
  cout << "------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL myList;

    int m = rand()%MAX_SIZE;
    int p = myList.populate(m);

    myList.display();

    myList.shuffle();

    cout << "After shuffle\n";

    myList.display();

    myList.sortBubble2();

    cout << "After sortBubble2\n";

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

/*
sortBubble2

Description:
  sort in increasing order
Examples:
  [-inf,6,2,3,+inf] => [-inf,2,3,6,+inf]
Algorithm0:
  Possibilities: n<=3,n>3

  if n<=3 then exit
  do
    {
    sorted=true
    scan values from left to right
      if a pair is out of order then
        swap the values and set sorted=false
    }
    while (!sorted)


Algorithm1:
  if n<=3 then exit
  do
    {
    sorted=true
    for i=1 to n-3 do the following
      if a[i]>a[i+1] then
        swap a[i], a[i+1]
        sorted=false
        end if
      next i
    }
    while (!sorted)
    
Code:
Output:
*/

void COOL::sortBubble2(void)
  {
  //supply the code Project #03
  //due 9/26/2005
  }


void test_sortBubble1(void)
  {
  cout << "------------\n";
  cout << "test_sortBubble1\n";
  cout << "------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL myList;

    int m = rand()%MAX_SIZE;
    int p = myList.populate(m);

    myList.display();

    myList.shuffle();

    cout << "After shuffle\n";

    myList.display();

    myList.sortBubble1();

    cout << "After sortBubble1\n";

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

/*
Description:
  sort in increasing order
Examples:
  [-inf,6,2,3,+inf] => [-inf,2,3,6,+inf]
Algorithms:
  Possibilities: n<=3,n>3

  if n<=3 then exit
  for i=1 to m-1
    try to put values in order
    next i


  if n<=3 then exit
  for i=1 to n-3
    for j=1 to n-3
      if a[j] > a[j+1] then 
         swap a[j],a[j+1]
      next j
    next i

    
Code:
Output:
*/
void COOL::sortBubble1(void)
  {
  if (n<=3)
    return;
  for (int i=1; i<=n-3; i++)
    for (int j=1; j<=n-3; j++)
      if (a[j] > a[j+1]) swap(a[j],a[j+1]);
  }


void COOL::swap(int &x, int &y)
  {
  int t=x;
  x = y;
  y = t;
  }


void test_shuffle(void)
  {
  cout << "------------\n";
  cout << "test_shuffle\n";
  cout << "------------\n";

  for (int i=1; i<=TEST_COUNT; i++)
    {
    COOL myList;

    int m = rand()%MAX_SIZE;
    int p = myList.populate(m);

    myList.display();

    myList.shuffle();

    cout << "After shuffle\n";

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

/*
Description:
  Shuffles the values in the list
  do not touch -INFINITY and +INFINITY
Example:
Algorithm:
  Scheme1: Shift to left or right
  Scheme2: swap two randomly chosen values
  Scheme3: move a randomly chosen value to the top/bottom
  Scheme4: move a randomly chosen value to another random position
  Scheme5: move lower approx half to the top
  Scheme6: Split and bridge
  Scheme7: Pick random value and move to a new list

  Scheme2:
    do the following n times
      pick p1, p2 randomly between 1 and n-2
      swap values at p1 and p2
*/
void COOL::shuffle(void)
  {
  if (n <= 3)
    return;

  for (int i=1; i<=n; i++)
    {
    int p1 = 1 + rand()%(n-2 - 1 + 1);
    int p2 = 1 + rand()%(n-2 - 1 + 1);
    //cout << "n=" << n << " p1=" << p1 << " p2=" << p2 << endl;
    //cout << "before swap " << a[p1] << " " << a[p2] << endl;
    swap(a[p1], a[p2]);
    //cout << "after  swap " << a[p1] << " " << a[p2] << endl;
    }
  }


void test_populate(void)
  {
  COOL myList;
  myList.display();
  for (int i=1; i<=TEST_COUNT; i++)
    {
    int m = rand()%MAX_SIZE;
    int p = myList.populate(m);
    cout << "asked for m = " << m << " inserted " << p << " values\n";
    myList.display();
    }
  }

/*
Description:
  insert m random values into an existing no-empty list
  returns the actual number of items added
Example:
Algorithm:
  count = 0
  for i=1 to m
    x = random value bet min and max
    insert x into the list
    if overflow then break else count++
    next i

  return count
*/
int COOL::populate(int m)
  {
  int count = 0;
  for (int i=1; i<=m; i++)
    {
    int x = MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1);
    //int p = myList.insert(x);
    //int p = (*this).insert(x);
    //int p = this->insert(x);
    int p = insert(x);
    //this->display();
    if (p != -1)
      count++;
    else
      break;
    }

  return count;
  }


void test_insert(void)
  {
  COOL myList;
  myList.display();
  for (int i=1; i<=TEST_COUNT; i++)
    {
    //int x = rand()%MAX_VALUE; //p1: change to get values fro -10 to 10
    // -11, -10, -9, -8, ..., 0, 1, 2, ..., 9, 10
    // -11 + (0, 1, ..., 21)
    // MIN_VALUE + (0... (MAX_VALUE-MIN_VALUE))
    // MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1)
    int x = MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1);
    int p = myList.insert(x);
    myList.display();
    if (p != -1)
      cout << "Value " << x << " was inserted at " << p << " location\n";
    else
      cout << "Overflow\n";
    }
  }

/*
int COOL::insert(int x)
inserts x into the list keeping it in order
possibilities:
  (a) x is out of range
  (b) x is in range
      (c) list is empty
      (d) x >= the last value in the list
      (e) x < the first value in the list
      (f) x is between two values in the list

Solutions:
  (a) add to the end and sort
  (b) four cases
  (c) start with dummy values and just one case

Chosen
  start with dummy values and have just one case
  insert x in the list
  a[n] = x
  check if a[n-1] <= a[n] return n
           else swap a[n-1], a[n]
  check if a[n-2] <= a[n-1] return n-1
           else swap a[n-2], a[n-1]
           ....
  check if a[0] <= a[1] return 1
           else swap a[0], a[1] will never happen


  m=n
  a[m] = x
  while (a[m-1] > a[m])
    swap a[m-1], a[m]
    m--
    end while
  
  n++
  return m
*/
int COOL::insert(int x)
  {
  if (n>=(MAX_SIZE+2))//??
    return -1;

  int m=n;
  a[m] = x;

  while (a[m-1] > a[m])
    {
    int temp = a[m-1];
    a[m-1] = a[m];
    a[m] = temp;
    m--;
    }
  
  n++;
  return m;
  }


void COOL::display(void) const
  {
  //cout << "COOL[" << n << "]: ";

  //for (int i=0; i<=MAX_SIZE+1; i++)
  //  cout << a[i] << ' ';
  //
  //cout << endl;

  cout << "COOL[" << n-2 << "]: ";

  for (int i=1; i<=n-2; i++)
    cout << a[i] << ' ';
  
  cout << endl;
  }

  
COOL::COOL(void)
  {
  cout << "Default constructor is called\n";
  this->init();
  }


void COOL::init(void)
  {
  a[0] = -INFINITY;
  a[1] = +INFINITY;

  for (int i=2; i<=MAX_SIZE+1; i++)
    a[i] = UNDEFINED;

  n = 2;
  }