SortedList14
[ Home ] [ Up ]

//sortedList14.cpp
//date: 10/09/2002
//author: AOU


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


////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
const int ARRAY_SIZE  = 10;
const int UNDEFINED   = -9999;
const int MAX_VALUE   = 99;
const int TEST_COUNT  = 10;


////////////////////////////////////////////////////////////
// Test function prototypes
////////////////////////////////////////////////////////////
void testSortBubble2(void);
void testSearchSeq(void);
void testSearchBinary(void);
void testSearchBinaryLM(void);
void testDisplayDistinct(void);
void testDisplayDistinctWithCounts(void);
void testRemove(void);
void testSortInsertion1(void);
void testAssignOperator(void);


////////////////////////////////////////////////////////////
// Class CSortedList
////////////////////////////////////////////////////////////
class CSortedList
  {
  private:
    int m_array[ARRAY_SIZE];
    int m_count;
    int m_min;
    int m_max;
  public:
    CSortedList(void);
    CSortedList(char ch);
    CSortedList(int n);               //2002.10.02
    void display(void) const;
    bool insert(int x); 
    bool isSorted(void) const;
    void sortBubble1(void);
    void sortBubble2(void);
    void sortInsertion1(void);            //2002.10.07
    void shuffle(void);
    int searchSeq(int x) const;
    int searchBinary(int x) const;        //2002.09.23
    int searchBinaryLM(int x) const;      //2002.09.25
    void displayDistinct(void) const;
    void displayDistinctWithCounts(void) const;
    bool remove(int x);                   //2002.09.30
    int getAt(int p);                     //2002.10.02
    int getCount(void);                   //2002.10.04
    bool operator ==(CSortedList list2);  //2002.10.09
  };


////////////////////////////////////////////////////////////
// main function
////////////////////////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));
  //testSortBubble2();
  //testSearchSeq();
  //testSearchBinary();
  //testSearchBinaryLM();
  //testDisplayDistinct();
  //testDisplayDistinctWithCounts();
  //testRemove();
  //testSortInsertion1();
  testAssignOperator();
  }


////////////////////////////////////////////////////////////
// EqualOperator
////////////////////////////////////////////////////////////
bool CSortedList::operator ==(CSortedList list2)
  {
  if (this->m_count != list2.m_count)
      return false;

  for (int i=0; i<this->m_count; i++)
    if (this->m_array[i] != list2.m_array[i])
      return false;

  return true;
  }


////////////////////////////////////////////////////////////
// testAssignOperator
////////////////////////////////////////////////////////////
void testAssignOperator(void)
  {
  CSortedList myList('r'), yourList(4), hisList('r');
  cout << "myList\n";
  myList.display();
  cout << "yourList\n";
  yourList.display();
  cout << "hisList\n";
  hisList.display();

  if (myList.operator == (yourList))
      cout << "myList == yourList\n";
    else
      cout << "myList != yourList\n";

  myList = yourList = hisList;
  cout << "After myList = yourList;\n";

  cout << "myList\n";
  myList.display();
  cout << "yourList\n";
  yourList.display();
  cout << "hisList\n";
  hisList.display();

  int a=3, b=4, c=5;
  cout << a << ' ' << b << ' ' << c << endl;
  a = b = c;
  cout << a << ' ' << b << ' ' << c << endl;


  if (myList == yourList)
      cout << "myList == yourList\n";
    else
      cout << "myList != yourList\n";
  }


////////////////////////////////////////////////////////////
// sortInsertion1
////////////////////////////////////////////////////////////
void CSortedList::sortInsertion1(void)
  {
  int i, temp;
  bool sorted = false;

  while (!sorted)
    {
    sorted = true;
    for (i=m_count-2; i>=0; i--)
      {
      if (m_array[i] > m_array[i+1])
        {
        temp = m_array[i];
        m_array[i] = m_array[i+1];
        m_array[i+1] = temp;
        sorted = false;
        }
      } //end for
    }//end while
  }


