Solution05
[ Home ] [ Up ]

//Solution5_sortedList19.cpp
//date: 11/01/2002
//author: AOU


// Assignment #5
// Due 11/08/2002

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


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


////////////////////////////////////////////////////////////
// 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);
void testInsertionOperator(void);
void testNotEqualOperator(void);
void testIsEmpty(void);

void testAdd(void);
void testSub(void);

void testAddMultiple(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;             //2002.10.21
    void displayDistinctWithCounts(void) const;   //2002.10.23
    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
    friend ostream & operator <<                  //2002.10.17
      (ostream & bob, const CSortedList &aList); 
    bool operator !=(CSortedList list2);          //2002.10.17

    friend bool isEmpty(const CSortedList &aList);//2002.10.18

    //Assignment #4, Due 10/25/2002
    // c = a + b; no duplicate values in c, add(a, b, c);
    friend void add(const CSortedList &aList, 
      const CSortedList &bList, CSortedList &cList);
    // c = a - b; all elements of a that are not in b, sub(a,b,c); 
    friend void sub(const CSortedList &aList, 
      const CSortedList &bList, CSortedList &cList);
    //printed source code of the functions you create and the output

    //Assignment #5 Due 11/08/2002
    friend void addMultiple(const CSortedList aList[], int listCount, 
      CSortedList &mList);
    
  };


////////////////////////////////////////////////////////////
// main function
////////////////////////////////////////////////////////////
void main(void)
  {
  srand(time(NULL));
  //testSortBubble2();
  //testSearchSeq();
  //testSearchBinary();
  //testSearchBinaryLM();
  //testRemove();
  //testSortInsertion1();
  //testAssignOperator();
  //testInsertionOperator();
  //testNotEqualOperator();
  //testAdd();
  //testSub();
  //testIsEmpty();
  //testDisplayDistinct();
  //testDisplayDistinctWithCounts();
  testAddMultiple();
  }


void addMultiple(const CSortedList inList[], int listCount, 
      CSortedList &outList)
  {
  /*
  Combine the values from lists in inList[] to outList

  Algorithm:
  empty outList
  for i=0 to listCount-1
    for each value in inList[i]
      if the value is not in outList then
        insert the value in outList
  */

  outList.m_count = 0;
  for (int i=0; i<listCount; i++)
    for (int j=0; j<inList[i].m_count; j++)
      if (outList.searchBinary(inList[i].m_array[j]) == -1)
        outList.insert(inList[i].m_array[j]);
  }


void testAddMultiple(void)
  {
  const int m = 6;
  for (int j=0; j<TEST_COUNT; j++)
    {
    CSortedList myLists[m];

    for (int i= 0; i<m; i++)
      {
      myLists[i] = CSortedList(rand()%(ARRAY_SIZE/m));
      cout << "List " << i << ": " << myLists[i];
      }

    CSortedList finalList;
    cout << "FINAL: " ;
    finalList.display();

    addMultiple(myLists, m, finalList);

    cout << "After addMultiple(myLists, m, finalList);\n";

    for (i= 0; i<m; i++)
      cout << "List " << i << ": " << myLists[i];

    cout << "FINAL: " ;
    finalList.display();
    
    cout << "==================================\n";
    }
  }


////////////////////////////////////////////////////////////
// displayDistinct()
////////////////////////////////////////////////////////////
void CSortedList::displayDistinct(void) const
  {
  /*
  Cases: empty, one value, more than one value
  i = 0
  p= i
  display value at p

  s1: if i< count-1 then
    i = i+1
    if value at i is not same as value at p then
      p= i
      display value at p
      endif
  goto s1:


  i = 0
  p = i
  display value at p

  while i< count-1
    i = i+1
    if value at i is not same as value at p then
      p = i
      display value at p
      endif
    end while


  for i=0 to count-1
    print the value if it is the first or not the same as previous
    if i=0 or value[i]<>value[i-1] then display it
    end for

  */
  cout << "Distinct: ";

  for (int i=0; i<this->m_count; i++)
    if ((0==i) || (m_array[i]!=m_array[i-1]))
      cout << m_array[i] << ' ';

  cout << endl;
  }



