// Cuenta las reservas de memoria de un programa, reemplazando el operator new global.
// Se incluye en un solo .cpp de cada programa.
#ifndef ALLOC_COUNTER_H
#define ALLOC_COUNTER_H

#include <cstddef>
#include <cstdlib>
#include <new>

// Número de llamadas a operator new desde que empezó el programa.
inline std::size_t& allocation_count() {
    static std::size_t count = 0;
    return count;
}

void* operator new(std::size_t size) {
    allocation_count()++;
    void* block = std::malloc(size == 0 ? 1 : size);
    if (block == nullptr) {
        throw std::bad_alloc();
    }
    return block;
}

void operator delete(void* block) noexcept {
    std::free(block);
}

void operator delete(void* block, std::size_t) noexcept {
    std::free(block);
}

#endif

// Medidor de tiempos del curso. Compilar con -O2 y sin sanitizers.
#ifndef BENCH_H
#define BENCH_H

#include <algorithm>
#include <chrono>
#include <vector>

// Corre fn `reps` veces y devuelve la mediana en segundos.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
    std::vector<double> times;
    times.reserve(reps);
    for (int i = 0; i < reps; i++) {
        auto start = std::chrono::steady_clock::now();
        fn();
        auto stop = std::chrono::steady_clock::now();
        times.push_back(std::chrono::duration<double>(stop - start).count());
    }
    std::sort(times.begin(), times.end());
    return times[times.size() / 2];
}

// Evita que el compilador borre un cálculo cuyo resultado no se usa.
template <typename T>
void keep(const T& value) {
    volatile T sink = value;
    (void)sink;
}

#endif

// Árbol binario de búsqueda sin valores: el conjunto de claves de los apuntes.
// El laboratorio construye un mapa con valores y con puntero al padre.
#ifndef BST_SET_H
#define BST_SET_H

#include <cassert>
#include <cstddef>
#include <sstream>
#include <string>
#include <vector>

// Invariantes:
// - En cada nodo, todas las claves del subárbol izquierdo son menores que la suya,
//   y todas las del derecho son mayores. Por eso no hay claves repetidas.
// - El árbol tiene exactamente size_ nodos, y root_ es nulo si y solo si size_ == 0.
//
// K solo necesita operator<: a y b son la misma clave si ni a < b ni b < a.
template <typename K>
class BstSet {
    struct Node {
        K key;
        Node* left = nullptr;
        Node* right = nullptr;
    };

public:
    BstSet() = default;

    // Sin recursión: un árbol degenerado no agota la pila.
    ~BstSet() {
        std::vector<Node*> pending;
        if (root_ != nullptr) {
            pending.push_back(root_);
        }
        while (!pending.empty()) {
            Node* node = pending.back();
            pending.pop_back();
            if (node->left != nullptr) {
                pending.push_back(node->left);
            }
            if (node->right != nullptr) {
                pending.push_back(node->right);
            }
            delete node;
        }
    }

    // Este conjunto es para estudiar las operaciones: no se copia ni se mueve.
    BstSet(const BstSet&) = delete;
    BstSet& operator=(const BstSet&) = delete;

    std::size_t size() const { return size_; }
    bool empty() const { return size_ == 0; }

    bool contains(const K& key) const {
        const Node* node = root_;
        while (node != nullptr) {
            if (key < node->key) {
                node = node->left;
            } else if (node->key < key) {
                node = node->right;
            } else {
                return true;
            }
        }
        return false;
    }

    // Devuelve false si la clave ya estaba.
    bool insert(const K& key) {
        Node** link = &root_;
        while (*link != nullptr) {
            if (key < (*link)->key) {
                link = &(*link)->left;
            } else if ((*link)->key < key) {
                link = &(*link)->right;
            } else {
                return false;
            }
        }
        *link = new Node{key};
        size_++;
        return true;
    }

