/*
 * File:   dijkstra.cc
 * Author: Filip Niksic, fniksic@gmail.com
 *
 * Created on 2008. veljaca 08, 17:47
 */

#include <vector>
#include <set>

#include "globals.h"
#include "graph.h"
#include "dijkstra.h"

using namespace std;

class DijkstraCompare {
    const std::vector<Real_T>& d;
public:
    explicit DijkstraCompare(const std::vector<Real_T> &distance) : d(distance) {}
    bool operator()(const Graph::Vertex_ID &u, const Graph::Vertex_ID &v) const {
        return (d[u] < d[v] ? true : false);
    }
};

void dijkstra(Graph g, Graph::Vertex_ID source, std::vector<Real_T> &distance, std::vector<Graph::Vertex_ID> &parent) {
    typedef Graph::Vertex_ID Vertex_ID;
    
    // Nazalost, priority_queue iz STL-a ne podrzava promjenu prioriteta elementa nakon
    // sto se promijeni kriterij usporedbe (kod mene je kriterij usporedbe distance).
    // Zato koristim set. Brisanjem i ponovnim umetanjem simuliram trazeno ponasanje,
    // a zadrzavam logaritamsku slozenost.
    DijkstraCompare cmp(distance);
    set<Vertex_ID, DijkstraCompare> myHeap(cmp);
    
    for (Vertex_ID v = 0; v != g.numVertices(); ++v) {
        distance[v] = Inf;
        parent[v] = v;
    }
    distance[source] = 0.0;
    myHeap.insert(source);
    while (!myHeap.empty()) {
        Vertex_ID u(*myHeap.begin());
        myHeap.erase(myHeap.begin());
        // Jednog lijepog dana moj graf ce dopustati iteriranje po susjedima od u, a dotad:
        for (Vertex_ID v = 0; v != g.numVertices(); ++v)
            if (g.existsEdge(u, v) && g.getEdge(u, v) + distance[u] < distance[v]) {
                // relaksacija vrha v
                myHeap.erase(v);
                distance[v] = distance[u] + g.getEdge(u, v);
                parent[v] = u;
                myHeap.insert(v);
            }
    }
}