Changeset 2263:9273fe7d850c in lemon-0.x for lemon/fib_heap.h

Timestamp:

10/26/06 16:20:17 (18 years ago)

Author:

mqrelly

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3021

Message:

Bug #46 fixed: Superfluous template parameter in Heap concept
NOTE: Not every affected file tested.

File:

• lemon/fib_heap.h (modified) (13 diffs)

lemon/fib_heap.h

@@ -44 +44 @@
   ///\e binary \e heap.
   ///
-  ///\param Item Type of the items to be stored.  
   ///\param Prio Type of the priority of the items.
   ///\param ItemIntMap A read and writable Item int map, used internally
@@ -56 +55 @@
  
 #ifdef DOXYGEN
-  template <typename Item, 
-            typename Prio, 
+  template <typename Prio, 
             typename ItemIntMap, 
             typename Compare>
 #else
-  template <typename Item, 
-            typename Prio, 
+  template <typename Prio, 
             typename ItemIntMap, 
             typename Compare = std::less<Prio> >
 #endif
   class FibHeap {
-  public:     
+  public:
+    typedef typename ItemIntMap::Key Item;
     typedef Prio PrioType;
     
@@ -272 +270 @@
     // **********************************************************************
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::set 
   (Item const item, PrioType const value) 
   {
@@ -284 +282 @@
   }
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::push 
   (Item const item, PrioType const value) {
       int i=iimap[item];      
@@ -317 +315 @@
     }
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::pop() {
       /*The first case is that there are only one root.*/
       if ( container[minimum].left_neighbor==minimum ) {
@@ -351 +349 @@
 
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::erase 
   (const Item& item) {
       int i=iimap[item];
@@ -368 +366 @@
   }
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::decrease 
   (Item item, PrioType const value) {
       int i=iimap[item];
@@ -384 +382 @@
  
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::balance() {      
 
     int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
@@ -429 +427 @@
     }
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::makeroot 
   (int c) {
       int s=c;
@@ -441 +439 @@
   
   
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::cut 
   (int a, int b) {    
     /*
@@ -470 +468 @@
   
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::cascade 
   (int a) 
     {
@@ -487 +485 @@
 
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::fuse 
   (int a, int b) {
       unlace(b);
@@ -518 +516 @@
    *It is invoked only if a has siblings.
    */
-  template <typename Item, typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
+  template <typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Prio, ItemIntMap, Compare>::unlace 
   (int a) {      
       int leftn=container[a].left_neighbor;