# HG changeset patch
# User deba
# Date 1145037902 0
# Node ID d9a221218ea4a6f203e1250f1fe8c772de84a7ec
# Parent  a9933b493198bd3d3d856dbdfaa67959689b409a
Changing the mining of the clear in heaps
It does not touch the heap cross ref. It is
sometimes more clean useable and more efficient

diff -r a9933b493198 -r d9a221218ea4 lemon/bin_heap.h
--- a/lemon/bin_heap.h	Fri Apr 14 15:05:51 2006 +0000
+++ b/lemon/bin_heap.h	Fri Apr 14 18:05:02 2006 +0000
@@ -112,11 +112,11 @@
 
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference map.
+    /// If you want to reuse what is not surely empty you should first clear
+    /// the heap and after that you should set the cross reference map for
+    /// each item to \c PRE_HEAP.
     void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-	iim.set(data[i].first, POST_HEAP);
-      }
       data.clear(); 
     }
 
diff -r a9933b493198 -r d9a221218ea4 lemon/bucket_heap.h
--- a/lemon/bucket_heap.h	Fri Apr 14 15:05:51 2006 +0000
+++ b/lemon/bucket_heap.h	Fri Apr 14 18:05:02 2006 +0000
@@ -90,11 +90,11 @@
 
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-	index[data[i].item] = -2;
-      }
       data.clear(); first.clear(); minimal = 0;
     }
 
@@ -349,9 +349,6 @@
     bool empty() const { return data.empty(); }
 
     void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-	index[data[i].item] = -2;
-      }
       data.clear(); first.clear(); maximal = -1; 
     }
 
diff -r a9933b493198 -r d9a221218ea4 lemon/fib_heap.h
--- a/lemon/fib_heap.h	Fri Apr 14 15:05:51 2006 +0000
+++ b/lemon/fib_heap.h	Fri Apr 14 18:05:02 2006 +0000
@@ -116,13 +116,11 @@
 
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear() {
-      if (num_items != 0) {
-	for (int i = 0; i < (int)container.size(); ++i) {
-	  iimap[container[i].name] = -2;
-	}
-      }
       container.clear(); minimum = 0; num_items = 0;
     }
 
diff -r a9933b493198 -r d9a221218ea4 lemon/fredman_tarjan.h
--- a/lemon/fredman_tarjan.h	Fri Apr 14 15:05:51 2006 +0000
+++ b/lemon/fredman_tarjan.h	Fri Apr 14 18:05:02 2006 +0000
@@ -211,9 +211,12 @@
 
   private:
 
