1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2009 |
---|
6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
8 | * |
---|
9 | * Permission to use, modify and distribute this software is granted |
---|
10 | * provided that this copyright notice appears in all copies. For |
---|
11 | * precise terms see the accompanying LICENSE file. |
---|
12 | * |
---|
13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
14 | * express or implied, and with no claim as to its suitability for any |
---|
15 | * purpose. |
---|
16 | * |
---|
17 | */ |
---|
18 | |
---|
19 | #include <lemon/counter.h> |
---|
20 | #include <vector> |
---|
21 | #include <sstream> |
---|
22 | |
---|
23 | #include "test/test_tools.h" |
---|
24 | |
---|
25 | using namespace lemon; |
---|
26 | |
---|
27 | template <typename T> |
---|
28 | void bubbleSort(std::vector<T>& v) { |
---|
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; |
---|
43 | } |
---|
44 | } |
---|
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"); |
---|
49 | } |
---|
50 | |
---|
51 | template <typename T> |
---|
52 | void insertionSort(std::vector<T>& v) { |
---|
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; |
---|
69 | } |
---|
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"); |
---|
74 | } |
---|
75 | |
---|
76 | template <typename MyCounter> |
---|
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 | } |
---|
101 | } |
---|
102 | |
---|
103 | void init(std::vector<int>& v) { |
---|
104 | v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100; |
---|
105 | v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70; |
---|
106 | } |
---|
107 | |
---|
108 | int main() |
---|
109 | { |
---|
110 | counterTest<Counter>(true); |
---|
111 | counterTest<NoCounter>(false); |
---|
112 | |
---|
113 | std::vector<int> x(10); |
---|
114 | init(x); bubbleSort(x); |
---|
115 | init(x); insertionSort(x); |
---|
116 | |
---|
117 | return 0; |
---|
118 | } |
---|