Changeset 2263:9273fe7d850c in lemon-0.x for lemon/bin_heap.h

Timestamp:

10/26/06 16:20:17 (18 years ago)

Author:

mqrelly

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3021

Message:

Bug #46 fixed: Superfluous template parameter in Heap concept
NOTE: Not every affected file tested.

File:

• lemon/bin_heap.h (modified) (13 diffs)

lemon/bin_heap.h

@@ -40 +40 @@
   ///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
@@ -49 +48 @@
   ///\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;
@@ -162 +161 @@
     /// \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.
@@ -169 +168 @@
     /// Compare.  
     /// \pre The heap must be nonempty.  
-    Item top() const {
+    ItemType top() const {
       return data[0].first;
     }
@@ -195 +194 @@
     /// already stored in the heap.
     /// \param i The item to erase. 
-    void erase(const Item &i) {
+    void erase(const ItemType &i) {
       rmidx(iim[i]);
     }
@@ -205 +204 @@
     /// \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;
@@ -217 +216 @@
     /// \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 ) {
@@ -237 +236 @@
     /// \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));
@@ -249 +248 @@
     /// \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());
@@ -262 +261 @@
     /// 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 )
@@ -276 +275 @@
     /// \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:
@@ -293 +292 @@
 
   
-  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]) ) {
@@ -305 +304 @@
   }
 
-  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) {