diff -r d8475431bbbb -r 8e85e6bbefdf lemon/fib_heap.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/fib_heap.h	Mon May 23 04:48:14 2005 +0000
@@ -0,0 +1,531 @@
+/* -*- C++ -*-
+ * lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_FIB_HEAP_H
+#define LEMON_FIB_HEAP_H
+
+///\file
+///\ingroup auxdat
+///\brief Fibonacci Heap implementation.
+
+#include <vector>
+#include <functional>
+#include <cmath>
+
+namespace lemon {
+  
+  /// \addtogroup auxdat
+  /// @{
+
+  /// Fibonacci Heap.
+
+  ///This class implements the \e Fibonacci \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 Compare specifies the ordering of the priorities. In a heap
+  ///one can change the priority of an item, add or erase an item, etc.
+  ///
+  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
+  ///heap. In case of many calls to these operations, it is better to use a
+  ///\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
+  ///to handle the cross references.
+  ///\param Compare A class for the ordering of the priorities. The
+  ///default is \c std::less<Prio>.
+  ///
+  ///\sa BinHeap
+  ///\sa Dijkstra
+  ///\author Jacint Szabo 
+ 
+#ifdef DOXYGEN
+  template <typename Item, 
+	    typename Prio, 
+	    typename ItemIntMap, 
+	    typename Compare>
+#else
+  template <typename Item, 
+	    typename Prio, 
+	    typename ItemIntMap, 
+	    typename Compare = std::less<Prio> >
+#endif
+  class FibHeap {
+  public:     
+    typedef Prio PrioType;
+    
+  private:
+    class store;
+    
+    std::vector<store> container;
+    int minimum;
+    ItemIntMap &iimap;
+    Compare comp;
+    int num_items;
+    
+  public:
+    ///Status of the nodes
+    enum state_enum {
+      ///The node is in the heap
+      IN_HEAP = 0,
+      ///The node has never been in the heap
+      PRE_HEAP = -1,
+      ///The node was in the heap but it got out of it
+      POST_HEAP = -2
+    };
+    
+    ///The constructor
+
+    /**
+       \c _iimap should be given to the constructor, since it is
+       used internally to handle the cross references.
+    */
+    explicit FibHeap(ItemIntMap &_iimap) 
+      : minimum(0), iimap(_iimap), num_items() {} 
+ 
+    ///The constructor
+
+    /**
+       \c _iimap should be given to the constructor, since it is used
+       internally to handle the cross references. \c _comp is an
+       object for ordering of the priorities. 
+    */
+    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
+		  iimap(_iimap), comp(_comp), num_items() {}
+    
+    ///The number of items stored in the heap.
+
+    /**
+       Returns the number of items stored in the heap.
+    */
+    int size() const { return num_items; }
+
+    ///Checks if the heap stores no items.
+    
+    /**
+       Returns \c true if and only if the heap stores no items.
+    */
+    bool empty() const { return num_items==0; }
+
+    ///\c item gets to the heap with priority \c value independently if \c item was already there.
+
+    /**
+       This method calls \ref push(\c item, \c value) if \c item is not
+       stored in the heap and it calls \ref decrease(\c item, \c value) or
+       \ref increase(\c item, \c value) otherwise.
+    */
+    void set (Item const item, PrioType const value); 
+    
+    ///Adds \c item to the heap with priority \c value. 
+    
+    /**
+       Adds \c item to the heap with priority \c value. 
+       \pre \c item must not be stored in the heap. 
+    */
+    void push (Item const item, PrioType const value);
+    
+    ///Returns the item with minimum priority relative to \c Compare.
+    
+    /**
+       This method returns the item with minimum priority relative to \c
+       Compare.  
+       \pre The heap must be nonempty.  
+    */
+    Item top() const { return container[minimum].name; }
+
+    ///Returns the minimum priority relative to \c Compare.
+
+    /**
+       It returns the minimum priority relative to \c Compare.
+       \pre The heap must be nonempty.
+    */
+    PrioType prio() const { return container[minimum].prio; }
+    
+    ///Returns the priority of \c item.
+
+    /**
+       This function returns the priority of \c item.
+       \pre \c item must be in the heap.
+    */
+    PrioType& operator[](const Item& item) { 
+      return container[iimap[item]].prio; 
+    }
+    
+    ///Returns the priority of \c item.
+    
+    /**
+       It returns the priority of \c item.
+       \pre \c item must be in the heap.
+    */
+    const PrioType& operator[](const Item& item) const { 
+      return container[iimap[item]].prio; 
+    }
+
+
+    ///Deletes the item with minimum priority relative to \c Compare.
+
+    /**
+    This method deletes the item with minimum priority relative to \c
+    Compare from the heap.  
+    \pre The heap must be non-empty.  
+    */
+    void pop();
+
+    ///Deletes \c item from the heap.
+
+    /**
+       This method deletes \c item from the heap, if \c item was already
+       stored in the heap. It is quite inefficient in Fibonacci heaps.
+    */
+    void erase (const Item& item); 
+
+    ///Decreases the priority of \c item to \c value.
+
+    /**
+       This method decreases the priority of \c item to \c value.
+       \pre \c item must be stored in the heap with priority at least \c
+       value relative to \c Compare.
+    */
+    void decrease (Item item, PrioType const value); 
+
+    ///Increases the priority of \c item to \c value.
+
+    /**
+       This method sets the priority of \c item to \c value. Though
+       there is no precondition on the priority of \c item, this
+       method should be used only if it is indeed necessary to increase
+       (relative to \c Compare) the priority of \c item, because this
+       method is inefficient.
+    */
+    void increase (Item item, PrioType const value) {
+      erase(item);
+      push(item, value);
+    }
+
+
+    ///Returns if \c item is in, has already been in, or has never been in the heap.
+
+    /**
+       This method returns PRE_HEAP if \c item has never been in the
+       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+       otherwise. In the latter case it is possible that \c item will
+       get back to the heap again.
+    */
+    state_enum state(const Item &item) const {
+      int i=iimap[item];
+      if( i>=0 ) {
+	if ( container[i].in ) i=0;
+	else i=-2; 
+      }
+      return state_enum(i);
+    }    
+    
+  private:
+    
+    void balance();
+    void makeroot(int c);
+    void cut(int a, int b);
+    void cascade(int a);
+    void fuse(int a, int b);
+    void unlace(int a);
+
+
+    class store {
+      friend class FibHeap;
+      
+      Item name;
+      int parent;
+      int left_neighbor;
+      int right_neighbor;
+      int child;
+      int degree;  
+      bool marked;
+      bool in;
+      PrioType prio;
+      
+      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
+    };
+  };    
+ 
+
+
+    // **********************************************************************
+    //  IMPLEMENTATIONS
+    // **********************************************************************
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
+  (Item const item, PrioType const value) 
+  {
+    int i=iimap[item];
+    if ( i >= 0 && container[i].in ) {
+      if ( comp(value, container[i].prio) ) decrease(item, value); 
+      if ( comp(container[i].prio, value) ) increase(item, value); 
+    } else push(item, value);
+  }
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
+  (Item const item, PrioType const value) {
+      int i=iimap[item];      
+      if ( i < 0 ) {
+	int s=container.size();
+	iimap.set( item, s );	
+	store st;
+	st.name=item;
+	container.push_back(st);
+	i=s;
+      } else {
+	container[i].parent=container[i].child=-1;
+	container[i].degree=0;
+	container[i].in=true;
+	container[i].marked=false;
+      }
+
+      if ( num_items ) {
+	container[container[minimum].right_neighbor].left_neighbor=i;
+	container[i].right_neighbor=container[minimum].right_neighbor;
+	container[minimum].right_neighbor=i;
+	container[i].left_neighbor=minimum;
+	if ( comp( value, container[minimum].prio) ) minimum=i; 
+      } else {
+	container[i].right_neighbor=container[i].left_neighbor=i;
+	minimum=i;	
+      }
+      container[i].prio=value;
+      ++num_items;
+    }
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
+      /*The first case is that there are only one root.*/
+      if ( container[minimum].left_neighbor==minimum ) {
+	container[minimum].in=false;
+	if ( container[minimum].degree!=0 ) { 
+	  makeroot(container[minimum].child);
+	  minimum=container[minimum].child;
+	  balance();
+	}
+      } else {
+	int right=container[minimum].right_neighbor;
+	unlace(minimum);
+	container[minimum].in=false;
+	if ( container[minimum].degree > 0 ) {
+	  int left=container[minimum].left_neighbor;
+	  int child=container[minimum].child;
+	  int last_child=container[child].left_neighbor;
+	
+	  makeroot(child);
+	  
+	  container[left].right_neighbor=child;
+	  container[child].left_neighbor=left;
+	  container[right].left_neighbor=last_child;
+	  container[last_child].right_neighbor=right;
+	}
+	minimum=right;
+	balance();
+      } // the case where there are more roots
+      --num_items;   
+    }
+
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
+  (const Item& item) {
+      int i=iimap[item];
+      
+      if ( i >= 0 && container[i].in ) { 	
+	if ( container[i].parent!=-1 ) {
+	  int p=container[i].parent;
+	  cut(i,p);	    
+	  cascade(p);
+	}
+	minimum=i;     //As if its prio would be -infinity
+	pop();
+      }
+  }
+    
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
+  (Item item, PrioType const value) {
+      int i=iimap[item];
+      container[i].prio=value;
+      int p=container[i].parent;
+      
+      if ( p!=-1 && comp(value, container[p].prio) ) {
+	cut(i,p);	    
+	cascade(p);
+      }      
+      if ( comp(value, container[minimum].prio) ) minimum=i; 
+  }
+ 
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
+
+    int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
+  
+    std::vector<int> A(maxdeg,-1); 
+    
+    /*
+     *Recall that now minimum does not point to the minimum prio element.
+     *We set minimum to this during balance().
+     */
+    int anchor=container[minimum].left_neighbor; 
+    int next=minimum; 
+    bool end=false; 
+    	
+       do {
+	int active=next;
+	if ( anchor==active ) end=true;
+	int d=container[active].degree;
+	next=container[active].right_neighbor;
+
+	while (A[d]!=-1) {	  
+	  if( comp(container[active].prio, container[A[d]].prio) ) {
+	    fuse(active,A[d]); 
+	  } else { 
+	    fuse(A[d],active);
+	    active=A[d];
+	  } 
+	  A[d]=-1;
+	  ++d;
+	}	
+	A[d]=active;
+       } while ( !end );
+
+
+       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
+       int s=minimum;
+       int m=minimum;
+       do {  
+	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
+	 s=container[s].right_neighbor;
+       } while ( s != m );
+    }
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
+  (int c) {
+      int s=c;
+      do {  
+	container[s].parent=-1;
+	s=container[s].right_neighbor;
+      } while ( s != c );
+    }
+  
+  
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
+  (int a, int b) {    
+    /*
+     *Replacing a from the children of b.
+     */
+    --container[b].degree;
+    
+    if ( container[b].degree !=0 ) {
+      int child=container[b].child;
+      if ( child==a ) 
+	container[b].child=container[child].right_neighbor;
+      unlace(a);
+    }
+    
+    
+    /*Lacing a to the roots.*/
+    int right=container[minimum].right_neighbor;
+    container[minimum].right_neighbor=a;
+    container[a].left_neighbor=minimum;
+    container[a].right_neighbor=right;
+    container[right].left_neighbor=a;
+    
+    container[a].parent=-1;
+    container[a].marked=false;
+  }
+  
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
+  (int a) 
+    {
+      if ( container[a].parent!=-1 ) {
+	int p=container[a].parent;
+	
+	if ( container[a].marked==false ) container[a].marked=true;
+	else {
+	  cut(a,p);
+	  cascade(p);
+	}
+      }
+    }
+
+
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
+  (int a, int b) {
+      unlace(b);
+      
+      /*Lacing b under a.*/
+      container[b].parent=a;
+
+      if (container[a].degree==0) {
+	container[b].left_neighbor=b;
+	container[b].right_neighbor=b;
+	container[a].child=b;	
+      } else {
+	int child=container[a].child;
+	int last_child=container[child].left_neighbor;
+	container[child].left_neighbor=b;
+	container[b].right_neighbor=child;
+	container[last_child].right_neighbor=b;
+	container[b].left_neighbor=last_child;
+      }
+
+      ++container[a].degree;
+      
+      container[b].marked=false;
+    }
+
+  
+  /*
+   *It is invoked only if a has siblings.
+   */
+  template <typename Item, typename Prio, typename ItemIntMap, 
+    typename Compare>
+  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
+  (int a) {      
+      int leftn=container[a].left_neighbor;
+      int rightn=container[a].right_neighbor;
+      container[leftn].right_neighbor=rightn;
+      container[rightn].left_neighbor=leftn;
+  }
+  
+  ///@}
+
+} //namespace lemon
+
+#endif //LEMON_FIB_HEAP_H
+