fibonacci_heap.h

Go to the documentation of this file.

#ifndef FIBONACCI_HEAP_H
#define FIBONACCI_HEAP_H

#include "fibheap.h"
#include "hash_map.h"

template<class Data>
class HeapNode : public FibHeapNode {
public:
    Data *data;
    double key;

    HeapNode() : FibHeapNode() { key = 0.0; data=NULL;}
    HeapNode(Data* _data, double _key) : FibHeapNode() { key=_key; data=_data;}

    virtual void operator =(FibHeapNode& RHS);
    virtual int  operator ==(FibHeapNode& RHS);
    virtual int  operator <(FibHeapNode& RHS);

    virtual void Print();

    inline void set(Data *_data, double _key) { data=_data; key=_key;}
};

template<class Data>
class FHeap {
private:
    typedef hashers::hash_map<Data*, unsigned> Hash_T;
    typedef typename Hash_T::iterator Hash_iterator_T;
    Hash_T node_idx;
    HeapNode<Data> *nodes;
    FibHeap heap;
    unsigned next_idx;
    unsigned size;

public:
    FHeap(unsigned _size);
    ~FHeap();

    /* decrease will insert if data is not already in heap */
    bool decrease(Data* data, double val);
    bool rem_min(Data* &data, double &val);
    inline bool empty();
};


template<class Data>
void HeapNode<Data>::Print() {
    FibHeapNode::Print();
    std::cout <<"Key:"<< key << " Data:"<< data;
}

template<class Data>
void HeapNode<Data>::operator =(FibHeapNode& RHS) {
    FHN_Assign(RHS);
    key = ((HeapNode&) RHS).key;
    data = ((HeapNode&) RHS).data;
}

template<class Data>
int  HeapNode<Data>::operator ==(FibHeapNode& RHS) {
    if (FHN_Cmp(RHS)) return 0;
    return key == ((HeapNode&) RHS).key ? 1 : 0;
}

template<class Data>
int  HeapNode<Data>::operator <(FibHeapNode& RHS) {
    int x;
    if ((x = FHN_Cmp(RHS)) != 0) return x < 0 ? 1 : 0;
    return key < ((HeapNode&) RHS).key ? 1 : 0;
};


template <class Data>
FHeap<Data>::FHeap(unsigned _size){
    size = _size;
    next_idx = 0;
    nodes = new HeapNode<Data>[size];
    node_idx.resize(3*size);

}

template <class Data>
FHeap<Data>::~FHeap(){
    delete[] nodes;
}

template <class Data>
bool FHeap<Data>::decrease(Data* data, double val){
    Hash_iterator_T i;
    int idx;

    i = node_idx.find(data);
    if( i == node_idx.end() ){
        if(next_idx == size) return false;
        idx = next_idx++;
        node_idx[data] = idx;
        nodes[idx].set(data, val);
        heap.Insert( &nodes[idx] );
        return true;
    }

    HeapNode<Data> temp(data, val);
    idx = (*i).second;
    return heap.DecreaseKey(&nodes[idx], temp) == OK;
}

template <class Data>
bool FHeap<Data>::rem_min(Data* &data, double &val){
    HeapNode<Data> *temp;
    temp = (HeapNode<Data>*)heap.ExtractMin();
    if(!temp) return false;
    data = temp->data;
    val = temp->key;
    return true;
}

template <class Data>
bool FHeap<Data>::empty(){
    return heap.Minimum() == NULL;
}

#endif /* FIBONACCI_HEAP_H */

---