// Una arista negativa: Dijkstra da por definitivo un nodo que todavía podía mejorar.
#include <iostream>
#include <vector>

#include "../sample_graphs.h"
#include "../shortest_paths.h"

namespace {

// La misma idea sin arreglo de sacados: una entrada es vieja si no coincide con la distancia.
// Si target no es -1, se detiene al sacarlo.
std::vector<Meters> without_settled_array(const Graph& graph, int source, int target, int& pulled) {
    std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
    MinFirstQueue heap;
    distance[source] = 0;
    heap.push({0, source});
    while (!heap.empty() && pulled < 100) {
        auto [d, u] = heap.top();
        heap.pop();
        pulled++;
        if (d != distance[u]) {
            continue;
        }
        if (u == target) {
            break;
        }
        for (const Edge& edge : graph.neighbors(u)) {
            if (d + edge.weight < distance[edge.to]) {
                distance[edge.to] = d + edge.weight;
                heap.push({distance[edge.to], edge.to});
            }
        }
    }
    return distance;
}

void print(const char* title, const std::vector<Meters>& distance) {
    std::cout << title;
    for (Meters d : distance) {
        std::cout << " " << d;
    }
    std::cout << "\n";
}

}  // namespace

int main() {
    Graph graph = negative_edge_graph();
    DijkstraResult result = dijkstra(graph, 0);
    print("dijkstra:          ", result.distance);
    std::cout << "ruta real a 3: 0 2 1 3, con 3 + (-2) + 1 = 2\n";
    int pulled = 0;
    print("sin arreglo:       ", without_settled_array(graph, 0, -1, pulled));
    std::cout << "entradas sacadas: " << pulled << "\n";
    pulled = 0;
    std::cout << "sin arreglo, parando al sacar el 1: " << without_settled_array(graph, 0, 1, pulled)[1]
              << " (la verdad es 1)\n";

    Graph cycle(3, true);
    cycle.add_edge(0, 1, 1);
    cycle.add_edge(1, 2, -3);
    cycle.add_edge(2, 1, 1);
    pulled = 0;
    without_settled_array(cycle, 0, -1, pulled);
    std::cout << "con un ciclo negativo, cortado tras " << pulled << " entradas sacadas\n";
    return 0;
}