cArray09
[ Home ] [ Up ]

//Date:   2003.02.24
//Author: AOU
//File:   cArray09.cpp



/*
Added the following member functions:
  void frag (void); 
  void testFrag(void);

*/


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


///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 10; //maximum size of array
const int MAX_VALUE = 5;
const int UNDEFINED = -9;


///////////////////////////////////////////////////////////
// prototypes
///////////////////////////////////////////////////////////
void testSearchSeq(void);
void testAreDistinct(void);
void testConstructorR(void);
void testSortBubble(void);
void testDisplayAll(void);
void testIsSorted(void);
void testShuffle(void);

void testFrag(void);

///////////////////////////////////////////////////////////
// class CArray
///////////////////////////////////////////////////////////
class CArray
  {
  private:
    int m_a[MAX_COUNT];
    int m_n;
    void swap(int &x, int &y);
  public:
    CArray(void);
    CArray(int m); 
    void display(void) const;
    void displayMultiple(int c) const;
    void populate(void);
    bool areDistinct(void) const; 
    bool searchSeq(int x) const;
    CArray(char ch);
    void sortBubble(void);
    void displayAll(void) const;
    bool isSorted(void);
    void shuffle(void);

    void frag(void);

  };


///////////////////////////////////////////////////////////
// void main(void)
///////////////////////////////////////////////////////////
void main(void)
  {
  //srand(time(NULL));
  // srand(2);
  // testSearchSeq();
  // testAreDistinct();
  // testConstructorR();
  // testSortBubble();
  // testDisplayAll();
  // testIsSorted();
  // testShuffle();
  testFrag();
  }


///////////////////////////////////////////////////////////
// void testFrag(void)
///////////////////////////////////////////////////////////
void testFrag(void)
  {
  cout << "testFrag\n";
  cout << "========\n";

  for (int i=1; i<=10; i++)
    {
    cout << "Case #" << i << endl;

    CArray myArray('r');

    myArray.displayAll();

    myArray.frag();

    cout << "After frag\n";

    myArray.displayAll();

    cout << "------------------------\n";

    }
  }


///////////////////////////////////////////////////////////
// void frag(void);
///////////////////////////////////////////////////////////
/*
Description:
  Fragments/scatters/unpack the values in the array
Example:
  [1, 2, 3, 4,-9,-9, -9,-9,-9,-9] 
      => [-9, 2,-9, 3,-9, 4,-9, 1,-9,-9]

Algorithm:
  

*/

void CArray::frag(void)
  {
  for (int i=1; i<=MAX_COUNT*1000; i++)
    {
    int pick  = rand()%MAX_COUNT;

    swap(m_a[pick], m_a[0]);
    }
  }


///////////////////////////////////////////////////////////
// void CArray::swap(int &x, int &y);
///////////////////////////////////////////////////////////
void CArray::swap(int &x, int &y)
  {
  int temp;
  temp = x;
  x = y;
  y = temp;
  };


///////////////////////////////////////////////////////////
// void testShuffle(void)
///////////////////////////////////////////////////////////
void testShuffle(void)
  {
  cout << "testShuffle\n";
  cout << "===========\n";

  for (int i=1; i<=10; i++)
    {
    cout << "Case #" << i << endl;

    CArray myArray('r');

    myArray.display();

    myArray.shuffle();

    cout << "After shuffle\n";

    myArray.display();

    cout << "------------------------\n";

    }
  }


///////////////////////////////////////////////////////////
//void CArray::shuffle(void)
///////////////////////////////////////////////////////////
/*
a[1,3,6] => a[6,3,1] 
a[3,3,1] => a[3,1,3]
a[1,2,3,4,5,6,7,8,9] => a[4,2,3,7,5,6,1,8,9]

Algorithm0:
do the following n*100 times
  Pick a value randomly and swap it with the first value

Algorithm1:
do the following n*100 times
  Pick a value randomly 
  Swap it with the first value

Algorithm2:
do the following n*100 times
  pick = random value between 0 and n-1 
  Swap a[pick] with a[0]

*/
void CArray::shuffle(void)
  {
  for (int i=1; i<=m_n*100; i++)
    {
    int pick  = rand()%m_n;

    swap(m_a[pick], m_a[0]);
    }
  }


///////////////////////////////////////////////////////////
// void testIsSorted(void)
///////////////////////////////////////////////////////////
void testIsSorted(void)
  {
  cout << "testIsSorted\n";
  cout << "============\n";
  for (int i=1; i<=10; i++)
    {
    cout << "Case #" << i << endl;
    CArray myArray('r');

    myArray.display();

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

    myArray.sortBubble();

    cout << "After sortBubble\n";

    myArray.display();

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

    cout << "------------------------\n";

    }
  }