////////////////////////////////////////////////////////////
// testSortInsertion1
////////////////////////////////////////////////////////////
void testSortInsertion1(void)
  {
  for (int i=1; i<=10; i++)
    {
    CSortedList myList('r');

    cout << "Original list\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

    myList.shuffle();
    cout << "Shuffled list\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

    myList.sortInsertion1();
    cout << "After sortInsertion1\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

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

////////////////////////////////////////////////////////////
// getAt(int p)
////////////////////////////////////////////////////////////
int CSortedList::getAt(int p)
  {
  if ((p < m_count) && (p >= 0))
      return this->m_array[p];
    else
      return UNDEFINED;
  };


////////////////////////////////////////////////////////////
// getCount(void)
////////////////////////////////////////////////////////////
int CSortedList::getCount(void)
  {
  return this->m_count;
  };


////////////////////////////////////////////////////////////
// CSortedList(int n)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(int n)
  {
  this->m_count = 0;
  int x;

  for (int i=0; i<n; i++)
    {
    x = rand()%(MAX_VALUE+1);
    this->insert(x);
    }
  }

////////////////////////////////////////////////////////////
// remove(x)
////////////////////////////////////////////////////////////
/*
Algorithm0:
  Search for x
  if not found return false
  put position of x in p
  shiftLeft all values on right of p
  return true

Algorithm1:
  Search for x
  if not found return false
  put position of x in p
  for i= p to count-2
    array[i] = array[i+1]
    end for

  count--
  return true
*/
bool CSortedList::remove(int x)
  {
  int p = searchSeq(x);
  if (-1 == p) 
      return false;

  //shift left starting at p+1
  for (int i=p; i<=m_count-2; i++)
    m_array[i] = m_array[i+1];

  this->m_count--;
  return true;
  }


////////////////////////////////////////////////////////////
// testRemove()
////////////////////////////////////////////////////////////
void testRemove(void)
  {
  /*
  TEST CASES0:

  list with count=0

  list with count=1, x is not in the list
  list with count=1, x is in the list

  list with count=2, x is not in the list
  list with count=2, x is at 0 position
  list with count=2, x is at count-1 position

  list with count>2, x is not in the list
  list with count>2, x is at 0 position
  list with count>2, x is at count-1 position
  list with count>2, x is at position [1..count-2]
  -------------------------------------------------

  TEST CASES1:

  list with count=0

  list with count=1, x is not in the list
  list with count=1, x is in the list

  list with count>1, x is not in the list
  list with count>1, x is at 0 position
  list with count>1, x is at count-1 position

  list with count>2, x is at position [1..count-2]

  
  */
  cout << "Case0: Random cases:\n\n";

  for (int j=1; j<=5; j++)
    {
    CSortedList myList('r');
    int x;
    bool result;

    myList.display();

    for (int i=0; i<10; i++)
      {
      x = rand()%(MAX_VALUE+1);
      result = myList.remove(x);
      if (result)
          cout << x << " was deleted from the list\n";
        else
          cout << x << " could not be deleted from the list\n";

      myList.display();
      cout << endl;
      }
    cout << "----------------------------------\n";
    }

  //list with count=0
    {
    cout << "Case1: //list with count=0\n\n";

    CSortedList myList;
    int x;
    bool result;

    myList.display();
    x = rand()%(MAX_VALUE+1);
    result = myList.remove(x);

    if (result)
        cout << x << " was deleted from the list\n\n";
      else
        cout << x << " could not be deleted from the list\n";

    myList.display();
    cout << "********************************" << endl;
    }

  //list with count=1, x is not in the list
    {
    cout << "Case2: //list with count=1, x is not in the list\n\n";

    CSortedList myList(1);
    int x = MAX_VALUE+1;
    bool result;

    myList.display();
    result = myList.remove(x);

    if (result)
        cout << x << " was deleted from the list\n";
      else
        cout << x << " could not be deleted from the list\n";

    myList.display();
    cout << "********************************" << endl;
    }

  //list with count=1, x is in the list
    {
    cout << "Case3: //list with count=1, x is in the list\n\n";

    CSortedList myList(1);
    int x = myList.getAt(0);
    bool result;

    myList.display();
    result = myList.remove(x);

    if (result)
        cout << x << " was deleted from the list\n";
      else
        cout << x << " could not be deleted from the list\n";

    myList.display();
    cout << "********************************" << endl;
    }

  //list with count>1, x is not in the list
    {
    cout << "Case4: //list with count>1, x is not in the list\n\n";

    CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);
    int x = rand()%MAX_VALUE + MAX_VALUE + 1;

    bool result;

    myList.display();
    result = myList.remove(x);

    if (result)
        cout << x << " was deleted from the list\n";
      else
        cout << x << " could not be deleted from the list\n";

    myList.display();
    cout << "********************************" << endl;
    }



  //list with count>1, x is at 0 position
    {
    cout << "Case5: //list with count>1, x is at 0 position\n\n";

    CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);
    int x = myList.getAt(0);

    bool result;

    myList.display();
    result = myList.remove(x);

    if (result)
        cout << x << " was deleted from the list\n";
      else
        cout << x << " could not be deleted from the list\n";

    myList.display();
    cout << "********************************" << endl;
    }


  //list with count>1, x is at count-1 position
    {
    cout << "Case6: //list with count>1, x is at count-1 position\n\n";

    CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);

    int x = myList.getAt(myList.getCount()-1);

    bool result;

    myList.display();
    result = myList.remove(x);

    if (result)
        cout << x << " was deleted from the list\n";
      else
        cout << x << " could not be deleted from the list\n";

    myList.display();
    cout << "********************************" << endl;
    }

  //list with count>2, x is at position [1..count-2]
    {
    cout << "Case7: //list with count>2, x is at position [1..count-2]\n\n";

    CSortedList myList(rand()%(ARRAY_SIZE-1) + 2);
    
    int p = 1 + rand()%(myList.getCount()-2);

    int x = myList.getAt(p);

    bool result;

    myList.display();
    result = myList.remove(x);

    if (result)
        cout << x << " was deleted from the list\n";
      else
        cout << x << " could not be deleted from the list\n";

    myList.display();
    cout << "********************************" << endl;
    }

  }


