// Paso 4: cuántos nodos se ahorra Dijkstra al detenerse, según lo lejos que esté el destino.
// Uso: savings mapa.txt calles.tsv "calle de origen"
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

#include "map_file.h"
#include "routes.h"

int main(int argc, char* argv[]) {
    if (argc != 4) {
        std::cerr << "uso: savings mapa.txt calles.tsv origen\n";
        return 2;
    }
    Graph graph = build_map_graph(read_map_file(argv[1]));
    int source = node_of_street(read_streets(argv[2]), argv[3]);
    DijkstraResult whole = dijkstra(graph, source);
    std::vector<int> by_distance(graph.node_count());
    std::iota(by_distance.begin(), by_distance.end(), 0);
    std::sort(by_distance.begin(), by_distance.end(),
              [&](int a, int b) { return whole.distance[a] < whole.distance[b]; });
    std::cout << "origen: " << argv[3] << ", nodo " << source << ", " << whole.counts.settled << " nodos sacados sin parar\n";
    std::cout << "destino   metros  sacados  ahorro  aristas leidas\n";
    for (int percent : {1, 5, 10, 25, 50, 75, 90, 100}) {
        std::size_t position = (by_distance.size() - 1) * percent / 100;
        int target = by_distance[position];
        DijkstraResult stopped = dijkstra_to(graph, source, target);
        double saved = 100.0 * (1.0 - static_cast<double>(stopped.counts.settled) / whole.counts.settled);
        std::cout << std::setw(6) << percent << " %" << std::setw(9) << stopped.distance[target] << std::setw(9)
                  << stopped.counts.settled << std::fixed << std::setprecision(1) << std::setw(6) << saved << " %"
                  << std::setw(16) << stopped.counts.edges_read << "\n";
    }
    return 0;
}