16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <lemon/counter.h> |
19 #include <lemon/counter.h> |
20 #include <vector> |
20 #include <vector> |
|
21 #include <sstream> |
|
22 |
|
23 #include "test/test_tools.h" |
21 |
24 |
22 using namespace lemon; |
25 using namespace lemon; |
23 |
26 |
24 template <typename T> |
27 template <typename T> |
25 void bubbleSort(std::vector<T>& v) { |
28 void bubbleSort(std::vector<T>& v) { |
26 Counter op("Bubble Sort - Operations: "); |
29 std::stringstream s1, s2, s3; |
27 Counter::NoSubCounter as(op, "Assignments: "); |
30 { |
28 Counter::NoSubCounter co(op, "Comparisons: "); |
31 Counter op("Bubble Sort - Operations: ", s1); |
29 for (int i = v.size()-1; i > 0; --i) { |
32 Counter::SubCounter as(op, "Assignments: ", s2); |
30 for (int j = 0; j < i; ++j) { |
33 Counter::SubCounter co(op, "Comparisons: ", s3); |
31 if (v[j] > v[j+1]) { |
34 for (int i = v.size()-1; i > 0; --i) { |
32 T tmp = v[j]; |
35 for (int j = 0; j < i; ++j) { |
33 v[j] = v[j+1]; |
36 if (v[j] > v[j+1]) { |
34 v[j+1] = tmp; |
37 T tmp = v[j]; |
35 as += 3; |
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 template <typename T> |
51 template <typename T> |
43 void insertionSort(std::vector<T>& v) { |
52 void insertionSort(std::vector<T>& v) { |
44 Counter op("Insertion Sort - Operations: "); |
53 std::stringstream s1, s2, s3; |
45 Counter::NoSubCounter as(op, "Assignments: "); |
54 { |
46 Counter::NoSubCounter co(op, "Comparisons: "); |
55 Counter op("Insertion Sort - Operations: ", s1); |
47 for (int i = 1; i < int(v.size()); ++i) { |
56 Counter::SubCounter as(op, "Assignments: ", s2); |
48 T value = v[i]; |
57 Counter::SubCounter co(op, "Comparisons: ", s3); |
49 ++as; |
58 for (int i = 1; i < int(v.size()); ++i) { |
50 int j = i; |
59 T value = v[i]; |
51 while (j > 0 && v[j-1] > value) { |
60 ++as; |
52 v[j] = v[j-1]; |
61 int j = i; |
53 --j; |
62 while (j > 0 && v[j-1] > value) { |
54 ++co; ++as; |
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 template <typename MyCounter> |
76 template <typename MyCounter> |
62 void counterTest() { |
77 void counterTest(bool output) { |
63 MyCounter c("Main Counter: "); |
78 std::stringstream s1, s2, s3; |
64 c++; |
79 { |
65 typename MyCounter::SubCounter d(c, "SubCounter: "); |
80 MyCounter c("Main Counter: ", s1); |
66 d++; |
81 c++; |
67 typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: "); |
82 typename MyCounter::SubCounter d(c, "SubCounter: ", s2); |
68 e++; |
83 d++; |
69 d+=3; |
84 typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ", s3); |
70 c-=4; |
85 e++; |
71 e-=2; |
86 d+=3; |
72 c.reset(2); |
87 c-=4; |
73 c.reset(); |
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 void init(std::vector<int>& v) { |
103 void init(std::vector<int>& v) { |
77 v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100; |
104 v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100; |
78 v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70; |
105 v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70; |
79 } |
106 } |
80 |
107 |
81 int main() |
108 int main() |
82 { |
109 { |
83 counterTest<Counter>(); |
110 counterTest<Counter>(true); |
84 counterTest<NoCounter>(); |
111 counterTest<NoCounter>(false); |
85 |
112 |
86 std::vector<int> x(10); |
113 std::vector<int> x(10); |
87 init(x); bubbleSort(x); |
114 init(x); bubbleSort(x); |
88 init(x); insertionSort(x); |
115 init(x); insertionSort(x); |
89 |
116 |