Routing.cpp

#include "Routing.h"

Routing::Routing(OSM *o){
    this->o = o;
}
Routing::~Routing(void){
}
short Routing::DijkstraFib(KOO* s, KOO* e, char max, char min, OSM* o,int Si){
    Neighbour* n;
    resetSTRONG(o->get_first_KOO(),Si);
    FibunacciHeap<STRONGfib> f;
    STRONGfib* t = f.ins(0), *t2;
    s->cd->s[Si].from =  new STRONGfib;
    ((STRONGfib*)(s->cd->s[Si].from))->d = -1;
    s->cd->s[Si].via = NULL;
    t->k = s;
    t->from = NULL;
    t->via = s->cd->neighbours;
        
    t = f.extmin();
    while(t != NULL && t->d >-1){
        /*Die Prioritaetswarteliste hatte noch Elemente und das gewaehlte
        Element ist nicht zum ueberspringen freigegeben (d.h. t->d = -1)*/
        n = t->k->cd->neighbours;
        while(n != NULL){
            if(n->way->type >= min && n->way->type <= max ){
                /*Der Weg erfüllt die Anforderung an den Typ und hat die
                Prioritaetswarteschlange noch nie durchlaufen*/
                if(    n->nb->cd->s[Si].from == NULL 
                    && n->nb->cd->s[Si].via == NULL){
                    /*KOO wurde noch nie erreicht*/
                    t2 = f.ins(t->d + n->d);
                    t2->k = n->nb;
                    t2->from = &(t->k->cd->s[Si]);
                    t2->via = n;
                    n->nb->cd->s[Si].from = t2;
                }
                else{
                    /*KOO wurde schon erreicht, pruefe: hat der Punkt die
                    Prioritaetswarteschlange schon wieder verlassen, falls
                    nicht: pruefe, ob Distanz jetzt kuerzer ist*/
                    if( n->nb->cd->s[Si].via == NULL &&
                        ((STRONGfib*)(n->nb->cd->s[Si].from))->d > t->d + n->d){
                        /*alten Eintrag löschen und neuen erzeugen*/
                        ((STRONGfib*)(n->nb->cd->s[Si].from))->d = -1;
                        t2 = f.ins(t->d + n->d);
                        t2->k = n->nb;
                        t2->from = &(t->k->cd->s[Si]);
                        t2->via = n;
                        n->nb->cd->s[Si].from = t2;
                    }
                }
            }
            n = n->next;
        }
        /*KOO ist abgehandelt, Daten koennen gespeichert werden*/
        t->k->cd->s[Si].via = t->via;
        t->k->cd->s[Si].from = t->from;
        
        
        if(t->k != e)
            do{
            delete(t);                  //Datenstruktur des FibunacciHeap free
            t = f.extmin();//naechste zu bearbeitende KOO
            }while(t != NULL && t->d < 0);
        else
            t->d = -1;                  //Endpunkt erreicht
    }
    
    if(t == NULL)
        return 0;                       //Endpunkt wurde nicht erreicht
    else{
        delete(t);
        return 1;                       //Endpunkt wurde erreicht
    }
}
short Routing::DijkstraFib_minHM(KOO* s, KOO* e, char max, char min, OSM* o,
                                 int Si){
    Neighbour* n;
    resetSTRONG(o->get_first_KOO(),Si);
    FibunacciHeap<STRONGfib> f;
    STRONGfib* t = f.ins(0), *t2;
    s->cd->s[Si].from = new STRONGfib;
    ((STRONGfib*)(s->cd->s[Si].from))->d = -1;
    s->cd->s[Si].via = NULL;
    t->k = s;
    t->from = NULL;
    t->via = s->cd->neighbours;
        
    t = f.extmin();
    while(t != NULL && t->d >-1){
        /*Die Prioritaetswarteliste hatte noch Elemente und das gewaehlte
        Element ist nicht zum ueberspringen freigegeben (d.h. t->d = -1)*/
        n = t->k->cd->neighbours;
        while(n != NULL){
            if(n->way->type >= min && n->way->type <= max ){
                /*Der Weg erfüllt die Anforderung an den Typ und hat die
                Prioritaetswarteschlange noch nie durchlaufen*/
                if(n->nb->cd->s[Si].from == NULL && n->nb->cd->s[Si].via == NULL){
                    /*KOO wurde noch nie erreicht*/
                    t2 = f.ins(t->d + n->hm);
                    t2->k = n->nb;
                    t2->from = &(t->k->cd->s[Si]);
                    t2->via = n;
                    n->nb->cd->s[Si].from = t2;
                }
                else{
                    /*KOO wurde schon erreicht, pruefe: hat der Punkt die
                    Prioritaetswarteschlange schon wieder verlassen, falls
                    nicht: pruefe, ob Distanz jetzt kuerzer ist*/
                    if( n->nb->cd->s[Si].via == NULL &&
                        ((STRONGfib*)(n->nb->cd->s[Si].from))->d > t->d + n->hm){
                        /*alten Eintrag löschen und neuen erzeugen*/
                        ((STRONGfib*)(n->nb->cd->s[Si].from))->d = -1;
                        t2 = f.ins(t->d + n->hm);
                        t2->k = n->nb;
                        t2->from = &(t->k->cd->s[Si]);
                        t2->via = n;
                        n->nb->cd->s[Si].from = t2;
                    }
                }
            }
            n = n->next;
        }
        /*KOO ist abgehandelt, Daten koennen gespeichert werden*/
        t->k->cd->s[Si].via = t->via;
        t->k->cd->s[Si].from = t->from;
        
        
        if(t->k != e)
            do{
            delete(t);                  //Datenstruktur des FibunacciHeap free
            t = f.extmin();//naechste zu bearbeitende KOO
            }while(t != NULL && t->d < 0);
        else
            t->d = -1;                  //Endpunkt erreicht
    }

    if(t == NULL)
        return 0;                       //Endpunkt wurde nicht erreicht
    else{
        delete(t);
        return 1;                       //Endpunkt wurde erreicht
    }

}
void Routing::resetSTRONG(KOO* k, int STRONGindex){
    if(k != NULL){
        if(k->cd != NULL)
            if(k->cd->s != NULL){
                k->cd->s[STRONGindex].from = NULL;
                k->cd->s[STRONGindex].via = NULL;
            }
        resetSTRONG(k->r, STRONGindex);
        resetSTRONG(k->l, STRONGindex);
    }
}
void Routing::setSTRONG(KOO* k, KOO* s, KOO* e, float radius, int n){
    if(k != NULL){
        if(k->cd != NULL){
            if( s == NULL || e == NULL ||
                distance(k->lat,k->lon,s->lat,s->lon)
               +distance(k->lat,k->lon,e->lat,e->lon) < radius){
                delete(k->cd->s);
                k->cd->s = new STRONG[n];
                for(int i = 0; i < n; i++){
                    k->cd->s[i].from = NULL;
                    k->cd->s[i].via = NULL;
                }
            }
            else{
                delete(k->cd->s);
                k->cd->s = NULL;
            }
        }
        setSTRONG(k->l, s, e, radius, n);
        setSTRONG(k->r, s, e, radius, n);
    }
}
void Routing::extract_neighbourlist(STRONG* s, STRONG* e,
                                    Neighbour ***nl,int* nc){
    STRONG* st = e;
    int nct = 0;
    while(st != s){
        st = (STRONG*)st->from;
        nct++;
    }
    *nl = new Neighbour*[nct];
    *nc = nct;
    st = e;
    while(st != s){
        nct--;
        (*nl)[nct] = st->via;
        st = (STRONG*)st->from;
    }
}
void Routing::finish_STRONG(){
    setSTRONG(o->get_first_KOO(), NULL, NULL,0,2);
}
void Routing::STRONGlayer_reset_d(KOO* k){
    if(k!= NULL){
        if(k->cd != NULL){
            Neighbour* n = k->cd->neighbours;
            while(n != NULL){
                n->d = 0;
                n = n->next;
            }
        }
        STRONGlayer_reset_d(k->l);
        STRONGlayer_reset_d(k->r);
    }
}
void Routing::STRONGlayer_reconstruct_d(KOO* k){
    if(k!= NULL){
        if(k->cd != NULL){
            Neighbour* n = k->cd->neighbours;
            while(n != NULL){
                n->d = n->tp[n->tpc-1].d;
                n = n->next;
            }
        }
        STRONGlayer_reconstruct_d(k->l);
        STRONGlayer_reconstruct_d(k->r);
    }
}
void Routing::STRONGlayer_count_neighbours(KOO* k, int *nbc){
    if(k!= NULL){
        if(k->cd != NULL){
            if(k->lon > SLlonmax) SLlonmax = k->lon;
            if(k->lon < SLlonmin) SLlonmin = k->lon;
            if(k->lat > SLlatmax) SLlatmax = k->lat;
            if(k->lat < SLlatmin) SLlatmin = k->lat;
            Neighbour* n = k->cd->neighbours;
            while(n != NULL){
                if(n->rd == fw) (*nbc)++;
                n = n->next;
            }
        }
        STRONGlayer_count_neighbours(k->l, nbc);
        STRONGlayer_count_neighbours(k->r, nbc);
    }
}
void Routing::STRONGlayer_mark_neighbours(KOO* k, int si){
    if(k!= NULL){
        if(    k->cd != NULL
            && k->cd->s != NULL
            && k->cd->s[si].from != NULL)
            if(STRONGlayer_grid_free(k)){
                STRONG* s = &(k->cd->s[si]);
                while(s != NULL){
                    if(s->via->rd == fw)    s->via->d ++;
                    else                    s->via->brthr->d ++;
                    s = (STRONG*) s->from;
                }
            }
        STRONGlayer_mark_neighbours(k->l, si);
        STRONGlayer_mark_neighbours(k->r, si);
    }
}
void Routing::STRONGlayer_fill_neighbours(KOO* k, STRONGlayerele* data, 
                                          int *nbc){
    if(k!= NULL){
        if(k->cd != NULL){
            Neighbour* n = k->cd->neighbours;
            while(n != NULL){
                if(n->rd == fw){
                    data[*nbc].n = n;
                    (*nbc)++;
                }
                n = n->next;
            }
        }
        STRONGlayer_fill_neighbours(k->l, data, nbc);
        STRONGlayer_fill_neighbours(k->r, data, nbc);
    }
}
void Routing::STRONGlayer_grid_new(){
    double gridperkm = 0.5;
    SLlatmax = SLlatmax +0.01;
    SLlonmax = SLlonmax +0.01;
    SLlatmin = SLlatmin -0.01;
    SLlonmin = SLlonmin -0.01;
    dlat = SLlatmax-SLlatmin;
    dlon = SLlonmax-SLlonmin;
    nlat = dlat*111*gridperkm;
    nlon = dlon*111*sin(double((SLlatmax+SLlatmin)/360.*3.14159265))*gridperkm;
    SLgrid = new char*[nlon];
    for(int x = 0; x < nlon; x++){
        SLgrid[x] = new char[nlat];
    }
}
void Routing::STRONGlayer_grid_reset(){
    for(int x = 0; x < nlon; x++)
        for(int y = 0; y < nlat; y++)
            SLgrid[x][y] = 0;
}
short Routing::STRONGlayer_grid_free(KOO* k){
    int x = int((k->lon-SLlonmin)/dlon*nlon);
    int y = int((k->lat-SLlatmin)/dlat*nlat);
    if( x >= 0 && x < nlon && y >= 0 && y < nlat && SLgrid[x][y] == 0){
        SLgrid[x][y] = 1;
        return 1;
    }
    else
        return 0;
}
void Routing::STRONGlayer_grid_delete(){
    for(int x = 0; x < nlon; x++)
        delete(SLgrid[x]);
    delete(SLgrid);
}
STRONGlayer* Routing::STRONGlayer_create(STRONGlayer* SL,int N){
    if(SL == NULL) return STRONGlayer_create(N);
    /*andernfalls liegen neighbourpointer schon vor*/
    /*Indeces absammeln*/
    STRONGlayer_grid_new();
    STRONGlayer_grid_reset();
    STRONGlayer_reset_d(o->get_first_KOO());
    //    for(int i = 0; i <= N; i++)
    STRONGlayer_mark_neighbours(o->get_first_KOO(),N);
    for(int j = 0; j < SL->ncount; j++){
        /*double maxq = 0, d,hm;
        for(int i = 10; i < N; i++){
            STRONG* s = &(SL->data[j].n->brthr->nb->cd->s[i]);
            d = hm = 0;
            while(s != NULL){
                d += s->via->d;
                hm += s->via->hm;
                s = (STRONG*) s->from;
            }
            if(d > 0 && hm/d > maxq)
                maxq = hm/d;
        }
        SL->data[j].index = maxq;*/
        SL->data[j].index = SL->data[j].n->d;

    }
    STRONGlayer_grid_delete();

    /*Indeces normieren*/
    float max = 0;
    for(int j = 0; j < SL->ncount; j++){
        if(SL->data[j].index > max)
            max = SL->data[j].index;
    }
    for(int j = 0; j < SL->ncount; j++){
        SL->data[j].index = SL->data[j].index / max;
    }
    /*Distanz wieder herstellen (wurde zum Rechnen benutzt)*/
    STRONGlayer_reconstruct_d(o->get_first_KOO());

    STRONGlayer_sort(SL,0,SL->ncount-1);
    return SL;
}
STRONGlayer* Routing::STRONGlayer_create(int N){
    int nbc = 0;
    SLlonmax = -90; SLlatmax = -180; SLlonmin = 90; SLlatmin = 180;
    STRONGlayer_count_neighbours(o->get_first_KOO(),&nbc);
    STRONGlayer* SL = new STRONGlayer;
    SL->ncount = nbc;
    SL->data = new STRONGlayerele[nbc];

    /*Nachbarschaftrelation ins Array laden*/
    nbc = 0;
    STRONGlayer_fill_neighbours(o->get_first_KOO(),SL->data,&nbc);
    
    SL = STRONGlayer_create(SL,N);
    return SL;
}
STRONGlayer* Routing::STRONGlayer_load(char* filename){
    qint64 kid,knid; KOO* k;
    FILE* f = fopen(filename,"rb");
    STRONGlayer* SL = new STRONGlayer;
    fread(&(SL->ncount),sizeof(int),1,f);
    SL->data = new STRONGlayerele[SL->ncount];
    Neighbour* n;
    for(int j = 0; j < SL->ncount; j++){
        fread(&(kid),sizeof(qint64),1,f);
        fread(&(knid),sizeof(qint64),1,f);
        fread(&(SL->data[j].index),sizeof(float),1,f);
        k = o->search(kid,o->get_first_KOO());
        if(k != NULL && k->cd != NULL){
            n = k->cd->neighbours;
            while( n!= NULL && n->nb->id != knid){
                n = n->next;
            }
            if(n != NULL)
                SL->data[j].n = n;
            else
                SL->data[j].n = NULL;
        }
        else
            SL->data[j].n = NULL;
    }
    fclose(f);
    return SL;
}
void Routing::STRONGlayer_save(char* filename, STRONGlayer *SL){
    /*Datei speichern*/
    FILE* f = fopen(filename,"wb");
    fwrite(&(SL->ncount),sizeof(int),1,f);
    for(int j = 0; j < SL->ncount; j++){
        fwrite(&(SL->data[j].n->node[0]->id),sizeof(qint64),1,f);
        fwrite(&(SL->data[j].n->nb->id),sizeof(qint64),1,f);
        fwrite(&(SL->data[j].index),sizeof(float),1,f);
    }
    fclose(f);
}
void Routing::STRONGlayer_sort(STRONGlayer* SL, long s, long e){
    long l = s, r = e;
    STRONGlayerele c;
    float p = SL->data[(s+e)/2].index;
    do{
        while(SL->data[l].index < p) l++;
        while(SL->data[r].index > p) r--;
        if(l<=r){
            c = SL->data[l];
            SL->data[l] = SL->data[r];
            SL->data[r] = c;
            l++;
            r--;
        }
    }while(l <= r);
    if(s < r) STRONGlayer_sort(SL,s,r);
    if(l < e) STRONGlayer_sort(SL,l,e);
}