// Tabla hash con linear probing y tombstones. Completen cada método marcado con not_implemented.
#ifndef PROBING_HASH_MAP_H
#define PROBING_HASH_MAP_H

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <string>
#include <unordered_set>
#include <utility>

#include "not_implemented.h"

// 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.
// - size_ cuenta las casillas llenas y tombstones_ los tombstones.
// - size_ + tombstones_ <= max_load_ * capacity_, con max_load_ < 1: siempre queda al menos una
//   casilla vacía, y por eso toda búsqueda termina.
// - No hay claves repetidas. Entre la casilla inicial de una clave y la casilla donde está, sin
//   contar esta última, no hay ninguna casilla vacía.
//
// El factor de carga máximo es 0.7 si no se cambia: el 1.0 de la semana 7 no sirve aquí, porque
// una tabla abierta necesita casillas vacías.
//
// V debe tener constructor por defecto, porque el arreglo se reserva con new Slot[]: las
// casillas sin elemento también guardan un V.
template <typename V>
class ProbingHashMap {
public:
    ProbingHashMap() : slots_(new Slot[INITIAL_CAPACITY]), capacity_(INITIAL_CAPACITY) {}

    ~ProbingHashMap() { delete[] slots_; }

    ProbingHashMap(const ProbingHashMap& other)
        : slots_(other.capacity_ == 0 ? nullptr : new Slot[other.capacity_]),
          capacity_(other.capacity_), size_(other.size_),
          tombstones_(other.tombstones_), max_load_(other.max_load_) {
        for (std::size_t i = 0; i < capacity_; i++) {
            slots_[i] = other.slots_[i];
        }
    }

    ProbingHashMap(ProbingHashMap&& other) noexcept
        : slots_(other.slots_), capacity_(other.capacity_), size_(other.size_),
          tombstones_(other.tombstones_), max_load_(other.max_load_) {
        // Como en la semana 7, el origen queda vacío y usable, con capacity() == 0, sin reservar
        // memoria: por eso puede ser noexcept.
        other.slots_ = nullptr;
        other.capacity_ = 0;
        other.size_ = 0;
        other.tombstones_ = 0;
    }

    // Se recibe por valor: sirve para copiar y para mover, y cubre la autoasignación.
    ProbingHashMap& operator=(ProbingHashMap other) noexcept {
        std::swap(slots_, other.slots_);
        std::swap(capacity_, other.capacity_);
        std::swap(size_, other.size_);
        std::swap(tombstones_, other.tombstones_);
        std::swap(max_load_, other.max_load_);
        return *this;
    }

    // Inserta la clave, o reemplaza su valor si ya está.
    //   1. Recorran desde home(key) hasta encontrar la clave (se reemplaza y se termina) o una
    //      casilla vacía. Recuerden el primer tombstone que vean, sin detenerse en él.
    //   2. Si la clave no estaba y vieron un tombstone, reúsenlo: no sube size_ + tombstones_.
    //   3. Si no, y size_ + tombstones_ + 1 pasa del límite, llamen a rebuild_for(size_ + 1) y
    //      vuelvan a buscar una casilla vacía, porque la tabla cambió.
    //   4. Usen la casilla vacía.
    // Una tabla movida tiene capacity_ == 0: antes de todo, si es el caso, llamen a rebuild_for.
    void set(const std::string& key, const V& value) {
        (void)key;
        (void)value;
        not_implemented("ProbingHashMap::set");
    }

    // nullptr si la clave no está. Recuerden: se busca hasta la primera casilla VACÍA.
    const V* get(const std::string& key) const {
        (void)key;
        not_implemented("ProbingHashMap::get");
    }

    bool contains(const std::string& key) const {
        (void)key;
        not_implemented("ProbingHashMap::contains");
    }

    // Deja un tombstone, y limpien la clave y el valor para soltar lo que tengan reservado:
    // slot.key = std::string{}; slot.value = V{};
    bool remove(const std::string& key) {
        (void)key;
        not_implemented("ProbingHashMap::remove");
    }