///////////////////////////////////////////////////////////
//bool CArray::isSorted(void)
///////////////////////////////////////////////////////////
/*
a[1,3,6] => true
a[3,3,1] => false
a[3,3,9] => true

Algorithm0:
if a[0] and a[1] out of order then return false 
if a[1] and a[2] out of order then return false 
if a[2] and a[3] out of order then return false 
...
if a[n-2] and a[n-1] out of order then return false
return true


Algorithm1:
do the following for i= 0 to n-2
  if a[i] and a[i+1] out of order then return false 
  end do

return true

*/
bool CArray::isSorted(void)
  {
  for (int i= 0; i<= m_n-2; i++)
    if (m_a[i] > m_a[i+1])
        return false;

  return true;
  }


///////////////////////////////////////////////////////////
// void testDisplayAll(void)
///////////////////////////////////////////////////////////
void testDisplayAll(void)
  {
  cout << "testDisplayAll\n";
  cout << "==============\n";
  for (int i=1; i<=10; i++)
    {
    cout << "Case #" << i << endl;
    CArray array1('r');
    array1.display();
    array1.displayAll();
    }
  }


///////////////////////////////////////////////////////////
// void CArray::displayAll(void) const
///////////////////////////////////////////////////////////
void CArray::displayAll(void) const
  {
  cout << "array[" << m_n << "]=";

  for (int i=0; i<MAX_COUNT; i++)
    cout << m_a[i] << ' ';

  cout << endl;
  }


///////////////////////////////////////////////////////////
// void testSortBubble(void)
///////////////////////////////////////////////////////////
void testSortBubble(void)
  {
  cout << "testSortBubble\n";
  cout << "==============\n";
  for (int i=1; i<=10; i++)
    {
    cout << "Case #" << i << endl;
    CArray array1('r');
    array1.display();
    array1.sortBubble();
    cout << "After sortBubble\n";
    array1.display();
    }
  }


///////////////////////////////////////////////////////////
// void CArray::sortBubble(void)
///////////////////////////////////////////////////////////
/*
Sorts array contets in increasing order
[2, 3, 1] => [1, 2, 3]
Algorithm:
Check for special cases

repeat
  from left to right put values in order
  while something changed

somethingChanged = true
while somethingChanged = true
  somethingChanged = false
  do the following for i=0 to n-2
    if a[i] > a[i+1] then
       switch a[i] and a[i+1]
       somethingChanged = true
       end if
  end while

repeat
  somethingChanged = false
  do the following for i=0 to n-2
    if a[i] > a[i+1] then
       switch a[i] and a[i+1]
       somethingChanged = true
       end if
  while something changed

*/
void CArray::sortBubble(void)
  {
  if (m_n <= 1)
      return;

  bool somethingChanged;
  int i;

  do
    {
    somethingChanged = false;
    for (i=0; i<=m_n-2; i++)
      {
      if (m_a[i] > m_a[i+1])
          {
          int temp = m_a[i+1];
          m_a[i+1] = m_a[i];
          m_a[i] = temp;
          somethingChanged = true;
          }
      }
    } while (somethingChanged == true);
  }


///////////////////////////////////////////////////////////
// void testConstructorR(void)
///////////////////////////////////////////////////////////
void testConstructorR(void)
  {
  cout << "testConstructorR\n";
  cout << "================\n";
  for (int i=1; i<=10; i++)
    {
    cout << "Case #" << i << endl;
    CArray array1('r');
    array1.display();
    }
  }


///////////////////////////////////////////////////////////
// CArray::CArray(char ch)
///////////////////////////////////////////////////////////
/*
A constructor fills array with values
depending on the value of parameter ch.
If ch is equal to 'r' then it fills the
array with random values which are
also random in count.

CArray array1('r');
gives: m_a[4,1,2], m_n=3

CArray array2('r');
gives: m_a[4,1,2,3,5,3], m_n=6

Algorithm:
m_n = random integer bet 0 and MAX_COUNT
do the following for i=0 to m_n-1
  m_a[i] = random integer between 0 and MAX_VALUE
*/
CArray::CArray(char ch)
  {
  if (('r'==ch) || ('R'==ch))
      {
      m_n = rand()%(MAX_COUNT+1);

      for (int i=0; i<=m_n-1; i++)
        m_a[i] = rand()%(MAX_VALUE+1);

      for (i=m_n; i<MAX_COUNT; i++)
        m_a[i] = UNDEFINED;
      }
    else
      m_n = 0;
  }


///////////////////////////////////////////////////////////
// void testAreDistinct(void)
///////////////////////////////////////////////////////////
void testAreDistinct(void)
  {
  cout << "testAreDistinct\n";
  cout << "===============\n";

  for (int p=1; p <= 10; p++)
    {
    cout << "Case #" << p << endl;

    int n = rand()%(MAX_COUNT+1);

    CArray myArray(n);

    myArray.display();

    if (myArray.areDistinct())
        cout << "Array has distinct values\n";
      else
        cout << "Array does not have distinct values\n";
    cout << "--------------------------------------\n";
    }
  }


