fibunacci.h

/*Prioritätswartelist, sortiert Elemente gemäß dem Float, der an erster Stelle
in ele->data[0] steht*/
#pragma once
#include <string>                                   //c++-String-Klasse
#include <stdio.h>                                  //C-File-Handling
#include <math.h>
#include "DataTyps.h"

template <class T> class ele{
public:
    ele();
    ele(float d);
    T* data;                            //mit Knoten verbundene Daten
    ele<T> *l, *r, *next;               //Blattstruktur
    int m;                              //Markierung
    float* d;
};
template <class T> ele<T>::ele(){
}
template<> ele<STRONGfib>::ele(float d);
template<> ele<STRONGPlusfib>::ele(float d);
template<> ele<CAfib>::ele(float d);
template <class T> class FibunacciHeap{
    public:
        FibunacciHeap();
        ~FibunacciHeap();
        T* ins(float d);
        T* getmin();
        T* extmin();
        T* del(ele<T>* e);
    private:
        void clean();
        ele<T>* m;
        long int n;
};
template <class T> FibunacciHeap<T>::FibunacciHeap(){
    m = NULL;
    n = 0;
}
template <class T> FibunacciHeap<T>::~FibunacciHeap(){
    if(m != NULL){
        ele<T>* k;
        ele<T> dummy;
        m->l->r = &dummy;
        while(m != &dummy && m != NULL){
            if(m->next != NULL){
                /*einfuegen der Kinder in die Wurzelliste*/
                k = m->next;
                k->l->r = m->r;
                m->r->l = k->l;
                k->l = m;
                m->r = k;

                /*loeschen des Wurzelelements*/
                k = m;
                m = m->r;
                delete k->data;
                delete k;
            }
            else{
                k = m;
                m = m->r;
                delete k->data;
                delete k;
            }
        }
        m = NULL;
    }
}
template <class T> T* FibunacciHeap<T>::getmin(){
    return m->data;
}
template <class T> T* FibunacciHeap<T>::ins(float d){
    ele<T>* e = new ele<T>(d);
    e->m = 0;
    e->next = NULL;

    /*Einbinden in Wurzelliste*/
    if(m != NULL){
        e->l = m->l;
        e->r = m;
        m->l = e;
        e->l->r = e;
        if(*((float*)(m->data)) > d)
            m = e;
    }
    else{
        e->l = e;
        e->r = e;
        m = e;
    }

    n++;
    return e->data;
}
template <class T> T* FibunacciHeap<T>::extmin(){
    if(m != NULL){
        T* result = m->data;
        /*alle Kinder in die Wurzelliste einfuegen*/
        ele<T>* k = m->next, *b;
        if(k != NULL)
            k->l->r = NULL;             //Listen aufbrechen
        while(k != NULL){
            k->l = m->l;
            b = k->r;                   //naechstes Kind abfangen
            k->r = m;
            m->l = k;
            k->l->r = k;
            k = b;
        }
        /*altes min-Elemente ausklinken*/
        m->l->r = m->r;
        m->r->l = m->l;
        b = m->r;
        if(b != m){
            /*falls noch Elemente im fibunacci-Heap vorhanden sind*/
            delete m;
            m = b;

            /*Liste aufraeumen, neues Minimalelement suchen*/
            n--;
            clean();
            return result;
        }
        else{
            delete m;
            m = NULL;
            n = 0;
            return result;
        }

    }
    else
        return NULL;
}
template <class T> void FibunacciHeap<T>::clean(){
    if(n > 1){
        /*Hilfsarray a[] anlegen, in das Unterbäume ihrem Grade/Markierung nach
        eingeordnet werden*/
        long int N = (long int) ceil(2*log((double)n));
        ele<T>** a = new ele<T>*[N];
        for(long int i = 0; i < N; i++)
            a[i] = NULL;
        /*Alle Wurzelemente in a[] einordnen*/
        ele<T>* k = m;
        k->l->r = NULL;
        while(k != NULL){
            if(a[k->m] == NULL){
                /*Falls das Array an der Stelle k->m frei ist*/
                a[k->m] = k;
                k = k->r;
            }
            else{
                /*an der Stelle k->m ist steht schon ein Baum*/
                if(*((float*)a[k->m]->data) <= *((float*) k->data)){
                    /*der bestehende Baum hat einen kleineren Schluesselwert als
                    der einzuordnende Baum, der einzuordnende Baum wird Kind des
                    bestehenden*/
                    ele<T>* b = k->r;

                    if(a[k->m]->next == NULL){
                        a[k->m]->next = k;
                        k->l = k;
                        k->r = k;
                    }
                    else{
                        k->l = a[k->m]->next->l;
                        k->r = a[k->m]->next;
                        k->l->r = k;
                        a[k->m]->next->l = k;
                    }

                    if(a[k->m]->m < k->m + 1){
                        /*der bestehende Baum steht jetzt leider an der falschen
                        Stelle im Array, da sein Grad gewachsen ist, er muss neu
                        eingeordnet werden*/
                        a[k->m]->r = b;     //damit alle noch einzuordnenden
                                            //Wurzelelemente verarbeitet werden
                        a[k->m]->m = k->m + 1;
                        k = a[k->m];
                        a[k->m-1] = NULL;
                    }
                    else
                        /*sonst mit dem naechsten Wurzelelement fortfahren*/
                        k = b;
                }
                else{
                    /*der bestehende Baum hat einen groesseren Schluesselwert als
                    der einzuordnende Baum, der bestehende Baum wird Kind des
                    einzuordnenden Baum, der einzuordnende Baum bestetzt a[k->m]*/
                    if(k->next == NULL){
                        k->next = a[k->m];
                        a[k->m]->l = a[k->m];
                        a[k->m]->r = a[k->m];
                    }
                    else{
                        a[k->m]->l = k->next->l;
                        a[k->m]->r = k->next;
                        a[k->m]->l->r = a[k->m];
                        k->next->l = a[k->m];
                    }
                    if(a[k->m]->m + 1 > k->m){
                        /*der neu eingeordnete Baum steht jetzt leider an der
                        falschen Stelle im Array, da sein Grad gewachsen ist, er
                        muss neu eingeordnet werden*/
                        int b = k->m;
                        k->m = a[b]->m + 1;
                        a[b] = NULL;
                    }
                    else{
                        a[k->m] = k;
                        k = k->r;
                    }
                }
            }
        }

        /*neue Wurzelliste zusammensetzen, nebenbei neues Minimalelement finden*/
        m = NULL;
        long int i = 0;
        while(m == NULL){
            if(a[i] != NULL)
                m = a[i];
            i++;
        }
        m->l = m;
        m->r = m;
        for(; i < N; i++)
            if (a[i] != NULL){
                a[i]->l = m->l;
                a[i]->r = m;
                a[i]->l->r = a[i];
                a[i]->r->l = a[i];
                if(*a[i]->d <* m->d)
                    m = a[i];
            }
        delete a;
    }
}