Open
Graph Drawing
Framework

 v.2012.05
 

MinHeap.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
00007  ***************************************************************/
00008  
00042 #ifdef _MSC_VER
00043 #pragma once
00044 #endif
00045 
00046 #ifndef OGDF_MIN_HEAP_H
00047 #define OGDF_MIN_HEAP_H
00048 
00049 #include<ogdf/basic/Array.h>
00050 
00051 namespace ogdf {
00052 
00054 
00058 template<class X, class Priority=double> class Prioritized {
00059     X x;
00060     Priority p;
00061 public:
00063     Prioritized() : x(0), p(0) {};
00065     Prioritized(X xt, Priority pt) : x(xt),p(pt) {}
00067     Prioritized(const Prioritized& P) : x(P.x),p(P.p) {}
00069     Priority priority() const { return p; }
00071     X item() const { return x;}
00073     bool operator<(const Prioritized<X,Priority>& P) const { return p<P.p; }
00075     bool operator<=(const Prioritized<X,Priority>& P) const { return p<=P.p; }
00077     bool operator>(const Prioritized<X,Priority>& P) const { return p>P.p; }
00079     bool operator>=(const Prioritized<X,Priority>& P) const { return p>=P.p; }
00081     bool operator==(const Prioritized<X,Priority>& P) const { return p==P.p; }
00083     bool operator!=(const Prioritized<X,Priority>& P) const { return p!=P.p; }
00084 };
00085 
00086 
00088 
00101 template<class X, class INDEX = int>
00102 class BinaryHeapSimple {    
00103 private:
00104     Array<X,INDEX> data; // array starts at index 1
00105     INDEX num;
00106 public:
00108     BinaryHeapSimple(INDEX size) : data(1, size), num(0) {}
00109 
00111     bool empty() const { return num == 0; }
00113     INDEX size() const { return num; }
00114     
00116     void clear() { num = 0; }
00117 
00119     const X& top() const {
00120         return data[1];
00121     }
00123     inline const X& getMin() const {
00124         return top();
00125     }
00126     
00128     void push(X& x) {
00129         X y;
00130         if(num == capacity())
00131             data.grow(capacity(),y); // double the size & init with nulls
00132         data[++num] = x;
00133         heapup(num);
00134     }
00136     inline void insert(X& x) {
00137         push(x);
00138     }
00139     
00141     X pop() {
00142         data.swap(1, num--);
00143         heapdown();
00144         return data[num+1];
00145     }
00147     inline X extractMin() {
00148         return pop();
00149     }
00150     
00152     const X& operator[](INDEX idx) const {
00153         return data[idx+1];
00154     }
00155     
00156 
00157 protected:
00159     INDEX capacity() const { return data.size(); }
00160 
00161     void heapup(INDEX idx) {
00162         INDEX papa;
00163         while( (papa = idx/2) > 0) {
00164             if( data[papa] > data[idx] ) {
00165                 data.swap(papa, idx);
00166                 idx = papa;
00167             } else return; //done
00168         }
00169     }
00170     
00171     void heapdown() {
00172         INDEX papa = 1;
00173         INDEX son;
00174         while(true) {
00175             if( (son = 2*papa) < num && data[son+1] < data[son] )
00176                 son++;
00177             if( son <= num && data[son] < data[papa]) {
00178                 data.swap(papa, son);
00179                 papa = son;
00180             } else return;
00181         }       
00182     }   
00183 };
00184 
00186 
00194 template<class X, class INDEX = int>
00195 class Top10Heap : protected BinaryHeapSimple<X,INDEX> { // favors the 10 highest values...
00196 public:
00198     enum PushResult { Accepted, Rejected, Swapped };
00199     
00201     static bool successful(PushResult r) { return r != Rejected; }
00203     static bool returnedSomething(PushResult r) { return r != Accepted; }
00204 
00206     Top10Heap() : BinaryHeapSimple<X,INDEX>(10) {}
00208     Top10Heap(INDEX size) : BinaryHeapSimple<X,INDEX>(size) {}
00209 
00211     bool empty() const { return BinaryHeapSimple<X,INDEX>::empty(); }
00213     bool full() const { return size() == capacity(); }
00215     INDEX size() const { return BinaryHeapSimple<X,INDEX>::size(); }
00217     INDEX capacity() const { return BinaryHeapSimple<X,INDEX>::capacity(); }
00218 
00220     void clear() { BinaryHeapSimple<X,INDEX>::clear(); }
00221 
00223 
00239     PushResult push(X& x, X& out) { // returns element that got kicked out - out is uninitialized if heap wasn't full (i.e. PushResult equals Accepted)
00240         PushResult ret = Accepted;
00241         if(capacity() == size()) {
00242             if(BinaryHeapSimple<X,INDEX>::top() >= x) {// reject new item since it's too bad
00243                 out = x;
00244                 return Rejected;
00245             }
00246             out = BinaryHeapSimple<X,INDEX>::pop(); // remove worst first
00247             ret = Swapped;
00248         }
00249         BinaryHeapSimple<X,INDEX>::push(x);
00250         return ret;
00251     }
00253     inline PushResult insert(X& x, X& out) {
00254         return push(x, out);
00255     }
00256     
00258 
00261     void pushBlind(X& x) {
00262         if(capacity() == size()) {
00263             if(BinaryHeapSimple<X,INDEX>::top() >= x) // reject new item since it's too bad
00264                 return;
00265             BinaryHeapSimple<X,INDEX>::pop(); // remove worst first
00266         }
00267         BinaryHeapSimple<X,INDEX>::push(x);
00268     }
00270     inline void insertBlind(X& x, X& out) {
00271         return pushBlind(x, out);
00272     }
00273     
00275 
00279     const X& operator[](INDEX idx) const { // ATTN: simulate index starting at 0, to be "traditional" to the outside!!!
00280         return BinaryHeapSimple<X,INDEX>::operator[](idx);
00281     }
00282 };
00283 
00285 
00293 template<class X, class Priority=double, class STATICCOMPARER=StdComparer<X>, class INDEX = int >
00294 class DeletingTop10Heap : public Top10Heap<Prioritized<X*,Priority>,INDEX > {
00295 public:
00297     DeletingTop10Heap(int size) : Top10Heap<Prioritized<X*, Priority>,INDEX >(size) {}
00299 
00304     void pushAndDelete(X* x, Priority p) {
00305         Prioritized<X*, Priority> vo;
00306         Prioritized<X*, Priority> nv(x, p);
00307         if(returnedSomething( Top10Heap<Prioritized<X*, Priority>,INDEX >::push(nv, vo) ))
00308             delete vo.item();
00309     }
00311     inline void insertAndDelete(X* x, Priority p) {
00312         pushAndDelete(x, p);
00313     }
00315 
00319     void pushAndDeleteNoRedundancy(X* x, Priority p) {
00320         for(INDEX i = Top10Heap<Prioritized<X*,Priority>,INDEX >::size(); i-->0;) {
00321             X* k = Top10Heap<Prioritized<X*,Priority>,INDEX >::operator[](i).item();
00322 //          OGDF_ASSERT( x )
00323 //          OGDF_ASSERT( k )
00324             if(TargetComparer<X,STATICCOMPARER>::equal(k,x)) {
00325                 delete x;
00326                 return;
00327             }
00328         }
00329         pushAndDelete(x, p);
00330     }       
00332     inline void insertAndDeleteNoRedundancy(X* x, Priority p) {
00333         pushAndDeleteNoRedundancy(p, x);
00334     }
00335 };
00336 
00337 } // end namespace ogdf
00338 
00339 
00340 #endif