# HG changeset patch
# User deba
# Date 1198762816 0
# Node ID f393a81626889729dd631f45e736092e577cb0b6
# Parent  b5eba564bb602a9578dd92614c5c3d7e3bec182b
Renaming state_enum to State
Removing "Type" suffix from typedefs
Moving implementation into the class definition

diff -r b5eba564bb60 -r f393a8162688 lemon/bin_heap.h
--- a/lemon/bin_heap.h	Thu Dec 20 15:21:22 2007 +0000
+++ b/lemon/bin_heap.h	Thu Dec 27 13:40:16 2007 +0000
@@ -39,24 +39,24 @@
   ///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.
   ///
-  ///\param Prio Type of the priority of the items.
-  ///\param ItemIntMap A read and writable Item int map, used internally
+  ///\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>.
+  ///\param _Compare A class for the ordering of the priorities. The
+  ///default is \c std::less<_Prio>.
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename Prio, typename ItemIntMap,
-	    typename Compare = std::less<Prio> >
+  template <typename _Prio, typename _ItemIntMap,
+	    typename _Compare = std::less<_Prio> >
   class BinHeap {
 
   public:
-    typedef typename ItemIntMap::Key         ItemType;
-    typedef Prio                             PrioType;
-    typedef std::pair<ItemType,PrioType>     PairType;
-    typedef ItemIntMap                       ItemIntMapType;
-    typedef Compare                          PrioCompare;
+    typedef _ItemIntMap ItemIntMap;
+    typedef _Prio Prio;
+    typedef typename ItemIntMap::Key Item;
+    typedef std::pair<Item,Prio> Pair;
+    typedef _Compare Compare;
 
     /// \brief Type to represent the items states.
     ///
@@ -66,14 +66,14 @@
     ///
     /// The ItemIntMap \e should be initialized in such way that it maps
     /// PRE_HEAP (-1) to any element to be put in the heap...
-    enum state_enum {
+    enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
       POST_HEAP = -2
     };
 
   private:
-    std::vector<PairType> data;
+    std::vector<Pair> data;
     Compare comp;
     ItemIntMap &iim;
 
@@ -122,11 +122,11 @@
     static int parent(int i) { return (i-1)/2; }
 
     static int second_child(int i) { return 2*i+2; }
-    bool less(const PairType &p1, const PairType &p2) const {
+    bool less(const Pair &p1, const Pair &p2) const {
       return comp(p1.second, p2.second);
     }
 
-    int bubble_up(int hole, PairType p) {
+    int bubble_up(int hole, Pair p) {
       int par = parent(hole);
       while( hole>0 && less(p,data[par]) ) {
 	move(data[par],hole);
@@ -137,7 +137,7 @@
       return hole;
     }
 
-    int bubble_down(int hole, PairType p, int length) {
+    int bubble_down(int hole, Pair p, int length) {
       int child = second_child(hole);
       while(child < length) {
 	if( less(data[child-1], data[child]) ) {
@@ -159,7 +159,7 @@
       return hole;
     }
 
-    void move(const PairType &p, int i) {
+    void move(const Pair &p, int i) {
       data[i] = p;
       iim.set(p.first, i);
     }
@@ -169,7 +169,7 @@
     ///
     /// Adds \c p.first to the heap with priority \c p.second.
     /// \param p The pair to insert.
-    void push(const PairType &p) {
+    void push(const Pair &p) {
       int n = data.size();
       data.resize(n+1);
       bubble_up(n, p);
@@ -180,14 +180,14 @@
     /// Adds \c i to the heap with priority \c p. 
     /// \param i The item to insert.
     /// \param p The priority of the item.
-    void push(const ItemType &i, const Prio &p) { push(PairType(i,p)); }
+    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 
     /// \brief 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.  
-    ItemType top() const {
+    Item top() const {
       return data[0].first;
     }
 
@@ -218,7 +218,7 @@
     /// This method deletes item \c i from the heap.
     /// \param i The item to erase.
     /// \pre The item should be in the heap.
-    void erase(const ItemType &i) {
+    void erase(const Item &i) {
       int h = iim[i];
       int n = data.size()-1;
       iim.set(data[h].first, POST_HEAP);
@@ -236,7 +236,7 @@
     /// This function returns the priority of item \c i.  
     /// \pre \c i must be in the heap.
     /// \param i The item.
-    Prio operator[](const ItemType &i) const {
+    Prio operator[](const Item &i) const {
       int idx = iim[i];
       return data[idx].second;
     }
@@ -248,16 +248,16 @@
     /// in the heap and sets the priority of \c i to \c p otherwise.
     /// \param i The item.
     /// \param p The priority.
-    void set(const ItemType &i, const Prio &p) {
+    void set(const Item &i, const Prio &p) {
       int idx = iim[i];
       if( idx < 0 ) {
 	push(i,p);
       }
       else if( comp(p, data[idx].second) ) {
-	bubble_up(idx, PairType(i,p));
+	bubble_up(idx, Pair(i,p));
       }
       else {
-	bubble_down(idx, PairType(i,p), data.size());
+	bubble_down(idx, Pair(i,p), data.size());
       }
     }
 
@@ -268,9 +268,9 @@
     /// p relative to \c Compare.
     /// \param i The item.
     /// \param p The priority.
-    void decrease(const ItemType &i, const Prio &p) {
+    void decrease(const Item &i, const Prio &p) {
       int idx = iim[i];
-      bubble_up(idx, PairType(i,p));
+      bubble_up(idx, Pair(i,p));
     }
     
     /// \brief Increases the priority of \c i to \c p.
@@ -280,9 +280,9 @@
     /// p relative to \c Compare.
     /// \param i The item.
     /// \param p The priority.
-    void increase(const ItemType &i, const Prio &p) {
+    void increase(const Item &i, const Prio &p) {
       int idx = iim[i];
-      bubble_down(idx, PairType(i,p), data.size());
+      bubble_down(idx, Pair(i,p), data.size());
     }
 
     /// \brief Returns if \c item is in, has already been in, or has 
@@ -293,11 +293,11 @@
     /// otherwise. In the latter case it is possible that \c item will
     /// get back to the heap again.
     /// \param i The item.
-    state_enum state(const ItemType &i) const {
+    State state(const Item &i) const {
       int s = iim[i];
       if( s>=0 )
 	s=0;
-      return state_enum(s);
+      return State(s);
     }
 
     /// \brief Sets the state of the \c item in the heap.
@@ -307,7 +307,7 @@
     /// better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP. 
-    void state(const ItemType& i, state_enum st) {
+    void state(const Item& i, State st) {
       switch (st) {
       case POST_HEAP:
       case PRE_HEAP:
diff -r b5eba564bb60 -r f393a8162688 lemon/bucket_heap.h
--- a/lemon/bucket_heap.h	Thu Dec 20 15:21:22 2007 +0000
+++ b/lemon/bucket_heap.h	Thu Dec 27 13:40:16 2007 +0000
@@ -49,9 +49,13 @@
   class BucketHeap {
 
   public:
+    /// \e
     typedef typename _ItemIntMap::Key Item;
+    /// \e
     typedef int Prio;
+    /// \e
     typedef std::pair<Item, Prio> Pair;
+    /// \e
     typedef _ItemIntMap ItemIntMap;
 
     /// \brief Type to represent the items states.
@@ -62,7 +66,7 @@
     ///
     /// The ItemIntMap \e should be initialized in such way that it maps
     /// PRE_HEAP (-1) to any element to be put in the heap...
-    enum state_enum {
+    enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
       POST_HEAP = -2
@@ -278,10 +282,10 @@
     /// otherwise. In the latter case it is possible that \c item will
     /// get back to the heap again.
     /// \param i The item.
-    state_enum state(const Item &i) const {
+    State state(const Item &i) const {
       int idx = index[i];
       if (idx >= 0) idx = 0;
-      return state_enum(idx);
+      return State(idx);
     }
 
     /// \brief Sets the state of the \c item in the heap.
@@ -291,7 +295,7 @@
     /// better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP. 
-    void state(const Item& i, state_enum st) {
+    void state(const Item& i, State st) {
       switch (st) {
       case POST_HEAP:
       case PRE_HEAP:
@@ -334,7 +338,7 @@
     typedef std::pair<Item, Prio> Pair;
     typedef _ItemIntMap ItemIntMap;
 
-    enum state_enum {
+    enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
       POST_HEAP = -2
@@ -472,13 +476,13 @@
       lace(idx);
     }
 
-    state_enum state(const Item &i) const {
+    State state(const Item &i) const {
       int idx = index[i];
       if (idx >= 0) idx = 0;
-      return state_enum(idx);
+      return State(idx);
     }
 
-    void state(const Item& i, state_enum st) {
+    void state(const Item& i, State st) {
       switch (st) {
       case POST_HEAP:
       case PRE_HEAP:
@@ -546,7 +550,7 @@
     ///
     /// The ItemIntMap \e should be initialized in such way that it maps
     /// PRE_HEAP (-1) to any element to be put in the heap...
-    enum state_enum {
+    enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
       POST_HEAP = -2
@@ -683,10 +687,10 @@
     /// otherwise. In the latter case it is possible that \c item will
     /// get back to the heap again.
     /// \param i The item.
-    state_enum state(const Item &i) const {
+    State state(const Item &i) const {
       int idx = index[i];
       if (idx >= 0) idx = 0;
-      return state_enum(idx);
+      return State(idx);
     }
 
   private:
@@ -716,7 +720,7 @@
     typedef std::pair<Item, Prio> Pair;
     typedef _ItemIntMap ItemIntMap;
 
-    enum state_enum {
+    enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
       POST_HEAP = -2
@@ -798,10 +802,10 @@
       return -1;
     }
 
-    state_enum state(const Item &i) const {
+    State state(const Item &i) const {
       int idx = index[i];
       if (idx >= 0) idx = 0;
-      return state_enum(idx);
+      return State(idx);
     }
 
   private:
diff -r b5eba564bb60 -r f393a8162688 lemon/concepts/heap.h
--- a/lemon/concepts/heap.h	Thu Dec 20 15:21:22 2007 +0000
+++ b/lemon/concepts/heap.h	Thu Dec 27 13:40:16 2007 +0000
@@ -52,7 +52,7 @@
       ///
       /// The ItemIntMap _should_ be initialized in such way, that it maps
       /// PRE_HEAP (-1) to any element to be put in the heap...
-      enum state_enum {
+      enum State {
 	IN_HEAP = 0,
 	PRE_HEAP = -1,
 	POST_HEAP = -2
@@ -155,7 +155,7 @@
       /// otherwise. In the latter case it is possible that \c item will
       /// get back to the heap again.
       /// \param i The item.
-      state_enum state(const Item &i) const {}
+      State state(const Item &i) const {}
 
       /// \brief Sets the state of the \c item in the heap.
       ///
@@ -164,7 +164,7 @@
       /// better time complexity.
       /// \param i The item.
       /// \param st The state. It should not be \c IN_HEAP. 
-      void state(const Item& i, state_enum st) {}
+      void state(const Item& i, State st) {}
 
 
       template <typename _Heap>
@@ -181,8 +181,8 @@
 	  ignore_unused_variable_warning(item);
 	  ignore_unused_variable_warning(prio);
 
-	  typedef typename _Heap::state_enum state_enum;
-	  state_enum state;
+	  typedef typename _Heap::State State;
+	  State state;
 
 	  ignore_unused_variable_warning(state);
       
diff -r b5eba564bb60 -r f393a8162688 lemon/fib_heap.h
--- a/lemon/fib_heap.h	Thu Dec 20 15:21:22 2007 +0000
+++ b/lemon/fib_heap.h	Thu Dec 27 13:40:16 2007 +0000
@@ -41,31 +41,34 @@
   ///
   ///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.
+  ///\ref BinHeap "binary heap".
   ///
-  ///\param Prio Type of the priority of the items.
-  ///\param ItemIntMap A read and writable Item int map, used internally
+  ///\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>.
+  ///\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 Prio, 
-	    typename ItemIntMap, 
-	    typename Compare>
+  template <typename _Prio, 
+	    typename _ItemIntMap, 
+	    typename _Compare>
 #else
-  template <typename Prio, 
-	    typename ItemIntMap, 
-	    typename Compare = std::less<Prio> >
+  template <typename _Prio, 
+	    typename _ItemIntMap, 
+	    typename _Compare = std::less<_Prio> >
 #endif
   class FibHeap {
   public:
+    typedef _ItemIntMap ItemIntMap;
+    typedef _Prio Prio;
     typedef typename ItemIntMap::Key Item;
-    typedef Prio PrioType;
+    typedef std::pair<Item,Prio> Pair;
+    typedef _Compare Compare;
     
   private:
     class store;
@@ -78,7 +81,7 @@
     
   public:
     ///Status of the nodes
-    enum state_enum {
+    enum State {
       ///The node is in the heap
       IN_HEAP = 0,
       ///The node has never been in the heap
@@ -99,8 +102,8 @@
     /// \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() {}
+    FibHeap(ItemIntMap &_iimap, const Compare &_comp) 
+      : minimum(0), iimap(_iimap), comp(_comp), num_items() {}
     
     /// \brief The number of items stored in the heap.
     ///
@@ -128,163 +131,19 @@
     /// 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); 
+    void set (const Item& item, const Prio& 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);
+    }
     
     /// \brief 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);
-    
-    /// \brief 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; }
-
-    /// \brief 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; }
-    
-    /// \brief 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; 
-    }
-    
-    /// \brief 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; 
-    }
-
-
-    /// \brief 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();
-
-    /// \brief 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); 
-
-    /// \brief 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); 
-
-    /// \brief 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);
-    }
-
-
-    /// \brief 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);
-    }    
-
-    /// \brief Sets the state of the \c item in the heap.
-    ///
-    /// Sets the state of the \c item in the heap. It can be used to
-    /// manually clear the heap when it is important to achive the
-    /// better time complexity.
-    /// \param i The item.
-    /// \param st The state. It should not be \c IN_HEAP. 
-    void state(const Item& i, state_enum st) {
-      switch (st) {
-      case POST_HEAP:
-      case PRE_HEAP:
-        if (state(i) == IN_HEAP) {
-          erase(i);
-        }
-        iimap[i] = st;
-        break;
-      case IN_HEAP:
-        break;
-      }
-    }
-    
-  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 Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<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 Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::push 
-  (Item const item, PrioType const value) {
+    void push (const Item& item, const Prio& value) {
       int i=iimap[item];      
       if ( i < 0 ) {
 	int s=container.size();
@@ -314,9 +173,33 @@
       ++num_items;
     }
     
-  template <typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::pop() {
+    /// \brief 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; }
+
+    /// \brief Returns the minimum priority relative to \c Compare.
+    ///
+    /// It returns the minimum priority relative to \c Compare.
+    /// \pre The heap must be nonempty.
+    const Prio& prio() const { return container[minimum].prio; }
+        
+    /// \brief Returns the priority of \c item.
+    ///
+    /// It returns the priority of \c item.
+    /// \pre \c item must be in the heap.
+    const Prio& operator[](const Item& item) const { 
+      return container[iimap[item]].prio; 
+    }
+
+    /// \brief 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() {
       /*The first case is that there are only one root.*/
       if ( container[minimum].left_neighbor==minimum ) {
 	container[minimum].in=false;
@@ -333,7 +216,7 @@
 	  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;
@@ -347,11 +230,11 @@
       --num_items;   
     }
 
-
-  template <typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::erase 
-  (const Item& item) {
+    /// \brief 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) {
       int i=iimap[item];
       
       if ( i >= 0 && container[i].in ) { 	
@@ -363,12 +246,14 @@
 	minimum=i;     //As if its prio would be -infinity
 	pop();
       }
-  }
-    
-  template <typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::decrease 
-  (Item item, PrioType const value) {
+    }
+
+    /// \brief 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, const Prio& value) {
       int i=iimap[item];
       container[i].prio=value;
       int p=container[i].parent;
@@ -378,26 +263,75 @@
 	cascade(p);
       }      
       if ( comp(value, container[minimum].prio) ) minimum=i; 
-  }
- 
+    }
 
-  template <typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::balance() {      
+    /// \brief 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, const Prio& value) {
+      erase(item);
+      push(item, value);
+    }
 
-    int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
+
+    /// \brief 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 state(const Item &item) const {
+      int i=iimap[item];
+      if( i>=0 ) {
+	if ( container[i].in ) i=0;
+	else i=-2; 
+      }
+      return State(i);
+    }    
+
+    /// \brief Sets the state of the \c item in the heap.
+    ///
+    /// Sets the state of the \c item in the heap. It can be used to
+    /// manually clear the heap when it is important to achive the
+    /// better time complexity.
+    /// \param i The item.
+    /// \param st The state. It should not be \c IN_HEAP. 
+    void state(const Item& i, State st) {
+      switch (st) {
+      case POST_HEAP:
+      case PRE_HEAP:
+        if (state(i) == IN_HEAP) {
+          erase(i);
+        }
+        iimap[i] = st;
+        break;
+      case IN_HEAP:
+        break;
+      }
+    }
+    
+  private:
+    
+    void balance() {
+
+      int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
   
-    std::vector<int> A(maxdeg,-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; 
+      /*
+       *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 {
+      do {
 	int active=next;
 	if ( anchor==active ) end=true;
 	int d=container[active].degree;
@@ -414,64 +348,53 @@
 	  ++d;
 	}	
 	A[d]=active;
-       } while ( !end );
+      } 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 );
+      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 Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::makeroot 
-  (int c) {
+    void makeroot(int c) {
       int s=c;
       do {  
 	container[s].parent=-1;
 	s=container[s].right_neighbor;
       } while ( s != c );
     }
-  
-  
-  template <typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::cut 
-  (int a, int b) {    
-    /*
-     *Replacing a from the children of b.
-     */
-    --container[b].degree;
+
+    void 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);
+      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;
     }
-    
-    
-    /*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 Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::cascade 
-  (int a) 
-    {
+    void cascade(int a) {
       if ( container[a].parent!=-1 ) {
 	int p=container[a].parent;
 	
@@ -483,11 +406,7 @@
       }
     }
 
-
-  template <typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::fuse 
-  (int a, int b) {
+    void fuse(int a, int b) {
       unlace(b);
       
       /*Lacing b under a.*/
@@ -511,20 +430,33 @@
       container[b].marked=false;
     }
 
-  
-  /*
-   *It is invoked only if a has siblings.
-   */
-  template <typename Prio, typename ItemIntMap, 
-    typename Compare>
-  void FibHeap<Prio, ItemIntMap, Compare>::unlace 
-  (int a) {      
+    /*
+     *It is invoked only if a has siblings.
+     */
+    void 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;
-  }
-  
+    }
+
+
+    class store {
+      friend class FibHeap;
+      
+      Item name;
+      int parent;
+      int left_neighbor;
+      int right_neighbor;
+      int child;
+      int degree;  
+      bool marked;
+      bool in;
+      Prio prio;
+      
+      store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
+    };
+  };    
 
 } //namespace lemon
 
diff -r b5eba564bb60 -r f393a8162688 lemon/radix_heap.h
--- a/lemon/radix_heap.h	Thu Dec 20 15:21:22 2007 +0000
+++ b/lemon/radix_heap.h	Thu Dec 27 13:40:16 2007 +0000
@@ -28,19 +28,6 @@
 
 namespace lemon {
 
-  /// \brief Exception thrown by RadixHeap.
-  ///  
-  /// This Exception is thrown when a smaller priority
-  /// is inserted into the \e RadixHeap then the last time erased.
-  /// \see RadixHeap
-  /// \author Balazs Dezso
-
-  class UnderFlowPriorityError : public RuntimeError {
-  public:
-    virtual const char* what() const throw() {
-      return "lemon::UnderFlowPriorityError";
-    }  
-  };
 
   /// \ingroup auxdata
   ///
@@ -69,6 +56,20 @@
     typedef int Prio;
     typedef _ItemIntMap ItemIntMap;
 
+    /// \brief Exception thrown by RadixHeap.
+    ///  
+    /// This Exception is thrown when a smaller priority
+    /// is inserted into the \e RadixHeap then the last time erased.
+    /// \see RadixHeap
+    /// \author Balazs Dezso
+    
+    class UnderFlowPriorityError : public RuntimeError {
+    public:
+      virtual const char* what() const throw() {
+	return "lemon::RadixHeap::UnderFlowPriorityError";
+      }  
+    };
+
     /// \brief Type to represent the items states.
     ///
     /// Each Item element have a state associated to it. It may be "in heap",
@@ -77,7 +78,7 @@
     ///
     /// The ItemIntMap \e should be initialized in such way that it maps
     /// PRE_HEAP (-1) to any element to be put in the heap...
-    enum state_enum {
+    enum State {
       IN_HEAP = 0,
       PRE_HEAP = -1,
       POST_HEAP = -2
@@ -401,10 +402,10 @@
     /// otherwise. In the latter case it is possible that \c item will
     /// get back to the heap again.
     /// \param i The item.
-    state_enum state(const Item &i) const {
+    State state(const Item &i) const {
       int s = iim[i];
       if( s >= 0 ) s = 0;
-      return state_enum(s);
+      return State(s);
     }
 
     /// \brief Sets the state of the \c item in the heap.
@@ -414,7 +415,7 @@
     /// better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP. 
-    void state(const Item& i, state_enum st) {
+    void state(const Item& i, State st) {
       switch (st) {
       case POST_HEAP:
       case PRE_HEAP: