Index: src/work/jacint/fib_heap.h
===================================================================
--- src/work/jacint/fib_heap.h	(revision 161)
+++ src/work/jacint/fib_heap.h	(revision 167)
@@ -32,9 +32,13 @@
  *void erase(Item) : deletes Item from the heap if it was already there
  *
- *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap 
- *     with prio at least P.
+ *void decrease(Item, P) : decreases prio of Item to P. 
+ *     Item must be in the heap with prio at least P.
  *
  *void increase(Item, P) : sets prio of Item to P. 
  *
+ *state_enum state(Item) : returns PRE_HEAP if Item has not been in the 
+ *     heap until now, IN_HEAP if it is in the heap at the moment, and 
+ *     POST_HEAP otherwise. In the latter case it is possible that Item
+ *     will get back to the heap again. 
  *
  *In Fibonacci heaps, increase and erase are not efficient, in case of
@@ -65,4 +69,10 @@
     ItemIntMap &iimap;
     Compare comp;
+
+    enum state_enum {
+      IN_HEAP = 0,
+      PRE_HEAP = -1,
+      POST_HEAP = -2
+    };
     
   public :
@@ -102,6 +112,11 @@
 	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 ( !blank ) {
 	container[container[minimum].right_neighbor].left_neighbor=i;
@@ -110,5 +125,4 @@
 	container[i].left_neighbor=minimum;
 	if ( !comp( container[minimum].prio, value) ) minimum=i; 
-	
       } else {
 	container[i].right_neighbor=container[i].left_neighbor=i;
@@ -120,5 +134,4 @@
     
 
-
     Item top() const {
       if ( !blank ) { 
@@ -139,6 +152,5 @@
     
 
-    const PrioType get(const Item& it) const
-    {
+    const PrioType get(const Item& it) const {
       int i=iimap.get(it);
       
@@ -151,43 +163,42 @@
 
 
+
+
     void pop() {
-      if ( !blank ) {
+      /*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 ) blank=true; 
+	else { 
+	  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;
 	
-	/*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 ) blank=true; 
-	  else { 
-	    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;
-	   
-	   container[left].right_neighbor=child;
-	   container[child].left_neighbor=left;
-	   container[right].left_neighbor=last_child;
-	   container[last_child].right_neighbor=right;
-	   
-	   makeroot(child);
-	 }
-	 minimum=right;
-	 balance();
-       } // the case where there are more roots
-     } 
-   }
-
-    
-   void erase (const Item& it) {
-     int i=iimap.get(it);
-     
-     if ( i >= 0 && container[i].in ) { 
+	  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
+    }
+
+    
+    void erase (const Item& it) {
+      int i=iimap.get(it);
+      
+      if ( i >= 0 && container[i].in ) { 
 	
        if ( container[i].parent!=-1 ) {
@@ -206,5 +217,5 @@
       container[i].prio=value;
       int p=container[i].parent;
- 
+      
       if ( p!=-1 && comp(value, container[p].prio) ) {
 	cut(i,p);	    
@@ -221,7 +232,18 @@
 
 
+    state_enum state(const Item &it) const {
+      int i=iimap.get(it);
+      if( i>=0 ) {
+	if ( container[i].in ) i=0;
+	else i=-2; 
+      }
+      return state_enum(i);
+    }
+
+
   private:
     
     void balance() {      
+
     int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
   
@@ -238,12 +260,9 @@
        do {
 	int active=next;
+	if ( anchor==active ) end=true;
 	int d=container[active].degree;
-	if ( anchor==active ) end=true;
-	next = container[active].right_neighbor;
-	if ( !comp(container[minimum].prio, container[active].prio) )
-	  minimum=active;
-
-	while (A[d]!=-1) {
-	  
+	next=container[active].right_neighbor;
+
+	while (A[d]!=-1) {	  
 	  if( comp(container[active].prio, container[A[d]].prio) ) {
 	    fuse(active,A[d]); 
@@ -254,18 +273,20 @@
 	  A[d]=-1;
 	  ++d;
-	}
-	
+	}	
 	A[d]=active;
        } while ( !end );
-  }
-
-
-
-
-    /*
-     *All the siblings of a are made roots.
-     */
-    void makeroot (int c)  
-    {
+
+
+       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 );
+    }
+
+
+    void makeroot (int c) {
       int s=c;
       do {  
@@ -276,22 +297,18 @@
     
 
-    void cut (int a, int b) 
-    {    
-
+    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);
-	
-      }
-    
-
+	int child=container[b].child;
+	if ( child==a ) 
+	  container[b].child=container[child].right_neighbor;
+	unlace(a);
+      }
+      
+      
       /*Lacing i to the roots.*/
       int right=container[minimum].right_neighbor;
@@ -320,9 +337,6 @@
 
 
-    void fuse (int a, int b) 
-    {
-      
+    void fuse (int a, int b) {
       unlace(b);
-
       
       /*Lacing b under a.*/
@@ -351,5 +365,4 @@
      *It is invoked only if a has siblings.
      */
-
     void unlace (int a) {      
       int leftn=container[a].left_neighbor;
