p004
[ Home ] [ Up ]

//file: p004.cpp
//Author: AOU
//Date 08/30/2004

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


int const MAX_SIZE = 20+2;
int const INFINITY = 9999; 
int const TEST_COUNT = 15;
int const MAX_VALUE = 20;

/*
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:

void initialize(int a[], int &n);
bool insert(int a[], int &n, int x);
void display(int a[], int n);

bool isSorted(int a[], int n);

void test_initialize(void);

void main(void)
  {
  srand(time(NULL));
  test_initialize();
  }


// bool isSorted(int a[], int n)
/*
Description: checks if the list is in order
Example:
Algorithm:

*/
bool isSorted(int a[], int n)
  {
  for (int i=0; i<=n-2; i++)
    if (a[i] > a[i+1])
      return false;

  return true;
  }



void test_initialize(void)
  {
  int myArray[MAX_SIZE];
  int m;

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

      int p = rand()%m;
      x = myArray[p];
      myArray[p] = 10;

      display(myArray, m);
      if (isSorted(myArray, m))
        cout << "List is in order\n";
      else
        cout << "List is NOT in order\n";

      myArray[p] = x;

      }
    }

  }


////////////////////////////////////////////////////////
//void initialize(int a[], int &n)
////////////////////////////////////////////////////////
/*
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


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

  }


////////////////////////////////////////////////////////
//bool insert(int a[], int &n, 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}
Algorithm:
  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

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


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

  a[m] = x
  n++

*/
bool insert(int a[], int &n, 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 display(int a[], int n)
////////////////////////////////////////////////////////
/*
Description:
Algorithm:
*/
void display(int a[], int n)
  {
  for (int i=0; i<=n-1; i++)
    cout << a[i] << ' ';

  cout << endl;
  }