// BFS sobre los tres mapas. Las lecturas se cuentan; los tiempos dependen de la máquina.
// Compilar con -O2 y sin sanitizers. Uso: bfs_scaling mapa...
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>

#include "bench.h"
#include "map_file.h"
#include "matrix_graph.h"
#include "traversals.h"

namespace {

// BFS sobre la matriz: para saber los vecinos de u hay que leer su fila completa.
std::int64_t matrix_bfs_reads(const MatrixGraph& matrix, int source) {
    int n = matrix.node_count();
    std::vector<int> distance(n, -1);
    std::queue<int> pending;
    std::int64_t reads = 0;
    distance[source] = 0;
    pending.push(source);
    while (!pending.empty()) {
        int u = pending.front();
        pending.pop();
        for (int v = 0; v < n; v++) {
            reads++;
            if (matrix.has_edge(u, v) && distance[v] == -1) {
                distance[v] = distance[u] + 1;
                pending.push(v);
            }
        }
    }
    return reads;
}

}  // namespace

int main(int argc, char* argv[]) {
    const int reps = 11;
    std::cout << "    nodos   aristas  sacados  entradas leidas   ms lista  ns/(V+E)\n";
    for (int i = 1; i < argc; i++) {
        Graph graph = read_map(argv[i]);
        std::int64_t size = graph.node_count() + static_cast<std::int64_t>(graph.edge_count());
        std::int64_t pulled = 0;
        std::int64_t reads = 0;
        double seconds = median_seconds(reps, [&] {
            BfsResult result = bfs(graph, 0);
            pulled = static_cast<std::int64_t>(result.order.size());
            keep(result.distance.back());
        });
        for (int u = 0; u < graph.node_count(); u++) {
            reads += static_cast<std::int64_t>(graph.neighbors(u).size());
        }
        std::cout << std::setw(9) << graph.node_count() << std::setw(10) << graph.edge_count() << std::setw(9) << pulled
                  << std::setw(17) << reads << std::fixed << std::setprecision(3) << std::setw(11) << seconds * 1000
                  << std::setprecision(1) << std::setw(10) << seconds * 1e9 / static_cast<double>(size) << "\n";
        std::cout.unsetf(std::ios::fixed);
        std::cout << std::setprecision(6);
    }

    // La matriz solo con el primer mapa: en lima.txt necesitaría más de 6 GB.
    Graph first = read_map(argv[1]);
    MatrixGraph matrix(first.node_count());
    for (int u = 0; u < first.node_count(); u++) {
        for (const Edge& edge : first.neighbors(u)) {
            if (u < edge.to) {
                matrix.add_edge(u, edge.to);
            }
        }
    }
    std::int64_t matrix_reads = 0;
    double matrix_seconds = median_seconds(reps, [&] { matrix_reads = matrix_bfs_reads(matrix, 0); keep(matrix_reads); });
    double list_seconds = median_seconds(reps, [&] { keep(bfs(first, 0).distance.back()); });
    std::cout << std::fixed << std::setprecision(3);
    std::cout << "matriz en el primer mapa: " << matrix_reads << " celdas leidas, " << matrix_seconds * 1000 << " ms\n";
    std::cout << "listas en el primer mapa: " << list_seconds * 1000 << " ms\n";
    return 0;
}