// Tabla hash con encadenamiento que crece. Las claves son std::string.
// Completen cada función que llama a not_written. Lo demás ya está hecho, y conviene leerlo.
// Este archivo no depende de ningún otro de la carpeta: en la semana 9 lo copiarán tal cual.
#ifndef HASH_MAP_H
#define HASH_MAP_H

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <utility>

// Para lo que todavía no escriben: detiene el programa y dice qué falta.
[[noreturn]] inline void not_written(const char* name) {
    std::fprintf(stderr, "sin implementar: %s\n", name);
    std::abort();
}

// FNV-1a de 64 bits, con las constantes de los apuntes. Cuidado: char puede tener signo.
inline std::uint64_t fnv1a(const std::string&) {
    not_written("fnv1a");
}

// Invariantes:
// - capacity_ == 0 si y solo si slots_ es nulo. Solo ocurre en un objeto del que se movió.
// - Si capacity_ > 0, capacity_ es 8 multiplicado por una potencia de 2.
// - Cada nodo de la cadena i cumple fnv1a(key) % capacity_ == i.
// - Una clave aparece en un solo nodo.
// - size_ es el total de nodos, y size_ <= max_load_ * capacity_.
template <typename V>
class HashMap {
public:
    HashMap() : slots_(new Node*[INITIAL_CAPACITY]()), capacity_(INITIAL_CAPACITY) {}

    ~HashMap() { destroy(); }

    HashMap(const HashMap& other)
        : slots_(other.capacity_ == 0 ? nullptr : new Node*[other.capacity_]()),
          capacity_(other.capacity_),
          size_(other.size_),
          max_load_(other.max_load_) {
        for (std::size_t i = 0; i < capacity_; i++) {
            for (Node* node = other.slots_[i]; node != nullptr; node = node->next) {
                slots_[i] = new Node{node->key, node->value, slots_[i]};
            }
        }
    }

    HashMap& operator=(const HashMap& other) {
        HashMap copy(other);
        swap(copy);
        return *this;
    }

    // Al mover, el origen queda vacío y se puede seguir usando, con capacity() == 0.
    HashMap(HashMap&& other) noexcept
        : slots_(std::exchange(other.slots_, nullptr)),
          capacity_(std::exchange(other.capacity_, 0)),
          size_(std::exchange(other.size_, 0)),
          max_load_(other.max_load_) {}

    HashMap& operator=(HashMap&& other) noexcept {
        if (this != &other) {
            destroy();
            slots_ = std::exchange(other.slots_, nullptr);
            capacity_ = std::exchange(other.capacity_, 0);
            size_ = std::exchange(other.size_, 0);
            max_load_ = other.max_load_;
        }
        return *this;
    }

    // Inserta o sobrescribe. Sobrescribir no hace crecer la tabla. Antes de insertar una clave
    // nueva, crece mientras needs_growth(size_ + 1). Inserten el nodo al inicio de su cadena.
    void set(const std::string&, const V&) {
        not_written("set");
    }

    // Puntero al valor, o nullptr si la clave no está.
    const V* get(const std::string&) const {
        not_written("get");
    }

    bool contains(const std::string&) const {
        not_written("contains");
    }

    // Devuelve true si la clave estaba. Cuidado con capacity_ == 0, y con el primer nodo de la cadena.
    bool remove(const std::string&) {
        not_written("remove");
    }

    std::size_t size() const { return size_; }
    std::size_t capacity() const { return capacity_; }

    // Si la tabla ya supera el nuevo máximo, crece de inmediato.
    void set_max_load_factor(double alpha) {
        assert(alpha > 0);
        max_load_ = alpha;
        while (capacity_ > 0 && needs_growth(size_)) {
            grow();
        }
    }

    bool check_invariants() const {
        if ((capacity_ == 0) != (slots_ == nullptr)) {
            return false;
        }
        if (capacity_ != 0 && (capacity_ < INITIAL_CAPACITY || capacity_ % INITIAL_CAPACITY != 0 ||
                               (capacity_ & (capacity_ - 1)) != 0)) {
            return false;
        }
        std::size_t total = 0;
        for (std::size_t i = 0; i < capacity_; i++) {
            for (Node* node = slots_[i]; node != nullptr; node = node->next) {
                total++;
                if (fnv1a(node->key) % capacity_ != i) {
                    return false;
                }
                for (Node* other = node->next; other != nullptr; other = other->next) {
                    if (other->key == node->key) {
                        return false;
                    }
                }
            }
        }
        return total == size_ && static_cast<double>(size_) <= max_load_ * static_cast<double>(capacity_);
    }

private:
    static constexpr std::size_t INITIAL_CAPACITY = 8;

    struct Node {
        std::string key;
        V value;
        Node* next;
    };

    // Con capacity_ == 0 no se puede llamar: sería un resto de la división entre 0.
    std::size_t slot_of(const std::string& key) const {
        return fnv1a(key) % capacity_;
    }

    bool needs_growth(std::size_t new_size) const {
        return capacity_ == 0 || static_cast<double>(new_size) > max_load_ * static_cast<double>(capacity_);
    }

    // El nodo de esta clave, o nullptr. Lo usarán set, get y contains. Debe funcionar con capacity_ == 0.
    Node* find_node(const std::string&) const {
        not_written("find_node");
    }

    // Duplica las casillas, o crea INITIAL_CAPACITY si no hay. Cada nodo vuelve a enlazarse donde le
    // toca con la capacidad nueva, sin crear ni copiar nodos ni valores.
    void grow() {
        not_written("grow");
    }

    void destroy() {
        for (std::size_t i = 0; i < capacity_; i++) {
            Node* node = slots_[i];
            while (node != nullptr) {
                Node* next = node->next;
                delete node;
                node = next;
            }
        }
        delete[] slots_;
    }

    void swap(HashMap& other) noexcept {
        std::swap(slots_, other.slots_);
        std::swap(capacity_, other.capacity_);
        std::swap(size_, other.size_);
        std::swap(max_load_, other.max_load_);
    }

    Node** slots_ = nullptr;
    std::size_t capacity_ = 0;
    std::size_t size_ = 0;
    double max_load_ = 1.0;
};

#endif