    // Devuelve false si la clave no estaba.
    bool erase(const K& key) {
        Node** link = &root_;
        while (*link != nullptr) {
            if (key < (*link)->key) {
                link = &(*link)->left;
            } else if ((*link)->key < key) {
                link = &(*link)->right;
            } else {
                break;
            }
        }
        if (*link == nullptr) {
            return false;
        }
        Node* node = *link;
        if (node->left != nullptr && node->right != nullptr) {
            // Dos hijos: el sucesor es el mínimo del subárbol derecho.
            Node** next_link = &node->right;
            while ((*next_link)->left != nullptr) {
                next_link = &(*next_link)->left;
            }
            node->key = (*next_link)->key;
            // Ahora el que se quita es el nodo del sucesor, que no tiene hijo izquierdo.
            link = next_link;
            node = *link;
        }
        *link = node->left != nullptr ? node->left : node->right;
        delete node;
        size_--;
        return true;
    }

    // Puntero a la clave menor; nulo si está vacío.
    const K* min() const {
        const Node* node = root_;
        if (node == nullptr) {
            return nullptr;
        }
        while (node->left != nullptr) {
            node = node->left;
        }
        return &node->key;
    }

    // Puntero a la clave mayor; nulo si está vacío.
    const K* max() const {
        const Node* node = root_;
        if (node == nullptr) {
            return nullptr;
        }
        while (node->right != nullptr) {
            node = node->right;
        }
        return &node->key;
    }

    // Puntero a la mayor clave <= key; nulo si no hay.
    const K* floor(const K& key) const {
        const Node* node = root_;
        const K* candidate = nullptr;
        while (node != nullptr) {
            if (key < node->key) {
                node = node->left;
            } else if (node->key < key) {
                candidate = &node->key;
                node = node->right;
            } else {
                return &node->key;
            }
        }
        return candidate;
    }

    // Las claves de [low, high), en orden.
    std::vector<K> range(const K& low, const K& high) const {
        std::vector<K> keys;
        collect_range(root_, low, high, keys);
        return keys;
    }

    std::vector<K> in_order() const {
        std::vector<K> keys;
        walk_in(root_, keys);
        return keys;
    }

    std::vector<K> pre_order() const {
        std::vector<K> keys;
        walk_pre(root_, keys);
        return keys;
    }

    std::vector<K> post_order() const {
        std::vector<K> keys;
        walk_post(root_, keys);
        return keys;
    }

    // Altura: aristas del camino más largo desde la raíz. Vacío: -1. Un solo nodo: 0.
    // Va nivel por nivel, sin recursión.
    int height() const {
        int levels = 0;
        std::vector<const Node*> level;
        if (root_ != nullptr) {
            level.push_back(root_);
        }
        while (!level.empty()) {
            std::vector<const Node*> next;
            for (const Node* node : level) {
                if (node->left != nullptr) {
                    next.push_back(node->left);
                }
                if (node->right != nullptr) {
                    next.push_back(node->right);
                }
            }
            level = std::move(next);
            levels++;
        }
        return levels - 1;
    }

    // Suma de las profundidades de todos los nodos: la raíz tiene profundidad 0.
    long total_depth() const {
        long total = 0;
        long depth = 0;
        std::vector<const Node*> level;
        if (root_ != nullptr) {
            level.push_back(root_);
        }
        while (!level.empty()) {
            std::vector<const Node*> next;
            for (const Node* node : level) {
                total += depth;
                if (node->left != nullptr) {
                    next.push_back(node->left);
                }
                if (node->right != nullptr) {
                    next.push_back(node->right);
                }
            }
            level = std::move(next);
            depth++;
        }
        return total;
    }

    // La forma del árbol en una línea: clave(izquierdo,derecho), con _ si falta un hijo.
    std::string shape() const {
        std::ostringstream out;
        write_shape(root_, out);
        return out.str();
    }

    // Comprueba con límites: mirar solo a los hijos directos no alcanza.
    // Es recursiva: su profundidad es la altura del árbol.
    void check_invariants() const {
        assert(count_checked(root_, nullptr, nullptr) == size_);
        assert((root_ == nullptr) == (size_ == 0));
    }

private:
    static void walk_in(const Node* node, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        walk_in(node->left, keys);
        keys.push_back(node->key);
        walk_in(node->right, keys);
    }

    static void walk_pre(const Node* node, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        keys.push_back(node->key);
        walk_pre(node->left, keys);
        walk_pre(node->right, keys);
    }

    static void walk_post(const Node* node, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        walk_post(node->left, keys);
        walk_post(node->right, keys);
        keys.push_back(node->key);
    }

