Changes in / [685:a27356ceb5bd:687:fb93895f84d9] in lemon-main

Files:

• lemon/Makefile.am (modified) (4 diffs)
• lemon/bin_heap.h (modified) (3 diffs)
• lemon/bucket_heap.h (added)
• lemon/fib_heap.h (added)
• lemon/radix_heap.h (added)
• test/heap_test.cc (modified) (2 diffs)

lemon/Makefile.am

@@ -60 +60 @@
         lemon/bfs.h \
         lemon/bin_heap.h \
+        lemon/bucket_heap.h \
         lemon/cbc.h \
         lemon/circulation.h \
@@ -77 +78 @@
         lemon/error.h \
         lemon/euler.h \
+        lemon/fib_heap.h \
         lemon/full_graph.h \
         lemon/glpk.h \
@@ -91 +93 @@
         lemon/lp_base.h \
         lemon/lp_skeleton.h \
-        lemon/list_graph.h \
         lemon/maps.h \
         lemon/matching.h \
@@ -100 +101 @@
         lemon/path.h \
         lemon/preflow.h \
+        lemon/radix_heap.h \
         lemon/radix_sort.h \
         lemon/random.h \

lemon/bin_heap.h

@@ -34 +34 @@
   ///\brief A Binary Heap implementation.
   ///
-  ///This class implements the \e binary \e heap data structure. 
-  /// 
+  ///This class implements the \e binary \e heap data structure.
+  ///
   ///A \e heap is a data structure for storing items with specified values
   ///called \e priorities in such a way that finding the item with minimum
-  ///priority is efficient. \c Comp specifies the ordering of the priorities.
+  ///priority is efficient. \c CMP specifies the ordering of the priorities.
   ///In a heap one can change the priority of an item, add or erase an
   ///item, etc.
@@ -45 +45 @@
   ///\tparam IM A read and writable item map with int values, used internally
   ///to handle the cross references.
-  ///\tparam Comp A functor class for the ordering of the priorities.
+  ///\tparam CMP A functor class for the ordering of the priorities.
   ///The default is \c std::less<PR>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename PR, typename IM, typename Comp = std::less<PR> >
+  template <typename PR, typename IM, typename CMP = std::less<PR> >
   class BinHeap {
 
@@ -63 +63 @@
     typedef std::pair<Item,Prio> Pair;
     ///\e
-    typedef Comp Compare;
+    typedef CMP Compare;
 
     /// \brief Type to represent the items states.

test/heap_test.cc

@@ -32 +32 @@
 
 #include <lemon/bin_heap.h>
+#include <lemon/fib_heap.h>
+#include <lemon/radix_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include "test_tools.h"
@@ -184 +187 @@
   }
 
+  {
+    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);
+  }
+
+  {
+    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);
+  }
+
+  {
+    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);
+  }
+
+
   return 0;
 }