    // Solo de esta tabla: cuántas casillas revisa buscar esta clave, contando la última, que es
    // aquella donde está la clave o la vacía donde termina la búsqueda. En una tabla movida, 0.
    std::size_t probes_for(const std::string& key) const {
        (void)key;
        not_implemented("ProbingHashMap::probes_for");
    }

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

    // Solo de esta tabla: cuántos tombstones hay ahora.
    std::size_t tombstones() const { return tombstones_; }

    bool check_invariants() const {
        if ((capacity_ == 0) != (slots_ == nullptr)) {
            return false;
        }
        if (capacity_ == 0) {
            return size_ == 0 && tombstones_ == 0;
        }
        if (capacity_ < INITIAL_CAPACITY || (capacity_ & (capacity_ - 1)) != 0 || !(max_load_ < 1.0)) {
            return false;
        }
        if (static_cast<double>(size_ + tombstones_) > max_load_ * static_cast<double>(capacity_)) {
            return false;
        }
        std::unordered_set<std::string> seen;
        std::size_t full = 0;
        std::size_t dead = 0;
        for (std::size_t i = 0; i < capacity_; i++) {
            if (slots_[i].state == State::tombstone) {
                dead++;
            } else if (slots_[i].state == State::full) {
                full++;
                if (!seen.insert(slots_[i].key).second) {
                    return false;
                }
                // Desde su casilla inicial hasta aquí no puede haber una vacía.
                for (std::size_t j = home(slots_[i].key); j != i; j = (j + 1) & (capacity_ - 1)) {
                    if (slots_[j].state == State::empty) {
                        return false;
                    }
                }
            }
        }
        return full == size_ && dead == tombstones_ && size_ + tombstones_ < capacity_;
    }

    // alpha debe estar entre 0 y 1, sin incluirlos: con alpha = 1 la tabla podría llenarse y una
    // búsqueda sin éxito no terminaría. Si la tabla ya no cumple el límite, crece de inmediato.
    void set_max_load_factor(double alpha) {
        assert(alpha > 0.0 && alpha < 1.0);
        max_load_ = alpha;
        if (capacity_ > 0 && used_limit_exceeded(size_ + tombstones_)) {
            rebuild_for(size_);
        }
    }

    // FNV-1a de 64 bits. Está dentro de la clase porque el corrector incluye esta tabla y la de la
    // semana 7, y esa ya define una función libre llamada fnv1a.
    static std::uint64_t hash_of(const std::string& key) {
        std::uint64_t hash = 14695981039346656037ULL;
        for (char c : key) {
            hash ^= static_cast<unsigned char>(c);
            hash *= 1099511628211ULL;
        }
        return hash;
    }

private:
    enum class State : unsigned char { empty, full, tombstone };

    struct Slot {
        State state = State::empty;
        std::string key;
        V value{};
    };

    static constexpr std::size_t INITIAL_CAPACITY = 8;

    // Casilla donde empieza el probing de una clave. La capacidad es potencia de 2.
    std::size_t home(const std::string& key) const {
        return hash_of(key) & (capacity_ - 1);
    }

    bool used_limit_exceeded(std::size_t used) const {
        return static_cast<double>(used) > max_load_ * static_cast<double>(capacity_);
    }

    // Pasa las claves a un arreglo nuevo, sin tombstones, donde caben `needed` claves.
    // Empiecen de la capacidad actual, o de INITIAL_CAPACITY si es menor. Si needed es como mucho
    // la mitad del límite (max_load_ * capacidad / 2), la capacidad no cambia: casi todo lo que
    // ocupaba la tabla eran tombstones, y reconstruir los limpia. Si no, dupliquen, y sigan
    // duplicando mientras needed no quepa en el límite. Reserven con new Slot[nueva], reinserten
    // solo las casillas llenas, liberen el arreglo viejo y dejen tombstones_ en 0.
    void rebuild_for(std::size_t needed) {
        (void)needed;
        not_implemented("ProbingHashMap::rebuild_for");
    }

    Slot* slots_;
    std::size_t capacity_;
    std::size_t size_ = 0;
    std::size_t tombstones_ = 0;
    double max_load_ = 0.7;
};

#endif