r605:f53d641aa967
Fri, 27 Mar 2009 18:49:25
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -18,59 +18,86 @@ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/counter.h> |
| 20 | 20 |
#include <vector> |
| 21 |
#include <sstream> |
|
| 22 |
|
|
| 23 |
#include "test/test_tools.h" |
|
| 21 | 24 |
|
| 22 | 25 |
using namespace lemon; |
| 23 | 26 |
|
| 24 | 27 |
template <typename T> |
| 25 | 28 |
void bubbleSort(std::vector<T>& v) {
|
| 26 |
Counter op("Bubble Sort - Operations: ");
|
|
| 27 |
Counter::NoSubCounter as(op, "Assignments: "); |
|
| 28 |
Counter::NoSubCounter co(op, "Comparisons: "); |
|
| 29 |
for (int i = v.size()-1; i > 0; --i) {
|
|
| 30 |
for (int j = 0; j < i; ++j) {
|
|
| 31 |
if (v[j] > v[j+1]) {
|
|
| 32 |
T tmp = v[j]; |
|
| 33 |
v[j] = v[j+1]; |
|
| 34 |
v[j+1] = tmp; |
|
| 35 |
as += 3; |
|
| 29 |
std::stringstream s1, s2, s3; |
|
| 30 |
{
|
|
| 31 |
Counter op("Bubble Sort - Operations: ", s1);
|
|
| 32 |
Counter::SubCounter as(op, "Assignments: ", s2); |
|
| 33 |
Counter::SubCounter co(op, "Comparisons: ", s3); |
|
| 34 |
for (int i = v.size()-1; i > 0; --i) {
|
|
| 35 |
for (int j = 0; j < i; ++j) {
|
|
| 36 |
if (v[j] > v[j+1]) {
|
|
| 37 |
T tmp = v[j]; |
|
| 38 |
v[j] = v[j+1]; |
|
| 39 |
v[j+1] = tmp; |
|
| 40 |
as += 3; |
|
| 41 |
} |
|
| 42 |
++co; |
|
| 36 | 43 |
} |
| 37 |
++co; |
|
| 38 | 44 |
} |
| 39 | 45 |
} |
| 46 |
check(s1.str() == "Bubble Sort - Operations: 102\n", "Wrong counter"); |
|
| 47 |
check(s2.str() == "Assignments: 57\n", "Wrong subcounter"); |
|
| 48 |
check(s3.str() == "Comparisons: 45\n", "Wrong subcounter"); |
|
| 40 | 49 |
} |
| 41 | 50 |
|
| 42 | 51 |
template <typename T> |
| 43 | 52 |
void insertionSort(std::vector<T>& v) {
|
| 44 |
Counter op("Insertion Sort - Operations: ");
|
|
| 45 |
Counter::NoSubCounter as(op, "Assignments: "); |
|
| 46 |
Counter::NoSubCounter co(op, "Comparisons: "); |
|
| 47 |
for (int i = 1; i < int(v.size()); ++i) {
|
|
| 48 |
T value = v[i]; |
|
| 49 |
++as; |
|
| 50 |
int j = i; |
|
| 51 |
while (j > 0 && v[j-1] > value) {
|
|
| 52 |
v[j] = v[j-1]; |
|
| 53 |
--j; |
|
| 54 |
|
|
| 53 |
std::stringstream s1, s2, s3; |
|
| 54 |
{
|
|
| 55 |
Counter op("Insertion Sort - Operations: ", s1);
|
|
| 56 |
Counter::SubCounter as(op, "Assignments: ", s2); |
|
| 57 |
Counter::SubCounter co(op, "Comparisons: ", s3); |
|
| 58 |
for (int i = 1; i < int(v.size()); ++i) {
|
|
| 59 |
T value = v[i]; |
|
| 60 |
++as; |
|
| 61 |
int j = i; |
|
| 62 |
while (j > 0 && v[j-1] > value) {
|
|
| 63 |
v[j] = v[j-1]; |
|
| 64 |
--j; |
|
| 65 |
++co; ++as; |
|
| 66 |
} |
|
| 67 |
v[j] = value; |
|
| 68 |
++as; |
|
| 55 | 69 |
} |
| 56 |
v[j] = value; |
|
| 57 |
++as; |
|
| 58 | 70 |
} |
| 71 |
check(s1.str() == "Insertion Sort - Operations: 56\n", "Wrong counter"); |
|
| 72 |
check(s2.str() == "Assignments: 37\n", "Wrong subcounter"); |
|
| 73 |
check(s3.str() == "Comparisons: 19\n", "Wrong subcounter"); |
|
| 59 | 74 |
} |
| 60 | 75 |
|
| 61 | 76 |
template <typename MyCounter> |
| 62 |
void counterTest() {
|
|
| 63 |
MyCounter c("Main Counter: ");
|
|
| 64 |
c++; |
|
| 65 |
typename MyCounter::SubCounter d(c, "SubCounter: "); |
|
| 66 |
d++; |
|
| 67 |
typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: "); |
|
| 68 |
e++; |
|
| 69 |
d+=3; |
|
| 70 |
c-=4; |
|
| 71 |
e-=2; |
|
| 72 |
c.reset(2); |
|
| 73 |
c.reset(); |
|
| 77 |
void counterTest(bool output) {
|
|
| 78 |
std::stringstream s1, s2, s3; |
|
| 79 |
{
|
|
| 80 |
MyCounter c("Main Counter: ", s1);
|
|
| 81 |
c++; |
|
| 82 |
typename MyCounter::SubCounter d(c, "SubCounter: ", s2); |
|
| 83 |
d++; |
|
| 84 |
typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ", s3); |
|
| 85 |
e++; |
|
| 86 |
d+=3; |
|
| 87 |
c-=4; |
|
| 88 |
e-=2; |
|
| 89 |
c.reset(2); |
|
| 90 |
c.reset(); |
|
| 91 |
} |
|
| 92 |
if (output) {
|
|
| 93 |
check(s1.str() == "Main Counter: 3\n", "Wrong Counter"); |
|
| 94 |
check(s2.str() == "SubCounter: 3\n", "Wrong SubCounter"); |
|
| 95 |
check(s3.str() == "", "Wrong NoSubCounter"); |
|
| 96 |
} else {
|
|
| 97 |
check(s1.str() == "", "Wrong NoCounter"); |
|
| 98 |
check(s2.str() == "", "Wrong SubCounter"); |
|
| 99 |
check(s3.str() == "", "Wrong NoSubCounter"); |
|
| 100 |
} |
|
| 74 | 101 |
} |
| 75 | 102 |
|
| 76 | 103 |
void init(std::vector<int>& v) {
|
| ... | ... |
@@ -80,8 +107,8 @@ |
| 80 | 107 |
|
| 81 | 108 |
int main() |
| 82 | 109 |
{
|
| 83 |
counterTest<Counter>(); |
|
| 84 |
counterTest<NoCounter>(); |
|
| 110 |
counterTest<Counter>(true); |
|
| 111 |
counterTest<NoCounter>(false); |
|
| 85 | 112 |
|
| 86 | 113 |
std::vector<int> x(10); |
| 87 | 114 |
init(x); bubbleSort(x); |
| ... | ... |
@@ -39,18 +39,16 @@ |
| 39 | 39 |
{
|
| 40 | 40 |
Timer T; |
| 41 | 41 |
unsigned int n; |
| 42 |
for(n=0;T.realTime()< |
|
| 42 |
for(n=0;T.realTime()<0.1;n++) ; |
|
| 43 | 43 |
std::cout << T << " (" << n << " time queries)\n";
|
| 44 |
T.restart(); |
|
| 45 |
while(T.realTime()<2.0) ; |
|
| 46 |
|
|
| 44 |
|
|
| 47 | 45 |
TimeStamp full; |
| 48 | 46 |
TimeStamp t; |
| 49 |
t=runningTimeTest(f,1,&n,&full); |
|
| 47 |
t=runningTimeTest(f,0.1,&n,&full); |
|
| 50 | 48 |
std::cout << t << " (" << n << " tests)\n";
|
| 51 | 49 |
std::cout << "Total: " << full << "\n"; |
| 52 | 50 |
|
| 53 |
t=runningTimeTest(g,1,&n,&full); |
|
| 51 |
t=runningTimeTest(g,0.1,&n,&full); |
|
| 54 | 52 |
std::cout << t << " (" << n << " tests)\n";
|
| 55 | 53 |
std::cout << "Total: " << full << "\n"; |
| 56 | 54 |
|
0 comments (0 inline)