////////////////////////////////////////////////////////////
// displayDistinctWithCounts()
////////////////////////////////////////////////////////////
void CSortedList::displayDistinctWithCounts(void) const
  {
  cout << "Missing code for displayDistinctWithCounts\n";
  }


////////////////////////////////////////////////////////////
// testDisplayDistinctWithCounts()
////////////////////////////////////////////////////////////
void testDisplayDistinctWithCounts(void)
  {
  for (int j=1; j<=TEST_COUNT; j++)
    {
    CSortedList myList('r');
    myList.display();
    myList.displayDistinctWithCounts();
    cout << "-----------------\n";
    }
  }


////////////////////////////////////////////////////////////
// displayDistinct()
////////////////////////////////////////////////////////////
void CSortedList::displayDistinct(void) const
  {
  cout << "Missing code for displayDistinct\n";
  }


////////////////////////////////////////////////////////////
// testDisplayDistinct()
////////////////////////////////////////////////////////////
void testDisplayDistinct(void)
  {
  for (int j=1; j<=TEST_COUNT; j++)
    {
    CSortedList myList('r');
    myList.display();
    myList.displayDistinct();
    cout << "-----------------\n";
    }
  }


////////////////////////////////////////////////////////////
// searchBinaryLM(x)
////////////////////////////////////////////////////////////
/*
  Given sorted array[0..count-1], x
  [12, 23, 23, 29, 32], 23 => 1
  [12, 23, 27, 27, 32], 24 => 2

  Algorithm0:
  Find the position of x in p using binary search
  if not found then return -1

  while (value at p-1 is same as at p)
    p--

  end while

*/

int CSortedList::searchBinaryLM(int x) const
  {
  int p;

  p = this->searchBinary(x);

  if (-1 == p)
      return -1;

  while((p>0) && (this->m_array[p] == this->m_array[p-1]))
    p--;

  return p;
  }