////////////////////////////////////////////////////////////
// testDisplayDistinct()
////////////////////////////////////////////////////////////
void testDisplayDistinct(void)
  {
    {
    CSortedList myList;
    myList.display();
    myList.displayDistinct();
    cout << "-----------------\n";
    }

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



////////////////////////////////////////////////////////////
// isEmpty
////////////////////////////////////////////////////////////
bool isEmpty(const CSortedList &aList)
  {
  return (0 == aList.m_count);
  }


////////////////////////////////////////////////////////////
// testIsEmpty
////////////////////////////////////////////////////////////
void testIsEmpty(void)
  {
  cout << "testIsEmpty\n";
  cout << "-------\n";
  for (int i=0; i<TEST_COUNT; i++)
    {
    CSortedList aL('r'), bL;
    cout << "aL = " << aL;
    cout << "bL = " << bL;
    
    if (isEmpty(aL))
        cout << "aL is empty\n";
      else
        cout << "aL is not empty\n";

    if (isEmpty(bL))
        cout << "bL is empty\n";
      else
        cout << "bL is not empty\n";

    cout <<"=================\n";
    }
  }


////////////////////////////////////////////////////////////
// add
////////////////////////////////////////////////////////////
void add(const CSortedList &aList, 
  const CSortedList &bList, CSortedList &cList)
  {
  //put in c distinct values from a and b
  //a={1, 3, 5, 5}, b={3, 3, 4, 6, 6} then
  //c={1, 3, 4, 5, 6}
  /*
  Algorithm:
  empty cList
  for each value in aList
    if the value is not in cList then
      insert the value to cList

  for each value in bList
    if the value is not in cList then
      insert the value to cList

  */
  cList.m_count = 0;

  for (int i=0; i<aList.m_count; i++)
    if (cList.searchBinary(aList.m_array[i]) == -1)
      cList.insert(aList.m_array[i]);

  for (i=0; i<bList.m_count; i++)
    if (cList.searchBinary(bList.m_array[i]) == -1)
      cList.insert(bList.m_array[i]);
  }


////////////////////////////////////////////////////////////
// testAdd
////////////////////////////////////////////////////////////
void testAdd(void)
  {
  cout << "testAdd\n";
  cout << "-------\n";
  int m1 = rand()%(ARRAY_SIZE/2);
  int m2 = rand()%(ARRAY_SIZE/2);

  for (int i=0; i<TEST_COUNT; i++)
    {
    CSortedList aL(m1), bL(m2), cL('r');
    cout << "aL = " << aL;
    cout << "bL = " << bL;
    cout << "cL = " << cL;
    
    add(aL, bL, cL);
    cout << "After add(aL, bL, cL);\n";

    cout << "aL = " << aL;
    cout << "bL = " << bL;
    cout << "cL = " << cL;

    cout <<"=================\n";
    }
  }


////////////////////////////////////////////////////////////
// sub
////////////////////////////////////////////////////////////
void sub(const CSortedList &aList, 
  const CSortedList &bList, CSortedList &cList)
  {
  //put in c distinct values from a not in b
  //a={1, 3, 5, 5}, b={3, 3, 4, 6, 6} then
  //c={1, 5}
  /*
  Algorithm:
  empty cList
  for each value in aList
    if the value is not in bList then
      if the value is not in cList then
        insert the value in cList
  */
  cList.m_count = 0;
  for (int i=0; i<aList.m_count; i++)
    if (bList.searchBinary(aList.m_array[i]) == -1)
      if (cList.searchBinary(aList.m_array[i]) == -1)
        cList.insert(aList.m_array[i]);
  }


////////////////////////////////////////////////////////////
// testSub
////////////////////////////////////////////////////////////
void testSub(void)
  {
  cout << "testSub\n";
  cout << "-------\n";
  for (int i=0; i<TEST_COUNT; i++)
    {
    CSortedList aL('r'), bL('r'), cL('r');
    cout << "aL = " << aL;
    cout << "bL = " << bL;
    cout << "cL = " << cL;
    
    sub(aL, bL, cL); // cL = aL-bL;
    cout << "After sub(aL, bL, cL);\n";

    cout << "aL = " << aL;
    cout << "bL = " << bL;
    cout << "cL = " << cL;

    cout <<"=================\n";
    }
  }


////////////////////////////////////////////////////////////
// operator !=
////////////////////////////////////////////////////////////
bool CSortedList::operator !=(CSortedList list2)
  {
  return !(*this==list2);
  }


////////////////////////////////////////////////////////////
// testNotEqualOperator
////////////////////////////////////////////////////////////
void testNotEqualOperator(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 = hisList;\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";
  }



////////////////////////////////////////////////////////////
// operator <<
////////////////////////////////////////////////////////////
ostream & operator << (ostream & bob, const CSortedList &aList)
  {
  bob << "SortedList[" << aList.m_count << "]= ";
  for (int i=0; i<aList.m_count; i++)
    bob << aList.m_array[i] << ' ';

  bob << endl;

  return bob;
  }


////////////////////////////////////////////////////////////
// testInsertionOperator
////////////////////////////////////////////////////////////
void testInsertionOperator(void)
  {
  CSortedList myList('r');

  CSortedList yourList('r');
  
  cout << myList << yourList;

  }


////////////////////////////////////////////////////////////
// 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 = hisList;\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
  {
  int copies;

  /*
  for (int i=0; i<this->m_count; i++)
    {
    if (0==i)
      copies = 1;

      if ((i!=0) && (this->m_array[i] != this->m_array[i-1]))
        {
        cout << copies << ' ' << this->m_array[i-1] << endl;
        copies = 1;
        }

      if ((i!=0) && (this->m_array[i] == this->m_array[i-1]))
        copies++;

    if (i == (this->m_count-1))
      cout << copies << ' ' << this->m_array[i] << endl;

    }
  */

  /*
  for (int i=0; i<this->m_count; i++)
    {
    if (0==i)
        copies = 1;
      else
        {
        if (this->m_array[i] != this->m_array[i-1])
            {
            cout << copies << ' ' << this->m_array[i-1] << endl;
            copies = 1;
            }
          else
            copies++;
        }

    if (i == (this->m_count-1))
      cout << copies << ' ' << this->m_array[i] << endl;

    }
  */

  int total = 0;

  for (int i=0; i<this->m_count; i++)
    {
    if (0==i)
        copies = 1;
      else if (this->m_array[i] != this->m_array[i-1])
        {
        cout << copies << ' ' << this->m_array[i-1] << endl;
        total += copies;
        copies = 1;
        }
      else
        copies++;

    if (i == (this->m_count-1))
      {
      cout << copies << ' ' << this->m_array[i] << endl;
      total += copies;
      }
    }
    cout << "Total = " << total << endl;
  
  }


////////////////////////////////////////////////////////////
// testDisplayDistinctWithCounts()
////////////////////////////////////////////////////////////
void testDisplayDistinctWithCounts(void)
  {
    {
    CSortedList myList;
    myList.display();
    myList.displayDistinctWithCounts();
    cout << "-----------------\n";
    }

  for (int j=1; j<=TEST_COUNT; j++)
    {
    CSortedList myList('r');
    myList.display();
    myList.displayDistinctWithCounts();
    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

*/

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:

List 0: SortedList[4]= 4 8 10 10
List 1: SortedList[3]= 0 1 8
List 2: SortedList[0]=
List 3: SortedList[4]= 5 6 7 8
List 4: SortedList[8]= 1 2 2 6 6 8 9 9
List 5: SortedList[7]= 0 3 3 5 10 10 10
FINAL: SortedList(0)=
After addMultiple(myLists, m, finalList);
List 0: SortedList[4]= 4 8 10 10
List 1: SortedList[3]= 0 1 8
List 2: SortedList[0]=
List 3: SortedList[4]= 5 6 7 8
List 4: SortedList[8]= 1 2 2 6 6 8 9 9
List 5: SortedList[7]= 0 3 3 5 10 10 10
FINAL: SortedList(11)= 0 1 2 3 4 5 6 7 8 9 10
==================================
List 0: SortedList[0]=
List 1: SortedList[3]= 0 3 6
List 2: SortedList[1]= 3
List 3: SortedList[7]= 6 8 9 9 10 10 10
List 4: SortedList[6]= 1 7 8 9 9 10
List 5: SortedList[4]= 4 4 4 8
FINAL: SortedList(0)=
After addMultiple(myLists, m, finalList);
List 0: SortedList[0]=
List 1: SortedList[3]= 0 3 6
List 2: SortedList[1]= 3
List 3: SortedList[7]= 6 8 9 9 10 10 10
List 4: SortedList[6]= 1 7 8 9 9 10
List 5: SortedList[4]= 4 4 4 8
FINAL: SortedList(9)= 0 1 3 4 6 7 8 9 10
==================================
List 0: SortedList[4]= 4 4 7 10
List 1: SortedList[4]= 0 4 8 10
List 2: SortedList[3]= 0 1 9
List 3: SortedList[1]= 3
List 4: SortedList[8]= 0 1 1 1 4 5 8 9
List 5: SortedList[5]= 3 3 3 10 10
FINAL: SortedList(0)=
After addMultiple(myLists, m, finalList);
List 0: SortedList[4]= 4 4 7 10
List 1: SortedList[4]= 0 4 8 10
List 2: SortedList[3]= 0 1 9
List 3: SortedList[1]= 3
List 4: SortedList[8]= 0 1 1 1 4 5 8 9
List 5: SortedList[5]= 3 3 3 10 10
FINAL: SortedList(9)= 0 1 3 4 5 7 8 9 10
==================================
List 0: SortedList[7]= 3 5 6 7 7 10 10
List 1: SortedList[3]= 1 3 6
List 2: SortedList[4]= 4 5 8 10
List 3: SortedList[7]= 0 1 1 6 8 9 10
List 4: SortedList[1]= 1
List 5: SortedList[5]= 0 0 4 7 10
FINAL: SortedList(0)=
After addMultiple(myLists, m, finalList);
List 0: SortedList[7]= 3 5 6 7 7 10 10
List 1: SortedList[3]= 1 3 6
List 2: SortedList[4]= 4 5 8 10
List 3: SortedList[7]= 0 1 1 6 8 9 10
List 4: SortedList[1]= 1
List 5: SortedList[5]= 0 0 4 7 10
FINAL: SortedList(10)= 0 1 3 4 5 6 7 8 9 10
==================================
List 0: SortedList[3]= 7 8 10
List 1: SortedList[7]= 0 2 5 5 6 7 7
List 2: SortedList[7]= 0 3 4 5 6 7 10
List 3: SortedList[9]= 0 0 2 3 3 5 9 9 10
List 4: SortedList[6]= 0 2 4 4 7 10
List 5: SortedList[8]= 0 1 2 6 6 7 7 10
FINAL: SortedList(0)=
After addMultiple(myLists, m, finalList);
List 0: SortedList[3]= 7 8 10
List 1: SortedList[7]= 0 2 5 5 6 7 7
List 2: SortedList[7]= 0 3 4 5 6 7 10
List 3: SortedList[9]= 0 0 2 3 3 5 9 9 10
List 4: SortedList[6]= 0 2 4 4 7 10
List 5: SortedList[8]= 0 1 2 6 6 7 7 10
FINAL: SortedList(11)= 0 1 2 3 4 5 6 7 8 9 10
==================================
Press any key to continue
Press any key to continue
*/