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

// Qué orden sale al comparar bytes, y por qué un std::string no se confunde con el signo de char.
// Uso: byte_order archivo_de_terminos
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

#include "lab/terms_io.h"

namespace {

// Compara char por char. Depende de si char tiene signo en esta máquina.
bool less_by_char(const std::string& a, const std::string& b) {
    std::size_t common = std::min(a.size(), b.size());
    for (std::size_t i = 0; i < common; i++) {
        if (a[i] != b[i]) {
            return a[i] < b[i];
        }
    }
    return a.size() < b.size();
}

void print_words(const char* label, const std::vector<std::string>& words) {
    std::cout << label << ":";
    for (const std::string& word : words) {
        std::cout << " " << word;
    }
    std::cout << "\n";
}

void print_bytes(const std::string& word) {
    std::cout << word << " =";
    for (char c : word) {
        std::printf(" %02x", static_cast<unsigned>(static_cast<unsigned char>(c)));
    }
    std::cout << ", size() = " << word.size() << "\n";
}

// Busca revisando todo el archivo: es lento, y por eso es confiable para este ejemplo.
void scan_prefix(const std::vector<Term>& sorted_terms, const std::string& prefix) {
    std::size_t first = sorted_terms.size();
    std::size_t last = 0;
    std::size_t count = 0;
    for (std::size_t i = 0; i < sorted_terms.size(); i++) {
        if (sorted_terms[i].text.starts_with(prefix)) {
            first = std::min(first, i);
            last = i + 1;
            count++;
        }
    }
    std::printf("%-4s %5zu términos en [%zu, %zu): de %s a %s\n", prefix.c_str(), count, first, last,
                sorted_terms[first].text.c_str(), sorted_terms[last - 1].text.c_str());
}

}  // namespace

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: byte_order archivo_de_terminos\n";
        return 2;
    }
    print_bytes("a");
    print_bytes("á");
    print_bytes("ñ");
    print_bytes("z");

    std::vector<std::string> words = {"zorro", "cámara", "caña", "ñandú", "cazar", "árbol", "cama"};
    std::cout << "char con signo: " << (std::numeric_limits<char>::is_signed ? "sí" : "no") << "\n";
    std::sort(words.begin(), words.end());
    print_words("con std::string", words);
    std::sort(words.begin(), words.end(), less_by_char);
    print_words("char por char ", words);

    std::vector<Term> terms;
    if (!load_terms(argv[1], terms)) {
        std::cerr << "no se pudo leer " << argv[1] << "\n";
        return 1;
    }
    std::sort(terms.begin(), terms.end(), [](const Term& a, const Term& b) { return a.text < b.text; });
    for (const char* prefix : {"a", "á", "ca", "cá", "cañ", "z", "ñ"}) {
        scan_prefix(terms, prefix);
    }
    std::string wanted_low = "ca";
    std::string wanted_high = "cazzzz";
    std::size_t naive = 0;
    for (const Term& term : terms) {
        if (term.text >= wanted_low && term.text <= wanted_high) {
            naive++;
        }
    }
    std::printf("entre ca y cazzzz: %zu términos\n", naive);
    return 0;
}

// Pasarle un comparador a std::sort, de tres maneras.
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

#include "lab/terms_io.h"

namespace {

bool by_text(const Term& a, const Term& b) {
    return a.text < b.text;
}

void print_terms(const char* label, const std::vector<Term>& terms) {
    std::cout << label << ":";
    for (const Term& term : terms) {
        std::cout << " " << term.text << "(" << term.weight << ")";
    }
    std::cout << "\n";
}

}  // namespace

