// Date: 2005/10/26
// Author: AOU
// File: COOL017.cpp
#include<iostream>
#include <fstream>
using namespace std;
/*
Description:
Examples:
Algorithms:
Code:
Output:
*/
/*
maintain Ordered Dense List, allow duplicate values
Operations:
create (COOL myList; )
populate (myList.populate(1,10);)
populate (myList.populate(20);)
populate (myList.populate("myList.dat");)
shuffle (myList.shuffle();)
insert (myList.insert(45);)
deleteByValue (myList.delete(45);)
display (a.display();)
deleteAll
sort
sum (a = myList.sum();)
*/
int const MAX_SIZE = 10;
int const UNDEFINED = -6;
int const MIN_VALUE = 1;
int const MAX_VALUE = 9;
int const INFINITY = 9999;
int const TEST_COUNT= MAX_SIZE+10;
class COOL
{
private:
int a[MAX_SIZE+2];
int n;
void swap(int &x, int &y);
public:
COOL(void);
COOL(int n);
void display(void) const;
int insert(int x);
int populate(int m);
int populate(int n1, int n2);
//Project#2 with a test function
//random values between n1 and n2
//returns number of values added
void shuffle(void);
void sortBubble1(void);
void sortBubble2(void); //p03
void displayDistinct(void) const; //p04
void displayDistinctWithCounts(void) const; //p05
friend bool isEqual(const COOL &list1, const COOL &list2);
bool isEqual(const COOL &list2) const;
bool operator ==(const COOL &list2) const;
bool operator !=(const COOL &list2) const;
int sum(void) const;
private:
void init(void);
public:
COOL(char ch); //r=>random, d=>distinct
bool has(int x) const;
int operator +(void) const;
COOL(const COOL &aList);
COOL & operator = (const COOL &aList);
friend void merge(const COOL &aList, const COOL &bList, COOL &cList);//p06
//cList should not have duplicate values due 10/21/2005
bool deleteByPos(int p);
friend ostream & operator << (ostream & bob, const COOL & aList);
//project #7 assigned today, due 10/31/2005
//overload >> operator for input with a test function
// http://smccd.net/accounts/hasson/C++2Notes/OpOverLoading.html
/*
Overloading << and >> for input and output
cout << x; works just find if x is an int, but the computer doesn't know what to do if x is an intList.
To make << and >> work for objects, these symbols must be overloaded with operator functions.
Again this must be done using friend functions. Here I overload << and >> for the intList class.
Add friend prototypes to the intList class definition:
ostream& operator<< (ostream&, intList&);
istream& operator>> (istream&, intList&);
cout is an example of an ostream object. cin is an example of an istream object.
So the way ostream& operator<< (ostream&, intList&); will work is the following:
We give the operator << function an ostream object (like cout) and an intList object as arguments.
We accumulate the printing in the ostream object in the body of the function.
Then we return the ostream object again so that ``chaining'' will work. cout << x << "George" << endl; is chaining.
For the computer to know what ostream and istream mean, #include <iostream> must be included in the intList.h file.
Add these functions to the intList.cpp file:
ostream& operator<< (ostream& out, intList& aList)
{
for (int n = 0; n < aList.size; n++)
out << aList.theList [n] << endl;
return out;
}
istream& operator>> (istream& in, intList& aList)
{
in >> aList.size;
delete []aList.theList;
aList.theList = new int [aList.size];
for (int n = 0; n < aList.size; n++)
in >> aList.theList [n];
return in;
}
*/
int populate(char *fileName);
int deleteByValue(int p);
int deleteByValueAll(int p);
int deleteByValueN(int p, int n);
int deleteByValueLast(int p);
};
//bool isEqual(const COOL &list1, const COOL &list2);
void test_insert(void);
void test_populate(void);
void test_shuffle(void);
void test_sortBubble1(void);
void test_sortBubble2(void);
void test_constructorN(void);
void test_isEqualFriend(void);
void test_isEqual(void);
void test_operator_isEqual(void);
void test_operator_isNotEqual(void);
void test_sum(void);
void test_constructorChar(void);
void test_has(void);
void test_operatorUniPlus(void);
void test_constructorCopy(void);
void test_operator_assign(void);
void test_mergeFriend(void);
void test_deleteByPos(void);
void test_operator_insertion(void);
void test_populate_file(void);
void main ()
{
//test_insert();
//test_populate();
//test_shuffle();
//test_sortBubble1();
//test_sortBubble2();
//test_constructorN();
//test_isEqualFriend();
//test_isEqual();
//test_operator_isEqual();
//test_operator_isNotEqual();
//test_sum();
//test_constructorChar();
//test_has();
//test_operatorUniPlus();
//test_constructorCopy();
//test_operator_assign();
//test_mergeFriend();
//test_deleteByPos();
//test_operator_insertion();
test_populate_file();
}
void test_populate_file(void)
{
cout << "--------------------\n";
cout << "test_populate_file\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList;
myList.display();
myList.populate("sample.in");
cout << myList << endl ;
cout << "........................\n";
}
}
int COOL::populate(char *fileName)
{
ifstream iFile(fileName, ios::in);
char input[10];
if (!iFile)
{
cout << "File " << fileName << " does NOT exist\n";
return 0;
}
cout << "File " << fileName << " does exist\n";
int count =0;
while (!iFile.eof())
{
iFile >> input;
this->insert(atoi(input));
count++;
}
iFile.close();
return count;
}
void test_operator_insertion(void)
{
cout << "--------------------\n";
cout << "test_operator_insertion\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList('r');
myList.display();
cout << myList << endl ;
cout << "........................\n";
}
}
ostream & operator << (ostream & bob, const COOL & aList)
{
bob << "COOL[" << aList.n-2 << "]: ";
for (int i=1; i<=aList.n-2; i++)
bob << aList.a[i] << ' ';
return bob;
}
void test_deleteByPos(void)
{
cout << "--------------------\n";
cout << "test_deleteByPos\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList('r');
myList.display();
int p = -1 + rand()%(MAX_SIZE+1 - -1 + 1);
cout << p << endl;
bool result = myList.deleteByPos(p);
myList.display();
if (result)
cout << "delete by position was a success\n";
else
cout << "delete by position was NOT a succes\n";
cout << "........................\n";
}
}
/*
bool COOL::deleteByPos(int p)
Description:
delete a value from a given valid position
Example:
{-inf, 5, 6, 9, +inf}, 2 => {-inf, 5, 9, +inf}, true
{-inf, 5, 6, 9, +inf}, 0 => {-inf, 5, 6, 9, +inf}, false
{-inf, 5, 6, 9, +inf}, 4 => {-inf, 5, 6, 9, +inf}, false
{-inf, 5, 6, 9, +inf}, 9 => {-inf, 5, 6, 9, +inf}, false
{-inf, 5, 6, 9, +inf},-9 => {-inf, 5, 6, 9, +inf}, false
Algorithm0:
if p <= 0 or >= n-1 then
return false
else
delete the value at position p by shifting values to the left
decrease n by 1
return true
end if
Algorithm1:
if p <= 0 or >= n-1 then
return false
else
//delete the value at position p by shifting values to the left
for i=p to n-2 step 1
a[i] = a[i+1]
end for
a[n-1] = UNDEFINED
decrease n by 1
return true
end if
*/
bool COOL::deleteByPos(int p)
{
if ((p <= 0) || (p >= n-1))
return false;
else
//delete the value at position p by shifting values to the left
{
for (int i=p; i<=n-2; i++)
a[i] = a[i+1];
a[n-1] = UNDEFINED;
n--;
return true;
}
}
void test_mergeFriend(void)
{
cout << "----------------\n";
cout << "test_mergeFriend\n";
cout << "----------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL aList('r'), bList('r'), cList('r');
aList.display();
bList.display();
cList.display();
merge(aList, bList, cList);
cout << "After merge(aList, bList, cList);\n";
aList.display();
bList.display();
cList.display();
cout << "........................\n";
}
}
/*
merge(const COOL &aList, const COOL &bList, COOL &cList)
Algorithm
clear cList
for each value x in aList do the following
if x is not in cList then
insert x into cList
end if
end for
for each value x in bList do the following
if x is not in cList then
insert x into cList
end if
end for
*/
void merge(const COOL &aList, const COOL &bList, COOL &cList)
{
cout << "MISSING CODE\n";
}
COOL & COOL::operator = (const COOL &aList)
{
cout << "Did you just call me?\n";
for (int i=0; i<=MAX_SIZE+1; i++)
this->a[i] = aList.a[i];
this->n = aList.n;
return *this;
}
void test_operator_assign(void)
{
cout << "--------------------\n";
cout << "test_operator_assign\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList('r');
myList.display();
COOL yourList('r');
yourList.display();
COOL hisList('r');
hisList.display();
myList = yourList = hisList;
cout << "After myList = yourList = hisList;\n";
myList.display();
yourList.display();
hisList.display();
if (myList == yourList)
cout << "myList == yourList\n";
else
cout << "myList != yourList\n";
cout << "........................\n";
}
}
void test_constructorCopy(void)
{
cout << "--------------------\n";
cout << "test_constructorCopy\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList('r');
myList.display();
COOL yourList(myList);
yourList.display();
if (myList == yourList)
cout << "myList == yourList\n";
else
cout << "myList != yourList\n";
cout << "........................\n";
}
}
COOL::COOL(const COOL &aList)
{
cout << "You just called copy constructor\n";
for (int i=0; i<=MAX_SIZE+1; i++)
this->a[i] = aList.a[i];
this->n = aList.n;
}
void test_has(void)
{
cout << "--------------------\n";
cout << "test_has\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList('r');
myList.display();
int x = MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1);
cout << x << endl;
if (myList.has(x))
cout << "has it\n";
else
cout << "DOES NOT have it\n";
cout << "........................\n";
}
}
bool COOL::has(int x) const
{
if (2 == this->n)
return false;
for (int i=1; i<=this->n-2; i++)
if (this->a[i] == x)
return true;
return false;
}
void test_constructorChar(void)
{
cout << "--------------------\n";
cout << "test_constructorChar\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList('d');
myList.display();
COOL yourList('x');
yourList.display();
cout << "........................\n";
}
}
COOL::COOL(char ch)
{
init();
if ('r' == ch)
{
int n = rand()%(MAX_SIZE+1);
this->populate(n);
}
else if ('d' == ch)
{
//supply the missing code
}
}
void test_operatorUniPlus(void)
{
cout << "------------------------\n";
cout << "test_operatorUniPlus\n";
cout << "------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int n = rand()%MAX_SIZE;
COOL myList(n);
myList.display();
cout << "myList.sum() = " << +myList << endl;
cout << "........................\n";
}
}
int COOL::operator +(void) const
{
int result = 0;
for (int i=1; i<=n-2; i++)
result = result + a[i];
return result;
}
void test_sum(void)
{
cout << "------------------------\n";
cout << "test_sum\n";
cout << "------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int n = rand()%MAX_SIZE;
COOL myList(n);
myList.display();
cout << "myList.sum() = " << myList.sum() << endl;
cout << "........................\n";
}
}
int COOL::sum(void) const
{
int result = 0;
for (int i=1; i<=n-2; i++)
result = result + a[i];
return result;
}
void test_operator_isNotEqual(void)
{
cout << "------------------------\n";
cout << "test_operator_isNotEqual\n";
cout << "------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int n = rand()%MAX_SIZE;
COOL myList(n);
int m = rand()%MAX_SIZE;
COOL yourList(m);
myList.display();
yourList.display();
if (myList.operator !=(yourList))
cout << "myList is NOT equal to yourList\n";
else
cout << "myList is equal to yourList\n";
cout << "myList = yourList;\n";
myList = yourList;
myList.display();
yourList.display();
if (myList != yourList)
cout << "myList is NOT equal to yourList\n";
else
cout << "myList is equal to yourList\n";
cout << "........................\n";
}
}
bool COOL::operator !=(const COOL &list2) const
{
return !(*this == list2);
/*
if (*this == list2)
return false;
else
return true;
*/
/*
if (n != list2.n)
return true;
if (n <= 2)
return false;
for (int i=0; i<=n-1; i++)
if (a[i] != list2.a[i])
return true;
return false;
*/
}
void test_operator_isEqual(void)
{
cout << "------------\n";
cout << "test_operator_isEqual\n";
cout << "------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int n = rand()%MAX_SIZE;
COOL myList(n);
int m = rand()%MAX_SIZE;
COOL yourList(m);
myList.display();
yourList.display();
if (myList.operator ==(yourList))
cout << "myList is equal to yourList\n";
else
cout << "myList is NOT equal to yourList\n";
cout << "myList = yourList;\n";
myList = yourList;
myList.display();
yourList.display();
if (myList == yourList)
cout << "myList is equal to yourList\n";
else
cout << "myList is NOT equal to yourList\n";
cout << "........................\n";
}
}
bool COOL::operator ==(const COOL &list2) const
{
if (n != list2.n)
return false;
if (n <= 2)
return true;
for (int i=0; i<=n-1; i++)
if (a[i] != list2.a[i])
return false;
return true;
}
void test_isEqual(void)
{
cout << "------------\n";
cout << "test_isEqual\n";
cout << "------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int n = rand()%MAX_SIZE;
COOL myList(n);
int m = rand()%MAX_SIZE;
COOL yourList(m);
myList.display();
yourList.display();
if (myList.isEqual(yourList))
cout << "myList is equal to yourList\n";
else
cout << "myList is NOT equal to yourList\n";
cout << "myList = yourList;\n";
myList = yourList;
myList.display();
yourList.display();
if (myList.isEqual(yourList))
cout << "myList is equal to yourList\n";
else
cout << "myList is NOT equal to yourList\n";
cout << "........................\n";
}
}
bool COOL::isEqual(const COOL &list2) const
{
if (n != list2.n)
return false;
if (n <= 2)
return true;
for (int i=0; i<=n-1; i++)
if (a[i] != list2.a[i])
return false;
return true;
}
void test_isEqualFriend(void)
{
cout << "------------------\n";
cout << "test_isEqualFriend\n";
cout << "------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int n = rand()%MAX_SIZE;
COOL myList(n);
int m = rand()%MAX_SIZE;
COOL yourList(m);
myList.display();
yourList.display();
if (isEqual(myList, yourList))
cout << "myList is equal to yourList\n";
else
cout << "myList is NOT equal to yourList\n";
cout << "myList = yourList;\n";
myList = yourList;
myList.display();
yourList.display();
if (isEqual(myList, yourList))
cout << "myList is equal to yourList\n";
else
cout << "myList is NOT equal to yourList\n";
cout << "........................\n";
}
}
bool isEqual(const COOL &list1, const COOL &list2)
{
if (list1.n != list2.n)
return false;
if (list1.n <= 2)
return true;
for (int i=0; i<=list1.n-1; i++)
if (list1.a[i] != list2.a[i])
return false;
return true;
}
void test_constructorN(void)
{
cout << "-----------------\n";
cout << "test_constructorN\n";
cout << "-----------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int n = rand()%MAX_SIZE;
COOL myList(n);
myList.display();
cout << "........................\n";
}
}
COOL::COOL(int n)
{
//a[0] = -INFINITY;
//a[1] = +INFINITY;
//for (int i=2; i<=MAX_SIZE+1; i++)
// a[i] = UNDEFINED;
//this->n = 2;
this->init();
this->populate(n);
}
/*
Description:
displays distinct values from the list
Examples:
[-inf, 1, 1, 1, 2, 5, 5, +inf] =>
-inf 1
1 3
2 1
5 2
+inf 1
Algorithms0:
print the first value
do the following for the rest of the values
if the next value != value printed
print next value, prinedValue=nextValue
Algorithms0:
i=0
x=a[i]
print x
do the following for i=1 to n-1
if a[i] != x then
x = a[i]
print x
end if
end do
Code:
Output:
*/
void COOL::displayDistinctWithCounts(void) const //p04
{
/*
*/
}
/*
Description:
displays distinct values from the list
Examples:
[-inf, 1, 1, 1, 2,+inf] => -inf, 1, 2, +inf
Algorithms0:
print the first value
do the following for the rest of the values
if the next value != value printed
print next value, prinedValue=nextValue
Algorithms0:
i=0
x=a[i]
print x
do the following for i=1 to n-1
if a[i] != x then
x = a[i]
print x
end if
end do
Code:
Output:
*/
void COOL::displayDistinct(void) const //p04
{
}
void test_sortBubble2(void)
{
cout << "------------\n";
cout << "test_sortBubble2\n";
cout << "------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList;
int m = rand()%MAX_SIZE;
int p = myList.populate(m);
myList.display();
myList.shuffle();
cout << "After shuffle\n";
myList.display();
myList.sortBubble2();
cout << "After sortBubble2\n";
myList.display();
cout << "........................\n";
}
}
/*
sortBubble2
Description:
sort in increasing order
Examples:
[-inf,6,2,3,+inf] => [-inf,2,3,6,+inf]
Algorithm0:
Possibilities: n<=3,n>3
if n<=3 then exit
do
{
sorted=true
scan values from left to right
if a pair is out of order then
swap the values and set sorted=false
}
while (!sorted)
Algorithm1:
if n<=3 then exit
do
{
sorted=true
for i=1 to n-3 do the following
if a[i]>a[i+1] then
swap a[i], a[i+1]
sorted=false
end if
next i
}
while (!sorted)
Code:
Output:
*/
void COOL::sortBubble2(void)
{
//supply the code Project #03
//due 9/26/2005
}
void test_sortBubble1(void)
{
cout << "------------\n";
cout << "test_sortBubble1\n";
cout << "------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList;
int m = rand()%MAX_SIZE;
int p = myList.populate(m);
myList.display();
myList.shuffle();
cout << "After shuffle\n";
myList.display();
myList.sortBubble1();
cout << "After sortBubble1\n";
myList.display();
cout << "........................\n";
}
}
/*
Description:
sort in increasing order
Examples:
[-inf,6,2,3,+inf] => [-inf,2,3,6,+inf]
Algorithms:
Possibilities: n<=3,n>3
if n<=3 then exit
for i=1 to m-1
try to put values in order
next i
if n<=3 then exit
for i=1 to n-3
for j=1 to n-3
if a[j] > a[j+1] then
swap a[j],a[j+1]
next j
next i
Code:
Output:
*/
void COOL::sortBubble1(void)
{
if (n<=3)
return;
for (int i=1; i<=n-3; i++)
for (int j=1; j<=n-3; j++)
if (a[j] > a[j+1]) swap(a[j],a[j+1]);
}
void COOL::swap(int &x, int &y)
{
int t=x;
x = y;
y = t;
}
void test_shuffle(void)
{
cout << "------------\n";
cout << "test_shuffle\n";
cout << "------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
COOL myList;
int m = rand()%MAX_SIZE;
int p = myList.populate(m);
myList.display();
myList.shuffle();
cout << "After shuffle\n";
myList.display();
cout << "........................\n";
}
}
/*
Description:
Shuffles the values in the list
do not touch -INFINITY and +INFINITY
Example:
Algorithm:
Scheme1: Shift to left or right
Scheme2: swap two randomly chosen values
Scheme3: move a randomly chosen value to the top/bottom
Scheme4: move a randomly chosen value to another random position
Scheme5: move lower approx half to the top
Scheme6: Split and bridge
Scheme7: Pick random value and move to a new list
Scheme2:
do the following n times
pick p1, p2 randomly between 1 and n-2
swap values at p1 and p2
*/
void COOL::shuffle(void)
{
if (n <= 3)
return;
for (int i=1; i<=n; i++)
{
int p1 = 1 + rand()%(n-2 - 1 + 1);
int p2 = 1 + rand()%(n-2 - 1 + 1);
//cout << "n=" << n << " p1=" << p1 << " p2=" << p2 << endl;
//cout << "before swap " << a[p1] << " " << a[p2] << endl;
swap(a[p1], a[p2]);
//cout << "after swap " << a[p1] << " " << a[p2] << endl;
}
}
void test_populate(void)
{
COOL myList;
myList.display();
for (int i=1; i<=TEST_COUNT; i++)
{
int m = rand()%MAX_SIZE;
int p = myList.populate(m);
cout << "asked for m = " << m << " inserted " << p << " values\n";
myList.display();
}
}
/*
Description:
insert m random values into an existing no-empty list
returns the actual number of items added
Example:
Algorithm:
count = 0
for i=1 to m
x = random value bet min and max
insert x into the list
if overflow then break else count++
next i
return count
*/
int COOL::populate(int m)
{
int count = 0;
for (int i=1; i<=m; i++)
{
int x = MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1);
//int p = myList.insert(x);
//int p = (*this).insert(x);
//int p = this->insert(x);
int p = insert(x);
//this->display();
if (p != -1)
count++;
else
break;
}
return count;
}
void test_insert(void)
{
COOL myList;
myList.display();
for (int i=1; i<=TEST_COUNT; i++)
{
//int x = rand()%MAX_VALUE; //p1: change to get values fro -10 to 10
// -11, -10, -9, -8, ..., 0, 1, 2, ..., 9, 10
// -11 + (0, 1, ..., 21)
// MIN_VALUE + (0... (MAX_VALUE-MIN_VALUE))
// MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1)
int x = MIN_VALUE + rand()%(MAX_VALUE - MIN_VALUE + 1);
int p = myList.insert(x);
myList.display();
if (p != -1)
cout << "Value " << x << " was inserted at " << p << " location\n";
else
cout << "Overflow\n";
}
}
/*
int COOL::insert(int x)
inserts x into the list keeping it in order
possibilities:
(a) x is out of range
(b) x is in range
(c) list is empty
(d) x >= the last value in the list
(e) x < the first value in the list
(f) x is between two values in the list
Solutions:
(a) add to the end and sort
(b) four cases
(c) start with dummy values and just one case
Chosen
start with dummy values and have just one case
insert x in the list
a[n] = x
check if a[n-1] <= a[n] return n
else swap a[n-1], a[n]
check if a[n-2] <= a[n-1] return n-1
else swap a[n-2], a[n-1]
....
check if a[0] <= a[1] return 1
else swap a[0], a[1] will never happen
m=n
a[m] = x
while (a[m-1] > a[m])
swap a[m-1], a[m]
m--
end while
n++
return m
*/
int COOL::insert(int x)
{
if (n>=(MAX_SIZE+2))//??
return -1;
int m=n;
a[m] = x;
while (a[m-1] > a[m])
{
int temp = a[m-1];
a[m-1] = a[m];
a[m] = temp;
m--;
}
n++;
return m;
}
void COOL::display(void) const
{
//cout << "COOL[" << n << "]: ";
//for (int i=0; i<=MAX_SIZE+1; i++)
// cout << a[i] << ' ';
//
//cout << endl;
cout << "COOL[" << n-2 << "]: ";
for (int i=1; i<=n-2; i++)
cout << a[i] << ' ';
cout << endl;
}
COOL::COOL(void)
{
cout << "Default constructor is called\n";
this->init();
}
void COOL::init(void)
{
a[0] = -INFINITY;
a[1] = +INFINITY;
for (int i=2; i<=MAX_SIZE+1; i++)
a[i] = UNDEFINED;
n = 2;
}
|