OB_List03
[ Home ] [ Up ]

//Date:   2003.09.24
//File:   OB_List03.cpp
//Author: AOU

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


/*
maintain an ordered list of integeres

  testShuffle();
  testSortBubble();
  void shuffle(void);
  void sortBubble(void);

*/


////////////////////////////////////////
//constants
////////////////////////////////////////
const int MAX_SIZE = 25;
const int TEST_COUNT = 19;
const int MAX_VALUE = 15;
const int UNDEFINED = -911;


////////////////////////////////////////
//prototypes
////////////////////////////////////////
void testSortBubble(void);
void testInsert(void);
void testShuffle(void);
void testIsSorted(void);
void testPopulate(void);
void testConstructor(void);



////////////////////////////////////////
//class COList
////////////////////////////////////////
class COList
  {
  private:
    int a[MAX_SIZE];
    int n;
    void swap(int &x, int &y);
  public:
    COList(void);
    void display(void);
    void initialize(void);
    bool insert(int x);
    bool isSorted(void);
    void shuffle(void);
    void sortBubble(void);
    void populate(int n);
    COList(char ch);

  };


////////////////////////////////////////
//main
////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));

  /*
  COList myList, youList, hisList;
  myList.display();

  myList.insert(12);
  myList.display();

  myList.insert(16);
  myList.display();

  myList.insert(14);
  myList.display();
  //testInsert();
  //testShuffle();
  //testSortBubble();
  */
  ///testPopulate();
  //testIsSorted();
  //testShuffle();
  //testSortBubble();
  //testConstructor();
  COList myList('r');
  myList.display();
  COList yourList('r');
  yourList.display();

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

  /*
  if (myList == yourList)
    cout << "Go home\n";
  else
    cout << "Stay here\n";
  */
  }


void testConstructor(void)
  {
  cout << "++++++++++++++\n";
  cout << "testConstructor\n";
  cout << "++++++++++++++\n";

  for (int c=1; c<=TEST_COUNT; c++)
    {
    COList myList('c');

    myList.display();

    cout << "*****************\n";

    }
  }


COList::COList(char ch)
  {
  //(*this).initialize();
  this->initialize();
  //initialize();

  int n = rand()%(MAX_SIZE+1);
  (*this).populate(n);
  }


void COList::swap(int &x, int &y)
  {
  if (x != y)
    {
    int temp = x;
    x = y;
    y = temp;
    }
  };


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

  for (int c=1; c<=TEST_COUNT; c++)
    {
    COList myList('r');

    myList.display();


    myList.shuffle();

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

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

    cout << "*****************\n";

    }
  }



void COList::sortBubble(void)
  {
  int swaps;
  do 
    {
    swaps = 0;
    for (int i=0; i<=n-2; i++)
      if (a[i] > a[i+1])
        {
        swap(a[i], a[i+1]);
        swaps++;
        }

    } while (swaps!=0);

  }


void testShuffle(void)
  {
  cout << "+++++++++++\n";
  cout << "testShuffle\n";
  cout << "+++++++++++\n";

  for (int c=1; c<=TEST_COUNT; c++)
    {
    COList myList('r');


    myList.display();


    myList.shuffle();

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

    cout << "*****************\n";

    }
  }


void COList::shuffle(void)
  {
  for (int i=1; i<=n*n; i++)
    {
    int pick = rand()%n;
    swap (a[0], a[pick]);
    }

  }


void testPopulate(void)
  {
  cout << "++++++++++++\n";
  cout << "testPopulate\n";
  cout << "++++++++++++\n";

  for (int c=1; c<=TEST_COUNT; c++)
    {
    COList myList;

    int n = rand()%(MAX_SIZE+1);
    cout << "n = " << n << endl;
    myList.populate(n);

    myList.display();

    cout << "*****************\n";

    }
  }


void COList::populate(int n)
  {
  for (int i=1; i<=n; i++)
    {
    int x = rand()%(MAX_VALUE+1);
    (*this).insert(x);
    }
  }


void testIsSorted(void)
  {
  cout << "++++++++++++\n";
  cout << "testIsSorted\n";
  cout << "++++++++++++\n";

  for (int c=1; c<=TEST_COUNT; c++)
    {
    COList myList('r');

    myList.display();

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


    cout << "*****************\n";

    }
  }


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

  return true;
  }


void COList::initialize(void)
  {
  for (int i=0; i<=MAX_SIZE-1; i++)
    a[i] = UNDEFINED;

  n = 0;
  }

bool COList::insert(int x)
  {
  if (0 == n)
      {
      a[n] = x;
      n++;
      return true;
      };

  if (MAX_SIZE == n)
      return false;

  if (n > 0)
      {
      a[n] = x;
      n++;

      for (int i=n-1; i>=1; i--)
        {
        if (a[i] >= a[i-1]) return true;
        swap(a[i], a[i-1]);
        }

      return true;
      }

  return false;

  }


void COList::display(void)
  {
  cout << "a[" << n << "]: ";
  for (int i=0; i<=n-1; i++)
    cout << a[i] << ' ';

  cout << endl;
  }


COList::COList(void)
  {
  cout << "BEING INITIALIZED\n";
  initialize();
  }