// Date: 2005/09/16
// Author: AOU
// File: COOL009.cpp
#include<iostream>
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 = -99;
int const MIN_VALUE = 1;
int const MAX_VALUE = 9;
int const INFINITY = 9999;
int const TEST_COUNT= MAX_SIZE+5;
class COOL
{
private:
int a[MAX_SIZE];
int n;
void swap(int &x, int &y);
public:
COOL(void);
void display(void);
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); //p04
void displayDistinctWithCounts(void); //p05
int populate(char *fileName);
bool deleteByPos(int p);
int deleteByValue(int p);
int deleteByValueAll(int p);
int deleteByValueN(int p);
int deleteByValueLast(int p);
int sum(void);
};
void test_insert(void);
void test_populate(void);
void test_shuffle(void);
void test_sortBubble1(void);
void test_sortBubble2(void);
void main ()
{
//test_insert();
//test_populate();
//test_shuffle();
//test_sortBubble1();
test_sortBubble2();
}
/*
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) //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) //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)
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)
{
cout << "COOL[" << n << "]: ";
for (int i=0; i<=MAX_SIZE-1; i++)
cout << a[i] << ' ';
cout << endl;
}
COOL::COOL(void)
{
cout << "Default constructor is called\n";
a[0] = -INFINITY;
a[1] = +INFINITY;
for (int i=2; i<=MAX_SIZE-1; i++)
a[i] = UNDEFINED;
n = 2;
}
|