MinHeap.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_MIN_HEAP_H
#define OGDF_MIN_HEAP_H

#include<ogdf/basic/Array.h>

namespace ogdf {


template<class X, class Priority=double> class Prioritized {
    X x;
    Priority p;
public:
    Prioritized() : x(0), p(0) {};
    Prioritized(X xt, Priority pt) : x(xt),p(pt) {}
    Prioritized(const Prioritized& P) : x(P.x),p(P.p) {}
    Priority priority() const { return p; }
    X item() const { return x;}
    bool operator<(const Prioritized<X,Priority>& P) const { return p<P.p; }
    bool operator<=(const Prioritized<X,Priority>& P) const { return p<=P.p; }
    bool operator>(const Prioritized<X,Priority>& P) const { return p>P.p; }
    bool operator>=(const Prioritized<X,Priority>& P) const { return p>=P.p; }
    bool operator==(const Prioritized<X,Priority>& P) const { return p==P.p; }
    bool operator!=(const Prioritized<X,Priority>& P) const { return p!=P.p; }
};



template<class X, class INDEX = int>
class BinaryHeapSimple {    
private:
    Array<X,INDEX> data; // array starts at index 1
    INDEX num;
public:
    BinaryHeapSimple(INDEX size) : data(1, size), num(0) {}

    bool empty() const { return num == 0; }
    INDEX size() const { return num; }
    
    void clear() { num = 0; }

    const X& top() const {
        return data[1];
    }
    inline const X& getMin() const {
        return top();
    }
    
    void push(X& x) {
        X y;
        if(num == capacity())
            data.grow(capacity(),y); // double the size & init with nulls
        data[++num] = x;
        heapup(num);
    }
    inline void insert(X& x) {
        push(x);
    }
    
    X pop() {
        data.swap(1, num--);
        heapdown();
        return data[num+1];
    }
    inline X extractMin() {
        return pop();
    }
    
    const X& operator[](INDEX idx) const {
        return data[idx+1];
    }
    

protected:
    INDEX capacity() const { return data.size(); }

    void heapup(INDEX idx) {
        INDEX papa;
        while( (papa = idx/2) > 0) {
            if( data[papa] > data[idx] ) {
                data.swap(papa, idx);
                idx = papa;
            } else return; //done
        }
    }
    
    void heapdown() {
        INDEX papa = 1;
        INDEX son;
        while(true) {
            if( (son = 2*papa) < num && data[son+1] < data[son] )
                son++;
            if( son <= num && data[son] < data[papa]) {
                data.swap(papa, son);
                papa = son;
            } else return;
        }       
    }   
};


template<class X, class INDEX = int>
class Top10Heap : protected BinaryHeapSimple<X,INDEX> { // favors the 10 highest values...
public:
    enum PushResult { Accepted, Rejected, Swapped };
    
    static bool successful(PushResult r) { return r != Rejected; }
    static bool returnedSomething(PushResult r) { return r != Accepted; }

    Top10Heap() : BinaryHeapSimple<X,INDEX>(10) {}
    Top10Heap(INDEX size) : BinaryHeapSimple<X,INDEX>(size) {}

    bool empty() const { return BinaryHeapSimple<X,INDEX>::empty(); }
    bool full() const { return size() == capacity(); }
    INDEX size() const { return BinaryHeapSimple<X,INDEX>::size(); }
    INDEX capacity() const { return BinaryHeapSimple<X,INDEX>::capacity(); }

    void clear() { BinaryHeapSimple<X,INDEX>::clear(); }


    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)
        PushResult ret = Accepted;
        if(capacity() == size()) {
            if(BinaryHeapSimple<X,INDEX>::top() >= x) {// reject new item since it's too bad
                out = x;
                return Rejected;
            }
            out = BinaryHeapSimple<X,INDEX>::pop(); // remove worst first
            ret = Swapped;
        }
        BinaryHeapSimple<X,INDEX>::push(x);
        return ret;
    }
    inline PushResult insert(X& x, X& out) {
        return push(x, out);
    }
    

    void pushBlind(X& x) {
        if(capacity() == size()) {
            if(BinaryHeapSimple<X,INDEX>::top() >= x) // reject new item since it's too bad
                return;
            BinaryHeapSimple<X,INDEX>::pop(); // remove worst first
        }
        BinaryHeapSimple<X,INDEX>::push(x);
    }
    inline void insertBlind(X& x, X& out) {
        return pushBlind(x, out);
    }
    

    const X& operator[](INDEX idx) const { // ATTN: simulate index starting at 0, to be "traditional" to the outside!!!
        return BinaryHeapSimple<X,INDEX>::operator[](idx);
    }
};


template<class X, class Priority=double, class STATICCOMPARER=StdComparer<X>, class INDEX = int >
class DeletingTop10Heap : public Top10Heap<Prioritized<X*,Priority>,INDEX > {
public:
    DeletingTop10Heap(int size) : Top10Heap<Prioritized<X*, Priority>,INDEX >(size) {}

    void pushAndDelete(X* x, Priority p) {
        Prioritized<X*, Priority> vo;
        Prioritized<X*, Priority> nv(x, p);
        if(returnedSomething( Top10Heap<Prioritized<X*, Priority>,INDEX >::push(nv, vo) ))
            delete vo.item();
    }
    inline void insertAndDelete(X* x, Priority p) {
        pushAndDelete(x, p);
    }

    void pushAndDeleteNoRedundancy(X* x, Priority p) {
        for(INDEX i = Top10Heap<Prioritized<X*,Priority>,INDEX >::size(); i-->0;) {
            X* k = Top10Heap<Prioritized<X*,Priority>,INDEX >::operator[](i).item();
//          OGDF_ASSERT( x )
//          OGDF_ASSERT( k )
            if(TargetComparer<X,STATICCOMPARER>::equal(k,x)) {
                delete x;
                return;
            }
        }
        pushAndDelete(x, p);
    }       
    inline void insertAndDeleteNoRedundancy(X* x, Priority p) {
        pushAndDeleteNoRedundancy(p, x);
    }
};

} // end namespace ogdf


#endif