// Pruebas del laboratorio. Uso: lab_tests nombre_de_prueba terminos_chicos.tsv terminos.tsv
// Cada prueba corre sola, en su propio proceso. Nunca miden tiempos: cuentan.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstring>
#include <functional>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>

#include "autocomplete.h"
#include "fixed_pivot.h"
#include "sorts.h"
#include "tracked.h"

namespace {

std::string fixture_path;
std::string data_path;

using IntSort = void (*)(std::vector<int>&);

void by_merge(std::vector<int>& items) {
    merge_sort(items, [](int a, int b) { return a < b; });
}

void by_quick(std::vector<int>& items) {
    quick_sort(items, [](int a, int b) { return a < b; });
}

void check_sorts(IntSort sort, const std::vector<int>& input) {
    std::vector<int> expected = input;
    std::sort(expected.begin(), expected.end());
    std::vector<int> items = input;
    sort(items);
    assert(items == expected);
}

void small_cases(IntSort sort) {
    check_sorts(sort, {});
    check_sorts(sort, {1});
    check_sorts(sort, {2, 1});
    check_sorts(sort, {1, 2});
    check_sorts(sort, {3, 3, 3});
    check_sorts(sort, {5, 2, 8, 1, 9, 3, 7, 4});
    check_sorts(sort, {3, 5, 3, 1, 3, 2, 5, 3});
}

std::vector<int> random_ints(std::mt19937& rng, std::size_t n, unsigned range) {
    std::vector<int> items(n);
    for (int& value : items) {
        value = static_cast<int>(rng() % range) - static_cast<int>(range / 2);
    }
    return items;
}

void random_cases(IntSort sort) {
    std::mt19937 rng(2026);
    for (int round = 0; round < 400; round++) {
        std::size_t n = rng() % 300;
        unsigned range = round % 2 == 0 ? 1000000 : 1 + rng() % 8;
        check_sorts(sort, random_ints(rng, n, range));
    }
}

std::vector<std::string> random_strings(std::mt19937& rng, std::size_t n) {
    const std::vector<std::string> letters = {"a", "b", "z", "á", "ñ", "ú", "ca", "cá"};
    std::vector<std::string> words(n);
    for (std::string& word : words) {
        std::size_t length = rng() % 5;
        for (std::size_t i = 0; i < length; i++) {
            word += letters[rng() % letters.size()];
        }
    }
    return words;
}

template <typename Sort>
void strings_like_the_library(Sort sort) {
    std::mt19937 rng(2026);
    for (int round = 0; round < 100; round++) {
        std::vector<std::string> words = random_strings(rng, rng() % 300);
        std::vector<std::string> expected = words;
        std::sort(expected.begin(), expected.end());
        sort(words);
        assert(words == expected);
    }
}

// ---------- sesión 1 ----------

void test_merge_small() {
    small_cases(by_merge);
}

void test_merge_random() {
    random_cases(by_merge);
}

void test_merge_strings() {
    strings_like_the_library([](std::vector<std::string>& words) {
        merge_sort(words, [](const std::string& a, const std::string& b) { return a < b; });
    });
}

void test_merge_uses_comparator() {
    std::vector<int> items = {1, 4, 2, 5, 3};
    merge_sort(items, std::greater<int>());
    assert((items == std::vector<int>{5, 4, 3, 2, 1}));
}

void test_merge_is_stable() {
    std::mt19937 rng(2026);
    std::vector<std::pair<int, int>> items;
    for (int i = 0; i < 5000; i++) {
        items.push_back({static_cast<int>(rng() % 20), i});
    }
    merge_sort(items, [](const auto& a, const auto& b) { return a.first < b.first; });
    for (std::size_t i = 1; i < items.size(); i++) {
        assert(items[i - 1].first <= items[i].first);
        if (items[i - 1].first == items[i].first) {
            assert(items[i - 1].second < items[i].second);
        }
    }
}

void test_merge_does_not_copy() {
    std::vector<Tracked> items;
    for (int i = 0; i < 1000; i++) {
        items.emplace_back((i * 7919) % 1000);
    }
    Tracked::copies() = 0;
    merge_sort(items, [](const Tracked& a, const Tracked& b) { return a.value() < b.value(); });
    assert(Tracked::copies() == 0);
    for (int i = 0; i < 1000; i++) {
        assert(items[static_cast<std::size_t>(i)].value() == i);
    }
}

void test_merge_counts() {
    for (int k = 1; k <= 14; k++) {
        std::size_t n = std::size_t{1} << k;
        std::mt19937 rng(static_cast<unsigned>(k));
        std::vector<int> items = random_ints(rng, n, 1000000);
        long long comparisons = 0;
        merge_sort(items, [&comparisons](int a, int b) {
            comparisons++;
            return a < b;
        });
        assert(comparisons <= static_cast<long long>(n) * k);
    }
}

void test_quick_small() {
    small_cases(by_quick);
}

void test_quick_random() {
    random_cases(by_quick);
}

void test_quick_strings() {
    strings_like_the_library([](std::vector<std::string>& words) {
        quick_sort(words, [](const std::string& a, const std::string& b) { return a < b; });
    });
}

void test_quick_uses_comparator() {
    std::vector<int> items = {1, 4, 2, 5, 3};
    quick_sort(items, std::greater<int>());
    assert((items == std::vector<int>{5, 4, 3, 2, 1}));
}

long long quick_count(std::vector<int> items) {
    long long comparisons = 0;
    quick_sort(items, [&comparisons](int a, int b) {
        comparisons++;
        return a < b;
    });
    assert(std::is_sorted(items.begin(), items.end()));
    return comparisons;
}

void test_quick_sorted_input_is_fast() {
    const long long n = 1 << 14;
    std::vector<int> items(static_cast<std::size_t>(n));
    for (long long i = 0; i < n; i++) {
        items[static_cast<std::size_t>(i)] = static_cast<int>(i);
    }
    // Un pivote fijo haría n(n-1)/2, unas 134 millones. Esto es mucho menos de eso.
    assert(quick_count(items) < 6 * n * 14);
    std::reverse(items.begin(), items.end());
    assert(quick_count(items) < 6 * n * 14);
}

void test_quick_all_equal_is_one_pass() {
    const std::size_t n = 5000;
    assert(quick_count(std::vector<int>(n, 7)) <= 2 * static_cast<long long>(n));
}

void test_quick_few_values_is_linear() {
    std::mt19937 rng(2026);
    const std::size_t n = 5000;
    // Con 3 valores: pocas pasadas, sin importar n.
    assert(quick_count(random_ints(rng, n, 3)) <= 8 * static_cast<long long>(n));
}

void test_quick_copies_only_pivots() {
    std::vector<Tracked> items;
    for (int i = 0; i < 1000; i++) {
        items.emplace_back((i * 7919) % 1000);
    }
    Tracked::copies() = 0;
    quick_sort(items, [](const Tracked& a, const Tracked& b) { return a.value() < b.value(); });
    assert(Tracked::copies() <= 1000);
    for (int i = 0; i < 1000; i++) {
        assert(items[static_cast<std::size_t>(i)].value() == i);
    }
}

void test_slow_input_is_slow() {
    const std::size_t n = 2000;
    std::vector<int> items = slow_input(n);
    assert(items.size() == n);
    long long comparisons = 0;
    quick_sort_first(items, [&comparisons](int a, int b) {
        comparisons++;
        return a < b;
    });
    assert(std::is_sorted(items.begin(), items.end()));
    assert(comparisons >= static_cast<long long>(n * n / 4));
}

// ---------- sesión 2 ----------

// Un arreglo de términos que cuenta las lecturas.
class CountingTerms {
public:
    explicit CountingTerms(const std::vector<Term>& terms) : terms_(terms) {}
    std::size_t size() const { return terms_.size(); }
    const Term& operator[](std::size_t i) const {
        reads_++;
        return terms_[i];
    }
    long long reads() const { return reads_; }

private:
    const std::vector<Term>& terms_;
    mutable long long reads_ = 0;
};

std::vector<Term> load_sorted(const std::string& path) {
    std::vector<Term> terms;
    bool ok = load_terms(path, terms);
    assert(ok);
    sort_by_text(terms);
    return terms;
}

std::vector<std::string> texts(const std::vector<Term>& terms) {
    std::vector<std::string> result;
    for (const Term& term : terms) {
        result.push_back(term.text);
    }
    return result;
}

std::vector<std::string> range_texts(const std::vector<Term>& terms, Range range) {
    assert(range.first <= range.last && range.last <= terms.size());
    std::vector<std::string> result;
    for (std::size_t i = range.first; i < range.last; i++) {
        result.push_back(terms[i].text);
    }
    return result;
}

using Words = std::vector<std::string>;

// El oráculo: revisar todo, con starts_with.
Range oracle_range(const std::vector<Term>& terms, const std::string& prefix) {
    std::size_t first = terms.size();
    std::size_t count = 0;
    for (std::size_t i = 0; i < terms.size(); i++) {
        if (terms[i].text.starts_with(prefix)) {
            first = std::min(first, i);
            count++;
        }
    }
    if (count == 0) {
        first = 0;
        while (first < terms.size() && terms[first].text < prefix) {
            first++;
        }
    }
    return Range{first, first + count};
}

void test_sort_is_byte_order() {
    std::vector<Term> terms = load_sorted(fixture_path);
    assert((texts(terms) == Words{"a", "az", "año", "aún", "ca", "cama", "casa", "cazar", "caña", "cañón",
                                  "cuna", "cámara", "cé", "de", "debe", "débil", "zapato", "zorro", "árbol",
                                  "ñandú"}));
}

void test_sort_real_file() {
    std::vector<Term> terms = load_sorted(data_path);
    assert(terms.size() == 28039);
    std::vector<std::string> expected = texts(terms);
    std::sort(expected.begin(), expected.end());
    assert(texts(terms) == expected);
    assert(terms[0].text == "a");
    assert(terms.back().text == "útilmente");
}

void test_prefix_ascii() {
    std::vector<Term> terms = load_sorted(fixture_path);
    assert((range_texts(terms, prefix_range(terms, "ca")) == Words{"ca", "cama", "casa", "cazar", "caña", "cañón"}));
    assert((range_texts(terms, prefix_range(terms, "cu")) == Words{"cuna"}));
    assert((range_texts(terms, prefix_range(terms, "z")) == Words{"zapato", "zorro"}));
}

void test_prefix_whole_term_is_included() {
    std::vector<Term> terms = load_sorted(fixture_path);
    assert((range_texts(terms, prefix_range(terms, "de")) == Words{"de", "debe"}));
    assert((range_texts(terms, prefix_range(terms, "zorro")) == Words{"zorro"}));
    assert((range_texts(terms, prefix_range(terms, "a")) == Words{"a", "az", "año", "aún"}));
}

void test_prefix_accents_are_other_bytes() {
    std::vector<Term> terms = load_sorted(fixture_path);
    // cámara no empieza con ca, y sí con cá. Lo mismo árbol con a.
    assert((range_texts(terms, prefix_range(terms, "cá")) == Words{"cámara"}));
    assert((range_texts(terms, prefix_range(terms, "á")) == Words{"árbol"}));
    assert((range_texts(terms, prefix_range(terms, "ñ")) == Words{"ñandú"}));
    // ñ va después de todas las letras sin tilde.
    assert((range_texts(terms, prefix_range(terms, "cañ")) == Words{"caña", "cañón"}));
    assert((range_texts(terms, prefix_range(terms, "añ")) == Words{"año"}));
}

void test_prefix_empty_is_everything() {
    std::vector<Term> terms = load_sorted(fixture_path);
    Range range = prefix_range(terms, "");
    assert(range.first == 0 && range.last == terms.size());
    std::vector<Term> none;
    Range nothing = prefix_range(none, "");
    assert(nothing.first == 0 && nothing.last == 0);
    Range also_nothing = prefix_range(none, "a");
    assert(also_nothing.first == 0 && also_nothing.last == 0);
}

void test_prefix_absent() {
    std::vector<Term> terms = load_sorted(fixture_path);
    struct Case {
        std::string prefix;
        std::size_t where;
    };
    for (const Case& absent : {Case{"0", 0}, Case{"b", 4}, Case{"caz0", 7}, Case{"zz", 18}, Case{"úa", 20}}) {
        Range range = prefix_range(terms, absent.prefix);
        assert(range.first == range.last);
        assert(range.first == absent.where);
    }
}

void test_prefix_extreme_bytes() {
    std::vector<Term> terms = load_sorted(fixture_path);
    // Un prefijo cortado en medio de una letra de dos bytes se trata como bytes.
    assert((range_texts(terms, prefix_range(terms, std::string("c\xC3"))) == Words{"cámara", "cé"}));
    assert((range_texts(terms, prefix_range(terms, std::string("\xC3"))) == Words{"árbol", "ñandú"}));
    // 0xFF no aparece en UTF-8: el rango queda vacío y al final. Sumarle 1 a ese byte falla.
    Range range = prefix_range(terms, std::string("\xFF"));
    assert(range.first == terms.size() && range.last == terms.size());
    std::vector<Term> with_high = {{"a", 1}, {std::string("a\xFF"), 1}, {std::string("a\xFF\xFF"), 1}, {"b", 1}};
    Range high = prefix_range(with_high, std::string("a\xFF"));
    assert(high.first == 1 && high.last == 3);
}

void test_prefix_real_counts() {
    std::vector<Term> terms = load_sorted(data_path);
    struct Case {
        std::string prefix;
        std::size_t count;
    };
    for (const Case& known : {Case{"", 28039}, Case{"a", 3471}, Case{"á", 41}, Case{"c", 3290}, Case{"ca", 819},
                              Case{"cá", 21}, Case{"cañ", 12}, Case{"de", 1474}, Case{"qu", 335}, Case{"ñ", 3},
                              Case{"z", 100}, Case{"zzz", 0}}) {
        Range range = prefix_range(terms, known.prefix);
        assert(range.last - range.first == known.count);
        for (std::size_t i = range.first; i < range.last; i++) {
            assert(terms[i].text.starts_with(known.prefix));
        }
    }
}

void test_prefix_matches_oracle() {
    std::vector<Term> terms = load_sorted(data_path);
    std::mt19937 rng(2026);
    for (int round = 0; round < 80; round++) {
        const std::string& text = terms[rng() % terms.size()].text;
        std::size_t length = rng() % (text.size() + 1);
        // Corta por bytes, a veces en medio de una letra.
        std::string prefix = text.substr(0, length);
        Range range = prefix_range(terms, prefix);
        Range expected = oracle_range(terms, prefix);
        assert(range.first == expected.first && range.last == expected.last);
    }
}

void test_prefix_reads_few_terms() {
    std::vector<Term> terms = load_sorted(data_path);
    CountingTerms counting(terms);
    for (const char* prefix : {"", "a", "ca", "cañ", "de", "zzz", "á", "ñ", "útil"}) {
        long long before = counting.reads();
        prefix_range(counting, prefix);
        // log2(28039) < 15. Dos búsquedas leen a lo sumo 2 * 16 términos, y esto da margen.
        assert(counting.reads() - before <= 40);
    }
}

void test_top_k_order_and_ties() {
    std::vector<Term> terms = load_sorted(fixture_path);
    Range ca = prefix_range(terms, "ca");
    assert((texts(top_k(terms, ca, 3)) == Words{"cama", "casa", "caña"}));
    assert((texts(top_k(terms, ca, 6)) == Words{"cama", "casa", "caña", "cañón", "cazar", "ca"}));
}

void test_top_k_edges() {
    std::vector<Term> terms = load_sorted(fixture_path);
    Range ca = prefix_range(terms, "ca");
    assert(top_k(terms, ca, 0).empty());
    assert(top_k(terms, ca, 100).size() == 6);
    assert(top_k(terms, ca, 5).size() == 5);
    assert(top_k(terms, ca, 6).size() == 6);
    assert(top_k_scan(terms, "ca", 5).size() == 5);
    assert(top_k(terms, Range{3, 3}, 5).empty());
    assert(top_k_scan(terms, "ca", 0).empty());
    assert(top_k_scan(terms, "zzz", 5).empty());
    assert(top_k_scan(terms, "ca", 100).size() == 6);
    std::vector<Term> all_of_them = top_k(terms, prefix_range(terms, ""), 100);
    assert(all_of_them.size() == terms.size());
    assert(terms[0].text == "a");  // top_k no cambia el arreglo
}

void test_top_k_keeps_weights() {
    std::vector<Term> terms = load_sorted(fixture_path);
    std::vector<Term> best = top_k(terms, prefix_range(terms, "cá"), 1);
    assert(best.size() == 1 && best[0].text == "cámara" && best[0].weight == 40);
}

void test_top_k_real_file_order() {
    // terminos.tsv está por frecuencia descendente, con los empates por bytes. Una vez ordenado
    // por texto, pedir todos los términos debe reconstruir el archivo línea por línea.
    std::vector<Term> file_order;
    bool ok = load_terms(data_path, file_order);
    assert(ok);
    std::vector<Term> terms = file_order;
    sort_by_text(terms);
    std::vector<Term> best = top_k(terms, prefix_range(terms, ""), terms.size());
    assert(texts(best) == texts(file_order));
}

void test_top_k_matches_scan() {
    std::vector<Term> terms = load_sorted(data_path);
    std::mt19937 rng(2026);
    for (int round = 0; round < 60; round++) {
        const std::string& text = terms[rng() % terms.size()].text;
        std::string prefix = text.substr(0, rng() % (text.size() + 1));
        std::size_t k = rng() % 12;
        std::vector<Term> fast = top_k(terms, prefix_range(terms, prefix), k);
        std::vector<Term> slow = top_k_scan(terms, prefix, k);
        assert(texts(fast) == texts(slow));
    }
}

void test_top_k_reads_only_the_range() {
    std::vector<Term> terms = load_sorted(data_path);
    Range range = prefix_range(terms, "ca");
    CountingTerms counting(terms);
    top_k(counting, range, 5);
    long long size = static_cast<long long>(range.last - range.first);
    assert(counting.reads() >= size);
    assert(counting.reads() <= 2 * size);
}

void test_scan_reads_the_whole_file() {
    std::vector<Term> terms = load_sorted(data_path);
    for (const char* prefix : {"", "a", "zzz"}) {
        CountingTerms counting(terms);
        top_k_scan(counting, prefix, 1);
        assert(counting.reads() >= static_cast<long long>(terms.size()));
    }
}

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

const std::vector<Test> ALL_TESTS = {
    {"merge_small", test_merge_small},
    {"merge_random", test_merge_random},
    {"merge_strings", test_merge_strings},
    {"merge_uses_comparator", test_merge_uses_comparator},
    {"merge_is_stable", test_merge_is_stable},
    {"merge_does_not_copy", test_merge_does_not_copy},
    {"merge_counts", test_merge_counts},
    {"quick_small", test_quick_small},
    {"quick_random", test_quick_random},
    {"quick_strings", test_quick_strings},
    {"quick_uses_comparator", test_quick_uses_comparator},
    {"quick_sorted_input_is_fast", test_quick_sorted_input_is_fast},
    {"quick_all_equal_is_one_pass", test_quick_all_equal_is_one_pass},
    {"quick_few_values_is_linear", test_quick_few_values_is_linear},
    {"quick_copies_only_pivots", test_quick_copies_only_pivots},
    {"slow_input_is_slow", test_slow_input_is_slow},
    {"sort_is_byte_order", test_sort_is_byte_order},
    {"sort_real_file", test_sort_real_file},
    {"prefix_ascii", test_prefix_ascii},
    {"prefix_whole_term_is_included", test_prefix_whole_term_is_included},
    {"prefix_accents_are_other_bytes", test_prefix_accents_are_other_bytes},
    {"prefix_empty_is_everything", test_prefix_empty_is_everything},
    {"prefix_absent", test_prefix_absent},
    {"prefix_extreme_bytes", test_prefix_extreme_bytes},
    {"prefix_real_counts", test_prefix_real_counts},
    {"prefix_matches_oracle", test_prefix_matches_oracle},
    {"prefix_reads_few_terms", test_prefix_reads_few_terms},
    {"top_k_order_and_ties", test_top_k_order_and_ties},
    {"top_k_edges", test_top_k_edges},
    {"top_k_keeps_weights", test_top_k_keeps_weights},
    {"top_k_real_file_order", test_top_k_real_file_order},
    {"top_k_matches_scan", test_top_k_matches_scan},
    {"top_k_reads_only_the_range", test_top_k_reads_only_the_range},
    {"scan_reads_the_whole_file", test_scan_reads_the_whole_file},
};

}  // namespace

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cerr << "uso: lab_tests nombre_de_prueba terminos_chicos.tsv terminos.tsv\n";
        return 2;
    }
    fixture_path = argv[2];
    data_path = argv[3];
    for (const Test& test : ALL_TESTS) {
        if (std::strcmp(test.name, argv[1]) == 0) {
            test.run();
            return 0;
        }
    }
    std::cerr << "no existe la prueba " << argv[1] << "\n";
    return 2;
}