    static void collect_range(const Node* node, const K& low, const K& high, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        if (low < node->key) {
            collect_range(node->left, low, high, keys);
        }
        if (!(node->key < low) && node->key < high) {
            keys.push_back(node->key);
        }
        if (node->key < high) {
            collect_range(node->right, low, high, keys);
        }
    }

    static void write_shape(const Node* node, std::ostringstream& out) {
        if (node == nullptr) {
            out << "_";
            return;
        }
        out << node->key;
        if (node->left != nullptr || node->right != nullptr) {
            out << "(";
            write_shape(node->left, out);
            out << ",";
            write_shape(node->right, out);
            out << ")";
        }
    }

    // Cuenta los nodos, y exige que cada clave quede entre low y high (nulo: sin límite).
    static std::size_t count_checked(const Node* node, const K* low, const K* high) {
        if (node == nullptr) {
            return 0;
        }
        assert(low == nullptr || *low < node->key);
        assert(high == nullptr || node->key < *high);
        return 1 + count_checked(node->left, low, &node->key)
                 + count_checked(node->right, &node->key, high);
    }

    Node* root_ = nullptr;
    std::size_t size_ = 0;
};

#endif

// El orden de std::string es el de los bytes. Consultas por rango sobre palabras.txt.
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <string>

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: byte_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::map<std::string, int> words;
    std::string word;
    while (std::getline(file, word)) {
        words[word] = 1;
    }

    auto count_range = [&](const std::string& low, const std::string& high) {
        auto first = words.lower_bound(low);
        auto last = words.lower_bound(high);
        long count = std::distance(first, last);
        std::cout << "[" << low << ", " << high << "): " << count;
        if (count > 0) {
            std::cout << ", de " << first->first << " a " << std::prev(last)->first;
        }
        std::cout << "\n";
    };

    std::cout << "ultima: " << words.rbegin()->first << "\n";
    count_range("a", "b");
    count_range("á", "â");
    count_range("n", "o");
    count_range("ñ", "ò");
    count_range("pre", "prf");
    count_range("z", "{");

    auto next = words.upper_bound("zuzos");
    std::cout << "despues de zuzos: " << next->first << "\n";
    auto before = std::prev(words.lower_bound("rodillas"));
    std::cout << "piso de rodillas: " << before->first << ", siguiente: " << std::next(before)->first << "\n";
    return 0;
}

// Clave entera que cuenta cuántas veces se compara. Solo tiene operator<.
#ifndef COUNTED_KEY_H
#define COUNTED_KEY_H

#include <ostream>

struct CountedKey {
    int value = 0;
    inline static long comparisons = 0;

    bool operator<(const CountedKey& other) const {
        comparisons++;
        return value < other.value;
    }
};

inline std::ostream& operator<<(std::ostream& out, const CountedKey& key) {
    return out << key.value;
}

#endif

// 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;
}

// Los tres casos del borrado, cada uno sobre el mismo árbol.
#include <iostream>

#include "bst_set.h"

namespace {

void show_erase(int key) {
    BstSet<int> tree;
    for (int value : {50, 30, 70, 20, 40, 60, 80, 35, 65, 90}) {
        tree.insert(value);
    }
    std::cout << "borrar " << key << ": " << tree.shape() << "\n";
    tree.erase(key);
    tree.check_invariants();
    std::cout << "queda:    " << tree.shape() << "\n";
}

}  // namespace

int main() {
    show_erase(20);
    show_erase(80);
    show_erase(60);
    show_erase(30);
    show_erase(50);
    show_erase(70);
    return 0;
}

// Altura y comparaciones al insertar n claves, al azar y ordenadas. Todo son conteos, no tiempos.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "bst_set.h"
#include "counted_key.h"