int main() {
    std::vector<Term> terms = {{"lima", 40}, {"cusco", 90}, {"puno", 40}, {"tacna", 95}, {"arequipa", 90}};

    std::sort(terms.begin(), terms.end(), by_text);
    print_terms("por texto", terms);

    std::sort(terms.begin(), terms.end(), [](const Term& a, const Term& b) {
        if (a.weight != b.weight) {
            return a.weight > b.weight;
        }
        return a.text < b.text;
    });
    print_terms("por frecuencia, y texto en los empates", terms);

    std::vector<int> values = {3, 1, 2};
    std::sort(values.begin(), values.end(), std::greater<int>());
    std::cout << "de mayor a menor: " << values[0] << " " << values[1] << " " << values[2] << "\n";

    // En std::lower_bound, el comparador recibe un elemento y el valor buscado.
    std::sort(terms.begin(), terms.end(), by_text);
    std::string wanted = "lima";
    auto found = std::lower_bound(terms.begin(), terms.end(), wanted,
                                  [](const Term& term, const std::string& x) { return term.text < x; });
    std::cout << "lower_bound de lima: " << found->text << " en la posición " << (found - terms.begin()) << "\n";
    return 0;
}

// Cuenta comparaciones: no depende de la máquina, y sí permite comparar algoritmos.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdio>
#include <vector>

#include "inputs.h"
#include "int_sorts.h"

namespace {

const unsigned SEED = 2026;

long long count_merge(std::vector<int> items) {
    long long comparisons = 0;
    merge_sort_ints(items, comparisons);
    return comparisons;
}

long long count_first(std::vector<int> items) {
    long long comparisons = 0;
    quick_sort_first_ints(items, comparisons);
    return comparisons;
}

long long count_random(std::vector<int> items) {
    long long comparisons = 0;
    quick_sort_random_ints(items, SEED, comparisons);
    return comparisons;
}

long long count_three(std::vector<int> items) {
    long long comparisons = 0;
    quick_sort_three_ints(items, SEED, comparisons);
    return comparisons;
}

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

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

void row(const char* name, const std::vector<int>& items) {
    std::printf("%-10s %9lld %9lld %9lld %9lld %9lld %9lld\n", name, count_merge(items),
                count_first(items), count_random(items), count_three(items), count_library(items),
                count_stable(items));
}

}  // namespace

int main() {
    const std::size_t n = 4096;
    std::printf("comparaciones con n = %zu\n", n);
    std::printf("%-10s %9s %9s %9s %9s %9s %9s\n", "entrada", "merge", "q.primero", "q.azar", "q.tres",
                "std::sort", "stable");
    row("al azar", random_input(n, SEED));
    row("ordenada", sorted_input(n));
    row("inversa", reversed_input(n));
    row("10 valores", repeated_input(n, 10, SEED));
    row("iguales", std::vector<int>(n, 7));

    std::printf("\nquicksort con el primero como pivote, entrada ordenada\n");
    std::printf("%6s %10s %12s\n", "n", "comparac.", "n(n-1)/2");
    for (std::size_t size : {1000, 2000, 4000, 8000}) {
        long long formula = static_cast<long long>(size) * (static_cast<long long>(size) - 1) / 2;
        std::printf("%6zu %10lld %12lld\n", size, count_first(sorted_input(size)), formula);
    }

    std::printf("\nquicksort con pivote al azar, entrada al azar: promedio de 20 semillas\n");
    std::printf("%8s %11s %11s %7s\n", "n", "comparac.", "2 n ln n", "razón");
    for (std::size_t size : {1000, 10000, 100000, 1000000}) {
        double total = 0;
        for (unsigned seed = 1; seed <= 20; seed++) {
            std::vector<int> items = random_input(size, seed);
            long long comparisons = 0;
            quick_sort_random_ints(items, seed + 100, comparisons);
            total += static_cast<double>(comparisons);
        }
        double average = total / 20;
        double estimate = 2 * static_cast<double>(size) * std::log(static_cast<double>(size));
        std::printf("%8zu %11.0f %11.0f %7.3f\n", size, average, estimate, average / estimate);
    }
    return 0;
}

// Las entradas con las que se comparan los ordenamientos. Semilla fija: se repiten igual.
#ifndef INPUTS_H
#define INPUTS_H

#include <cstddef>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

inline std::vector<int> sorted_input(std::size_t n) {
    std::vector<int> items(n);
    std::iota(items.begin(), items.end(), 0);
    return items;
}

inline std::vector<int> reversed_input(std::size_t n) {
    std::vector<int> items = sorted_input(n);
    for (std::size_t i = 0; i < n / 2; i++) {
        std::swap(items[i], items[n - 1 - i]);
    }
    return items;
}

