# HG changeset patch
# User mqrelly
# Date 1161872417 0
# Node ID 9273fe7d850c23c9753fb257b1b7875168684a55
# Parent  b9a7f4115abe35f7ca6d0c720ae71b01f1a62c97
Bug #46 fixed: Superfluous template parameter in Heap concept
NOTE: Not every affected file tested.

diff -r b9a7f4115abe -r 9273fe7d850c lemon/bin_heap.h
--- a/lemon/bin_heap.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/bin_heap.h	Thu Oct 26 14:20:17 2006 +0000
@@ -39,7 +39,6 @@
   ///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 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.
@@ -48,12 +47,12 @@
   ///
   ///\sa FibHeap
   ///\sa Dijkstra
-  template <typename Item, typename Prio, typename ItemIntMap,
+  template <typename Prio, typename ItemIntMap,
 	    typename Compare = std::less<Prio> >
   class BinHeap {
 
   public:
-    typedef Item                             ItemType;
+    typedef typename ItemIntMap::Key         ItemType;
     typedef Prio                             PrioType;
     typedef std::pair<ItemType,PrioType>     PairType;
     typedef ItemIntMap                       ItemIntMapType;
@@ -161,14 +160,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 Item &i, const Prio &p) { push(PairType(i,p)); }
+    void push(const ItemType &i, const Prio &p) { push(PairType(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.  
-    Item top() const {
+    ItemType top() const {
       return data[0].first;
     }
 
@@ -194,7 +193,7 @@
     /// This method deletes item \c i from the heap, if \c i was
     /// already stored in the heap.
     /// \param i The item to erase. 
-    void erase(const Item &i) {
+    void erase(const ItemType &i) {
       rmidx(iim[i]);
     }
 
@@ -204,7 +203,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 Item &i) const {
+    Prio operator[](const ItemType &i) const {
       int idx = iim[i];
       return data[idx].second;
     }
@@ -216,7 +215,7 @@
     /// 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 Item &i, const Prio &p) {
+    void set(const ItemType &i, const Prio &p) {
       int idx = iim[i];
       if( idx < 0 ) {
 	push(i,p);
@@ -236,7 +235,7 @@
     /// p relative to \c Compare.
     /// \param i The item.
     /// \param p The priority.
-    void decrease(const Item &i, const Prio &p) {
+    void decrease(const ItemType &i, const Prio &p) {
       int idx = iim[i];
       bubble_up(idx, PairType(i,p));
     }
@@ -248,7 +247,7 @@
     /// p relative to \c Compare.
     /// \param i The item.
     /// \param p The priority.
-    void increase(const Item &i, const Prio &p) {
+    void increase(const ItemType &i, const Prio &p) {
       int idx = iim[i];
       bubble_down(idx, PairType(i,p), data.size());
     }
@@ -261,7 +260,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_enum state(const ItemType &i) const {
       int s = iim[i];
       if( s>=0 )
 	s=0;
@@ -275,7 +274,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 ItemType& i, state_enum st) {
       switch (st) {
       case POST_HEAP:
       case PRE_HEAP:
@@ -292,8 +291,8 @@
   }; // class BinHeap
 
   
-  template <typename K, typename V, typename M, typename C>
-  int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
+  template <typename V, typename M, typename C>
+  int BinHeap<V,M,C>::bubble_up(int hole, PairType p) {
     int par = parent(hole);
     while( hole>0 && less(p,data[par]) ) {
       move(data[par],hole);
@@ -304,8 +303,8 @@
     return hole;
   }
 
-  template <typename K, typename V, typename M, typename C>
-  int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
+  template <typename V, typename M, typename C>
+  int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) {
     int child = second_child(hole);
     while(child < length) {
       if( less(data[child-1], data[child]) ) {
diff -r b9a7f4115abe -r 9273fe7d850c lemon/bipartite_matching.h
--- a/lemon/bipartite_matching.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/bipartite_matching.h	Thu Oct 26 14:20:17 2006 +0000
@@ -521,7 +521,7 @@
     /// anode graph's node.
     ///
     /// \sa BinHeap
-    typedef BinHeap<typename BpUGraph::Node, Value, HeapCrossRef> Heap;
+    typedef BinHeap<Value, HeapCrossRef> Heap;
     
     /// \brief Instantiates a Heap.
     ///
diff -r b9a7f4115abe -r 9273fe7d850c lemon/bucket_heap.h
--- a/lemon/bucket_heap.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/bucket_heap.h	Thu Oct 26 14:20:17 2006 +0000
@@ -41,16 +41,15 @@
   /// \f$ [0..C) \f$ range a list of items. So it should be used only when 
   /// the priorities are small. It is not intended to use as dijkstra heap.
   ///
-  /// \param _Item Type of the items to be stored.  
   /// \param _ItemIntMap A read and writable Item int map, used internally
   /// to handle the cross references.
   /// \param minimize If the given parameter is true then the heap gives back
   /// the lowest priority. 
-  template <typename _Item, typename _ItemIntMap, bool minimize = true >
+  template <typename _ItemIntMap, bool minimize = true >
   class BucketHeap {
 
   public:
-    typedef _Item Item;
+    typedef typename _ItemIntMap::Key Item;
     typedef int Prio;
     typedef std::pair<Item, Prio> Pair;
     typedef _ItemIntMap ItemIntMap;
@@ -326,11 +325,11 @@
   }; // class BucketHeap
 
 
-  template <typename _Item, typename _ItemIntMap>
-  class BucketHeap<_Item, _ItemIntMap, false> {
+  template <typename _ItemIntMap>
+  class BucketHeap<_ItemIntMap, false> {
 
   public:
-    typedef _Item Item;
+    typedef typename _ItemIntMap::Key Item;
     typedef int Prio;
     typedef std::pair<Item, Prio> Pair;
     typedef _ItemIntMap ItemIntMap;
@@ -524,18 +523,17 @@
   /// other way it does not supports erasing each elements just the
   /// minimal and it does not supports key increasing, decreasing.
   ///
-  /// \param _Item Type of the items to be stored.  
   /// \param _ItemIntMap A read and writable Item int map, used internally
   /// to handle the cross references.
   /// \param minimize If the given parameter is true then the heap gives back
   /// the lowest priority.
   ///
   /// \sa BucketHeap 
-  template <typename _Item, typename _ItemIntMap, bool minimize = true >
+  template <typename _ItemIntMap, bool minimize = true >
   class SimpleBucketHeap {
 
   public:
-    typedef _Item Item;
+    typedef typename _ItemIntMap::Key Item;
     typedef int Prio;
     typedef std::pair<Item, Prio> Pair;
     typedef _ItemIntMap ItemIntMap;
@@ -709,11 +707,11 @@
 
   }; // class SimpleBucketHeap
 
-  template <typename _Item, typename _ItemIntMap>
-  class SimpleBucketHeap<_Item, _ItemIntMap, false> {
+  template <typename _ItemIntMap>
+  class SimpleBucketHeap<_ItemIntMap, false> {
 
   public:
-    typedef _Item Item;
+    typedef typename _ItemIntMap::Key Item;
     typedef int Prio;
     typedef std::pair<Item, Prio> Pair;
     typedef _ItemIntMap ItemIntMap;
diff -r b9a7f4115abe -r 9273fe7d850c lemon/concepts/heap.h
--- a/lemon/concepts/heap.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/concepts/heap.h	Thu Oct 26 14:20:17 2006 +0000
@@ -36,9 +36,12 @@
     ///
     /// A concept structure describes the main interface of heaps.
     ///
-    template <typename Item, typename Prio, typename ItemIntMap>
+    template <typename Prio, typename ItemIntMap>
     class Heap {
     public:
+
+      ///\brief Type of the items stored in the heap.
+      typedef typename ItemIntMap::Key  Item;
   
 
       /// \brief Type to represent the items states.
diff -r b9a7f4115abe -r 9273fe7d850c lemon/dijkstra.h
--- a/lemon/dijkstra.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/dijkstra.h	Thu Oct 26 14:20:17 2006 +0000
@@ -73,8 +73,7 @@
     ///
     ///\sa BinHeap
     ///\sa Dijkstra
-    typedef BinHeap<typename Graph::Node, typename LM::Value,
-		    HeapCrossRef, std::less<Value> > Heap;
+    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
 
     static Heap *createHeap(HeapCrossRef& R) 
     {
@@ -847,8 +846,7 @@
     ///
     ///\sa BinHeap
     ///\sa Dijkstra
-    typedef BinHeap<typename Graph::Node, typename LM::Value,
-		    typename GR::template NodeMap<int>,
+    typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
 		    std::less<Value> > Heap;
 
     static Heap *createHeap(HeapCrossRef& R) 
diff -r b9a7f4115abe -r 9273fe7d850c lemon/fib_heap.h
--- a/lemon/fib_heap.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/fib_heap.h	Thu Oct 26 14:20:17 2006 +0000
@@ -43,7 +43,6 @@
   ///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.
@@ -55,18 +54,17 @@
   ///\author Jacint Szabo 
  
 #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;
     
   private:
@@ -271,9 +269,9 @@
     //  IMPLEMENTATIONS
     // **********************************************************************
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
+  void FibHeap<Prio, ItemIntMap, Compare>::set 
   (Item const item, PrioType const value) 
   {
     int i=iimap[item];
@@ -283,9 +281,9 @@
     } else push(item, value);
   }
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
+  void FibHeap<Prio, ItemIntMap, Compare>::push 
   (Item const item, PrioType const value) {
       int i=iimap[item];      
       if ( i < 0 ) {
@@ -316,9 +314,9 @@
       ++num_items;
     }
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
+  void FibHeap<Prio, ItemIntMap, Compare>::pop() {
       /*The first case is that there are only one root.*/
       if ( container[minimum].left_neighbor==minimum ) {
 	container[minimum].in=false;
@@ -350,9 +348,9 @@
     }
 
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
+  void FibHeap<Prio, ItemIntMap, Compare>::erase 
   (const Item& item) {
       int i=iimap[item];
       
@@ -367,9 +365,9 @@
       }
   }
     
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
+  void FibHeap<Prio, ItemIntMap, Compare>::decrease 
   (Item item, PrioType const value) {
       int i=iimap[item];
       container[i].prio=value;
@@ -383,9 +381,9 @@
   }
  
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
+  void FibHeap<Prio, ItemIntMap, Compare>::balance() {      
 
     int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
   
@@ -428,9 +426,9 @@
        } while ( s != m );
     }
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
+  void FibHeap<Prio, ItemIntMap, Compare>::makeroot 
   (int c) {
       int s=c;
       do {  
@@ -440,9 +438,9 @@
     }
   
   
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
+  void FibHeap<Prio, ItemIntMap, Compare>::cut 
   (int a, int b) {    
     /*
      *Replacing a from the children of b.
@@ -469,9 +467,9 @@
   }
   
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
+  void FibHeap<Prio, ItemIntMap, Compare>::cascade 
   (int a) 
     {
       if ( container[a].parent!=-1 ) {
@@ -486,9 +484,9 @@
     }
 
 
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
+  void FibHeap<Prio, ItemIntMap, Compare>::fuse 
   (int a, int b) {
       unlace(b);
       
@@ -517,9 +515,9 @@
   /*
    *It is invoked only if a has siblings.
    */
-  template <typename Item, typename Prio, typename ItemIntMap, 
+  template <typename Prio, typename ItemIntMap, 
     typename Compare>
-  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
+  void FibHeap<Prio, ItemIntMap, Compare>::unlace 
   (int a) {      
       int leftn=container[a].left_neighbor;
       int rightn=container[a].right_neighbor;
diff -r b9a7f4115abe -r 9273fe7d850c lemon/fredman_tarjan.h
--- a/lemon/fredman_tarjan.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/fredman_tarjan.h	Thu Oct 26 14:20:17 2006 +0000
@@ -280,7 +280,7 @@
       typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;
       typedef typename SrcGraph::template NodeMap<UEdge> PredMap;
       HeapCrossRef crossref(graph,-1);
-      FibHeap<Node,Value,HeapCrossRef> heap(crossref);
+      FibHeap<Value,HeapCrossRef> heap(crossref);
       PredMap pred(graph,INVALID);
       int rate=2*edgenum/countNodes(graph);
       int limit=(rate>std::numeric_limits<int>::digits)?
diff -r b9a7f4115abe -r 9273fe7d850c lemon/johnson.h
--- a/lemon/johnson.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/johnson.h	Thu Oct 26 14:20:17 2006 +0000
@@ -130,7 +130,7 @@
     ///
     ///\sa BinHeap
     ///\sa Dijkstra
-    typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
+    typedef BinHeap<typename LengthMap::Value,
 		    HeapCrossRef, std::less<Value> > Heap;
 
     ///Instantiates a Heap.
diff -r b9a7f4115abe -r 9273fe7d850c lemon/min_cost_arborescence.h
--- a/lemon/min_cost_arborescence.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/min_cost_arborescence.h	Thu Oct 26 14:20:17 2006 +0000
@@ -224,7 +224,7 @@
     
     HeapCrossRef *_heap_cross_ref;
 
-    typedef BinHeap<Node, int, HeapCrossRef> Heap;
+    typedef BinHeap<int, HeapCrossRef> Heap;
 
     Heap *_heap;
 
diff -r b9a7f4115abe -r 9273fe7d850c lemon/min_cut.h
--- a/lemon/min_cut.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/min_cut.h	Thu Oct 26 14:20:17 2006 +0000
@@ -38,17 +38,17 @@
 
     template <typename CapacityMap>
     struct HeapSelector {
-      template <typename Key, typename Value, typename Ref>
+      template <typename Value, typename Ref>
       struct Selector {
-        typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
+        typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
       };
     };
 
     template <typename CapacityKey>
     struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
-      template <typename Key, typename Value, typename Ref>
+      template <typename Value, typename Ref>
       struct Selector {
-        typedef BucketHeap<Key, Ref, false > Heap;
+        typedef BucketHeap<Ref, false > Heap;
       };
     };
 
@@ -99,7 +99,7 @@
     /// \sa MaxCardinalitySearch
     typedef typename _min_cut_bits
     ::HeapSelector<CapacityMap>
-    ::template Selector<typename Graph::Node, Value, HeapCrossRef>
+    ::template Selector<Value, HeapCrossRef>
     ::Heap Heap;
 
     /// \brief Instantiates a Heap.
@@ -766,7 +766,7 @@
     /// \sa MinCut
     typedef typename _min_cut_bits
     ::HeapSelector<CapacityMap>
-    ::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
+    ::template Selector<Value, HeapCrossRef>
     ::Heap Heap;
     
     /// \brief Instantiates a Heap.
diff -r b9a7f4115abe -r 9273fe7d850c lemon/prim.h
--- a/lemon/prim.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/prim.h	Thu Oct 26 14:20:17 2006 +0000
@@ -70,7 +70,7 @@
     ///
     ///\sa BinHeap
     ///\sa Prim
-    typedef BinHeap<typename UGraph::Node, typename CM::Value,
+    typedef BinHeap<typename CM::Value,
 		    HeapCrossRef, std::less<Value> > Heap;
 
     static Heap *createHeap(HeapCrossRef& _ref){
diff -r b9a7f4115abe -r 9273fe7d850c lemon/radix_heap.h
--- a/lemon/radix_heap.h	Thu Oct 26 13:35:35 2006 +0000
+++ b/lemon/radix_heap.h	Thu Oct 26 14:20:17 2006 +0000
@@ -54,7 +54,6 @@
   /// item, but the priority cannot be decreased under the last removed 
   /// item's priority.
   ///
-  /// \param _Item Type of the items to be stored.  
   /// \param _ItemIntMap A read and writable Item int map, used internally
   /// to handle the cross references.
   ///
@@ -62,11 +61,11 @@
   /// \see Dijkstra
   /// \author Balazs Dezso
 
-  template <typename _Item, typename _ItemIntMap>
+  template <typename _ItemIntMap>
   class RadixHeap {
 
   public:
-    typedef _Item Item;
+    typedef typename _ItemIntMap::Key Item;
     typedef int Prio;
     typedef _ItemIntMap ItemIntMap;
 
@@ -299,7 +298,7 @@
     /// This method returns the item with minimum priority.  
     /// \pre The heap must be nonempty.  
     Item top() const {
-      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
+      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
       return data[boxes[0].first].item;
     }
 
@@ -308,7 +307,7 @@
     /// It returns the minimum priority.
     /// \pre The heap must be nonempty.
     Prio prio() const {
-      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
+      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
       return data[boxes[0].first].prio;
      }