1.1 --- a/test/heap_test.cc Tue Aug 18 10:08:28 2009 +0200
1.2 +++ b/test/heap_test.cc Thu Nov 05 08:39:49 2009 +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/fourary_heap.h>
1.14 +#include <lemon/kary_heap.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/binom_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,31 @@
1.92 dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.93 }
1.94
1.95 + // FouraryHeap
1.96 + {
1.97 + typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
1.98 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.99 + heapSortTest<IntHeap>();
1.100 + heapIncreaseTest<IntHeap>();
1.101 +
1.102 + typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
1.103 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.104 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.105 + }
1.106 +
1.107 + // KaryHeap
1.108 + {
1.109 + typedef KaryHeap<Prio, ItemIntMap> IntHeap;
1.110 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.111 + heapSortTest<IntHeap>();
1.112 + heapIncreaseTest<IntHeap>();
1.113 +
1.114 + typedef KaryHeap<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 @@ -197,6 +221,19 @@
1.124 dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.125 }
1.126
1.127 + // PairingHeap
1.128 + {
1.129 + typedef PairingHeap<Prio, ItemIntMap> IntHeap;
1.130 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.131 + heapSortTest<IntHeap>();
1.132 + heapIncreaseTest<IntHeap>();
1.133 +
1.134 + typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
1.135 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.136 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.137 + }
1.138 +
1.139 + // RadixHeap
1.140 {
1.141 typedef RadixHeap<ItemIntMap> IntHeap;
1.142 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.143 @@ -208,6 +245,19 @@
1.144 dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.145 }
1.146
1.147 + // BinomHeap
1.148 + {
1.149 + typedef BinomHeap<Prio, ItemIntMap> IntHeap;
1.150 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.151 + heapSortTest<IntHeap>();
1.152 + heapIncreaseTest<IntHeap>();
1.153 +
1.154 + typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
1.155 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.156 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.157 + }
1.158 +
1.159 + // BucketHeap, SimpleBucketHeap
1.160 {
1.161 typedef BucketHeap<ItemIntMap> IntHeap;
1.162 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.163 @@ -217,8 +267,10 @@
1.164 typedef BucketHeap<IntNodeMap > NodeHeap;
1.165 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.166 dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.167 +
1.168 + typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
1.169 + heapSortTest<SimpleIntHeap>();
1.170 }
1.171
1.172 -
1.173 return 0;
1.174 }