///////////////////////////////////////////////////////////
// bool CArray::areDistinct(void) const
///////////////////////////////////////////////////////////
bool CArray::areDistinct(void) const
  {
  if (m_n <= 1) 
      return true;
    else
      {
      for (int i=1; i<=m_n-1; i++)
        for (int j=0; j<=i-1; j++)
          if (m_a[i] == m_a[j])
              return false;

      return true;
      }
  }
      

///////////////////////////////////////////////////////////
// void testSearchSeq(void)
///////////////////////////////////////////////////////////
void testSearchSeq(void)
  {
  cout << "testSearchSeq\n";
  cout << "=============\n";


  for (int p=1; p <= 10; p++)
    {
    cout << "Case #" << p << endl;
    int n = rand()%(MAX_COUNT+1);

    CArray myArray(n);

    myArray.display();

    int x;

    x = rand()%(MAX_VALUE+1);

    if (myArray.searchSeq(x))
        cout << x << " is in the Array\n";
      else
        cout << x << " is NOT in the Array\n";

    cout << "--------------------------------------\n";
    }
  }


///////////////////////////////////////////////////////////
// bool CArray::searchSeq(int x) const
///////////////////////////////////////////////////////////
bool CArray::searchSeq(int x) const
  {
  for (int i=0; i<=m_n-1; i++)
    if (x == m_a[i])
        return true;

  return false;
  }


///////////////////////////////////////////////////////////
// CArray::CArray(int m)
///////////////////////////////////////////////////////////
CArray::CArray(int m)
  {
  m_n = m;
  for (int i=0; i<=m_n-1; i++)
    m_a[i] = rand()%(MAX_VALUE+1);

  for (i=m_n; i<MAX_COUNT; i++)
    m_a[i] = UNDEFINED;

  }


///////////////////////////////////////////////////////////
// void CArray::populate(void)
///////////////////////////////////////////////////////////
void CArray::populate(void)
  {
  m_n = rand()%(MAX_COUNT+1);
  for (int i=0; i<=m_n-1; i++)
    m_a[i] = rand()%(MAX_VALUE+1);
  }


///////////////////////////////////////////////////////////
// void CArray::displayMultiple(int c)
///////////////////////////////////////////////////////////
void CArray::displayMultiple(int c) const
  {
  for (int i=1; i<=c; i++)
    display();
  };


///////////////////////////////////////////////////////////
// void CArray::display(void) const
///////////////////////////////////////////////////////////
void CArray::display(void) const
  {
  cout << "array[" << m_n << "]=";

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

  cout << endl;
  }


///////////////////////////////////////////////////////////
// CArray::CArray(void)
///////////////////////////////////////////////////////////
CArray::CArray(void)
  {
  m_n=0;
  for (int i=0; i<MAX_COUNT; i++)
    m_a[i] = UNDEFINED;

  cout << "Default constructor for CArray called\n";
  }


///////////////////////////////////////////////////////////
// SAMPLE RUN
///////////////////////////////////////////////////////////
/*
testFrag
========
Case #1
array[8]=5 4 4 5 4 0 0 4 -9 -9
After frag
array[8]=-9 4 0 4 0 5 4 5 4 -9
------------------------
Case #2
array[2]=3 2 -9 -9 -9 -9 -9 -9 -9 -9
After frag
array[2]=-9 -9 -9 -9 -9 2 -9 -9 -9 3
------------------------
Case #3
array[2]=1 1 -9 -9 -9 -9 -9 -9 -9 -9
After frag
array[2]=-9 1 1 -9 -9 -9 -9 -9 -9 -9
------------------------
Case #4
array[1]=1 -9 -9 -9 -9 -9 -9 -9 -9 -9
After frag
array[1]=-9 -9 1 -9 -9 -9 -9 -9 -9 -9
------------------------
Case #5
array[7]=1 3 1 4 0 3 3 -9 -9 -9
After frag
array[7]=-9 1 3 -9 4 -9 0 1 3 3
------------------------
Case #6
array[7]=2 2 4 0 0 3 1 -9 -9 -9
After frag
array[7]=-9 1 -9 -9 0 2 0 2 3 4
------------------------
Case #7
array[10]=1 5 2 2 0 2 2 4 4 4
After frag
array[10]=4 2 4 1 5 2 4 0 2 2
------------------------
Case #8
array[8]=3 4 1 3 5 1 1 2 -9 -9
After frag
array[8]=1 3 4 -9 2 5 1 3 1 -9
------------------------
Case #9
array[6]=3 4 2 4 1 5 -9 -9 -9 -9
After frag
array[6]=1 5 4 -9 4 -9 3 2 -9 -9
------------------------
Case #10
array[4]=5 0 2 2 -9 -9 -9 -9 -9 -9
After frag
array[4]=-9 5 -9 0 -9 -9 2 2 -9 -9
------------------------
Press any key to continue
*/