1.1 --- a/test/heap_test.cc Tue Dec 20 17:44:38 2011 +0100
1.2 +++ b/test/heap_test.cc Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -25,14 +25,17 @@
1.4 #include <lemon/concepts/heap.h>
1.5
1.6 #include <lemon/smart_graph.h>
1.7 -
1.8 #include <lemon/lgf_reader.h>
1.9 #include <lemon/dijkstra.h>
1.10 #include <lemon/maps.h>
1.11
1.12 #include <lemon/bin_heap.h>
1.13 +#include <lemon/quad_heap.h>
1.14 +#include <lemon/dheap.h>
1.15 #include <lemon/fib_heap.h>
1.16 +#include <lemon/pairing_heap.h>
1.17 #include <lemon/radix_heap.h>
1.18 +#include <lemon/binomial_heap.h>
1.19 #include <lemon/bucket_heap.h>
1.20
1.21 #include "test_tools.h"
1.22 @@ -89,18 +92,16 @@
1.23 template <typename Heap>
1.24 void heapSortTest() {
1.25 RangeMap<int> map(test_len, -1);
1.26 -
1.27 Heap heap(map);
1.28
1.29 std::vector<int> v(test_len);
1.30 -
1.31 for (int i = 0; i < test_len; ++i) {
1.32 v[i] = test_seq[i];
1.33 heap.push(i, v[i]);
1.34 }
1.35 std::sort(v.begin(), v.end());
1.36 for (int i = 0; i < test_len; ++i) {
1.37 - check(v[i] == heap.prio() ,"Wrong order in heap sort.");
1.38 + check(v[i] == heap.prio(), "Wrong order in heap sort.");
1.39 heap.pop();
1.40 }
1.41 }
1.42 @@ -112,7 +113,6 @@
1.43 Heap heap(map);
1.44
1.45 std::vector<int> v(test_len);
1.46 -
1.47 for (int i = 0; i < test_len; ++i) {
1.48 v[i] = test_seq[i];
1.49 heap.push(i, v[i]);
1.50 @@ -123,13 +123,11 @@
1.51 }
1.52 std::sort(v.begin(), v.end());
1.53 for (int i = 0; i < test_len; ++i) {
1.54 - check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
1.55 + check(v[i] == heap.prio(), "Wrong order in heap increase test.");
1.56 heap.pop();
1.57 }
1.58 }
1.59
1.60 -
1.61 -
1.62 template <typename Heap>
1.63 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
1.64 Node source) {
1.65 @@ -144,7 +142,7 @@
1.66 Node t = digraph.target(a);
1.67 if (dijkstra.reached(s)) {
1.68 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
1.69 - "Error in a shortest path tree!");
1.70 + "Error in shortest path tree.");
1.71 }
1.72 }
1.73
1.74 @@ -153,7 +151,7 @@
1.75 Arc a = dijkstra.predArc(n);
1.76 Node s = digraph.source(a);
1.77 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
1.78 - "Error in a shortest path tree!");
1.79 + "Error in shortest path tree.");
1.80 }
1.81 }
1.82
1.83 @@ -175,6 +173,7 @@
1.84 node("source", source).
1.85 run();
1.86
1.87 + // BinHeap
1.88 {
1.89 typedef BinHeap<Prio, ItemIntMap> IntHeap;
1.90 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.91 @@ -186,6 +185,93 @@
1.92 dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.93 }
1.94
1.95 + // QuadHeap
1.96 + {
1.97 + typedef QuadHeap<Prio, ItemIntMap> IntHeap;
1.98 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.99 + heapSortTest<IntHeap>();
1.100 + heapIncreaseTest<IntHeap>();
1.101 +
1.102 + typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
1.103 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.104 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.105 + }
1.106 +
1.107 + // DHeap
1.108 + {
1.109 + typedef DHeap<Prio, ItemIntMap> IntHeap;
1.110 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.111 + heapSortTest<IntHeap>();
1.112 + heapIncreaseTest<IntHeap>();
1.113 +
1.114 + typedef DHeap<Prio, IntNodeMap > NodeHeap;
1.115 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.116 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.117 + }
1.118 +
1.119 + // FibHeap
1.120 + {
1.121 + typedef FibHeap<Prio, ItemIntMap> IntHeap;
1.122 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.123 + heapSortTest<IntHeap>();
1.124 + heapIncreaseTest<IntHeap>();
1.125 +
1.126 + typedef FibHeap<Prio, IntNodeMap > NodeHeap;
1.127 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.128 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.129 + }
1.130 +
1.131 + // PairingHeap
1.132 + {
1.133 + typedef PairingHeap<Prio, ItemIntMap> IntHeap;
1.134 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.135 + heapSortTest<IntHeap>();
1.136 + heapIncreaseTest<IntHeap>();
1.137 +
1.138 + typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
1.139 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.140 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.141 + }
1.142 +
1.143 + // RadixHeap
1.144 + {
1.145 + typedef RadixHeap<ItemIntMap> IntHeap;
1.146 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.147 + heapSortTest<IntHeap>();
1.148 + heapIncreaseTest<IntHeap>();
1.149 +
1.150 + typedef RadixHeap<IntNodeMap > NodeHeap;
1.151 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.152 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.153 + }
1.154 +
1.155 + // BinomialHeap
1.156 + {
1.157 + typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
1.158 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.159 + heapSortTest<IntHeap>();
1.160 + heapIncreaseTest<IntHeap>();
1.161 +
1.162 + typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
1.163 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.164 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.165 + }
1.166 +
1.167 + // BucketHeap, SimpleBucketHeap
1.168 + {
1.169 + typedef BucketHeap<ItemIntMap> IntHeap;
1.170 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.171 + heapSortTest<IntHeap>();
1.172 + heapIncreaseTest<IntHeap>();
1.173 +
1.174 + typedef BucketHeap<IntNodeMap > NodeHeap;
1.175 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.176 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.177 +
1.178 + typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
1.179 + heapSortTest<SimpleIntHeap>();
1.180 + }
1.181 +
1.182 {
1.183 typedef FibHeap<Prio, ItemIntMap> IntHeap;
1.184 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();