Changes in test/heap_test.cc [440:88ed40ad0d4f:702:bdc7dfc8c054] in lemon1.2
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/heap_test.cc
r440 r702 26 26 27 27 #include <lemon/smart_graph.h> 28 29 28 #include <lemon/lgf_reader.h> 30 29 #include <lemon/dijkstra.h> … … 32 31 33 32 #include <lemon/bin_heap.h> 33 #include <lemon/fourary_heap.h> 34 #include <lemon/kary_heap.h> 35 #include <lemon/fib_heap.h> 36 #include <lemon/pairing_heap.h> 37 #include <lemon/radix_heap.h> 38 #include <lemon/binom_heap.h> 39 #include <lemon/bucket_heap.h> 34 40 35 41 #include "test_tools.h" … … 87 93 void heapSortTest() { 88 94 RangeMap<int> map(test_len, 1); 89 90 95 Heap heap(map); 91 96 92 97 std::vector<int> v(test_len); 93 94 98 for (int i = 0; i < test_len; ++i) { 95 99 v[i] = test_seq[i]; … … 98 102 std::sort(v.begin(), v.end()); 99 103 for (int i = 0; i < test_len; ++i) { 100 check(v[i] == heap.prio() ,"Wrong order in heap sort.");104 check(v[i] == heap.prio(), "Wrong order in heap sort."); 101 105 heap.pop(); 102 106 } … … 110 114 111 115 std::vector<int> v(test_len); 112 113 116 for (int i = 0; i < test_len; ++i) { 114 117 v[i] = test_seq[i]; … … 121 124 std::sort(v.begin(), v.end()); 122 125 for (int i = 0; i < test_len; ++i) { 123 check(v[i] == heap.prio() ,"Wrong order in heap increase test.");126 check(v[i] == heap.prio(), "Wrong order in heap increase test."); 124 127 heap.pop(); 125 128 } 126 129 } 127 128 129 130 130 131 template <typename Heap> … … 142 143 if (dijkstra.reached(s)) { 143 144 check( dijkstra.dist(t)  dijkstra.dist(s) <= length[a], 144 "Error in a shortest path tree!");145 "Error in shortest path tree."); 145 146 } 146 147 } … … 151 152 Node s = digraph.source(a); 152 153 check( dijkstra.dist(n)  dijkstra.dist(s) == length[a], 153 "Error in a shortest path tree!");154 "Error in shortest path tree."); 154 155 } 155 156 } … … 173 174 run(); 174 175 176 // BinHeap 175 177 { 176 178 typedef BinHeap<Prio, ItemIntMap> IntHeap; … … 184 186 } 185 187 188 // FouraryHeap 189 { 190 typedef FouraryHeap<Prio, ItemIntMap> IntHeap; 191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 192 heapSortTest<IntHeap>(); 193 heapIncreaseTest<IntHeap>(); 194 195 typedef FouraryHeap<Prio, IntNodeMap > NodeHeap; 196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 197 dijkstraHeapTest<NodeHeap>(digraph, length, source); 198 } 199 200 // KaryHeap 201 { 202 typedef KaryHeap<Prio, ItemIntMap> IntHeap; 203 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 204 heapSortTest<IntHeap>(); 205 heapIncreaseTest<IntHeap>(); 206 207 typedef KaryHeap<Prio, IntNodeMap > NodeHeap; 208 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 209 dijkstraHeapTest<NodeHeap>(digraph, length, source); 210 } 211 212 // FibHeap 213 { 214 typedef FibHeap<Prio, ItemIntMap> IntHeap; 215 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 216 heapSortTest<IntHeap>(); 217 heapIncreaseTest<IntHeap>(); 218 219 typedef FibHeap<Prio, IntNodeMap > NodeHeap; 220 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 221 dijkstraHeapTest<NodeHeap>(digraph, length, source); 222 } 223 224 // PairingHeap 225 { 226 typedef PairingHeap<Prio, ItemIntMap> IntHeap; 227 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 228 heapSortTest<IntHeap>(); 229 heapIncreaseTest<IntHeap>(); 230 231 typedef PairingHeap<Prio, IntNodeMap > NodeHeap; 232 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 233 dijkstraHeapTest<NodeHeap>(digraph, length, source); 234 } 235 236 // RadixHeap 237 { 238 typedef RadixHeap<ItemIntMap> IntHeap; 239 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 240 heapSortTest<IntHeap>(); 241 heapIncreaseTest<IntHeap>(); 242 243 typedef RadixHeap<IntNodeMap > NodeHeap; 244 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 245 dijkstraHeapTest<NodeHeap>(digraph, length, source); 246 } 247 248 // BinomHeap 249 { 250 typedef BinomHeap<Prio, ItemIntMap> IntHeap; 251 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 252 heapSortTest<IntHeap>(); 253 heapIncreaseTest<IntHeap>(); 254 255 typedef BinomHeap<Prio, IntNodeMap > NodeHeap; 256 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 257 dijkstraHeapTest<NodeHeap>(digraph, length, source); 258 } 259 260 // BucketHeap, SimpleBucketHeap 261 { 262 typedef BucketHeap<ItemIntMap> IntHeap; 263 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 264 heapSortTest<IntHeap>(); 265 heapIncreaseTest<IntHeap>(); 266 267 typedef BucketHeap<IntNodeMap > NodeHeap; 268 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 269 dijkstraHeapTest<NodeHeap>(digraph, length, source); 270 271 typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap; 272 heapSortTest<SimpleIntHeap>(); 273 } 274 186 275 return 0; 187 276 }
Note: See TracChangeset
for help on using the changeset viewer.