-    template<class SrcGraph,class OrigMap,class Heap,class ProcessedMap,class PredMap>
-    void processNextTree(const SrcGraph& graph,const OrigMap& orig,Heap &heap,
-	ProcessedMap& processed,PredMap& pred,int& tree_counter,const int limit){
+    template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef,
+             class ProcessedMap,class PredMap>
+    void processNextTree(const SrcGraph& graph,const OrigMap& orig,
+                         Heap &heap, HeapCrossRef& crossref,
+                         ProcessedMap& processed,PredMap& pred,
+                         int& tree_counter,const int limit){
       std::vector<typename SrcGraph::Node> tree_nodes;
       int tree_index=tree_counter;
       bool stop=false;
@@ -254,21 +257,23 @@
       for(int i=1;i<(int)tree_nodes.size();++i){
 	_tree->set(orig[pred[tree_nodes[i]]],true);
         processed.set(tree_nodes[i],tree_index);
-        heap.state(tree_nodes[i], Heap::PRE_HEAP);
+        crossref[tree_nodes[i]] = Heap::PRE_HEAP;
       }
       processed.set(tree_nodes[0],tree_index);
-      heap.state(tree_nodes[0],Heap::PRE_HEAP);
+      crossref[tree_nodes[0]] = Heap::PRE_HEAP;
       while (!heap.empty()) {
         typename SrcGraph::Node v=heap.top();
 	heap.pop();
-        heap.state(v,Heap::PRE_HEAP);
+        crossref[v] = Heap::PRE_HEAP;
       }
+      heap.clear();
       if(!stop)++tree_counter;
     }
 
     template<class SrcGraph,class OrigMap,class ProcessedMap>
-    void createTrees(const SrcGraph& graph,const OrigMap& orig, ProcessedMap& processed,
-	int edgenum,int& tree_counter){
+    void createTrees(const SrcGraph& graph, const OrigMap& orig, 
+                     ProcessedMap& processed,
+                     int edgenum,int& tree_counter){
       typedef typename SrcGraph::Node Node;
       typedef typename SrcGraph::UEdge UEdge;
       typedef typename SrcGraph::NodeIt NodeIt;
@@ -278,18 +283,22 @@
       FibHeap<Node,Value,HeapCrossRef> heap(crossref);
       PredMap pred(graph,INVALID);
       int rate=2*edgenum/countNodes(graph);
-      int limit=(rate>std::numeric_limits<int>::digits)?std::numeric_limits<int>::max():(1<<rate);
+      int limit=(rate>std::numeric_limits<int>::digits)?
+      std::numeric_limits<int>::max() : (1<<rate);
       for(NodeIt i(graph);i!=INVALID;++i){
 	if(processed[i]==-1){
 	  heap.push(i, Value());
-	  processNextTree(graph,orig,heap,processed,pred,tree_counter,limit);
+	  processNextTree(graph,orig,heap,crossref,
+                          processed,pred,tree_counter,limit);
 	}
       }
     }
 
-    template<class SrcGraph,class DestGraph,class SrcOrigMap,class DestOrigMap,class ProcessedMap>
-    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,DestGraph& destgraph,
-	DestOrigMap& destorig,const ProcessedMap& processed,const int tree_counter){
+    template<class SrcGraph,class DestGraph,class SrcOrigMap,
+             class DestOrigMap,class ProcessedMap>
+    void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,
+                 DestGraph& destgraph,DestOrigMap& destorig,
+                 const ProcessedMap& processed,const int tree_counter){
       typedef typename SrcGraph::Node Node;
       typedef typename DestGraph::Node DNode;
       typedef typename SrcGraph::UEdge UEdge;
@@ -310,14 +319,17 @@
 	}
       }
       
-      radixSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,sourceMap(srcgraph))));
-      counterSort(edges.begin(),edges.end(),mapFunctor(composeMap(processed,targetMap(srcgraph))));
+      radixSort(edges.begin(),edges.end(),
+                mapFunctor(composeMap(processed,sourceMap(srcgraph))));
+      counterSort(edges.begin(),edges.end(),
+                  mapFunctor(composeMap(processed,targetMap(srcgraph))));
       for(int i=0;i!=(int)edges.size();++i){
 	int srcproc=processed[srcgraph.source(edges[i])];
 	int trgproc=processed[srcgraph.target(edges[i])];
         Value minval=(*cost)[srcorig[edges[i]]];
         UEdge minpos=edges[i];
-	while (i+1!=(int)edges.size() && srcproc==processed[srcgraph.source(edges[i+1])] &&
+	while (i+1!=(int)edges.size() && 
+               srcproc==processed[srcgraph.source(edges[i+1])] &&
 	  trgproc==processed[srcgraph.target(edges[i+1])]) {
 	  if (minval>(*cost)[srcorig[edges[i+1]]]) {
             minval=(*cost)[srcorig[edges[i+1]]];
@@ -325,7 +337,8 @@
 	  }
           ++i;
 	} 
-	destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=srcorig[minpos];
+	destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=
+          srcorig[minpos];
       }
     }
 
diff -r a9933b493198 -r d9a221218ea4 lemon/radix_heap.h
--- a/lemon/radix_heap.h	Fri Apr 14 15:05:51 2006 +0000
+++ b/lemon/radix_heap.h	Fri Apr 14 18:05:02 2006 +0000
@@ -136,11 +136,11 @@
 
     /// \brief Make empty this heap.
     /// 
-    /// Make empty this heap.
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear(int minimal = 0, int capacity = 0) { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-	iim[data[i].item] = -2;
-      }
       data.clear(); boxes.clear(); 
       boxes.push_back(RadixBox(minimal, 1));
       boxes.push_back(RadixBox(minimal + 1, 1));