SortedList19
[ Home ] [ Up ]

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


// Assignment #5
// Due 11/08/2002
/* Implement addMultiple function as explained in the class with detailed
   documentstion.  Submit the source and the output.
    friend void addMultiple(const CSortedList aList[], int listCount, 
      CSortedList &mList);
*/
////////////////////////////////////////////////////////////
// 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   = 20;
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)
////////////////////////////////////////////////////////////
void addMultiple(const CSortedList inList[], int listCount, 
      CSortedList &outList)
  {
  //code to be supplied by you
  }


////////////////////////////////////////////////////////////
// void testAddMultiple(void)
////////////////////////////////////////////////////////////
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}

  cout << "NOT IMPLEMENTED\n";
  }


////////////////////////////////////////////////////////////
// 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}
  cout << "NOT IMPLEMENTED\n";
  }


////////////////////////////////////////////////////////////
// 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;
    }
  }


/*
*/