// Fisher-Yates: el mismo orden con la misma semilla, en cualquier biblioteca.
inline std::vector<int> random_input(std::size_t n, unsigned seed) {
    std::vector<int> items = sorted_input(n);
    std::mt19937 rng(seed);
    for (std::size_t i = n; i > 1; i--) {
        std::swap(items[i - 1], items[rng() % i]);
    }
    return items;
}

// Solo `distinct` valores distintos, repetidos muchas veces.
inline std::vector<int> repeated_input(std::size_t n, int distinct, unsigned seed) {
    std::vector<int> items(n);
    std::mt19937 rng(seed);
    for (int& value : items) {
        value = static_cast<int>(rng() % static_cast<unsigned>(distinct));
    }
    return items;
}

#endif

// Los ordenamientos de la clase, solo para enteros. Cuentan comparaciones para poder
// comparar algoritmos con un número que no depende de la máquina.
#ifndef INT_SORTS_H
#define INT_SORTS_H

#include <cstddef>
#include <random>
#include <utility>
#include <vector>

// Mezcla items[lo, mid) con items[mid, hi), que ya están ordenados.
inline void merge_runs(std::vector<int>& items, std::vector<int>& buffer, std::size_t lo,
                       std::size_t mid, std::size_t hi, long long& comparisons) {
    std::size_t left = lo;
    std::size_t right = mid;
    std::size_t out = lo;
    while (left < mid && right < hi) {
        comparisons++;
        if (items[right] < items[left]) {
            buffer[out++] = items[right++];
        } else {
            buffer[out++] = items[left++];
        }
    }
    while (left < mid) {
        buffer[out++] = items[left++];
    }
    while (right < hi) {
        buffer[out++] = items[right++];
    }
    for (std::size_t i = lo; i < hi; i++) {
        items[i] = buffer[i];
    }
}

inline void merge_sort_range(std::vector<int>& items, std::vector<int>& buffer, std::size_t lo,
                             std::size_t hi, long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    merge_sort_range(items, buffer, lo, mid, comparisons);
    merge_sort_range(items, buffer, mid, hi, comparisons);
    merge_runs(items, buffer, lo, mid, hi, comparisons);
}

inline void merge_sort_ints(std::vector<int>& items, long long& comparisons) {
    std::vector<int> buffer(items.size());
    merge_sort_range(items, buffer, 0, items.size(), comparisons);
}

// Partición con el primer elemento como pivote. Al terminar, el pivote queda en su lugar
// final, y se devuelve esa posición.
inline std::size_t partition_first(std::vector<int>& items, std::size_t lo, std::size_t hi,
                                   long long& comparisons) {
    int pivot = items[lo];
    std::size_t boundary = lo;
    // Invariante: items(lo, boundary] < pivot, e items(boundary, scan) >= pivot.
    for (std::size_t scan = lo + 1; scan < hi; scan++) {
        comparisons++;
        if (items[scan] < pivot) {
            boundary++;
            std::swap(items[boundary], items[scan]);
        }
    }
    std::swap(items[lo], items[boundary]);
    return boundary;
}

inline void quick_first_range(std::vector<int>& items, std::size_t lo, std::size_t hi,
                              long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::size_t p = partition_first(items, lo, hi, comparisons);
    quick_first_range(items, lo, p, comparisons);
    quick_first_range(items, p + 1, hi, comparisons);
}

inline void quick_sort_first_ints(std::vector<int>& items, long long& comparisons) {
    quick_first_range(items, 0, items.size(), comparisons);
}

// Lo mismo, pero antes de partir se cambia el primer elemento por uno al azar.
inline void quick_random_range(std::vector<int>& items, std::size_t lo, std::size_t hi,
                               std::mt19937& rng, long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::uniform_int_distribution<std::size_t> pick(lo, hi - 1);
    std::swap(items[lo], items[pick(rng)]);
    std::size_t p = partition_first(items, lo, hi, comparisons);
    quick_random_range(items, lo, p, rng, comparisons);
    quick_random_range(items, p + 1, hi, rng, comparisons);
}

inline void quick_sort_random_ints(std::vector<int>& items, unsigned seed, long long& comparisons) {
    std::mt19937 rng(seed);
    quick_random_range(items, 0, items.size(), rng, comparisons);
}

