bin_heap.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef LEMON_BIN_HEAP_H
00020 #define LEMON_BIN_HEAP_H
00021 
00025 
00026 #include <vector>
00027 #include <utility>
00028 #include <functional>
00029 
00030 namespace lemon {
00031 
00033 
00035   
00051   template <typename Item, typename Prio, typename ItemIntMap,
00052             typename Compare = std::less<Prio> >
00053   class BinHeap {
00054 
00055   public:
00056     typedef Item                             ItemType;
00057     // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
00058     typedef Prio                             PrioType;
00059     typedef std::pair<ItemType,PrioType>     PairType;
00060     typedef ItemIntMap                       ItemIntMapType;
00061     typedef Compare                          PrioCompare;
00062 
00071     enum state_enum {
00072       IN_HEAP = 0,
00073       PRE_HEAP = -1,
00074       POST_HEAP = -2
00075     };
00076 
00077   private:
00078     std::vector<PairType> data;
00079     Compare comp;
00080     ItemIntMap &iim;
00081 
00082   public:
00089     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
00090     
00099     BinHeap(ItemIntMap &_iim, const Compare &_comp) 
00100       : iim(_iim), comp(_comp) {}
00101 
00102 
00106     int size() const { return data.size(); }
00107     
00111     bool empty() const { return data.empty(); }
00112 
00116     void clear() { 
00117       for (int i = 0; i < (int)data.size(); ++i) {
00118         iim.set(data[i].first, POST_HEAP);
00119       }
00120       data.clear(); 
00121     }
00122 
00123   private:
00124     static int parent(int i) { return (i-1)/2; }
00125     static int second_child(int i) { return 2*i+2; }
00126     bool less(const PairType &p1, const PairType &p2) const {
00127       return comp(p1.second, p2.second);
00128     }
00129 
00130     int bubble_up(int hole, PairType p);
00131     int bubble_down(int hole, PairType p, int length);
00132 
00133     void move(const PairType &p, int i) {
00134       data[i] = p;
00135       iim.set(p.first, i);
00136     }
00137 
00138     void rmidx(int h) {
00139       int n = data.size()-1;
00140       if( h>=0 && h<=n ) {
00141         iim.set(data[h].first, POST_HEAP);
00142         if ( h<n ) {
00143           bubble_down(h, data[n], n);
00144         }
00145         data.pop_back();
00146       }
00147     }
00148 
00149   public:
00154     void push(const PairType &p) {
00155       int n = data.size();
00156       data.resize(n+1);
00157       bubble_up(n, p);
00158     }
00159 
00165     void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
00166 
00172     Item top() const {
00173       return data[0].first;
00174     }
00175 
00180     Prio prio() const {
00181       return data[0].second;
00182     }
00183 
00189     void pop() {
00190       rmidx(0);
00191     }
00192 
00198     void erase(const Item &i) {
00199       rmidx(iim[i]);
00200     }
00201 
00202     
00208     Prio operator[](const Item &i) const {
00209       int idx = iim[i];
00210       return data[idx].second;
00211     }
00212 
00220     void set(const Item &i, const Prio &p) {
00221       int idx = iim[i];
00222       if( idx < 0 ) {
00223         push(i,p);
00224       }
00225       else if( comp(p, data[idx].second) ) {
00226         bubble_up(idx, PairType(i,p));
00227       }
00228       else {
00229         bubble_down(idx, PairType(i,p), data.size());
00230       }
00231     }
00232 
00234 
00240     void decrease(const Item &i, const Prio &p) {
00241       int idx = iim[i];
00242       bubble_up(idx, PairType(i,p));
00243     }
00244     
00252     void increase(const Item &i, const Prio &p) {
00253       int idx = iim[i];
00254       bubble_down(idx, PairType(i,p), data.size());
00255     }
00256 
00265     state_enum state(const Item &i) const {
00266       int s = iim[i];
00267       if( s>=0 )
00268         s=0;
00269       return state_enum(s);
00270     }
00271 
00279     void state(const Item& i, state_enum st) {
00280       switch (st) {
00281       case POST_HEAP:
00282       case PRE_HEAP:
00283         if (state(i) == IN_HEAP) {
00284           erase(i);
00285         }
00286         iim[i] = st;
00287         break;
00288       case IN_HEAP:
00289         break;
00290       }
00291     }
00292 
00293   }; // class BinHeap
00294 
00295   
00296   template <typename K, typename V, typename M, typename C>
00297   int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
00298     int par = parent(hole);
00299     while( hole>0 && less(p,data[par]) ) {
00300       move(data[par],hole);
00301       hole = par;
00302       par = parent(hole);
00303     }
00304     move(p, hole);
00305     return hole;
00306   }
00307 
00308   template <typename K, typename V, typename M, typename C>
00309   int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
00310     int child = second_child(hole);
00311     while(child < length) {
00312       if( less(data[child-1], data[child]) ) {
00313         --child;
00314       }
00315       if( !less(data[child], p) )
00316         goto ok;
00317       move(data[child], hole);
00318       hole = child;
00319       child = second_child(hole);
00320     }
00321     child--;
00322     if( child<length && less(data[child], p) ) {
00323       move(data[child], hole);
00324       hole=child;
00325     }
00326   ok:
00327     move(p, hole);
00328     return hole;
00329   }
00330 
00331 
00332 } // namespace lemon
00333 
00334 #endif // LEMON_BIN_HEAP_H

Generated on Fri Feb 3 18:35:35 2006 for LEMON by  doxygen 1.4.6