Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

MinHeap.h

Go to the documentation of this file.

/*
 * $Revision: 1.7 $
 * 
 * last checkin:
 *   $Author: klein $ 
 *   $Date: 2007-11-12 15:53:31 +0100 (Mo, 12 Nov 2007) $ 
 ***************************************************************/
 
#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 Score, class X> class Valued {
    Score v;
    X x;
public:
    Valued() : v(0), x(0) {};
    Valued(Score vt, X xt) : v(vt), x(xt) {}
    Valued(const Valued& V) : v(V.v), x(V.x) {}
    Score value() const { return v; }
    X item() const { return x;}
    bool operator<(const Valued<Score,X>& V) const { return v<V.v; }
    bool operator<=(const Valued<Score,X>& V) const { return v<=V.v; }
    bool operator>(const Valued<Score,X>& V) const { return v>V.v; }
    bool operator>=(const Valued<Score,X>& V) const { return v>=V.v; }
    bool operator==(const Valued<Score,X>& V) const { return v==V.v; }
    bool operator!=(const Valued<Score,X>& V) const { return v!=V.v; }
};



template<class X, class INDEX = int>
class MinHeap { 
private:
    Array<X,INDEX> data; // array starts at index 1
    INDEX num;
public:
    MinHeap(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];
    }
    
    void push(X& x) {
        X y;
        if(num == capacity())
            data.grow(capacity(),y); // double the size & init with nulls
        data[++num] = x;
        heapup(num);
    }
    
    X pop() {
        data.swap(1, num--);
        heapdown();
        return data[num+1];
    }
    
    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 MinHeap<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() : MinHeap<X,INDEX>(10) {}
    Top10Heap(INDEX size) : MinHeap<X,INDEX>(size) {}

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

    void clear() { MinHeap<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(MinHeap<X,INDEX>::top() >= x) {// reject new item since it's too bad
                out = x;
                return Rejected;
            }
            out = MinHeap<X,INDEX>::pop(); // remove worst first
            ret = Swapped;
        }
        MinHeap<X,INDEX>::push(x);
        return ret;
    }
    

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

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

} // end namespace ogdf


#endif

---