int main() {
    std::cout << "Claves al azar, tres semillas\n";
    std::cout << std::setw(9) << "n" << std::setw(7) << "log2n" << std::setw(6) << "h1" << std::setw(6) << "h2"
              << std::setw(6) << "h3" << std::setw(9) << "h/log2n" << std::setw(11) << "prof.media"
              << std::setw(10) << "prof/log" << "\n";
    for (int n = 1000; n <= 1024000; n *= 4) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        double log_n = std::log2(n);
        int heights[3];
        double mean_depth = 0;
        for (int seed = 0; seed < 3; seed++) {
            std::mt19937 random(seed + 1);
            std::shuffle(keys.begin(), keys.end(), random);
            BstSet<int> tree;
            for (int key : keys) {
                tree.insert(key);
            }
            heights[seed] = tree.height();
            mean_depth += static_cast<double>(tree.total_depth()) / n / 3;
        }
        double mean_height = (heights[0] + heights[1] + heights[2]) / 3.0;
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(1) << std::setw(7) << log_n
                  << std::setw(6) << heights[0] << std::setw(6) << heights[1] << std::setw(6) << heights[2]
                  << std::setprecision(2) << std::setw(9) << mean_height / log_n << std::setw(11) << mean_depth
                  << std::setw(10) << mean_depth / log_n << "\n";
    }

    std::cout << "Claves ordenadas\n";
    std::cout << std::setw(9) << "n" << std::setw(9) << "altura" << std::setw(15) << "comparaciones"
              << std::setw(15) << "n(n-1)" << "\n";
    for (int n = 1000; n <= 16000; n *= 2) {
        BstSet<CountedKey> tree;
        CountedKey::comparisons = 0;
        for (int key = 0; key < n; key++) {
            tree.insert(CountedKey{key});
        }
        std::cout << std::setw(9) << n << std::setw(9) << tree.height() << std::setw(15) << CountedKey::comparisons
                  << std::setw(15) << static_cast<long>(n) * (n - 1) << "\n";
    }
    return 0;
}

// Tiempo de insertar y de buscar n claves, al azar y ordenadas. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

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

namespace {

double insert_seconds(const std::vector<int>& keys) {
    return median_seconds(5, [&] {
        BstSet<int> tree;
        for (int key : keys) {
            tree.insert(key);
        }
        keep(tree.size());
    });
}

}  // namespace

int main() {
    std::cout << std::setw(9) << "n" << std::setw(11) << "azar(s)" << std::setw(10) << "x" << std::setw(12) << "orden(s)"
              << std::setw(10) << "x" << "\n";
    std::mt19937 random(10);
    double last_random = 0;
    double last_sorted = 0;
    for (int n = 1000; n <= 32000; n *= 2) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 0);
        double sorted_time = insert_seconds(keys);
        std::shuffle(keys.begin(), keys.end(), random);
        double random_time = insert_seconds(keys);
        std::cout << std::setw(9) << n << std::fixed << std::setprecision(5) << std::setw(11) << random_time
                  << std::setprecision(1) << std::setw(10) << (last_random > 0 ? random_time / last_random : 0)
                  << std::setprecision(5) << std::setw(12) << sorted_time
                  << std::setprecision(1) << std::setw(10) << (last_sorted > 0 ? sorted_time / last_sorted : 0) << "\n";
        last_random = random_time;
        last_sorted = sorted_time;
    }
    return 0;
}

// Inserta las mismas 6 claves en todos los órdenes posibles y cuenta qué altura sale.
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

#include "bst_set.h"

int main() {
    std::vector<int> keys = {1, 3, 4, 5, 7, 8};
    std::map<int, int> orders_with_height;
    int total = 0;
    do {
        BstSet<int> tree;
        for (int key : keys) {
            tree.insert(key);
        }
        orders_with_height[tree.height()]++;
        total++;
    } while (std::next_permutation(keys.begin(), keys.end()));

    std::cout << "ordenes: " << total << "\n";
    for (const auto& [height, count] : orders_with_height) {
        std::cout << "altura " << height << ": " << count << " ordenes\n";
    }
    return 0;
}

// Qué promete std::map sobre sus elementos, y cuánta memoria pide esta biblioteca por nodo.
#include <cassert>
#include <cstddef>
#include <iostream>
#include <map>
#include <memory>
#include <unordered_map>

#include "alloc_counter.h"

namespace {

// Un asignador que anota cuántos bytes pidió el contenedor en cada reserva.
inline std::size_t last_block = 0;

template <typename T>
struct SpyAllocator {
    using value_type = T;
    SpyAllocator() = default;
    template <typename U>
    SpyAllocator(const SpyAllocator<U>&) {}
    T* allocate(std::size_t n) {
        last_block = n * sizeof(T);
        return std::allocator<T>{}.allocate(n);
    }
    void deallocate(T* block, std::size_t n) { std::allocator<T>{}.deallocate(block, n); }
    bool operator==(const SpyAllocator&) const { return true; }
};

}  // namespace

