COOL005
[ Home ] [ Up ]

// Date:   2005/09/07
// Author: AOU
// File:   COOL005.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  =  40;
int const UNDEFINED = -99;
int const MIN_VALUE =  1;
int const MAX_VALUE =  6;
int const INFINITY  =  9999;
int const TEST_COUNT=  MAX_SIZE+5;



class COOL
  {
  private:
    int a[MAX_SIZE];
    int n;
  public:
    COOL(void);
    void display(void);
    int insert(int x);
    int populate(int m);

    int populate(int n1, int n2);
    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 main ()
  {
  test_insert();
  }

/*
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 bet min and max
    insert x into the list
    if overflow then break else count++
    next i

  return count
*/
int COOL::populate(int m)
  {
  }


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;
  }