// Paso 6, opcional: un trie para buscar lugares por prefijo.
// Cada nodo es un prefijo, y sus hijos se indexan por byte. Trabaja con bytes: una letra con tilde son dos
// bytes, y dos niveles del trie.
#ifndef TRIE_H
#define TRIE_H

#include <cstddef>
#include <map>
#include <string>
#include <utility>
#include <vector>

#include "not_implemented.h"

// Invariantes, en un comentario y en check_invariants, como siempre:
// - La raíz es nodes_[0], y todo hijo es un índice válido de nodes_.
// - Cada nodo menos la raíz es hijo de exactamente uno.
// - place_count_ es la cantidad de nodos con place != -1.
// Los nodos viven en un std::vector y se apuntan por índice: no hay new ni delete, y copiar ya funciona.
class PlaceTrie {
public:
    PlaceTrie() : nodes_(1) {}

    // Guarda un lugar con su nodo del mapa. node >= 0. Si el nombre ya estaba, cambia su nodo.
    void insert(const std::string& name, int node) {
        (void)name;
        (void)node;
        not_implemented("PlaceTrie::insert");
    }

    // El nodo del mapa con ese nombre exacto, o -1 si no está.
    int find(const std::string& name) const {
        (void)name;
        not_implemented("PlaceTrie::find");
    }

    // Todos los lugares que empiezan con prefix, en orden de bytes. El prefijo vacío los da todos.
    std::vector<std::pair<std::string, int>> with_prefix(const std::string& prefix) const {
        (void)prefix;
        not_implemented("PlaceTrie::with_prefix");
    }

    std::size_t place_count() const { return place_count_; }
    std::size_t node_count() const { return nodes_.size(); }

    bool check_invariants() const {
        std::vector<int> times_child(nodes_.size(), 0);
        std::size_t places = 0;
        for (const TrieNode& node : nodes_) {
            places += node.place != -1 ? 1 : 0;
            for (const auto& [byte, child] : node.children) {
                if (child <= 0 || static_cast<std::size_t>(child) >= nodes_.size()) {
                    return false;
                }
                times_child[child]++;
            }
        }
        for (std::size_t i = 1; i < nodes_.size(); i++) {
            if (times_child[i] != 1) {
                return false;
            }
        }
        return times_child[0] == 0 && places == place_count_;
    }

private:
    struct TrieNode {
        std::map<unsigned char, int> children;  // sin signo: así el orden es el de bytes
        int place = -1;                         // nodo del mapa, o -1 si aquí no termina ningún nombre
    };

    std::vector<TrieNode> nodes_;
    std::size_t place_count_ = 0;
};

#endif