int main() {
    std::map<int, int> map;
    map[5] = 50;
    map[3] = 30;
    map[8] = 80;
    map[7] = 70;
    int* to_seven = &map[7];

    for (int i = 100; i < 1100; i++) {
        map[i] = i;
    }
    // Borrar el 5, que tiene dos hijos: el 7 sigue en su sitio, aunque es su sucesor.
    map.erase(5);
    std::cout << "puntero al 7 tras mil inserciones y un borrado: " << *to_seven << "\n";
    assert(to_seven == &map[7]);

    std::size_t before = allocation_count();
    std::map<int, int> counted;
    for (int i = 0; i < 1000; i++) {
        counted[i] = i;
    }
    std::cout << "reservas de std::map al insertar 1000 claves: " << allocation_count() - before << "\n";

    std::map<int, int, std::less<int>, SpyAllocator<std::pair<const int, int>>> spied;
    spied[1] = 1;
    std::cout << "bytes por nodo de std::map<int, int>: " << last_block << "\n";

    std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, SpyAllocator<std::pair<const int, int>>> spied_hash;
    spied_hash.reserve(16);
    spied_hash[1] = 1;
    std::cout << "bytes por nodo de std::unordered_map<int, int>: " << last_block << "\n";
    return 0;
}

// La misma consulta en std::map y en std::unordered_map: la menor clave >= x, y una por rango.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <random>
#include <unordered_map>
#include <vector>

#include "counted_key.h"

namespace {

struct CountedHash {
    std::size_t operator()(const CountedKey& key) const { return std::hash<int>{}(key.value); }
};

struct SameKey {
    bool operator()(const CountedKey& a, const CountedKey& b) const { return a.value == b.value; }
};

}  // namespace

int main() {
    const int n = 100000;
    std::mt19937 random(10);
    std::vector<int> values(n);
    for (int i = 0; i < n; i++) {
        values[i] = i * 3;
    }
    std::shuffle(values.begin(), values.end(), random);

    std::map<CountedKey, int> ordered;
    std::unordered_map<CountedKey, int, CountedHash, SameKey> hashed;
    for (int value : values) {
        ordered[CountedKey{value}] = value;
        hashed[CountedKey{value}] = value;
    }
    CountedKey target{100000};

    CountedKey::comparisons = 0;
    auto at_or_after = ordered.lower_bound(target);
    std::cout << "std::map, techo de 100000: " << at_or_after->first.value << ", comparaciones: "
              << CountedKey::comparisons << "\n";

    // Sin orden no queda más que mirar todas las claves.
    long visited = 0;
    int best = -1;
    for (const auto& [key, value] : hashed) {
        visited++;
        if (key.value >= target.value && (best == -1 || key.value < best)) {
            best = key.value;
        }
    }
    std::cout << "std::unordered_map, techo de 100000: " << best << ", claves visitadas: " << visited << "\n";

    CountedKey::comparisons = 0;
    auto after = ordered.upper_bound(CountedKey{100000});
    std::cout << "std::map, piso de 100000: " << std::prev(after)->first.value << ", comparaciones: "
              << CountedKey::comparisons << "\n";

    long in_range = 0;
    CountedKey::comparisons = 0;
    auto stop = ordered.lower_bound(CountedKey{100030});
    for (auto it = ordered.lower_bound(CountedKey{100000}); it != stop; ++it) {
        in_range++;
    }
    std::cout << "std::map, claves en [100000, 100030): " << in_range << ", comparaciones: "
              << CountedKey::comparisons << "\n";

    std::cout << "std::map, primeras:";
    auto it_map = ordered.begin();
    for (int i = 0; i < 5; i++, ++it_map) {
        std::cout << " " << it_map->first.value;
    }
    std::cout << "\n";

    std::cout << "std::unordered_map, primeras:";
    auto it_hash = hashed.begin();
    for (int i = 0; i < 5; i++, ++it_hash) {
        std::cout << " " << it_hash->first.value;
    }
    std::cout << "\n";
    return 0;
}