// Partición en tres, con pivote al azar. Invariante: items[lo, less_end) < pivot,
// items[less_end, scan) == pivot, items[scan, greater_start) sin revisar, items[greater_start, hi) > pivot.
inline void quick_three_range(std::vector<int>& items, std::size_t lo, std::size_t hi,
                              std::mt19937& rng, long long& comparisons) {
    if (hi - lo < 2) {
        return;
    }
    std::uniform_int_distribution<std::size_t> pick(lo, hi - 1);
    int pivot = items[pick(rng)];
    std::size_t less_end = lo;
    std::size_t scan = lo;
    std::size_t greater_start = hi;
    while (scan < greater_start) {
        comparisons++;
        if (items[scan] < pivot) {
            std::swap(items[less_end], items[scan]);
            less_end++;
            scan++;
            continue;
        }
        comparisons++;
        if (pivot < items[scan]) {
            greater_start--;
            std::swap(items[scan], items[greater_start]);
        } else {
            scan++;
        }
    }
    quick_three_range(items, lo, less_end, rng, comparisons);
    quick_three_range(items, greater_start, hi, rng, comparisons);
}

inline void quick_sort_three_ints(std::vector<int>& items, unsigned seed, long long& comparisons) {
    std::mt19937 rng(seed);
    quick_three_range(items, 0, items.size(), rng, comparisons);
}

