diff -r f47b6c94577e -r 684964884a2e test/heap_test.cc --- a/test/heap_test.cc Sun Aug 02 12:40:20 2009 +0200 +++ b/test/heap_test.cc Fri Sep 25 09:13:03 2009 +0200 @@ -25,12 +25,18 @@ #include <lemon/concepts/heap.h> #include <lemon/smart_graph.h> - #include <lemon/lgf_reader.h> #include <lemon/dijkstra.h> #include <lemon/maps.h> #include <lemon/bin_heap.h> +#include <lemon/fourary_heap.h> +#include <lemon/kary_heap.h> +#include <lemon/fib_heap.h> +#include <lemon/pairing_heap.h> +#include <lemon/radix_heap.h> +#include <lemon/binom_heap.h> +#include <lemon/bucket_heap.h> #include "test_tools.h" @@ -86,18 +92,16 @@ template <typename Heap> void heapSortTest() { RangeMap<int> map(test_len, -1); - Heap heap(map); std::vector<int> v(test_len); - for (int i = 0; i < test_len; ++i) { v[i] = test_seq[i]; heap.push(i, v[i]); } std::sort(v.begin(), v.end()); for (int i = 0; i < test_len; ++i) { - check(v[i] == heap.prio() ,"Wrong order in heap sort."); + check(v[i] == heap.prio(), "Wrong order in heap sort."); heap.pop(); } } @@ -109,7 +113,6 @@ Heap heap(map); std::vector<int> v(test_len); - for (int i = 0; i < test_len; ++i) { v[i] = test_seq[i]; heap.push(i, v[i]); @@ -120,13 +123,11 @@ } std::sort(v.begin(), v.end()); for (int i = 0; i < test_len; ++i) { - check(v[i] == heap.prio() ,"Wrong order in heap increase test."); + check(v[i] == heap.prio(), "Wrong order in heap increase test."); heap.pop(); } } - - template <typename Heap> void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, Node source) { @@ -141,7 +142,7 @@ Node t = digraph.target(a); if (dijkstra.reached(s)) { check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], - "Error in a shortest path tree!"); + "Error in shortest path tree."); } } @@ -150,7 +151,7 @@ Arc a = dijkstra.predArc(n); Node s = digraph.source(a); check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], - "Error in a shortest path tree!"); + "Error in shortest path tree."); } } @@ -172,6 +173,7 @@ node("source", source). run(); + // BinHeap { typedef BinHeap<Prio, ItemIntMap> IntHeap; checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); @@ -183,5 +185,92 @@ dijkstraHeapTest<NodeHeap>(digraph, length, source); } + // FouraryHeap + { + typedef FouraryHeap<Prio, ItemIntMap> IntHeap; + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); + heapSortTest<IntHeap>(); + heapIncreaseTest<IntHeap>(); + + typedef FouraryHeap<Prio, IntNodeMap > NodeHeap; + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); + dijkstraHeapTest<NodeHeap>(digraph, length, source); + } + + // KaryHeap + { + typedef KaryHeap<Prio, ItemIntMap> IntHeap; + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); + heapSortTest<IntHeap>(); + heapIncreaseTest<IntHeap>(); + + typedef KaryHeap<Prio, IntNodeMap > NodeHeap; + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); + dijkstraHeapTest<NodeHeap>(digraph, length, source); + } + + // FibHeap + { + typedef FibHeap<Prio, ItemIntMap> IntHeap; + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); + heapSortTest<IntHeap>(); + heapIncreaseTest<IntHeap>(); + + typedef FibHeap<Prio, IntNodeMap > NodeHeap; + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); + dijkstraHeapTest<NodeHeap>(digraph, length, source); + } + + // PairingHeap + { + typedef PairingHeap<Prio, ItemIntMap> IntHeap; + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); + heapSortTest<IntHeap>(); + heapIncreaseTest<IntHeap>(); + + typedef PairingHeap<Prio, IntNodeMap > NodeHeap; + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); + dijkstraHeapTest<NodeHeap>(digraph, length, source); + } + + // RadixHeap + { + typedef RadixHeap<ItemIntMap> IntHeap; + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); + heapSortTest<IntHeap>(); + heapIncreaseTest<IntHeap>(); + + typedef RadixHeap<IntNodeMap > NodeHeap; + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); + dijkstraHeapTest<NodeHeap>(digraph, length, source); + } + + // BinomHeap + { + typedef BinomHeap<Prio, ItemIntMap> IntHeap; + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); + heapSortTest<IntHeap>(); + heapIncreaseTest<IntHeap>(); + + typedef BinomHeap<Prio, IntNodeMap > NodeHeap; + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); + dijkstraHeapTest<NodeHeap>(digraph, length, source); + } + + // BucketHeap, SimpleBucketHeap + { + typedef BucketHeap<ItemIntMap> IntHeap; + checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); + heapSortTest<IntHeap>(); + heapIncreaseTest<IntHeap>(); + + typedef BucketHeap<IntNodeMap > NodeHeap; + checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); + dijkstraHeapTest<NodeHeap>(digraph, length, source); + + typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap; + heapSortTest<SimpleIntHeap>(); + } + return 0; }