// palabras.txt viene ordenado. ¿Qué árbol sale si se insertan sus palabras tal como vienen?
#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <vector>

#include "bench.h"
#include "bst_set.h"

namespace {

template <typename It>
void report(const std::string& name, It first, It last) {
    int height = 0;
    double seconds = median_seconds(3, [&] {
        BstSet<std::string> tree;
        for (It it = first; it != last; ++it) {
            tree.insert(*it);
        }
        height = tree.height();
    });
    std::cout << name << ": " << last - first << " palabras, altura " << height << ", " << seconds << " s\n";
}

}  // namespace

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: dictionary_order palabras.txt\n";
        return 2;
    }
    std::ifstream file(argv[1]);
    if (!file) {
        std::cerr << "no se pudo abrir " << argv[1] << "\n";
        return 2;
    }
    std::vector<std::string> words;
    std::string word;
    while (std::getline(file, word)) {
        words.push_back(word);
    }
    std::cout << "orden de bytes: " << (std::is_sorted(words.begin(), words.end()) ? "si" : "no") << "\n";

    report("tal como vienen", words.begin(), words.begin() + 20000);
    std::vector<std::string> shuffled = words;
    std::mt19937 random(10);
    std::shuffle(shuffled.begin(), shuffled.end(), random);
    report("barajadas", shuffled.begin(), shuffled.begin() + 20000);
    report("barajadas", shuffled.begin(), shuffled.end());

    // std::map se mantiene balanceado: el mismo orden que degenera a BstSet no le afecta.
    double seconds = median_seconds(3, [&] {
        std::map<std::string, int> map;
        for (const std::string& key : words) {
            map[key] = 1;
        }
        keep(map.size());
    });
    std::cout << "std::map, tal como vienen: " << words.size() << " palabras, " << seconds << " s\n";
    return 0;
}