COOL007
[ Home ] [ Up ]

// Date:   2005/12/09
// Author: AOU
// File:   COOL007.cpp

#include<iostream>
using namespace std;

/*
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 = -99;
int const MIN_VALUE =  1;
int const MAX_VALUE =  9;
int const INFINITY  =  9999;
int const TEST_COUNT=  MAX_SIZE+5;



class COOL
  {
  private:
    int a[MAX_SIZE];
    int n;
    void swap(int &x, int &y);
  public:
    COOL(void);
    void display(void);
    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

    int populate(char *fileName);
    void shuffle(void);
    void sortBubble(void);
    bool deleteByPos(int p);

    int deleteByValue(int p);
    int deleteByValueAll(int p);
    int deleteByValueN(int p);
    int deleteByValueLast(int p);

    int sum(void);


  };


void test_insert(void);
void test_populate(void);
void test_shuffle(void);

void main ()
  {
  //test_insert();
  //test_populate();
  test_shuffle();
  }

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)
    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)
  {
  cout << "COOL[" << n << "]: ";

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

  cout << endl;

  }
  
COOL::COOL(void)
  {
  cout << "Default constructor is called\n";
  a[0] = -INFINITY;
  a[1] = +INFINITY;

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

  n = 2;
  }