test/heap_test.cc
changeset 895 dca9eed2c375
parent 702 bdc7dfc8c054
child 948 f9e3f73e17f1
equal deleted inserted replaced
10:187f5622bad7 11:c664b7baced3
    28 #include <lemon/lgf_reader.h>
    28 #include <lemon/lgf_reader.h>
    29 #include <lemon/dijkstra.h>
    29 #include <lemon/dijkstra.h>
    30 #include <lemon/maps.h>
    30 #include <lemon/maps.h>
    31 
    31 
    32 #include <lemon/bin_heap.h>
    32 #include <lemon/bin_heap.h>
    33 #include <lemon/fourary_heap.h>
    33 #include <lemon/quad_heap.h>
    34 #include <lemon/kary_heap.h>
    34 #include <lemon/dheap.h>
    35 #include <lemon/fib_heap.h>
    35 #include <lemon/fib_heap.h>
    36 #include <lemon/pairing_heap.h>
    36 #include <lemon/pairing_heap.h>
    37 #include <lemon/radix_heap.h>
    37 #include <lemon/radix_heap.h>
    38 #include <lemon/binom_heap.h>
    38 #include <lemon/binomial_heap.h>
    39 #include <lemon/bucket_heap.h>
    39 #include <lemon/bucket_heap.h>
    40 
    40 
    41 #include "test_tools.h"
    41 #include "test_tools.h"
    42 
    42 
    43 using namespace lemon;
    43 using namespace lemon;
   183     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
   183     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
   184     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   184     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   185     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   185     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   186   }
   186   }
   187 
   187 
   188   // FouraryHeap
   188   // QuadHeap
   189   {
   189   {
   190     typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
   190     typedef QuadHeap<Prio, ItemIntMap> IntHeap;
   191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   192     heapSortTest<IntHeap>();
   192     heapSortTest<IntHeap>();
   193     heapIncreaseTest<IntHeap>();
   193     heapIncreaseTest<IntHeap>();
   194 
   194 
   195     typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
   195     typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
   196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   198   }
   198   }
   199 
   199 
   200   // KaryHeap
   200   // DHeap
   201   {
   201   {
   202     typedef KaryHeap<Prio, ItemIntMap> IntHeap;
   202     typedef DHeap<Prio, ItemIntMap> IntHeap;
   203     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   203     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   204     heapSortTest<IntHeap>();
   204     heapSortTest<IntHeap>();
   205     heapIncreaseTest<IntHeap>();
   205     heapIncreaseTest<IntHeap>();
   206 
   206 
   207     typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
   207     typedef DHeap<Prio, IntNodeMap > NodeHeap;
   208     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   208     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   209     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   209     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   210   }
   210   }
   211 
   211 
   212   // FibHeap
   212   // FibHeap
   243     typedef RadixHeap<IntNodeMap > NodeHeap;
   243     typedef RadixHeap<IntNodeMap > NodeHeap;
   244     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   244     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   245     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   245     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   246   }
   246   }
   247 
   247 
   248   // BinomHeap
   248   // BinomialHeap
   249   {
   249   {
   250     typedef BinomHeap<Prio, ItemIntMap> IntHeap;
   250     typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
   251     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   251     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   252     heapSortTest<IntHeap>();
   252     heapSortTest<IntHeap>();
   253     heapIncreaseTest<IntHeap>();
   253     heapIncreaseTest<IntHeap>();
   254 
   254 
   255     typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
   255     typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
   256     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   256     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   257     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   257     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   258   }
   258   }
   259 
   259 
   260   // BucketHeap, SimpleBucketHeap
   260   // BucketHeap, SimpleBucketHeap