// Pruebas del paso 6, que es opcional. Se corre una por proceso: optional_tests nombre carpeta_de_pruebas.
#include <algorithm>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "bloom.h"
#include "trie.h"

namespace {

std::string tests_dir;

std::vector<std::string> sample_words() {
    std::ifstream file(tests_dir + "/fixtures/palabras_muestra.txt");
    std::vector<std::string> words;
    std::string word;
    while (file >> word) {
        words.push_back(word);
    }
    assert(words.size() > 1000);
    return words;
}

// ---------- Trie ----------

void trie_insert_and_find() {
    PlaceTrie trie;
    assert(trie.find("Larco") == -1);
    assert(trie.find("") == -1);
    trie.insert("Larco", 38);
    trie.insert("Lar", 7);
    trie.insert("Lima", 9);
    assert(trie.find("Larco") == 38);
    assert(trie.find("Lar") == 7);
    assert(trie.find("La") == -1);
    assert(trie.find("Larcomar") == -1);
    assert(trie.place_count() == 3);
    trie.insert("Lar", 8);
    assert(trie.find("Lar") == 8);
    assert(trie.place_count() == 3);
    assert(trie.check_invariants());
}

void trie_shares_prefixes() {
    PlaceTrie trie;
    trie.insert("ab", 1);
    trie.insert("abc", 2);
    trie.insert("abd", 3);
    assert(trie.node_count() == 5);  // raíz, a, ab, abc, abd
    assert(trie.check_invariants());
}

void trie_prefix_in_byte_order() {
    PlaceTrie trie;
    trie.insert("cazo", 1);
    trie.insert("cañón", 2);
    trie.insert("ca", 3);
    trie.insert("caña", 4);
    trie.insert("cámara", 5);
    trie.insert("dos", 6);
    std::vector<std::pair<std::string, int>> expected{{"ca", 3}, {"cazo", 1}, {"caña", 4}, {"cañón", 2}};
    assert(trie.with_prefix("ca") == expected);
    assert(trie.with_prefix("zzz").empty());
    assert(trie.with_prefix("").size() == 6);
    std::vector<std::pair<std::string, int>> accented{{"cámara", 5}};
    assert(trie.with_prefix("cá") == accented);
}

void trie_random_against_map() {
    std::vector<std::string> words = sample_words();
    std::map<std::string, int> model;
    PlaceTrie trie;
    for (std::size_t i = 0; i < words.size(); i++) {
        trie.insert(words[i], static_cast<int>(i));
        model[words[i]] = static_cast<int>(i);
    }
    assert(trie.check_invariants());
    assert(trie.place_count() == model.size());
    std::mt19937 random(150);
    for (int round = 0; round < 200; round++) {
        const std::string& word = words[random() % words.size()];
        std::string prefix = word.substr(0, random() % (word.size() + 1));
        std::vector<std::pair<std::string, int>> expected;
        for (auto it = model.lower_bound(prefix); it != model.end() && it->first.compare(0, prefix.size(), prefix) == 0; ++it) {
            expected.push_back(*it);
        }
        assert(trie.with_prefix(prefix) == expected);
        assert(trie.find(word) == model[word]);
    }
}

// ---------- Filtro de Bloom ----------

void bloom_sets_the_right_bits() {
    BloomFilter filter(1009, 3);
    assert(filter.bits_on() == 0);
    assert(!filter.possibly_contains("lima"));
    filter.add("lima");
    std::set<std::size_t> positions;
    for (int i = 0; i < 3; i++) {
        positions.insert(bloom_position("lima", i, 1009));
    }
    assert(filter.bits_on() == positions.size());
    assert(filter.possibly_contains("lima"));
    filter.add("lima");
    assert(filter.bits_on() == positions.size());
}

void bloom_no_false_negatives() {
    std::vector<std::string> words = sample_words();
    for (std::size_t bits : {64, 1000, 20000}) {
        BloomFilter filter(bits, 4);
        for (const std::string& word : words) {
            filter.add(word);
        }
        for (const std::string& word : words) {
            assert(filter.possibly_contains(word));
        }
    }
}

// Agrega las líneas pares y pregunta por las impares, que no están.
std::size_t false_positives(const std::vector<std::string>& words, std::size_t bits, int k) {
    BloomFilter filter(bits, k);
    for (std::size_t i = 0; i < words.size(); i += 2) {
        filter.add(words[i]);
    }
    std::size_t positives = 0;
    for (std::size_t i = 1; i < words.size(); i += 2) {
        positives += filter.possibly_contains(words[i]) ? 1 : 0;
    }
    return positives;
}

void bloom_false_positives_fall_with_size() {
    std::vector<std::string> words = sample_words();
    std::size_t keys = words.size() / 2;
    std::size_t small = false_positives(words, keys * 2, 1);
    std::size_t large = false_positives(words, keys * 16, 1);
    assert(large < small);
    assert(small > 0);
    assert(false_positives(words, keys * 32, 5) <= keys / 50);
}

void bloom_uses_all_hashes() {
    BloomFilter one(100000, 1);
    BloomFilter five(100000, 5);
    one.add("lima");
    five.add("lima");
    assert(one.bits_on() == 1);
    assert(five.bits_on() == 5);
    assert(five.hash_count() == 5);
    assert(five.bit_count() == 100000);
}

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

const Case CASES[] = {
    {"trie_insert_and_find", trie_insert_and_find},
    {"trie_shares_prefixes", trie_shares_prefixes},
    {"trie_prefix_in_byte_order", trie_prefix_in_byte_order},
    {"trie_random_against_map", trie_random_against_map},
    {"bloom_sets_the_right_bits", bloom_sets_the_right_bits},
    {"bloom_no_false_negatives", bloom_no_false_negatives},
    {"bloom_false_positives_fall_with_size", bloom_false_positives_fall_with_size},
    {"bloom_uses_all_hashes", bloom_uses_all_hashes},
};

}  // namespace

int main(int argc, char* argv[]) {
    if (argc == 3) {
        tests_dir = argv[2];
        for (const Case& test : CASES) {
            if (std::strcmp(test.name, argv[1]) == 0) {
                test.run();
                return 0;
            }
        }
    }
    std::cerr << "uso: optional_tests nombre carpeta_de_pruebas\n";
    return 2;
}