// Memoria y costo de consulta de las dos representaciones, con 1000 nodos y 3000 aristas.
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <utility>
#include <vector>

#include "graph.h"
#include "map_file.h"
#include "matrix_graph.h"

int main() {
    const int nodes = 1000;
    const std::size_t edges = 3000;
    Graph lists(nodes);
    MatrixGraph matrix(nodes);
    std::set<std::pair<int, int>> seen;
    std::mt19937 rng(14);
    while (seen.size() < edges) {
        int u = static_cast<int>(rng() % nodes);
        int v = static_cast<int>(rng() % nodes);
        if (u > v) {
            std::swap(u, v);
        }
        if (u != v && seen.insert({u, v}).second) {
            lists.add_edge(u, v);
            matrix.add_edge(u, v);
        }
    }

    std::size_t entries = 0;
    std::size_t capacity = 0;
    std::size_t longest = 0;
    for (int u = 0; u < nodes; u++) {
        entries += lists.neighbors(u).size();
        capacity += lists.neighbors(u).capacity();
        longest = std::max(longest, lists.neighbors(u).size());
    }
    std::cout << "nodos: " << nodes << ", aristas: " << edges << "\n";
    std::cout << "sizeof(std::vector<Edge>): " << sizeof(std::vector<Edge>)
              << ", sizeof(Edge): " << sizeof(Edge) << "\n";
    std::cout << "matriz, bytes: " << matrix.bytes() << "\n";
    std::cout << "listas, entradas: " << entries << ", capacidad reservada: " << capacity << "\n";
    std::cout << "listas, bytes: " << list_bytes(lists) << "\n";
    std::cout << "lista mas larga: " << longest << "\n";

    // Celdas leídas por cada pregunta, sin contar la lectura de la lista.
    std::int64_t list_reads = 0;
    std::int64_t matrix_reads = 0;
    std::int64_t found = 0;
    for (int u = 0; u < nodes; u++) {
        for (int v = 0; v < nodes; v++) {
            matrix_reads++;
            bool in_matrix = matrix.has_edge(u, v);
            bool in_lists = false;
            for (const Edge& edge : lists.neighbors(u)) {
                list_reads++;
                if (edge.to == v) {
                    in_lists = true;
                    break;
                }
            }
            if (in_matrix != in_lists) {
                std::cout << "no coinciden\n";
                return 1;
            }
            found += in_lists ? 1 : 0;
        }
    }
    std::cout << "preguntas has_edge: " << matrix_reads << ", respuestas si: " << found << "\n";
    std::cout << "lecturas por pregunta, matriz: 1.00, listas: " << static_cast<double>(list_reads) / matrix_reads << "\n";

    // Recorrer los vecinos de todos los nodos.
    std::cout << "recorrer todos los vecinos, matriz: " << static_cast<std::int64_t>(nodes) * nodes
              << " lecturas, listas: " << entries << " lecturas\n";
    return 0;
}