1.1 --- a/test/heap_test.cc Sun Aug 02 12:40:20 2009 +0200
1.2 +++ b/test/heap_test.cc Fri Sep 25 09:13:03 2009 +0200
1.3 @@ -25,12 +25,18 @@
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
1.23 @@ -86,18 +92,16 @@
1.24 template <typename Heap>
1.25 void heapSortTest() {
1.26 RangeMap<int> map(test_len, -1);
1.27 -
1.28 Heap heap(map);
1.29
1.30 std::vector<int> v(test_len);
1.31 -
1.32 for (int i = 0; i < test_len; ++i) {
1.33 v[i] = test_seq[i];
1.34 heap.push(i, v[i]);
1.35 }
1.36 std::sort(v.begin(), v.end());
1.37 for (int i = 0; i < test_len; ++i) {
1.38 - check(v[i] == heap.prio() ,"Wrong order in heap sort.");
1.39 + check(v[i] == heap.prio(), "Wrong order in heap sort.");
1.40 heap.pop();
1.41 }
1.42 }
1.43 @@ -109,7 +113,6 @@
1.44 Heap heap(map);
1.45
1.46 std::vector<int> v(test_len);
1.47 -
1.48 for (int i = 0; i < test_len; ++i) {
1.49 v[i] = test_seq[i];
1.50 heap.push(i, v[i]);
1.51 @@ -120,13 +123,11 @@
1.52 }
1.53 std::sort(v.begin(), v.end());
1.54 for (int i = 0; i < test_len; ++i) {
1.55 - check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
1.56 + check(v[i] == heap.prio(), "Wrong order in heap increase test.");
1.57 heap.pop();
1.58 }
1.59 }
1.60
1.61 -
1.62 -
1.63 template <typename Heap>
1.64 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
1.65 Node source) {
1.66 @@ -141,7 +142,7 @@
1.67 Node t = digraph.target(a);
1.68 if (dijkstra.reached(s)) {
1.69 check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
1.70 - "Error in a shortest path tree!");
1.71 + "Error in shortest path tree.");
1.72 }
1.73 }
1.74
1.75 @@ -150,7 +151,7 @@
1.76 Arc a = dijkstra.predArc(n);
1.77 Node s = digraph.source(a);
1.78 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
1.79 - "Error in a shortest path tree!");
1.80 + "Error in shortest path tree.");
1.81 }
1.82 }
1.83
1.84 @@ -172,6 +173,7 @@
1.85 node("source", source).
1.86 run();
1.87
1.88 + // BinHeap
1.89 {
1.90 typedef BinHeap<Prio, ItemIntMap> IntHeap;
1.91 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.92 @@ -183,5 +185,92 @@
1.93 dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.94 }
1.95
1.96 + // FouraryHeap
1.97 + {
1.98 + typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
1.99 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.100 + heapSortTest<IntHeap>();
1.101 + heapIncreaseTest<IntHeap>();
1.102 +
1.103 + typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
1.104 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.105 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.106 + }
1.107 +
1.108 + // KaryHeap
1.109 + {
1.110 + typedef KaryHeap<Prio, ItemIntMap> IntHeap;
1.111 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.112 + heapSortTest<IntHeap>();
1.113 + heapIncreaseTest<IntHeap>();
1.114 +
1.115 + typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
1.116 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.117 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.118 + }
1.119 +
1.120 + // FibHeap
1.121 + {
1.122 + typedef FibHeap<Prio, ItemIntMap> IntHeap;
1.123 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.124 + heapSortTest<IntHeap>();
1.125 + heapIncreaseTest<IntHeap>();
1.126 +
1.127 + typedef FibHeap<Prio, IntNodeMap > NodeHeap;
1.128 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.129 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.130 + }
1.131 +
1.132 + // PairingHeap
1.133 + {
1.134 + typedef PairingHeap<Prio, ItemIntMap> IntHeap;
1.135 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.136 + heapSortTest<IntHeap>();
1.137 + heapIncreaseTest<IntHeap>();
1.138 +
1.139 + typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
1.140 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.141 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.142 + }
1.143 +
1.144 + // RadixHeap
1.145 + {
1.146 + typedef RadixHeap<ItemIntMap> IntHeap;
1.147 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.148 + heapSortTest<IntHeap>();
1.149 + heapIncreaseTest<IntHeap>();
1.150 +
1.151 + typedef RadixHeap<IntNodeMap > NodeHeap;
1.152 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.153 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.154 + }
1.155 +
1.156 + // BinomHeap
1.157 + {
1.158 + typedef BinomHeap<Prio, ItemIntMap> IntHeap;
1.159 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.160 + heapSortTest<IntHeap>();
1.161 + heapIncreaseTest<IntHeap>();
1.162 +
1.163 + typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
1.164 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.165 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.166 + }
1.167 +
1.168 + // BucketHeap, SimpleBucketHeap
1.169 + {
1.170 + typedef BucketHeap<ItemIntMap> IntHeap;
1.171 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.172 + heapSortTest<IntHeap>();
1.173 + heapIncreaseTest<IntHeap>();
1.174 +
1.175 + typedef BucketHeap<IntNodeMap > NodeHeap;
1.176 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.177 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.178 +
1.179 + typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
1.180 + heapSortTest<SimpleIntHeap>();
1.181 + }
1.182 +
1.183 return 0;
1.184 }