1.1 --- a/test/heap_test.cc Fri Oct 16 10:21:37 2009 +0200
1.2 +++ b/test/heap_test.cc Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -25,12 +25,18 @@
1.13 #include <lemon/concepts/heap.h>
1.14
1.15 #include <lemon/smart_graph.h>
1.16 -
1.17 #include <lemon/lgf_reader.h>
1.18 #include <lemon/dijkstra.h>
1.19 #include <lemon/maps.h>
1.20
1.21 #include <lemon/bin_heap.h>
1.22 +#include <lemon/fourary_heap.h>
1.23 +#include <lemon/kary_heap.h>
1.24 +#include <lemon/fib_heap.h>
1.25 +#include <lemon/pairing_heap.h>
1.26 +#include <lemon/radix_heap.h>
1.27 +#include <lemon/binom_heap.h>
1.28 +#include <lemon/bucket_heap.h>
1.29
1.30 #include "test_tools.h"
1.31
1.32 @@ -86,18 +92,16 @@
1.33 template <typename Heap>
1.34 void heapSortTest() {
1.35 RangeMap<int> map(test_len, -1);
1.36 -
1.37 Heap heap(map);
1.38
1.39 std::vector<int> v(test_len);
1.40 -
1.41 for (int i = 0; i < test_len; ++i) {
1.42 v[i] = test_seq[i];
1.43 heap.push(i, v[i]);
1.44 }
1.45 std::sort(v.begin(), v.end());
1.46 for (int i = 0; i < test_len; ++i) {
1.47 - check(v[i] == heap.prio() ,"Wrong order in heap sort.");
1.48 + check(v[i] == heap.prio(), "Wrong order in heap sort.");
1.49 heap.pop();
1.50 }
1.51 }
1.52 @@ -109,7 +113,6 @@
1.53 Heap heap(map);
1.54
1.55 std::vector<int> v(test_len);
1.56 -
1.57 for (int i = 0; i < test_len; ++i) {
1.58 v[i] = test_seq[i];
1.59 heap.push(i, v[i]);
1.60 @@ -120,13 +123,11 @@
1.61 }
1.62 std::sort(v.begin(), v.end());
1.63 for (int i = 0; i < test_len; ++i) {
1.64 - check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
1.65 + check(v[i] == heap.prio(), "Wrong order in heap increase test.");
1.66 heap.pop();
1.67 }
1.68 }
1.69
1.70 -
1.71 -
1.72 template <typename Heap>
1.73 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
1.74 Node source) {
1.75 @@ -141,7 +142,7 @@
1.76 Node t = digraph.target(a);
1.77 if (dijkstra.reached(s)) {
1.78 check( dijkstra.dist(t) - 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 @@ -150,7 +151,7 @@
1.85 Arc a = dijkstra.predArc(n);
1.86 Node s = digraph.source(a);
1.87 check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
1.88 - "Error in a shortest path tree!");
1.89 + "Error in shortest path tree.");
1.90 }
1.91 }
1.92
1.93 @@ -172,6 +173,7 @@
1.94 node("source", source).
1.95 run();
1.96
1.97 + // BinHeap
1.98 {
1.99 typedef BinHeap<Prio, ItemIntMap> IntHeap;
1.100 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.101 @@ -183,5 +185,92 @@
1.102 dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.103 }
1.104
1.105 + // FouraryHeap
1.106 + {
1.107 + typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
1.108 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.109 + heapSortTest<IntHeap>();
1.110 + heapIncreaseTest<IntHeap>();
1.111 +
1.112 + typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
1.113 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.114 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.115 + }
1.116 +
1.117 + // KaryHeap
1.118 + {
1.119 + typedef KaryHeap<Prio, ItemIntMap> IntHeap;
1.120 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.121 + heapSortTest<IntHeap>();
1.122 + heapIncreaseTest<IntHeap>();
1.123 +
1.124 + typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
1.125 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.126 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.127 + }
1.128 +
1.129 + // FibHeap
1.130 + {
1.131 + typedef FibHeap<Prio, ItemIntMap> IntHeap;
1.132 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.133 + heapSortTest<IntHeap>();
1.134 + heapIncreaseTest<IntHeap>();
1.135 +
1.136 + typedef FibHeap<Prio, IntNodeMap > NodeHeap;
1.137 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.138 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.139 + }
1.140 +
1.141 + // PairingHeap
1.142 + {
1.143 + typedef PairingHeap<Prio, ItemIntMap> IntHeap;
1.144 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.145 + heapSortTest<IntHeap>();
1.146 + heapIncreaseTest<IntHeap>();
1.147 +
1.148 + typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
1.149 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.150 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.151 + }
1.152 +
1.153 + // RadixHeap
1.154 + {
1.155 + typedef RadixHeap<ItemIntMap> IntHeap;
1.156 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.157 + heapSortTest<IntHeap>();
1.158 + heapIncreaseTest<IntHeap>();
1.159 +
1.160 + typedef RadixHeap<IntNodeMap > NodeHeap;
1.161 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.162 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.163 + }
1.164 +
1.165 + // BinomHeap
1.166 + {
1.167 + typedef BinomHeap<Prio, ItemIntMap> IntHeap;
1.168 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.169 + heapSortTest<IntHeap>();
1.170 + heapIncreaseTest<IntHeap>();
1.171 +
1.172 + typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
1.173 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.174 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.175 + }
1.176 +
1.177 + // BucketHeap, SimpleBucketHeap
1.178 + {
1.179 + typedef BucketHeap<ItemIntMap> IntHeap;
1.180 + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
1.181 + heapSortTest<IntHeap>();
1.182 + heapIncreaseTest<IntHeap>();
1.183 +
1.184 + typedef BucketHeap<IntNodeMap > NodeHeap;
1.185 + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
1.186 + dijkstraHeapTest<NodeHeap>(digraph, length, source);
1.187 +
1.188 + typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
1.189 + heapSortTest<SimpleIntHeap>();
1.190 + }
1.191 +
1.192 return 0;
1.193 }