//Date: 2003.10.01
//File: OB_List06.cpp
//Author: AOU
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
/*
project 02: 10/01/2003 - 10/08/2003
Implement the following fnctions with
corresponding test functions:
friend COList fUnion(const COList &thisList, const COList &thatList);
COList fUnion(const COList &thatList) const;
COList operator +(const COList &thatList) const;
Submit the following (on paper and disk)
for each function:
5 description
5 examples (2)
5 algorithm
5 properly indented function
5 properly indented test function
5 properly labeled output (10)
*/
/*
maintain an ordered list of integeres
int searchSequential(int x) const;
void testSearchSequential(void);
*/
////////////////////////////////////////
//constants
////////////////////////////////////////
const int MAX_SIZE = 25;
const int TEST_COUNT = 19;
const int MAX_VALUE = 15;
const int UNDEFINED = -911;
////////////////////////////////////////
//prototypes
////////////////////////////////////////
void testSortBubble(void);
void testInsert(void);
void testShuffle(void);
void testIsSorted(void);
void testPopulate(void);
void testConstructor(void);
void testIsEqual(void);
void testIsEqual2(void);
void testIsEqual3(void);
void testConstructorCopy(void);
void testSearchSequential(void);
////////////////////////////////////////
//class COList
////////////////////////////////////////
class COList
{
private:
int a[MAX_SIZE];
int n;
void swap(int &x, int &y);
public:
COList(void);
void display(void) const;
void initialize(void);
bool insert(int x);
bool isSorted(void) const;
void shuffle(void);
void sortBubble(void);
void populate(int n);
COList(char ch);
friend bool isEqual(const COList &thisList, const COList &thatList);
bool isEqual(const COList &thatList) const;
bool operator ==(const COList &thatList) const;
COList(const COList &givenList);
int searchSequential(int x) const;
friend COList fUnion(const COList &thisList, const COList &thatList);
COList fUnion(const COList &thatList) const;
COList operator +(const COList &thatList) const;
};
/*
Union of two lists
------------------
Plan1:
copy L1 to L3
merge values from L2 to L3
get rid of duplicates in L3
Plan2:
copy L1 to L3 ignoring duplicates
insert values from L2 to L3 ignoring duplicates
Plan3:
copy L1 to L3
append L2 to L3
sort L3
get rid of duplicates in L3
Plan4:
copy L1 to tL1
get rid of duplicates in tL1
copy L2 to L3
get rid of duplicates in L3
insert values from tL1 to L3 ignoring duplicates
Plan5:
insert values from L1 to L3 ignoring duplicates
insert values from L2 to L3 ignoring duplicates
Plan6:
pickSmart values from L1 and L2 to L3 ignoring duplicates
*/
//bool isEqual(COList thisList, COList thatList);
////////////////////////////////////////
//main
////////////////////////////////////////
void main(void)
{
srand(time(NULL));
/*
COList myList, youList, hisList;
myList.display();
myList.insert(12);
myList.display();
myList.insert(16);
myList.display();
myList.insert(14);
myList.display();
//testInsert();
//testShuffle();
//testSortBubble();
*/
///testPopulate();
//testIsSorted();
//testShuffle();
//testSortBubble();
//testConstructor();
//testIsEqual();
//testIsEqual2();
//testIsEqual3();
//testConstructorCopy();
testSearchSequential();
}
void testSearchSequential(void)
{
cout << "+++++++++++++++++++\n";
cout << "testSearchSequential\n";
cout << "+++++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c');
myList.display();
int x = rand()%(MAX_VALUE+1);
cout << "Searching for " << x << endl;
if (UNDEFINED == myList.searchSequential(x))
cout << x << " is NOT in the list\n";
else
cout << x << " is in the list at " << myList.searchSequential(x) << "\n";
myList.display();
cout << "*****************\n";
}
}
/*
Algorithm:
compare x from begin to end and return the position
if not found return UNDEFINED
for i=0 to n-1 do the following
if x = a[i] then return i
end for
return UNDEFINED
*/
int COList::searchSequential(int x) const
{
for (int i=0; i<=this->n-1; i++)
if (x == a[i])
return i;
return UNDEFINED;
}
void testConstructorCopy(void)
{
cout << "+++++++++++++++++++\n";
cout << "testConstructorCopy\n";
cout << "+++++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c');
myList.display();
COList yourList(myList);
yourList.display();
myList.display();
cout << "*****************\n";
}
}
COList::COList(const COList &oldList)
{
cout << "Copy constructor called\n";
this->n = oldList.n;
for (int i=0; i<=MAX_SIZE-1; i++)
this->a[i] = oldList.a[i];
}
void testIsEqual3(void)
{
cout << "++++++++++++\n";
cout << "testIsEqual3\n";
cout << "++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c');
myList.display();
COList yourList('r');
yourList.display();
if (myList==yourList)
cout << "Lists are equal\n";
else
cout << "Lists are NOT equal\n";
cout << "After myList = yourList;\n";
myList = yourList;
myList.display();
yourList.display();
if (myList.operator ==(yourList))
cout << "Lists are equal\n";
else
cout << "Lists are NOT equal\n";
cout << "*****************\n";
}
}
bool COList::operator ==(const COList &thatList) const
{
if (this->n != thatList.n)
return false;
for (int i=0; i<=this->n-1; i++)
if (this->a[i] != thatList.a[i])
return false;
return true;
}
void testIsEqual2(void)
{
cout << "++++++++++++\n";
cout << "testIsEqual2\n";
cout << "++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c');
myList.display();
COList yourList('r');
yourList.display();
if (myList.isEqual(yourList))
cout << "Lists are equal\n";
else
cout << "Lists are NOT equal\n";
cout << "After myList = yourList;\n";
myList = yourList;
myList.display();
yourList.display();
if (myList.isEqual(yourList))
cout << "Lists are equal\n";
else
cout << "Lists are NOT equal\n";
cout << "*****************\n";
}
}
bool COList::isEqual(const COList &thatList) const
{
if (this->n != thatList.n)
return false;
for (int i=0; i<=this->n-1; i++)
if (this->a[i] != thatList.a[i])
return false;
return true;
}
void testIsEqual(void)
{
cout << "+++++++++++\n";
cout << "testIsEqual\n";
cout << "+++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c');
myList.display();
COList yourList('r');
yourList.display();
if (isEqual(myList, yourList))
cout << "Lists are equal\n";
else
cout << "Lists are NOT equal\n";
cout << "After myList = yourList;\n";
myList = yourList;
myList.display();
yourList.display();
if (isEqual(myList, yourList))
cout << "Lists are equal\n";
else
cout << "Lists are NOT equal\n";
cout << "*****************\n";
}
/*
if (myList == yourList)
cout << "Go home\n";
else
cout << "Stay here\n";
*/
}
/*
check of the counts are same
check all the corresponding values in both lists
if n of thisList != n of thatList
exit with false
for i=0 to n-1
if a[i] of thisList != a[i] of thatList
exit with false
end for
exit with true
*/
bool isEqual(const COList &thisList, const COList &thatList)
{
if (thisList.n != thatList.n)
return false;
for (int i=0; i<=thisList.n-1; i++)
if (thisList.a[i] != thatList.a[i])
return false;
return true;
}
void testConstructor(void)
{
cout << "++++++++++++++\n";
cout << "testConstructor\n";
cout << "++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c');
myList.display();
cout << "*****************\n";
}
}
COList::COList(char ch)
{
cout << "Constructor COList(char ch) is called\n";
//(*this).initialize();
this->initialize();
//initialize();
int n = rand()%(MAX_SIZE+1);
(*this).populate(n);
}
void COList::swap(int &x, int &y)
{
if (x != y)
{
int temp = x;
x = y;
y = temp;
}
};
////////////////////////////////////////
//testSortBubble
////////////////////////////////////////
void testSortBubble(void)
{
cout << "++++++++++++++\n";
cout << "testSortBubble\n";
cout << "++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
myList.display();
myList.shuffle();
cout << "After shuffle\n";
myList.display();
cout << "After sortBubble\n";
myList.sortBubble();
myList.display();
cout << "*****************\n";
}
}
void COList::sortBubble(void)
{
int swaps;
do
{
swaps = 0;
for (int i=0; i<=n-2; i++)
if (a[i] > a[i+1])
{
swap(a[i], a[i+1]);
swaps++;
}
} while (swaps!=0);
}
void testShuffle(void)
{
cout << "+++++++++++\n";
cout << "testShuffle\n";
cout << "+++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
myList.display();
myList.shuffle();
cout << "After shuffle\n";
myList.display();
cout << "*****************\n";
}
}
void COList::shuffle(void)
{
for (int i=1; i<=n*n; i++)
{
int pick = rand()%n;
swap (a[0], a[pick]);
}
}
void testPopulate(void)
{
cout << "++++++++++++\n";
cout << "testPopulate\n";
cout << "++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList;
int n = rand()%(MAX_SIZE+1);
cout << "n = " << n << endl;
myList.populate(n);
myList.display();
cout << "*****************\n";
}
}
void COList::populate(int n)
{
for (int i=1; i<=n; i++)
{
int x = rand()%(MAX_VALUE+1);
(*this).insert(x);
}
}
void testIsSorted(void)
{
cout << "++++++++++++\n";
cout << "testIsSorted\n";
cout << "++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
myList.display();
if (myList.isSorted())
cout << "List is sorted\n";
else
cout << "List is NOT NOT sorted\n";
cout << "*****************\n";
}
}
bool COList::isSorted(void) const
{
for (int i=0; i<=n-2; i++)
if (a[i] > a[i+1])
return false;
return true;
}
void COList::initialize(void)
{
for (int i=0; i<=MAX_SIZE-1; i++)
a[i] = UNDEFINED;
n = 0;
}
bool COList::insert(int x)
{
if (0 == n)
{
a[n] = x;
n++;
return true;
};
if (MAX_SIZE == n)
return false;
if (n > 0)
{
a[n] = x;
n++;
for (int i=n-1; i>=1; i--)
{
if (a[i] >= a[i-1]) return true;
swap(a[i], a[i-1]);
}
return true;
}
return false;
}
void COList::display(void) const
{
cout << "a[" << n << "]: ";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';
cout << endl;
}
COList::COList(void)
{
cout << "BEING INITIALIZED\n";
initialize();
}
|