// Rutas sobre un mapa real. Completen cada función marcada con not_implemented.
#ifndef ROUTES_H
#define ROUTES_H

#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

#include "graph.h"
#include "map_file.h"
#include "min_heap.h"
#include "not_implemented.h"

// 64 bits: dos aristas de 2 000 000 000 ya no caben en un int.
using Meters = std::int64_t;

// Distancia de un nodo al que no se llega.
const Meters UNREACHABLE = std::numeric_limits<Meters>::max();

// Distancia primero: std::pair compara por first y, si empatan, por second. Usen este tipo en los
// heaps: así su MinHeap y std::priority_queue sacan las entradas en el mismo orden.
using HeapEntry = std::pair<Meters, int>;

struct DijkstraCounts {
    std::size_t settled = 0;     // nodos que salieron con su distancia definitiva
    std::size_t pushes = 0;      // entradas que entraron al heap, contando la del origen
    std::size_t stale = 0;       // entradas viejas, ignoradas al sacarlas
    std::size_t edges_read = 0;  // entradas de listas leídas al relajar
    std::size_t scanned = 0;     // solo sin heap: lecturas del arreglo para buscar el menor
};

struct DijkstraResult {
    std::vector<Meters> distance;  // UNREACHABLE si no se llega
    std::vector<int> parent;       // -1 si no se llega, y el origen es su propio padre
    DijkstraCounts counts;
};

// Paso 1: un nodo por cada nodo del archivo, y una arista no dirigida por cada tramo, con sus metros.
inline Graph build_map_graph(const MapFile& map) {
    (void)map;
    not_implemented("build_map_graph");
}

// Paso 2: Dijkstra con su MinHeap, hasta vaciar el heap. Requiere pesos no negativos.
inline DijkstraResult dijkstra(const Graph& graph, int source) {
    (void)graph;
    (void)source;
    not_implemented("dijkstra");
}

// Paso 2: del origen a target, los dos incluidos. Vacío si no se llega. El origen es su propio padre.
inline std::vector<int> route_to(const std::vector<int>& parent, int target) {
    (void)parent;
    (void)target;
    not_implemented("route_to");
}

// Paso 3: suma los pesos de una ruta. Requiere que cada par seguido de la ruta sea una arista.
// Una ruta vacía o de un solo nodo suma 0.
inline Meters route_meters(const Graph& graph, const std::vector<int>& route) {
    (void)graph;
    (void)route;
    not_implemented("route_meters");
}

// Paso 4: igual que dijkstra, pero se detiene al SACAR a target del heap, sin leer su lista. Solo las distancias
// de los nodos sacados quedan definitivas. Si no se llega a target, termina vaciando el heap.
inline DijkstraResult dijkstra_to(const Graph& graph, int source, int target) {
    (void)graph;
    (void)source;
    (void)target;
    not_implemented("dijkstra_to");
}

// Paso 5: igual que dijkstra, con std::priority_queue en vez de su MinHeap. Cuidado con el comparador.
inline DijkstraResult dijkstra_priority_queue(const Graph& graph, int source) {
    (void)graph;
    (void)source;
    not_implemented("dijkstra_priority_queue");
}

// Paso 5: sin heap. En cada vuelta recorre todo el arreglo buscando el nodo sin sacar con menor distancia,
// y cuenta esas lecturas en counts.scanned. Termina cuando no queda ninguno alcanzable.
inline DijkstraResult dijkstra_array(const Graph& graph, int source) {
    (void)graph;
    (void)source;
    not_implemented("dijkstra_array");
}

#endif