////////////////////////////////////////////////////////////
// testSearchBinaryLM
////////////////////////////////////////////////////////////
void testSearchBinaryLM(void)
  {
  for (int j=1; j<=5; j++)
    {
    CSortedList myList('r');
    int x, p1, p2;
    myList.display();

    for (int i=0; i<10; i++)
      {
      x = rand()%(MAX_VALUE+1);

      p1 = myList.searchBinaryLM(x);
      cout << x << " was found at position " << p1 << endl;

      p2 = myList.searchSeq(x);
      cout << x << " was found at position " << p2 << endl;

      if (p1 != p2)
        cout << "***************************\n";
      
      cout << endl;
      }

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


////////////////////////////////////////////////////////////
// searchBinary(x)
////////////////////////////////////////////////////////////
/*
  Given sorted array[0..count-1], x
  [12, 23, 27, 29, 32], 27 => 2
  [12, 23, 27, 29, 32], 24 => -1

  Algorithm0:
  while there is a list to be searched
    calculate mid point of the list to be searched
    if x = array[mid] then return mid
    find out which half of the list to be searched
    end while

  Algorithm1:


*/

int CSortedList::searchBinary(int x) const
  {
  int lower, upper, mid;

  lower = 0;
  upper = this->m_count-1;

  while (lower <= upper)
    {
    mid = (lower+upper)/2;
    if (x == this->m_array[mid])
      return mid;
    if (x < this->m_array[mid])
        upper = mid-1;
    if (x > this->m_array[mid])
        lower = mid+1;
    }

  return -1;
  }


////////////////////////////////////////////////////////////
// testSearchBinary
////////////////////////////////////////////////////////////
void testSearchBinary(void)
  {
  for (int j=1; j<=5; j++)
    {
    CSortedList myList('r');
    int x, p;
    myList.display();

    for (int i=0; i<10; i++)
      {
      x = rand()%(MAX_VALUE+1);
      p = myList.searchBinary(x);
      cout << x << " was found at position " << p << endl;
      p = myList.searchSeq(x);
      cout << x << " was found at position " << p << endl;
      }
    cout << "-----------------\n";
    }
  }


////////////////////////////////////////////////////////////
// searchSeq(x)
////////////////////////////////////////////////////////////
/*Given sorted array[0..count-1], x
  [12, 23, 27, 29, 32], 27 => 2
  [12, 23, 27, 29, 32], 24 => -1

  Algorithm0:
  search for x from left to right in array[]
    if found return the position

  return -1


  Algorithm1:
  for i=0 to count-1 do the following
    if x = array[i] then return i
    end for

  return -1


  Algorithm2:
  for i=0 to count-1 do the following
    if x = array[i] then return i
    if x < array[i] then exit for loop
    end for

  return -1

*/
int CSortedList::searchSeq(int x) const
  {
  for (int i=0; i<=this->m_count-1; i++)
    {
    if (x == m_array[i])
      return i;
    if (x < this->m_array[i])
      break;
    }

  return -1;
  }


////////////////////////////////////////////////////////////
// testSearchSeq
////////////////////////////////////////////////////////////
void testSearchSeq(void)
  {
  for (int j=1; j<=5; j++)
    {
    CSortedList myList('r');
    int x, p;
    myList.display();

    for (int i=0; i<10; i++)
      {
      x = rand()%(MAX_VALUE+1);
      p = myList.searchSeq(x);
      cout << x << " was found at position " << p << endl;
      }
    cout << "-----------------\n";
    }
  }

////////////////////////////////////////////////////////////
// CSortedList(void)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(void)
  {
  this->m_count = 0;
  this->m_min = UNDEFINED;
  this->m_max = UNDEFINED;
  } 


////////////////////////////////////////////////////////////
// CSortedList(char ch)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(char ch)
  {
  this->m_count = 0;
  int x, n;
  if ('r' == ch)
    {
    n = rand()%ARRAY_SIZE+1;
    for (int i=0; i<n; i++)
      {
      x = rand()%(MAX_VALUE+1);
      this->insert(x);
      }
    }
  }


////////////////////////////////////////////////////////////
// display(void)
////////////////////////////////////////////////////////////
void CSortedList::display(void) const
  {
  cout << "SortedList(" << this->m_count << ")= ";
  for (int i=0; i<this->m_count; i++)
    cout << this->m_array[i] << ' ';

  cout << endl;
  }


////////////////////////////////////////////////////////////
// insert(int x)
////////////////////////////////////////////////////////////
bool CSortedList::insert(int x)
  {
  //allow duplicate values
  /*
  there is no room then return false
  there is room then add to the end, sort, return true
  */
  if (ARRAY_SIZE == this->m_count) 
      return false;
    else
      {
      this->m_array[m_count] = x;
      this->m_count++;
      this->sortInsertion1();
      return true;
      }
  }


////////////////////////////////////////////////////////////
// sortBubble1(void)
////////////////////////////////////////////////////////////
void CSortedList::sortBubble1(void)
  {
  int j;
  for (int i=1; i<=this->m_count-1; i++)
    {
    for (j=0; j<=this->m_count-2; j++)
      {
      if (this->m_array[j] > this->m_array[j+1])
        {
        int temp = this->m_array[j];
        this->m_array[j] = this->m_array[j+1];
        this->m_array[j+1] = temp;
        }
      }
    }
  }


////////////////////////////////////////////////////////////
// sortBubble2(void)
////////////////////////////////////////////////////////////
/*
Algorithm0:
do 
  swaps =0
  make one pass trying to put items in order
  until swaps == 0

Algorithm1:
sorted = false
while not sorted
  sorted = true
  make one pass trying to put items in order
  end while

Algorithm2:
sorted = false
while not sorted
  sorted = true
  for i= 0 to m_count-2 do the following
    if m_array[i] > m_array[i+1] then
      swap m_array[i], m_array[i+1]
      sorted = false
      end if
    end for
  end while

*/
void CSortedList::sortBubble2(void)
  {
  int i, temp;
  bool sorted = false;

  while (!sorted)
    {
    sorted = true;
    for (i= 0; i<=m_count-2; i++)
      {
      if (m_array[i] > m_array[i+1])
        {
        temp = m_array[i];
        m_array[i] = m_array[i+1];
        m_array[i+1] = temp;
        sorted = false;
        }
      } //end for
    }//end while
  }


////////////////////////////////////////////////////////////
// testSortBubble2(void)
////////////////////////////////////////////////////////////
void testSortBubble2(void)
  {
  for (int i=1; i<=10; i++)
    {
    CSortedList myList('r');

    cout << "Original list\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

    myList.shuffle();
    cout << "Shuffled list\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

    myList.sortBubble2();
    cout << "After sortBubble2\n";
    myList.display();
    if (myList.isSorted())
        cout << "   List is SORTED\n";
      else
        cout << "   List is NOT SORTED\n";

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

////////////////////////////////////////////////////////////
// isSorted(void)
////////////////////////////////////////////////////////////
bool CSortedList::isSorted(void) const
  {
  for (int i=0; i<=this->m_count-2; i++)
    if (this->m_array[i] > this->m_array[i+1])
      return false;

  return true;
  }


////////////////////////////////////////////////////////////
// shuffle(void)
////////////////////////////////////////////////////////////
void CSortedList::shuffle(void)
  {
  int picked, temp;
  for (int i=0; i<=this->m_count-1; i++)
    {
    picked = rand()%this->m_count;
    temp = this->m_array[0];
    this->m_array[0] = this->m_array[picked];
    this->m_array[picked] = temp;
    }
  }


/*
SAMPLE RUN:
myList
SortedList(5)= 38 66 69 74 75
yourList
SortedList(4)= 1 49 59 92
hisList
SortedList(7)= 16 28 66 75 82 85 91
myList != yourList
After myList = yourList;
myList
SortedList(7)= 16 28 66 75 82 85 91
yourList
SortedList(7)= 16 28 66 75 82 85 91
hisList
SortedList(7)= 16 28 66 75 82 85 91
3 4 5
5 5 5
myList == yourList
Press any key to continue
*/