//Date: 2003.10.24
//File: OB_List12.cpp
//Author: AOU
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
///////////////////////////////////////////////////////////
// WHAT IS NEW
///////////////////////////////////////////////////////////
/*
int deleteDupes3r(void);
void testDeleteDupes3r(void);
*/
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
//constants
///////////////////////////////////////////////////////////
const int MAX_SIZE = 10;
const int TEST_COUNT = 25;
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);
void testFriendUnion(void);
void testMemberFunctionUnion(void);
void testMemberOperatorUnion(void);
void testOperatorIntersection(void);
void testOperatorMinus(void);
void testOperatorInsertion(void);
void testHasDistinct(void);
void testDeleteAtPos(void);
void testDeleteDupes(void);
void testDeleteDupes2(void);
void testDeleteDupes3(void);
void testDeleteDupes3r(void);
void testOperatorAssign(void);
void testMerge(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); //p02
COList fUnion(const COList &thatList) const; //p02
COList operator +(const COList &thatList) const; //p02
COList operator *(const COList &thatList) const;
COList operator -(const COList &thatList) const;
friend ostream & operator << (ostream &bob, const COList &aList);
bool hasDistinct(void) const;
bool deleteAtPos(int p);
int deleteDupes(void);
int deleteDupes2(void);
int deleteDupes3(void);
int deleteDupes3r(void);
COList & operator = (const COList &thatList);
friend void merge(COList &fList, COList iLists[], int m);
};
///////////////////////////////////////////////////////////
//main
///////////////////////////////////////////////////////////
void main(void)
{
//srand(time(NULL));
//testInsert();
//testShuffle();
//testSortBubble();
//testPopulate();
//testIsSorted();
//testShuffle();
//testSortBubble();
//testConstructor();
//testIsEqual();
//testIsEqual2();
//testIsEqual3();
//testConstructorCopy();
//testSearchSequential();
//testFriendUnion();
//testMemberFunctionUnion();
//testMemberOperatorUnion();
//testOperatorIntersection();
//testOperatorMinus();
//testOperatorInsertion();
//testHasDistinct();
//testDeleteAtPos();
//testDeleteDupes();
//testDeleteDupes2();
//testDeleteDupes3();
//testDeleteDupes3r();
//testOperatorAssign();
testMerge();
}
void testMerge(void)
{
COList iLists[5];
int m = 5;
for (int i=1; i<=m; i++)
{
COList aList('r');
iLists[i] = aList;
}
COList fList;
merge(fList, iLists, m);
cout << fList << endl;
}
void merge(COList &fList, COList iLists[], int m)
{
fList = iLists[0];
}
void testOperatorAssign(void)
{
cout << "++++++++++++++++++\n";
cout << "testOperatorAssign\n";
cout << "++++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r'), yourList('r'), a('r');
cout << "myList : "<< myList << endl;
cout << "yourList : "<< yourList << endl;
cout << "a : "<< a << endl;
myList = yourList = a;
cout << "After myLsit = yourList = a;\n";
cout << "myList : "<< myList << endl;
cout << "yourList : "<< yourList << endl;
cout << "a : "<< a << endl;
cout << "*****************\n";
}
}
COList & COList::operator = (const COList &thatList)
{
for (int i=0; i<=MAX_SIZE-1; i++)
this->a[i] = thatList.a[i];
this->n = thatList.n;
return *this;
}
////////////////////////////////////////
//testDeleteDupes3r
////////////////////////////////////////
void testDeleteDupes3r(void)
{
cout << "+++++++++++++++++\n";
cout << "testDeleteDupes3r\n";
cout << "+++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
cout << "Original list: " << myList << endl;
if (myList.hasDistinct())
cout << "The has distinct values\n";
else
cout << "The does NOT have distinct values\n";
int result = myList.deleteDupes3r();
cout << result << " values deleted\n";
cout << "Modified list: " << myList << endl;
if (myList.hasDistinct())
cout << "The list has distinct values\n";
else
cout << "The list does NOT have distinct values\n";
cout << "*****************\n";
}
}
////////////////////////////////////////
// int COList::deleteDupes3r(void)
////////////////////////////////////////
/*
[1,1,1,1,6,7,7,7]
[1,6,1,1,6,7,7,7]
Algorithm0:
if n==0 then return 0
distinctCount=1, p1 = 0, p2=p1+1
while p2 <= n-1
Find first value to right of p1 starting at p2 such that a[p1]<>a[p2]
move this value at p1+1
m++
p1++
p2++
end while
deleted = n - m
n = m
Algorithm1:
if n==0 or n==1 then return 0
distinctCount=1, p1 = 0, p2=p1+1
while p2 <= n-1
while (a[p1] == a[p2])
p2++
if p2>=n then
deleted = n-distinctCount, n = distinctCount, exit function
end if
end while
a[p1+1] = a[p2]
distinctCount++
p1++
p2++
end while
deleted = n - m
n = distinctCount
*/
/*
int COList::deleteDupes3r(void)
{
if (n<=1)
return 0;
int p1, p2, deleted, distinctCount;
p1 = 0;
p2=p1+1;
distinctCount = 1;
while (p2 <= n-1)
if (a[p1] == a[p2])
p2++;
else
{
a[++p1] = a[p2++];
distinctCount++;
}
deleted = n - distinctCount;
n = distinctCount;
for (int i=n; i<=MAX_SIZE-1; i++)
a[i] = UNDEFINED;
return deleted;
*/
int COList::deleteDupes3r(void)
{
int p1, p2, deleted;
deleted = 0;
p1 = 0;
p2=p1+1;
while (p2 <= n-1)
if (a[p1] == a[p2])
{
p2++;
deleted++;
}
else
{
p1++;
a[p1] = a[p2];
p2++;
}
n = n - deleted;
for (int i=n; i<=n+deleted-1; i++)
a[i] = UNDEFINED;
return deleted;
}
////////////////////////////////////////
//testDeleteDupes3
////////////////////////////////////////
void testDeleteDupes3(void)
{
cout << "++++++++++++++++\n";
cout << "testDeleteDupes3\n";
cout << "++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
cout << "Original list: " << myList << endl;
if (myList.hasDistinct())
cout << "The has distinct values\n";
else
cout << "The does NOT have distinct values\n";
int result = myList.deleteDupes3();
cout << result << " values deleted\n";
cout << "Modified list: " << myList << endl;
if (myList.hasDistinct())
cout << "The has distinct values\n";
else
cout << "The does NOT have distinct values\n";
cout << "*****************\n";
}
}
////////////////////////////////////////
// int COList::deleteDupes3(void)
////////////////////////////////////////
/*
[1,1,1,1,6,7,7,7]
[1,6,1,1,6,7,7,7]
Algorithm0:
if n==0 then return 0
distinctCount=1, p1 = 0, p2=p1+1
while p2 <= n-1
Find first value to right of p1 starting at p2 such that a[p1]<>a[p2]
move this value at p1+1
m++
p1++
p2++
end while
deleted = n - m
n = m
Algorithm1:
if n==0 or n==1 then return 0
distinctCount=1, p1 = 0, p2=p1+1
while p2 <= n-1
while (a[p1] == a[p2])
p2++
if p2>=n then
deleted = n-distinctCount, n = distinctCount, exit function
end if
end while
a[p1+1] = a[p2]
distinctCount++
p1++
p2++
end while
deleted = n - m
n = distinctCount
*/
int COList::deleteDupes3(void)
{
/*
if (n<=1)
return 0;
int deleted, distinctCount=1, p1 = 0, p2=p1+1;
while (p2 <= n-1)
{
while (a[p1] == a[p2])
{
p2++;
if (p2>=n)
goto s1;
}
a[p1+1] = a[p2];
distinctCount++;
p1++;
p2++;
}
s1:
deleted = n - distinctCount;
n = distinctCount;
for (int i=n+1; i<=MAX_SIZE-1; i++)
a[i] = UNDEFINED;
return deleted;
*/
if (n<=1)
return 0;
int deleted, distinctCount=1, p1 = 0, p2=p1+1;
while (p2 <= n-1)
if (a[p1] == a[p2])
a[p2++] = UNDEFINED;
//p2++;
else
{
a[++p1] = a[p2++];
distinctCount++;
//p1++;
//p2++;
}
deleted = n - distinctCount;
n = distinctCount;
return deleted;
}
////////////////////////////////////////
//testDeleteDupes2
////////////////////////////////////////
void testDeleteDupes2(void)
{
cout << "++++++++++++++++\n";
cout << "testDeleteDupes2\n";
cout << "++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
cout << "Original list: " << myList << endl;
if (myList.hasDistinct())
cout << "The has distinct values\n";
else
cout << "The does NOT have distinct values\n";
int result = myList.deleteDupes2();
cout << result << " values deleted\n";
cout << "Modified list: " << myList << endl;
if (myList.hasDistinct())
cout << "The has distinct values\n";
else
cout << "The does NOT have distinct values\n";
cout << "*****************\n";
}
}
////////////////////////////////////////
// int COList::deleteDupes2(void)
////////////////////////////////////////
/*
p=0
while increasing p by 1 do the following
if there is a duplicate at position p+1 then
delete it
else
p++
end while
p=0
while p<=n-2
if there is a duplicate at position p+1 then
delete it
else
p++
end while
*/
int COList::deleteDupes2(void)
{
int p=0, deleted=0;
while (p<=n-2)
if (a[p+1] == a[p])
deleteAtPos(p+1), deleted++;
else
p++;
return deleted;
}
////////////////////////////////////////
//testDeleteDupes
////////////////////////////////////////
void testDeleteDupes(void)
{
cout << "+++++++++++++++\n";
cout << "testDeleteDupes\n";
cout << "+++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
cout << "Original list: " << myList << endl;
if (myList.hasDistinct())
cout << "The has distinct values\n";
else
cout << "The does NOT have distinct values\n";
int result = myList.deleteDupes();
cout << result << " values deleted\n";
cout << "Modified list: " << myList << endl;
if (myList.hasDistinct())
cout << "The has distinct values\n";
else
cout << "The does NOT have distinct values\n";
cout << "*****************\n";
}
}
////////////////////////////////////////
// int COList::deleteDupes(void)
////////////////////////////////////////
/*
Algorithm0:
do
find a duplicate and delete it
while duplicate found and deleted
Algorithm1:
do
p = -1
for i=0 to n-2
if a[i] = a[i+1] then
p = i+1
delete the value at position p
exit for
end if
end for
while p<>-1
*/
int COList::deleteDupes(void)
{
int p, deleted=0;
do
{
p = -1;
for (int i=0; i<=n-2; i++)
if (a[i] == a[i+1])
{
p = i+1;
this->deleteAtPos(p);
deleted++;
break;
}
} while (p != -1);
return deleted;
}
////////////////////////////////////////
//testDeleteAtPos
////////////////////////////////////////
void testDeleteAtPos(void)
{
cout << "+++++++++++++++\n";
cout << "testDeleteAtPos\n";
cout << "+++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('r');
cout << "Original list " << myList << endl;
int p = rand()%(MAX_SIZE+1+10)-5;
cout << "About to delete value at position " << p << endl;
int result = myList.deleteAtPos(p);
if (result)
cout << "delete was successful\n";
else
cout << "delete was NOT successful\n";
cout << "Modified list " << myList << endl;
cout << "*****************\n";
}
}
////////////////////////////////////////
// bool COList::deleteAtPos(int p)
////////////////////////////////////////
/*
Algorithm0:
if p is out of range then return false
p is in range then
shift the values right to p to one position left
Algorithm1:
if p is out of range then
return false
else
for i=p to n-2 do the following
a[i] = a[i+1]
end for
a[n-1] = UNDEFINED
n--
return true
end if
*/
bool COList::deleteAtPos(int p)
{
if (p<0 || p>=n)
return false;
else
{
for (int i=p; i<=n-2; i++)
a[i] = a[i+1];
a[n-1] = UNDEFINED;
n--;
return true;
}
}
///////////////////////////////////////////////////////////
// void testHasDistinct(void)
///////////////////////////////////////////////////////////
void testHasDistinct(void)
{
cout << "+++++++++++++++\n";
cout << "testHasDistinct\n";
cout << "+++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c');
cout << "myList = " << myList << endl;
if (myList.hasDistinct())
cout << "myList has distinct values\n";
else
cout << "myList does NOT have distinct values\n";
cout << "*****************\n";
}
}
///////////////////////////////////////////////////////////
// bool COList::hasDistinct(void) const
///////////////////////////////////////////////////////////
bool COList::hasDistinct(void) const
{
for (int i=0; i<=this->n-2; i++)
if (this->a[i] == this->a[i+1])
return false;
return true;
}
///////////////////////////////////////////////////////////
// void testOperatorInsertion(void)
///////////////////////////////////////////////////////////
void testOperatorInsertion(void)
{
cout << "+++++++++++++++++++++\n";
cout << "testOperatorInsertion\n";
cout << "+++++++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c'), yourList('c'), hisList('c');
cout << "myList = " << myList << endl
<< "yourList = " << yourList << endl
<< "hisList = " << hisList << endl;
cout << "*****************\n";
}
}
///////////////////////////////////////////////////////////
// ostream & operator << (ostream &bob, const COList &aList)
///////////////////////////////////////////////////////////
ostream & operator << (ostream &bob, const COList &aList)
{
bob << "a[" << aList.n << "]: ";
//for (int i=0; i<=aList.n-1; i++)
for (int i=0; i<=MAX_SIZE-1; i++)
bob << aList.a[i] << ' ';
return bob;
}
///////////////////////////////////////////////////////////
// void testOperatorMinus(void)
///////////////////////////////////////////////////////////
void testOperatorMinus(void)
{
cout << "+++++++++++++++++\n";
cout << "testOperatorMinus\n";
cout << "+++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c'), yourList('c'), hisList('c');
cout << "myList = ";
myList.display();
cout << "yourList = ";
yourList.display();
cout << "hisList = ";
hisList.display();
hisList = myList - yourList;
cout << "After hisList = myList - yourList;\n";
cout << "myList = ";
myList.display();
cout << "yourList = ";
yourList.display();
cout << "hisList = ";
hisList.display();
cout << "*****************\n";
}
}
///////////////////////////////////////////////////////////
// COList COList::operator -(const COList &thatList) const
///////////////////////////////////////////////////////////
/*
Intersection operator
Algorithm1:
for each value x in this list do the following
if x is NOT in thatList and x is NOT in tempList then
insert x to tempList
return tempList
*/
COList COList::operator -(const COList &thatList) const
{
COList tempList;
int x;
for (int i=0; i<=this->n-1; i++)
{
x = this->a[i];
if (thatList.searchSequential(x) == UNDEFINED)
if (tempList.searchSequential(x) == UNDEFINED)
tempList.insert(x);
}
return tempList;
}
///////////////////////////////////////////////////////////
// void testOperatorIntersection(void)
///////////////////////////////////////////////////////////
void testOperatorIntersection(void)
{
cout << "++++++++++++++++++++++++\n";
cout << "testOperatorIntersection\n";
cout << "++++++++++++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
COList myList('c'), yourList('c'), hisList('c');
cout << "myList = ";
myList.display();
cout << "yourList = ";
yourList.display();
cout << "hisList = ";
hisList.display();
hisList = myList * yourList;
cout << "After hisList = myList * yourList;\n";
cout << "myList = ";
myList.display();
cout << "yourList = ";
yourList.display();
cout << "hisList = ";
hisList.display();
cout << "*****************\n";
}
}
///////////////////////////////////////////////////////////
// COList COList::operator *(const COList &thatList) const
///////////////////////////////////////////////////////////
/*
Build a third list of values that are in both lists
Intersection operator
Algorithm1:
for each value x in this list do the following
if x is in thatList and x is not in tempList then
insert x to tempList
return tempList
*/
COList COList::operator *(const COList &thatList) const
{
COList tempList;
int x;
for (int i=0; i<=this->n-1; i++)
{
x = this->a[i];
if (thatList.searchSequential(x) != UNDEFINED)
if (tempList.searchSequential(x) == UNDEFINED)
tempList.insert(x);
}
return tempList;
}
///////////////////////////////////////////////////////////
// void testSearchSequential(void)
///////////////////////////////////////////////////////////
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";
}
}
///////////////////////////////////////////////////////////
// int COList::searchSequential(int x) const
///////////////////////////////////////////////////////////
/*
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)
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
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
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
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
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
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";
*/
}
///////////////////////////////////////////////////////////
// bool isEqual(const COList &thisList, const COList &thatList)
///////////////////////////////////////////////////////////
/*
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)
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
void COList::swap(int &x, int &y)
{
if (x != y)
{
int temp = x;
x = y;
y = temp;
}
};
////////////////////////////////////////
// void testSortBubble(void)
////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
void COList::shuffle(void)
{
for (int i=1; i<=n*n; i++)
{
int pick = rand()%n;
swap (a[0], a[pick]);
}
}
///////////////////////////////////////////////////////////
// void testPopulate(void)
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
void COList::populate(int n)
{
for (int i=1; i<=n; i++)
{
int x = rand()%(MAX_VALUE+1);
(*this).insert(x);
}
}
///////////////////////////////////////////////////////////
// void testIsSorted(void)
///////////////////////////////////////////////////////////
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
///////////////////////////////////////////////////////////
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)
///////////////////////////////////////////////////////////
void COList::initialize(void)
{
for (int i=0; i<=MAX_SIZE-1; i++)
a[i] = UNDEFINED;
n = 0;
}
///////////////////////////////////////////////////////////
// bool COList::insert(int x)
///////////////////////////////////////////////////////////
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
///////////////////////////////////////////////////////////
void COList::display(void) const
{
cout << "a[" << n << "]: ";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';
cout << endl;
}
///////////////////////////////////////////////////////////
// COList::COList(void)
///////////////////////////////////////////////////////////
COList::COList(void)
{
//cout << "BEING INITIALIZED\n";
initialize();
}
///////////////////////////////////////////////////////////
// SAMPLE RUN:
///////////////////////////////////////////////////////////
|