// std::map frente a std::unordered_map con palabras reales. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>

#include "bench.h"

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: map_vs_unordered 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::mt19937 random(10);
    std::shuffle(words.begin(), words.end(), random);

    std::cout << "  (tiempo por palabra, en ns; mediana de 3)\n";
    std::cout << std::setw(9) << "n" << std::setw(10) << "ins.map" << std::setw(10) << "ins.hash" << std::setw(7) << "x"
              << std::setw(10) << "bus.map" << std::setw(10) << "bus.hash" << std::setw(7) << "x"
              << std::setw(10) << "ord.map" << std::setw(10) << "ord.hash" << std::setw(7) << "x" << "\n";
    for (std::size_t n : {std::size_t{10000}, std::size_t{100000}, words.size()}) {
        std::vector<std::string> keys(words.begin(), words.begin() + n);
        std::vector<std::string> queries = keys;
        std::shuffle(queries.begin(), queries.end(), random);
        double per_key = 1e9 / n;

        double insert_map = per_key * median_seconds(3, [&] {
            std::map<std::string, int> map;
            for (const std::string& key : keys) {
                map[key] = 1;
            }
            keep(map.size());
        });
        double insert_hash = per_key * median_seconds(3, [&] {
            std::unordered_map<std::string, int> map;
            for (const std::string& key : keys) {
                map[key] = 1;
            }
            keep(map.size());
        });

        std::map<std::string, int> ordered;
        std::unordered_map<std::string, int> hashed;
        for (const std::string& key : keys) {
            ordered[key] = 1;
            hashed[key] = 1;
        }
        double find_map = per_key * median_seconds(3, [&] {
            long found = 0;
            for (const std::string& key : queries) {
                found += ordered.count(key);
            }
            keep(found);
        });
        double find_hash = per_key * median_seconds(3, [&] {
            long found = 0;
            for (const std::string& key : queries) {
                found += hashed.count(key);
            }
            keep(found);
        });
        // Sacar todas las claves en orden: el mapa solo las recorre, y la tabla tiene que ordenarlas.
        double sorted_map = per_key * median_seconds(3, [&] {
            std::size_t bytes = 0;
            for (const auto& [key, value] : ordered) {
                bytes += key.size() + value;
            }
            keep(bytes);
        });
        double sorted_hash = per_key * median_seconds(3, [&] {
            std::vector<const std::string*> pointers;
            pointers.reserve(hashed.size());
            for (const auto& [key, value] : hashed) {
                pointers.push_back(&key);
            }
            std::sort(pointers.begin(), pointers.end(),
                      [](const std::string* a, const std::string* b) { return *a < *b; });
            std::size_t bytes = 0;
            for (const std::string* key : pointers) {
                bytes += key->size();
            }
            keep(bytes);
        });

        std::cout << std::setw(9) << n << std::fixed << std::setprecision(0) << std::setw(10) << insert_map
                  << std::setw(10) << insert_hash << std::setprecision(1) << std::setw(7) << insert_map / insert_hash
                  << std::setprecision(0) << std::setw(10) << find_map << std::setw(10) << find_hash
                  << std::setprecision(1) << std::setw(7) << find_map / find_hash
                  << std::setprecision(0) << std::setw(10) << sorted_map << std::setw(10) << sorted_hash
                  << std::setprecision(1) << std::setw(7) << sorted_hash / sorted_map << "\n";
    }
    return 0;
}

// Consultas ordenadas sobre un árbol perfecto de 1023 claves, contando comparaciones.
#include <iostream>
#include <vector>

#include "bst_set.h"
#include "counted_key.h"

namespace {

// La raíz primero: así el árbol sale perfecto.
void add_balanced(BstSet<CountedKey>& tree, int low, int high) {
    if (low > high) {
        return;
    }
    int middle = low + (high - low) / 2;
    tree.insert(CountedKey{middle * 10});
    add_balanced(tree, low, middle - 1);
    add_balanced(tree, middle + 1, high);
}

}  // namespace