// Búsqueda binaria. Devuelve la posición del primer elemento >= x, o size() si no hay.
inline std::size_t lower_bound_index(const std::vector<int>& items, int x, long long& probes) {
    std::size_t lo = 0;
    std::size_t hi = items.size();
    // Invariante: todo en [0, lo) es < x, y todo en [hi, n) es >= x.
    while (lo < hi) {
        std::size_t mid = lo + (hi - lo) / 2;
        probes++;
        if (items[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

#endif

// La estabilidad con un ejemplo chico y con el archivo de términos.
// Uso: stability archivo_de_terminos
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>

#include "lab/terms_io.h"

namespace {

struct Exam {
    int score;
    std::string name;
};

// La partición de la clase, sobre registros que se comparan solo por nota.
std::size_t partition_by_score(std::vector<Exam>& items, std::size_t lo, std::size_t hi) {
    int pivot = items[lo].score;
    std::size_t boundary = lo;
    for (std::size_t scan = lo + 1; scan < hi; scan++) {
        if (items[scan].score < pivot) {
            boundary++;
            std::swap(items[boundary], items[scan]);
        }
    }
    std::swap(items[lo], items[boundary]);
    return boundary;
}

void print_exams(const char* label, const std::vector<Exam>& items) {
    std::cout << label;
    for (const Exam& exam : items) {
        std::cout << " " << exam.score << exam.name;
    }
    std::cout << "\n";
}

// Ordena n registros con std::sort por una clave de 0 a 2, y cuenta vecinos empatados invertidos.
int inverted_ties(int n) {
    std::mt19937 rng(1);
    std::vector<Exam> items;
    for (int i = 0; i < n; i++) {
        items.push_back(Exam{static_cast<int>(rng() % 3), std::to_string(100 + i)});
    }
    std::sort(items.begin(), items.end(), [](const Exam& a, const Exam& b) { return a.score < b.score; });
    int inverted = 0;
    for (std::size_t i = 1; i < items.size(); i++) {
        if (items[i - 1].score == items[i].score && items[i - 1].name > items[i].name) {
            inverted++;
        }
    }
    return inverted;
}

std::size_t same_as(const std::vector<Term>& a, const std::vector<Term>& b) {
    std::size_t same = 0;
    for (std::size_t i = 0; i < a.size(); i++) {
        if (a[i].text == b[i].text) {
            same++;
        }
    }
    return same;
}

}  // namespace

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: stability archivo_de_terminos\n";
        return 2;
    }
    std::vector<Exam> exams = {{2, "a"}, {3, "b"}, {3, "c"}, {1, "d"}};
    print_exams("antes:   ", exams);
    partition_by_score(exams, 0, exams.size());
    print_exams("partido: ", exams);
    std::printf("std::sort con 16 elementos, empates invertidos: %d\n", inverted_ties(16));
    std::printf("std::sort con 17 elementos, empates invertidos: %d\n", inverted_ties(17));

    std::vector<Term> file_order;
    if (!load_terms(argv[1], file_order)) {
        std::cerr << "no se pudo leer " << argv[1] << "\n";
        return 1;
    }
    auto by_text = [](const Term& a, const Term& b) { return a.text < b.text; };
    auto by_weight = [](const Term& a, const Term& b) { return a.weight > b.weight; };
    std::vector<Term> sorted_terms = file_order;
    std::sort(sorted_terms.begin(), sorted_terms.end(), by_text);

    std::vector<Term> with_stable = sorted_terms;
    std::stable_sort(with_stable.begin(), with_stable.end(), by_weight);
    std::vector<Term> with_sort = sorted_terms;
    std::sort(with_sort.begin(), with_sort.end(), by_weight);

    std::printf("líneas: %zu\n", file_order.size());
    std::printf("std::stable_sort, iguales al archivo: %zu\n", same_as(with_stable, file_order));
    std::printf("std::sort,        iguales al archivo: %zu\n", same_as(with_sort, file_order));
    return 0;
}

// Mide los ordenamientos de la clase. Se compila con -O2 y sin sanitizers, con mediana de 5.
// Los tiempos dependen de la máquina.
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <vector>

#include "bench.h"
#include "inputs.h"
#include "int_sorts.h"

namespace {

const int REPS = 5;
const unsigned SEED = 2026;

template <typename Sort>
double millis(const std::vector<int>& input, Sort sort) {
    std::vector<std::vector<int>> copies(REPS, input);
    int rep = 0;
    double seconds = median_seconds(REPS, [&] {
        sort(copies[rep]);
        keep(copies[rep][0]);
        rep++;
    });
    return seconds * 1000;
}

void row(const char* name, const std::vector<int>& input) {
    long long ignored = 0;
    std::printf("%-10s %8.2f", name, millis(input, [&](std::vector<int>& v) { merge_sort_ints(v, ignored); }));
    std::printf(" %8.2f", millis(input, [&](std::vector<int>& v) { quick_sort_first_ints(v, ignored); }));
    std::printf(" %8.2f", millis(input, [&](std::vector<int>& v) { quick_sort_random_ints(v, SEED, ignored); }));
    std::printf(" %8.2f", millis(input, [&](std::vector<int>& v) { quick_sort_three_ints(v, SEED, ignored); }));
    std::printf(" %8.2f", millis(input, [](std::vector<int>& v) { std::sort(v.begin(), v.end()); }));
    std::printf(" %8.2f\n", millis(input, [](std::vector<int>& v) { std::stable_sort(v.begin(), v.end()); }));
    keep(ignored);
}

}  // namespace

int main() {
    const std::size_t n = 16000;
    std::printf("milisegundos con n = %zu\n", n);
    std::printf("%-10s %8s %8s %8s %8s %8s %8s\n", "entrada", "merge", "q.primero", "q.azar", "q.tres",
                "std::sort", "stable");
    row("al azar", random_input(n, SEED));
    row("ordenada", sorted_input(n));
    row("10 valores", repeated_input(n, 10, SEED));
    row("iguales", std::vector<int>(n, 7));

    std::printf("\nentrada al azar, milisegundos al duplicar n\n");
    std::printf("%8s %8s %8s %8s %9s %8s\n", "n", "merge", "q.azar", "q.tres", "std::sort", "stable");
    for (std::size_t size : {250000, 500000, 1000000}) {
        std::vector<int> input = random_input(size, SEED);
        long long ignored = 0;
        std::printf("%8zu", size);
        std::printf(" %8.1f", millis(input, [&](std::vector<int>& v) { merge_sort_ints(v, ignored); }));
        std::printf(" %8.1f", millis(input, [&](std::vector<int>& v) { quick_sort_random_ints(v, SEED, ignored); }));
        std::printf(" %8.1f", millis(input, [&](std::vector<int>& v) { quick_sort_three_ints(v, SEED, ignored); }));
        std::printf(" %9.1f", millis(input, [](std::vector<int>& v) { std::sort(v.begin(), v.end()); }));
        std::printf(" %8.1f\n", millis(input, [](std::vector<int>& v) { std::stable_sort(v.begin(), v.end()); }));
        keep(ignored);
    }
    return 0;
}

// El árbol de llamadas de mergesort para n = 8: primero las divisiones, después las mezclas.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

namespace {

struct Level {
    std::string runs;
    long long comparisons = 0;
    long long copied = 0;
};

std::string show(const std::vector<int>& items, std::size_t lo, std::size_t hi) {
    std::string text = "[";
    for (std::size_t i = lo; i < hi; i++) {
        text += (i == lo ? "" : " ") + std::to_string(items[i]);
    }
    return text + "] ";
}

void sort_range(std::vector<int>& items, std::size_t lo, std::size_t hi, std::size_t depth,
                std::vector<Level>& down, std::vector<Level>& up) {
    if (down.size() <= depth) {
        down.resize(depth + 1);
        up.resize(depth + 1);
    }
    down[depth].runs += show(items, lo, hi);
    if (hi - lo < 2) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    sort_range(items, lo, mid, depth + 1, down, up);
    sort_range(items, mid, hi, depth + 1, down, up);

    std::vector<int> merged;
    std::size_t left = lo;
    std::size_t right = mid;
    while (left < mid && right < hi) {
        up[depth].comparisons++;
        merged.push_back(items[right] < items[left] ? items[right++] : items[left++]);
    }
    while (left < mid) {
        merged.push_back(items[left++]);
    }
    while (right < hi) {
        merged.push_back(items[right++]);
    }
    for (std::size_t i = lo; i < hi; i++) {
        items[i] = merged[i - lo];
        up[depth].copied++;
    }
    up[depth].runs += show(items, lo, hi);
}

}  // namespace

int main() {
    std::vector<int> items = {5, 2, 8, 1, 9, 3, 7, 4};
    std::vector<Level> down;
    std::vector<Level> up;
    sort_range(items, 0, items.size(), 0, down, up);

    std::cout << "dividir\n";
    for (std::size_t depth = 0; depth < down.size(); depth++) {
        std::cout << "  nivel " << depth << ": " << down[depth].runs << "\n";
    }
    std::cout << "mezclar\n";
    for (std::size_t depth = up.size() - 1; depth-- > 0;) {
        std::cout << "  nivel " << depth << ": " << up[depth].runs << "\n";
        std::cout << "           " << up[depth].comparisons << " comparaciones, "
                  << up[depth].copied << " elementos copiados\n";
    }
    return 0;
}

// Sigue paso a paso las dos particiones de la clase.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

namespace {

void print_items(const std::vector<int>& items) {
    for (std::size_t i = 0; i < items.size(); i++) {
        std::cout << (i == 0 ? "" : " ") << items[i];
    }
}

void trace_first(std::vector<int> items) {
    std::cout << "pivote = primer elemento = " << items[0] << "\n";
    int pivot = items[0];
    std::size_t boundary = 0;
    for (std::size_t scan = 1; scan < items.size(); scan++) {
        if (items[scan] < pivot) {
            boundary++;
            std::swap(items[boundary], items[scan]);
        }
        std::cout << "  scan=" << scan << " boundary=" << boundary << "  ";
        print_items(items);
        std::cout << "\n";
    }
    std::swap(items[0], items[boundary]);
    std::cout << "  pivote a su lugar ";
    print_items(items);
    std::cout << "  (posición " << boundary << ")\n";
}

void trace_three(std::vector<int> items, int pivot) {
    std::cout << "pivote = " << pivot << "\n";
    std::size_t less_end = 0;
    std::size_t scan = 0;
    std::size_t greater_start = items.size();
    while (scan < greater_start) {
        if (items[scan] < pivot) {
            std::swap(items[less_end], items[scan]);
            less_end++;
            scan++;
        } else if (pivot < items[scan]) {
            greater_start--;
            std::swap(items[scan], items[greater_start]);
        } else {
            scan++;
        }
        std::cout << "  menores_fin=" << less_end << " scan=" << scan << " mayores_inicio="
                  << greater_start << "  ";
        print_items(items);
        std::cout << "\n";
    }
}

}  // namespace

int main() {
    trace_first({5, 2, 8, 1, 9, 3, 7, 4});
    trace_three({3, 5, 3, 1, 3, 2, 5, 3}, 3);
    return 0;
}

// Sigue la búsqueda binaria del primer elemento mayor o igual a x.
#include <cstddef>
#include <iostream>
#include <vector>

namespace {

void trace(const std::vector<int>& items, int x) {
    std::cout << "x = " << x << "\n";
    std::size_t lo = 0;
    std::size_t hi = items.size();
    while (lo < hi) {
        std::size_t mid = lo + (hi - lo) / 2;
        std::cout << "  lo=" << lo << " hi=" << hi << " mid=" << mid << " items[mid]=" << items[mid]
                  << (items[mid] < x ? " < x" : " >= x") << "\n";
        if (items[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    std::cout << "  termina con lo=hi=" << lo << "\n";
}

}  // namespace

int main() {
    std::vector<int> items = {2, 3, 3, 5, 8, 8, 9};
    trace(items, 8);
    trace(items, 4);
    trace(items, 10);
    return 0;
}

// Busca palabras en el diccionario con std::lower_bound y cuenta las comparaciones.
// Uso: word_search archivo_de_palabras palabra...
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: word_search archivo_de_palabras palabra...\n";
        return 2;
    }
    std::ifstream file(argv[1]);
    std::vector<std::string> words;
    std::string line;
    while (std::getline(file, line)) {
        words.push_back(line);
    }
    if (words.empty()) {
        std::cerr << "no se pudo leer " << argv[1] << "\n";
        return 1;
    }
    std::printf("%zu palabras; ordenado por bytes: %s\n", words.size(),
                std::is_sorted(words.begin(), words.end()) ? "sí" : "no");
    for (int i = 2; i < argc; i++) {
        std::string wanted = argv[i];
        long long comparisons = 0;
        auto found = std::lower_bound(words.begin(), words.end(), wanted,
                                      [&comparisons](const std::string& word, const std::string& x) {
                                          comparisons++;
                                          return word < x;
                                      });
        bool present = found != words.end() && *found == wanted;
        std::printf("%-10s %2lld comparaciones, %s", wanted.c_str(), comparisons, present ? "está" : "no está");
        if (!present && found != words.end()) {
            std::printf("; la siguiente es %s", found->c_str());
        }
        std::printf("\n");
    }
    return 0;
}

// Error a propósito: <= no es un orden estricto, y std::sort exige uno.
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> items(100, 7);
    std::sort(items.begin(), items.end(), [](int a, int b) { return a <= b; });
    std::cout << "terminó\n";
    return 0;
}

// Error a propósito: con el primero como pivote, una entrada ordenada recurre n niveles.
// Uso: deep_recursion n
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>

namespace {

void quick_first(std::vector<int>& items, std::size_t lo, std::size_t hi) {
    if (hi - lo < 2) {
        return;
    }
    int pivot = items[lo];
    std::size_t boundary = lo;
    for (std::size_t scan = lo + 1; scan < hi; scan++) {
        if (items[scan] < pivot) {
            boundary++;
            std::swap(items[boundary], items[scan]);
        }
    }
    std::swap(items[lo], items[boundary]);
    quick_first(items, lo, boundary);
    quick_first(items, boundary + 1, hi);
}

}  // namespace

int main(int argc, char** argv) {
    std::size_t n = argc > 1 ? static_cast<std::size_t>(std::atol(argv[1])) : 1000;
    std::vector<int> items(n);
    for (std::size_t i = 0; i < n; i++) {
        items[i] = static_cast<int>(i);
    }
    quick_first(items, 0, n);
    std::cout << "ordenó " << n << " elementos\n";
    return 0;
}

// Error a propósito: (lo + hi) / 2 con índices int hace overflow cuando el rango es grande.
#include <iostream>

namespace {

// Un arreglo enorme que no existe en memoria: el elemento i vale i.
bool is_at_least(int i, int x) {
    return i >= x;
}

}  // namespace

int main() {
    int lo = 0;
    int hi = 2000000000;
    int x = 1500000000;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (is_at_least(mid, x)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    std::cout << "primero >= x: " << lo << "\n";
    return 0;
}