// Corre las pruebas de la sesión 1: map_tests <nombre>, o map_tests para ver los nombres.
#include <cassert>
#include <cstring>
#include <iostream>
#include <memory>
#include <string>
#include <type_traits>
#include <vector>

#include "churn_test.h"
#include "hash_map.h"
#include "map_suite.h"
#include "probing_hash_map.h"

namespace {

using Probing = ProbingHashMap<int>;

// Las pruebas de abajo necesitan claves que empiecen en la misma casilla.
std::vector<std::string> colliding_keys(std::size_t capacity, std::size_t count) {
    std::vector<std::string> keys;
    const std::uint64_t target = Probing::hash_of("base") & (capacity - 1);
    for (int i = 0; keys.size() < count; i++) {
        const std::string key = "c" + std::to_string(i);
        if ((Probing::hash_of(key) & (capacity - 1)) == target) {
            keys.push_back(key);
        }
    }
    return keys;
}

void hash_vectors() {
    // Vectores de prueba publicados de FNV-1a de 64 bits.
    assert(Probing::hash_of("") == 0xcbf29ce484222325ULL);
    assert(Probing::hash_of("a") == 0xaf63dc4c8601ec8cULL);
    assert(Probing::hash_of("foobar") == 0x85944171f73967e8ULL);
}

void search_passes_tombstones() {
    // Es el error común de la semana: detenerse en el primer tombstone.
    Probing map;
    map.set_max_load_factor(0.5);
    while (map.capacity() < 64) {
        map.set("x" + std::to_string(map.size()), 0);
    }
    assert(map.capacity() == 64);
    const std::vector<std::string> same = colliding_keys(map.capacity(), 3);
    for (const std::string& key : same) {
        map.set(key, 7);
    }
    assert(map.capacity() == 64);
    assert(map.remove(same[0]));
    assert(map.tombstones() == 1);
    assert(!map.contains(same[0]));
    assert(map.contains(same[1]));
    assert(map.contains(same[2]));
    assert(*map.get(same[2]) == 7);
    assert(map.check_invariants());
}

void set_does_not_duplicate_past_tombstone() {
    // El tombstone va antes que la clave: insertar sin seguir buscando la duplicaría.
    Probing map;
    map.set_max_load_factor(0.5);
    while (map.capacity() < 64) {
        map.set("x" + std::to_string(map.size()), 0);
    }
    const std::vector<std::string> same = colliding_keys(map.capacity(), 3);
    map.set(same[0], 1);
    map.set(same[1], 2);
    map.remove(same[0]);
    const std::size_t before = map.size();
    map.set(same[1], 3);
    assert(map.size() == before);
    assert(*map.get(same[1]) == 3);
    assert(map.remove(same[1]));
    assert(!map.contains(same[1]));
    assert(map.check_invariants());
}

void set_reuses_tombstone() {
    Probing map;
    map.set_max_load_factor(0.5);
    while (map.capacity() < 64) {
        map.set("x" + std::to_string(map.size()), 0);
    }
    const std::vector<std::string> same = colliding_keys(map.capacity(), 2);
    map.set(same[0], 1);
    map.remove(same[0]);
    assert(map.tombstones() == 1);
    map.set(same[1], 2);  // mismo inicio: su búsqueda de lugar pasa por el tombstone
    assert(map.tombstones() == 0);
    assert(*map.get(same[1]) == 2);
    assert(map.check_invariants());
}

void new_table_has_8_slots() {
    assert(Probing().capacity() == 8);
}

void lowering_load_factor_rebuilds() {
    Probing map;
    for (int i = 0; i < 500; i++) {
        map.set(std::to_string(i), i);
    }
    map.set_max_load_factor(0.25);
    assert(static_cast<double>(map.size()) <= 0.25 * static_cast<double>(map.capacity()));
    assert(map.check_invariants());
    for (int i = 0; i < 500; i++) {
        assert(*map.get(std::to_string(i)) == i);
    }
}

void high_load_factor_still_ends() {
    // Con alpha = 0.99 tiene que quedar una casilla vacía, o una búsqueda sin éxito no termina.
    Probing map;
    map.set_max_load_factor(0.99);
    for (int i = 0; i < 3000; i++) {
        map.set(std::to_string(i), i);
    }
    assert(!map.contains("no está"));
    assert(map.check_invariants());
}

void probes_count_the_last_slot() {
    Probing map;
    // En una tabla vacía se revisa una casilla: la vacía donde termina.
    assert(map.probes_for("x") == 1);
    map.set("x", 1);
    assert(map.probes_for("x") == 1);
}

void churn_keeps_probes_low() {
    Probing map;
    for (int i = 0; i < 100; i++) {
        map.set("k" + std::to_string(i), i);
    }
    const std::size_t capacity_before = map.capacity();
    for (int i = 100; i < 50100; i++) {
        map.remove("k" + std::to_string(i - 100));
        map.set("k" + std::to_string(i), i);
    }
    assert(map.size() == 100);
    assert(map.check_invariants());
    // Solo hay 100 claves vivas: la tabla no debe crecer sin límite.
    assert(map.capacity() <= 4 * capacity_before);
    std::size_t total = 0;
    for (int i = 0; i < 1000; i++) {
        total += map.probes_for("ausente" + std::to_string(i));
    }
    assert(total / 1000 < 20);
}

void rebuild_clears_tombstones() {
    Probing map;
    for (int i = 0; i < 100; i++) {
        map.set("k" + std::to_string(i), i);
    }
    std::size_t max_tombstones = 0;
    for (int i = 100; i < 20100; i++) {
        map.remove("k" + std::to_string(i - 100));
        map.set("k" + std::to_string(i), i);
        if (map.tombstones() > max_tombstones) {
            max_tombstones = map.tombstones();
        }
    }
    assert(max_tombstones > 0);
    assert(static_cast<double>(map.size() + max_tombstones) <= 0.7 * static_cast<double>(map.capacity()));
}

void remove_releases_value() {
    ProbingHashMap<std::shared_ptr<int>> map;
    auto value = std::make_shared<int>(5);
    map.set("x", value);
    assert(value.use_count() == 2);
    map.remove("x");
    assert(value.use_count() == 1);
}

void moved_from_is_usable() {
    Probing first;
    first.set("a", 1);
    Probing second(std::move(first));
    assert(first.size() == 0);
    assert(first.capacity() == 0);
    Probing copy_of_empty(first);
    assert(copy_of_empty.capacity() == 0 && copy_of_empty.check_invariants());
    assert(!first.contains("a"));
    assert(!first.remove("a"));
    first.set("b", 2);
    assert(*first.get("b") == 2);
    assert(first.check_invariants());
    static_assert(std::is_nothrow_move_constructible_v<Probing>);
}

void string_values() {
    ProbingHashMap<std::string> map;
    map.set("llave", "valor con un texto bastante largo para reservar memoria");
    map.set("otra", "x");
    assert(*map.get("llave") == "valor con un texto bastante largo para reservar memoria");
    map.remove("llave");
    assert(map.get("llave") == nullptr);
}

struct Test {
    const char* name;
    void (*run)();
};

const Test kTests[] = {
    {"hash_vectors", hash_vectors},
    {"new_is_empty", test_new_is_empty<Probing>},
    {"set_and_get", test_set_and_get<Probing>},
    {"overwrite", test_overwrite<Probing>},
    {"contains", test_contains<Probing>},
    {"remove_present", test_remove_present<Probing>},
    {"remove_absent", test_remove_absent<Probing>},
    {"unusual_keys", test_unusual_keys<Probing>},
    {"growth", test_growth<Probing>},
    {"copy_is_independent", test_copy_is_independent<Probing>},
    {"self_assignment", test_self_assignment<Probing>},
    {"move_leaves_empty_and_usable", test_move_leaves_empty_and_usable<Probing>},
    {"random_small", test_random_small<Probing>},
    {"random_large", test_random_large<Probing>},
    {"new_table_has_8_slots", new_table_has_8_slots},
    {"search_passes_tombstones", search_passes_tombstones},
    {"set_does_not_duplicate_past_tombstone", set_does_not_duplicate_past_tombstone},
    {"set_reuses_tombstone", set_reuses_tombstone},
    {"lowering_load_factor_rebuilds", lowering_load_factor_rebuilds},
    {"high_load_factor_still_ends", high_load_factor_still_ends},
    {"probes_count_the_last_slot", probes_count_the_last_slot},
    {"churn_keeps_probes_low", churn_keeps_probes_low},
    {"rebuild_clears_tombstones", rebuild_clears_tombstones},
    {"remove_releases_value", remove_releases_value},
    {"moved_from_is_usable", moved_from_is_usable},
    {"string_values", string_values},
    {"my_churn_test", my_churn_test},
    {"week7_table_passes_suite", [] { run_map_suite<HashMap<int>>(); }},
    {"fnv1a_of_week7", [] {
         assert(fnv1a("") == 0xcbf29ce484222325ULL);
         assert(fnv1a("foobar") == 0x85944171f73967e8ULL);
     }},
};

}  // namespace

int main(int argc, char** argv) {
    if (argc < 2) {
        for (const Test& test : kTests) {
            std::cout << test.name << "\n";
        }
        return 0;
    }
    for (const Test& test : kTests) {
        if (std::strcmp(test.name, argv[1]) == 0) {
            test.run();
            return 0;
        }
    }
    std::cerr << "no existe la prueba " << argv[1] << "\n";
    return 2;
}