int main() {
    BstSet<CountedKey> tree;
    add_balanced(tree, 0, 1022);
    std::cout << "claves: " << tree.size() << ", altura: " << tree.height() << "\n";

    CountedKey::comparisons = 0;
    std::cout << "contains(5000): " << tree.contains(CountedKey{5000});
    std::cout << ", comparaciones: " << CountedKey::comparisons << "\n";

    CountedKey::comparisons = 0;
    std::cout << "contains(5001): " << tree.contains(CountedKey{5001});
    std::cout << ", comparaciones: " << CountedKey::comparisons << "\n";

    CountedKey::comparisons = 0;
    std::cout << "floor(5001): " << *tree.floor(CountedKey{5001});
    std::cout << ", comparaciones: " << CountedKey::comparisons << "\n";

    for (int count : {1, 10, 100, 1000}) {
        CountedKey::comparisons = 0;
        std::vector<CountedKey> keys = tree.range(CountedKey{100}, CountedKey{100 + count * 10});
        std::cout << "range con " << keys.size() << " claves, comparaciones: " << CountedKey::comparisons << "\n";
    }
    return 0;
}

// El árbol de los apuntes: sus tres recorridos, su altura, y qué pasa al borrar la raíz.
#include <iostream>
#include <string>
#include <vector>

#include "bst_set.h"

namespace {

void print_line(const std::string& name, const std::vector<int>& keys) {
    std::cout << name << ":";
    for (int key : keys) {
        std::cout << " " << key;
    }
    std::cout << "\n";
}

}  // namespace

int main() {
    BstSet<int> tree;
    for (int key : {5, 3, 8, 1, 4, 7}) {
        tree.insert(key);
    }
    std::cout << "forma: " << tree.shape() << "\n";
    print_line("en orden", tree.in_order());
    print_line("preorden", tree.pre_order());
    print_line("postorden", tree.post_order());
    std::cout << "altura: " << tree.height() << "\n";

    tree.erase(5);
    std::cout << "sin el 5: " << tree.shape() << "\n";
    print_line("en orden", tree.in_order());
    tree.check_invariants();
    return 0;
}

// Error a propósito: en el borrado con dos hijos, se copia la clave del sucesor
// y se olvida borrar el nodo del sucesor. check_invariants lo descubre.
#include <cassert>
#include <cstddef>
#include <iostream>

class BrokenSet {
    struct Node {
        int key;
        Node* left = nullptr;
        Node* right = nullptr;
    };

public:
    BrokenSet() = default;
    BrokenSet(const BrokenSet&) = delete;
    BrokenSet& operator=(const BrokenSet&) = delete;
    ~BrokenSet() { destroy(root_); }

    void insert(int key) {
        Node** link = &root_;
        while (*link != nullptr) {
            link = key < (*link)->key ? &(*link)->left : &(*link)->right;
        }
        *link = new Node{key};
        size_++;
    }

    void erase_two_children(int key) {
        Node* node = root_;
        while (node->key != key) {
            node = key < node->key ? node->left : node->right;
        }
        Node* next = node->right;
        while (next->left != nullptr) {
            next = next->left;
        }
        node->key = next->key;
        size_--;
        // Falta quitar next del árbol: su clave quedó dos veces.
    }

    void print_in_order() const {
        print(root_);
        std::cout << std::endl;
    }

    void check_invariants() const {
        assert(count_checked(root_, nullptr, nullptr) == size_);
    }

private:
    static void destroy(Node* node) {
        if (node != nullptr) {
            destroy(node->left);
            destroy(node->right);
            delete node;
        }
    }

    static void print(const Node* node) {
        if (node != nullptr) {
            print(node->left);
            std::cout << node->key << " ";
            print(node->right);
        }
    }

    static std::size_t count_checked(const Node* node, const int* low, const int* high) {
        if (node == nullptr) {
            return 0;
        }
        assert(low == nullptr || *low < node->key);
        assert(high == nullptr || node->key < *high);
        return 1 + count_checked(node->left, low, &node->key)
                 + count_checked(node->right, &node->key, high);
    }

    Node* root_ = nullptr;
    std::size_t size_ = 0;
};

int main() {
    BrokenSet tree;
    for (int key : {5, 3, 8, 1, 4, 7}) {
        tree.insert(key);
    }
    tree.erase_two_children(5);
    tree.print_in_order();
    tree.check_invariants();
    return 0;
}