Changeset 1065:b522385b2a0d in lemon for test/heap_test.cc
 Timestamp:
 07/13/11 14:52:22 (12 years ago)
 Branch:
 1.2
 Parents:
 1058:d9a2bf30b360 (diff), 1063:0dba9b96550a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

test/heap_test.cc
r929 r1065 273 273 } 274 274 275 { 276 typedef FibHeap<Prio, ItemIntMap> IntHeap; 277 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 278 heapSortTest<IntHeap>(); 279 heapIncreaseTest<IntHeap>(); 280 281 typedef FibHeap<Prio, IntNodeMap > NodeHeap; 282 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 283 dijkstraHeapTest<NodeHeap>(digraph, length, source); 284 } 285 286 { 287 typedef RadixHeap<ItemIntMap> IntHeap; 288 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 289 heapSortTest<IntHeap>(); 290 heapIncreaseTest<IntHeap>(); 291 292 typedef RadixHeap<IntNodeMap > NodeHeap; 293 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 294 dijkstraHeapTest<NodeHeap>(digraph, length, source); 295 } 296 297 { 298 typedef BucketHeap<ItemIntMap> IntHeap; 299 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 300 heapSortTest<IntHeap>(); 301 heapIncreaseTest<IntHeap>(); 302 303 typedef BucketHeap<IntNodeMap > NodeHeap; 304 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 305 dijkstraHeapTest<NodeHeap>(digraph, length, source); 306 } 307 308 275 309 return 0; 276 310 } 
test/heap_test.cc
r728 r1065 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/quad_heap.h> 34 #include <lemon/dheap.h> 34 35 #include <lemon/fib_heap.h> 36 #include <lemon/pairing_heap.h> 35 37 #include <lemon/radix_heap.h> 38 #include <lemon/binomial_heap.h> 36 39 #include <lemon/bucket_heap.h> 37 40 … … 90 93 void heapSortTest() { 91 94 RangeMap<int> map(test_len, 1); 92 93 95 Heap heap(map); 94 96 95 97 std::vector<int> v(test_len); 96 97 98 for (int i = 0; i < test_len; ++i) { 98 99 v[i] = test_seq[i]; … … 101 102 std::sort(v.begin(), v.end()); 102 103 for (int i = 0; i < test_len; ++i) { 103 check(v[i] == heap.prio() ,"Wrong order in heap sort.");104 check(v[i] == heap.prio(), "Wrong order in heap sort."); 104 105 heap.pop(); 105 106 } … … 113 114 114 115 std::vector<int> v(test_len); 115 116 116 for (int i = 0; i < test_len; ++i) { 117 117 v[i] = test_seq[i]; … … 124 124 std::sort(v.begin(), v.end()); 125 125 for (int i = 0; i < test_len; ++i) { 126 check(v[i] == heap.prio() ,"Wrong order in heap increase test.");126 check(v[i] == heap.prio(), "Wrong order in heap increase test."); 127 127 heap.pop(); 128 128 } 129 129 } 130 131 132 130 133 131 template <typename Heap> … … 145 143 if (dijkstra.reached(s)) { 146 144 check( dijkstra.dist(t)  dijkstra.dist(s) <= length[a], 147 "Error in a shortest path tree!");145 "Error in shortest path tree."); 148 146 } 149 147 } … … 154 152 Node s = digraph.source(a); 155 153 check( dijkstra.dist(n)  dijkstra.dist(s) == length[a], 156 "Error in a shortest path tree!");154 "Error in shortest path tree."); 157 155 } 158 156 } … … 176 174 run(); 177 175 176 // BinHeap 178 177 { 179 178 typedef BinHeap<Prio, ItemIntMap> IntHeap; … … 185 184 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 186 185 dijkstraHeapTest<NodeHeap>(digraph, length, source); 186 } 187 188 // QuadHeap 189 { 190 typedef QuadHeap<Prio, ItemIntMap> IntHeap; 191 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 192 heapSortTest<IntHeap>(); 193 heapIncreaseTest<IntHeap>(); 194 195 typedef QuadHeap<Prio, IntNodeMap > NodeHeap; 196 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 197 dijkstraHeapTest<NodeHeap>(digraph, length, source); 198 } 199 200 // DHeap 201 { 202 typedef DHeap<Prio, ItemIntMap> IntHeap; 203 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 204 heapSortTest<IntHeap>(); 205 heapIncreaseTest<IntHeap>(); 206 207 typedef DHeap<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 // BinomialHeap 249 { 250 typedef BinomialHeap<Prio, ItemIntMap> IntHeap; 251 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 252 heapSortTest<IntHeap>(); 253 heapIncreaseTest<IntHeap>(); 254 255 typedef BinomialHeap<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>(); 187 273 } 188 274
Note: See TracChangeset
for help on using the changeset viewer.