COIN-OR::LEMON - Graph Library

Changeset 2546:b5eba564bb60 in lemon-0.x for lemon


Ignore:
Timestamp:
12/20/07 16:21:22 (16 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3423
Message:

Bug fix in erase

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bin_heap.h

    r2529 r2546  
    121121  private:
    122122    static int parent(int i) { return (i-1)/2; }
     123
    123124    static int second_child(int i) { return 2*i+2; }
    124125    bool less(const PairType &p1, const PairType &p2) const {
     
    126127    }
    127128
    128     int bubble_up(int hole, PairType p);
    129     int bubble_down(int hole, PairType p, int length);
     129    int bubble_up(int hole, PairType p) {
     130      int par = parent(hole);
     131      while( hole>0 && less(p,data[par]) ) {
     132        move(data[par],hole);
     133        hole = par;
     134        par = parent(hole);
     135      }
     136      move(p, hole);
     137      return hole;
     138    }
     139
     140    int bubble_down(int hole, PairType p, int length) {
     141      int child = second_child(hole);
     142      while(child < length) {
     143        if( less(data[child-1], data[child]) ) {
     144          --child;
     145        }
     146        if( !less(data[child], p) )
     147          goto ok;
     148        move(data[child], hole);
     149        hole = child;
     150        child = second_child(hole);
     151      }
     152      child--;
     153      if( child<length && less(data[child], p) ) {
     154        move(data[child], hole);
     155        hole=child;
     156      }
     157    ok:
     158      move(p, hole);
     159      return hole;
     160    }
    130161
    131162    void move(const PairType &p, int i) {
    132163      data[i] = p;
    133164      iim.set(p.first, i);
    134     }
    135 
    136     void rmidx(int h) {
    137       int n = data.size()-1;
    138       if( h>=0 && h<=n ) {
    139         iim.set(data[h].first, POST_HEAP);
    140         if ( h<n ) {
    141           bubble_down(h, data[n], n);
    142         }
    143         data.pop_back();
    144       }
    145165    }
    146166
     
    186206    /// \pre The heap must be non-empty. 
    187207    void pop() {
    188       rmidx(0);
     208      int n = data.size()-1;
     209      iim.set(data[0].first, POST_HEAP);
     210      if (n > 0) {
     211        bubble_down(0, data[n], n);
     212      }
     213      data.pop_back();
    189214    }
    190215
    191216    /// \brief Deletes \c i from the heap.
    192217    ///
    193     /// This method deletes item \c i from the heap, if \c i was
    194     /// already stored in the heap.
    195     /// \param i The item to erase.
     218    /// This method deletes item \c i from the heap.
     219    /// \param i The item to erase.
     220    /// \pre The item should be in the heap.
    196221    void erase(const ItemType &i) {
    197       rmidx(iim[i]);
     222      int h = iim[i];
     223      int n = data.size()-1;
     224      iim.set(data[h].first, POST_HEAP);
     225      if( h < n ) {
     226        if ( bubble_up(h, data[n]) == h) {
     227          bubble_down(h, data[n], n);
     228        }
     229      }
     230      data.pop_back();
    198231    }
    199232
     
    290323
    291324  }; // class BinHeap
    292 
    293325 
    294   template <typename V, typename M, typename C>
    295   int BinHeap<V,M,C>::bubble_up(int hole, PairType p) {
    296     int par = parent(hole);
    297     while( hole>0 && less(p,data[par]) ) {
    298       move(data[par],hole);
    299       hole = par;
    300       par = parent(hole);
    301     }
    302     move(p, hole);
    303     return hole;
    304   }
    305 
    306   template <typename V, typename M, typename C>
    307   int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) {
    308     int child = second_child(hole);
    309     while(child < length) {
    310       if( less(data[child-1], data[child]) ) {
    311         --child;
    312       }
    313       if( !less(data[child], p) )
    314         goto ok;
    315       move(data[child], hole);
    316       hole = child;
    317       child = second_child(hole);
    318     }
    319     child--;
    320     if( child<length && less(data[child], p) ) {
    321       move(data[child], hole);
    322       hole=child;
    323     }
    324   ok:
    325     move(p, hole);
    326     return hole;
    327   }
    328 
    329 
    330326} // namespace lemon
    331327
Note: See TracChangeset for help on using the changeset viewer.