// El medidor de la semana 3.
#ifndef BENCH_H
#define BENCH_H

#include <algorithm>
#include <chrono>
#include <cstddef>
#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;
    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());
    std::size_t middle = times.size() / 2;
    if (times.size() % 2 == 1) {
        return times[middle];
    }
    return (times[middle - 1] + times[middle]) / 2;
}

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

#endif

// Muestra cuándo cambia la capacidad de un std::vector al insertar.
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    std::cout << "size 0: capacity " << v.capacity() << "\n";
    std::size_t last = v.capacity();
    for (int i = 0; i < 1000; i++) {
        v.push_back(i);
        if (v.capacity() != last) {
            last = v.capacity();
            std::cout << "size " << v.size() << ": capacity " << last << "\n";
        }
    }
    return 0;
}

// El molde para pedir un bloque y llenarlo sin fugas, aunque una copia falle.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>

// Lanza una excepción si la cadena de origen está vacía, para poder probar el camino del error.
std::string checked_copy(const std::string& text) {
    if (text.empty()) {
        throw std::runtime_error("cadena vacía");
    }
    return text;
}

// Quien llama es owner del bloque que recibe.
std::string* copy_block(const std::string* source, std::size_t count) {
    std::string* fresh = new std::string[count];
    try {
        for (std::size_t i = 0; i < count; i++) {
            fresh[i] = checked_copy(source[i]);
        }
    } catch (...) {
        delete[] fresh;
        throw;
    }
    return fresh;
}

int main() {
    const std::string good[] = {"ana", "beto"};
    std::string* block = copy_block(good, 2);
    std::cout << "copió " << block[0] << " y " << block[1] << "\n";
    delete[] block;

    const std::string bad[] = {"ana", ""};
    try {
        block = copy_block(bad, 2);
        delete[] block;
    } catch (const std::runtime_error& error) {
        std::cout << "excepción: " << error.what() << "; el bloque nuevo ya se liberó\n";
    }
    return 0;
}

// Sacar del frente de un arreglo traslada todo lo demás.
#include <initializer_list>
#include <iostream>
#include <queue>
#include <vector>

#include "tracked.h"

int main() {
    for (int n : {1000, 2000, 4000}) {
        std::vector<Tracked> v;
        v.reserve(n);
        for (int i = 0; i < n; i++) {
            v.push_back(Tracked(i));
        }
        Tracked::reset();
        while (!v.empty()) {
            v.erase(v.begin());
        }
        std::cout << "vaciar " << n << " elementos por el frente: " << Tracked::counts.moves
                  << " movimientos\n";
    }

    std::queue<int> waiting;
    waiting.push(10);
    waiting.push(20);
    waiting.push(30);
    std::cout << "std::queue: front " << waiting.front() << ", back " << waiting.back();
    waiting.pop();
    std::cout << "; tras pop, front " << waiting.front() << ", size " << waiting.size() << "\n";
    return 0;
}

// Cuenta los traslados de n inserciones con tres reglas de crecimiento.
#include <cstdio>
#include <initializer_list>

#include "growth_math.h"

int main() {
    std::printf("%10s %12s %12s %14s\n", "n", "duplicar", "por 3/2", "de a 1000");
    for (long long n : {16LL, 17LL, 1000LL, 10000LL, 100000LL, 1000000LL, 10000000LL}) {
        std::printf("%10lld %12lld %12lld %14lld\n", n, copies_doubling(n),
                    copies_three_halves(n), copies_step(n, 1000));
    }
    return 0;
}

// Cuenta cuántos elementos se trasladan al crecer, sin guardar ningún elemento:
// solo sigue el tamaño y la capacidad durante n inserciones.
#ifndef GROWTH_MATH_H
#define GROWTH_MATH_H

// next_capacity recibe la capacidad actual y devuelve la siguiente.
template <typename Next>
long long copies_for(long long n, Next next_capacity) {
    long long copies = 0;
    long long capacity = 0;
    for (long long size = 0; size < n; size++) {
        if (size == capacity) {
            copies += size;
            capacity = next_capacity(capacity);
        }
    }
    return copies;
}

inline long long copies_doubling(long long n) {
    return copies_for(n, [](long long c) { return c == 0 ? 1 : 2 * c; });
}

inline long long copies_step(long long n, long long k) {
    return copies_for(n, [k](long long c) { return c + k; });
}

// Multiplica por 3/2, redondeando hacia abajo, pero siempre crece al menos en 1.
inline long long copies_three_halves(long long n) {
    return copies_for(n, [](long long c) { return c < 2 ? c + 1 : c + c / 2; });
}

#endif

// Mide n inserciones en un std::vector<int>, duplicando y creciendo de a 1000.
// Se compila con -O2 y sin sanitizers. Cada tiempo es la mediana de 5 repeticiones.
#include <cstddef>
#include <cstdio>
#include <initializer_list>
#include <vector>

#include "bench.h"

// push_back solo: el vector duplica en este g++.
void fill_doubling(int n) {
    std::vector<int> v;
    for (int i = 0; i < n; i++) {
        v.push_back(i);
    }
    keep(v[n - 1]);
}

// reserve antes de llenarse: el vector crece de a step.
void fill_step(int n, std::size_t step) {
    std::vector<int> v;
    for (int i = 0; i < n; i++) {
        if (v.size() == v.capacity()) {
            v.reserve(v.capacity() + step);
        }
        v.push_back(i);
    }
    keep(v[n - 1]);
}

int main() {
    std::printf("%9s %13s %13s\n", "n", "duplicar(ms)", "de a 1000(ms)");
    for (int n : {100000, 200000, 400000, 800000, 1600000}) {
        double doubling = median_seconds(5, [n] { fill_doubling(n); });
        double step = median_seconds(5, [n] { fill_step(n, 1000); });
        std::printf("%9d %13.3f %13.3f\n", n, doubling * 1000, step * 1000);
    }
    return 0;
}

// Cuántos objetos vivos hay: new T[n] frente a std::vector.
#include <iostream>
#include <vector>

#include "tracked.h"

// No tiene constructor sin argumentos.
class NoDefault {
public:
    explicit NoDefault(int value) : value_(value) {}
    int value() const { return value_; }

private:
    int value_;
};

void report(const char* what) {
    std::cout << what << ": vivos " << Tracked::counts.alive() << ", construidos sin argumentos "
              << Tracked::counts.default_built << ", destruidos " << Tracked::counts.destroyed << "\n";
}

int main() {
    Tracked::reset();
    Tracked* block = new Tracked[100];
    report("new Tracked[100]");
    delete[] block;
    report("delete[]");

    Tracked::reset();
    {
        std::vector<Tracked> v;
        v.reserve(100);
        report("reserve(100) de std::vector");
        v.push_back(Tracked(1));
        v.push_back(Tracked(2));
        report("dos push_back");
        v.pop_back();
        report("un pop_back");
    }
    report("fin del vector");

    std::vector<NoDefault> values;
    values.push_back(NoDefault(7));
    std::cout << "std::vector<NoDefault> compila, y guarda " << values[0].value() << "\n";
    return 0;
}

// ¿std::vector copia o mueve al crecer? Depende de si el movimiento es noexcept.
#include <iostream>
#include <string>
#include <type_traits>
#include <vector>

#include "tracked.h"

template <typename T>
void insert_sixteen(const char* name) {
    std::vector<T> v;
    T::reset();
    for (int i = 0; i < 16; i++) {
        v.push_back(T(i));
    }
    std::cout << name << ": capacity " << v.capacity() << ", copias " << T::counts.copies
              << ", movimientos " << T::counts.moves << "\n";
}

// El compilador escribe su movimiento, y es noexcept porque el de std::string lo es.
struct Student {
    std::string name;
};

// Declarar un destructor apaga el movimiento automático: "mover" termina copiando.
struct StudentWithDestructor {
    std::string name;
    ~StudentWithDestructor() {}
};

// Promete noexcept al construir, pero no al asignar.
struct Mismatched {
    Mismatched() = default;
    Mismatched(const Mismatched&) = default;
    Mismatched(Mismatched&&) noexcept {}
    Mismatched& operator=(const Mismatched&) = default;
    Mismatched& operator=(Mismatched&&) { return *this; }
};

int main() {
    insert_sixteen<Tracked>("mover con noexcept");
    insert_sixteen<TrackedRiskyMove>("mover sin noexcept");
    std::cout << std::boolalpha;
    std::cout << "std::string: " << std::is_nothrow_move_constructible_v<std::string> << "\n";
    std::cout << "Student: " << std::is_nothrow_move_constructible_v<Student> << "\n";
    std::cout << "StudentWithDestructor: "
              << std::is_nothrow_move_constructible_v<StudentWithDestructor> << "\n";
    std::cout << "Mismatched, al construir: " << std::is_nothrow_move_constructible_v<Mismatched>
              << ", al asignar: " << std::is_nothrow_move_assignable_v<Mismatched> << "\n";
    return 0;
}

// Aritmética de índices de un buffer circular: no guarda elementos, solo calcula posiciones.
#include <cstdio>

void print_positions(int capacity, int front, int size) {
    std::printf("capacidad %d, frente %d, tamaño %d:", capacity, front, size);
    for (int i = 0; i < size; i++) {
        std::printf(" e%d->%d", i, (front + i) % capacity);
    }
    std::printf("\n");
}

// A dónde va cada elemento al desenrollar, si el bloque nuevo empieza en el frente.
void print_unroll(int capacity, int front, int size) {
    std::printf("desenrollar:");
    for (int i = 0; i < size; i++) {
        std::printf(" %d->%d", (front + i) % capacity, i);
    }
    std::printf("\n");
}

// Sigue una serie de operaciones: E encola, D desencola. Solo mueve índices.
void trace(int capacity, const char* operations) {
    int front = 0;
    int size = 0;
    int next_label = 0;
    std::printf("%-3s %-9s %-7s %-6s %s\n", "op", "capacidad", "frente", "tamaño", "posición usada");
    for (const char* op = operations; *op != '\0'; op++) {
        int position;
        if (*op == 'E') {
            if (size == capacity) {
                capacity *= 2;
                front = 0;
                std::printf("%-3s %-9d %-7d %-6d (desenrolla)\n", "--", capacity, front, size);
            }
            position = (front + size) % capacity;
            size++;
            next_label++;
        } else {
            position = front;
            front = (front + 1) % capacity;
            size--;
        }
        std::printf("%-3c %-9d %-7d %-6d %d\n", *op, capacity, front, size, position);
    }
    std::printf("encolados: %d\n", next_label);
}

int main() {
    trace(4, "EEEDDEEEE");
    print_positions(8, 6, 4);
    print_positions(8, 5, 8);
    print_unroll(8, 5, 8);
    print_positions(16, 0, 8);
    return 0;
}

// Compara dos reglas para encoger. Solo sigue el tamaño y la capacidad, y cuenta
// cuántos elementos se trasladan. Crecer siempre es duplicar.
#include <cstdio>

// Por debajo de esta capacidad no se encoge.
const long MIN_CAPACITY = 4;

struct Simulated {
    long size = 0;
    long capacity = 0;
    long moved = 0;
    long resizes = 0;
};

void resize_to(Simulated& a, long capacity) {
    a.moved += a.size;
    a.resizes++;
    a.capacity = capacity;
}

void push(Simulated& a) {
    if (a.size == a.capacity) {
        resize_to(a, a.capacity == 0 ? 1 : 2 * a.capacity);
    }
    a.size++;
}

// divisor es 2 para encoger al llegar a la mitad, y 4 para hacerlo al llegar a un cuarto.
void pop(Simulated& a, long divisor) {
    a.size--;
    if (a.capacity > MIN_CAPACITY && a.size * divisor <= a.capacity) {
        resize_to(a, a.capacity / 2);
    }
}

void alternate_at_edge(long divisor) {
    Simulated a;
    for (int i = 0; i < 1025; i++) {
        push(a);
    }
    std::printf("tras 1025 push: size %ld, capacity %ld, traslados %ld\n", a.size, a.capacity, a.moved);
    long before = a.moved;
    for (int i = 0; i < 1000; i++) {
        pop(a, divisor);
        push(a);
    }
    std::printf("tras 2000 operaciones más: capacity %ld, traslados nuevos %ld\n", a.capacity,
                a.moved - before);
}

int main() {
    std::printf("Encoger al llegar a la mitad\n");
    alternate_at_edge(2);
    std::printf("Encoger al llegar a un cuarto\n");
    alternate_at_edge(4);
    return 0;
}

// Cuándo cambia de lugar el bloque de un std::vector.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

// Guarda la dirección como número: un puntero al bloque anterior ya no se debe usar.
std::uintptr_t address_of(const std::vector<int>& v) {
    return reinterpret_cast<std::uintptr_t>(v.data());
}

void count_block_changes(std::vector<int>& v, int pushes) {
    int changes = 0;
    std::uintptr_t last = address_of(v);
    for (int i = 0; i < pushes; i++) {
        v.push_back(i);
        if (address_of(v) != last) {
            changes++;
            last = address_of(v);
        }
    }
    std::cout << pushes << " push_back: capacity " << v.capacity() << ", el bloque cambió " << changes
              << " veces\n";
}

int main() {
    std::vector<int> plain;
    count_block_changes(plain, 1000);

    std::vector<int> reserved;
    reserved.reserve(1000);
    count_block_changes(reserved, 1000);

    // Un índice sigue siendo válido después de crecer: se vuelve a calcular la posición.
    std::vector<int> grades = {10, 20};
    std::size_t first = 0;
    for (int i = 0; i < 100; i++) {
        grades.push_back(i);
    }
    std::cout << "grades[first] = " << grades[first] << "\n";
    return 0;
}

// Qué queda en un std::vector si una excepción interrumpe el crecimiento.
#include <iostream>
#include <stdexcept>
#include <vector>

// Se puede copiar, y su movimiento no es noexcept: al crecer, el vector lo copia.
// Lanza una excepción cuando copies_left llega a 0.
class FailsOnCopy {
public:
    inline static int copies_left = 2;
    explicit FailsOnCopy(int value) : value_(value) {}
    FailsOnCopy(const FailsOnCopy& other) : value_(other.value_) {
        if (copies_left == 0) {
            throw std::runtime_error("falló una copia");
        }
        copies_left--;
    }
    FailsOnCopy(FailsOnCopy&& other) : value_(other.value_) { other.value_ = -1; }
    int value() const { return value_; }

private:
    int value_;
};

// Solo se puede mover, y el movimiento no es noexcept. Lanza una excepción cuando
// moves_left llega a 0.
class FailsOnMove {
public:
    inline static int moves_left = 100;
    explicit FailsOnMove(int value) : value_(value) {}
    FailsOnMove(const FailsOnMove&) = delete;
    FailsOnMove(FailsOnMove&& other) : value_(other.value_) {
        if (moves_left == 0) {
            throw std::runtime_error("falló un movimiento");
        }
        moves_left--;
        other.value_ = -1;
    }
    int value() const { return value_; }

private:
    int value_;
};

template <typename T>
void print_values(const std::vector<T>& v) {
    std::cout << "size " << v.size() << ", capacity " << v.capacity() << ", valores:";
    for (const T& item : v) {
        std::cout << " " << item.value();
    }
    std::cout << "\n";
}

int main() {
    std::vector<FailsOnCopy> copied;
    copied.reserve(4);
    for (int i = 1; i <= 4; i++) {
        copied.push_back(FailsOnCopy(i));
    }
    try {
        copied.push_back(FailsOnCopy(5));
    } catch (const std::runtime_error& error) {
        std::cout << "excepción: " << error.what() << "\n";
    }
    print_values(copied);

    std::vector<FailsOnMove> moved;
    moved.reserve(4);
    for (int i = 1; i <= 4; i++) {
        moved.push_back(FailsOnMove(i));
    }
    FailsOnMove extra(5);
    FailsOnMove::moves_left = 3;
    try {
        moved.push_back(std::move(extra));
    } catch (const std::runtime_error& error) {
        std::cout << "excepción: " << error.what() << "\n";
    }
    print_values(moved);
    return 0;
}

// Un tipo que cuenta lo que le pasa: sirve para contar copias y movimientos.
#ifndef TRACKED_H
#define TRACKED_H

struct Counts {
    long default_built = 0;  // construidos sin argumentos
    long value_built = 0;    // construidos con un valor
    long copy_built = 0;     // construidos como copia
    long move_built = 0;     // construidos por movimiento
    long copies = 0;         // copias: por construcción y por asignación
    long moves = 0;          // movimientos: por construcción y por asignación
    long destroyed = 0;

    // Cuántos objetos están vivos en este momento.
    long alive() const { return default_built + value_built + copy_built + move_built - destroyed; }
};

// Los contadores son static porque new T[n] llama al constructor sin argumentos:
// no hay cómo pasarle a cada objeto un contador propio.
// NoexceptMove dice si el movimiento promete no lanzar excepciones.
template <bool NoexceptMove>
class BasicTracked {
public:
    inline static Counts counts;

    BasicTracked() { counts.default_built++; }
    explicit BasicTracked(int value) : value_(value) { counts.value_built++; }
    ~BasicTracked() { counts.destroyed++; }

    BasicTracked(const BasicTracked& other) : value_(other.value_) {
        counts.copies++;
        counts.copy_built++;
    }
    BasicTracked& operator=(const BasicTracked& other) {
        value_ = other.value_;
        counts.copies++;
        return *this;
    }
    BasicTracked(BasicTracked&& other) noexcept(NoexceptMove) : value_(other.value_) {
        other.value_ = -1;
        counts.moves++;
        counts.move_built++;
    }
    BasicTracked& operator=(BasicTracked&& other) noexcept(NoexceptMove) {
        value_ = other.value_;
        if (this != &other) {
            other.value_ = -1;
        }
        counts.moves++;
        return *this;
    }

    int value() const { return value_; }
    static void reset() { counts = Counts{}; }

private:
    int value_ = 0;
};

using Tracked = BasicTracked<true>;            // su movimiento es noexcept
using TrackedRiskyMove = BasicTracked<false>;  // su movimiento no promete nada

#endif

// Afirmaciones de los apuntes sobre std::vector, comprobadas con este g++.
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "tracked.h"

int main() {
    std::vector<int> v;
    for (int i = 0; i < 1000; i++) {
        v.push_back(i);
    }
    std::cout << "1000 push_back: size " << v.size() << ", capacity " << v.capacity() << "\n";
    for (int i = 0; i < 999; i++) {
        v.pop_back();
    }
    std::cout << "999 pop_back: size " << v.size() << ", capacity " << v.capacity() << "\n";
    v.clear();
    std::cout << "clear: size " << v.size() << ", capacity " << v.capacity() << "\n";
    v.reserve(10);
    std::cout << "reserve(10): capacity " << v.capacity() << "\n";
    v.shrink_to_fit();
    std::cout << "shrink_to_fit: capacity " << v.capacity() << "\n";

    std::vector<int> big;
    big.reserve(100);
    big.push_back(1);
    std::vector<int> copy = big;
    std::cout << "copia de size 1 y capacity 100: capacity " << copy.capacity() << "\n";

    // reserve exacto en cada inserción: el vector nunca duplica.
    std::vector<TrackedRiskyMove> slow;
    TrackedRiskyMove::reset();
    for (int i = 0; i < 1000; i++) {
        slow.reserve(slow.size() + 1);
        slow.push_back(TrackedRiskyMove(i));
    }
    std::cout << "reserve(size + 1) antes de 1000 push_back: copias " << TrackedRiskyMove::counts.copies
              << "\n";

    // El argumento apunta dentro del bloque que se va a liberar.
    std::vector<std::string> names = {std::string(40, 'a')};
    names.push_back(names[0]);
    names.push_back(names[0]);
    std::cout << "push_back(names[0]) con el vector lleno: " << names.size() << " nombres, el último de "
              << names.back().size() << " letras\n";
    return 0;
}

// Error de compilación: new T[n] necesita un constructor sin argumentos.
class NoDefault {
public:
    explicit NoDefault(int value) : value_(value) {}
    int value() const { return value_; }

private:
    int value_;
};

int main() {
    NoDefault* block = new NoDefault[4];
    delete[] block;
    return 0;
}

// Error: inserta en el vector que está recorriendo.
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    for (int item : v) {
        if (item == 2) {
            v.push_back(item * 10);
        }
    }
    std::cout << v.size() << "\n";
    return 0;
}

// Error: un arreglo de cadenas que libera el bloque viejo antes de leer el argumento.
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>

class Names {
public:
    ~Names() { delete[] data_; }
    Names() = default;
    Names(const Names&) = delete;
    Names& operator=(const Names&) = delete;

    std::string& operator[](std::size_t i) { return data_[i]; }

    void push_back(const std::string& value) {
        if (size_ == capacity_) {
            std::size_t bigger = capacity_ == 0 ? 1 : 2 * capacity_;
            std::string* fresh = new std::string[bigger];
            for (std::size_t i = 0; i < size_; i++) {
                fresh[i] = std::move(data_[i]);
            }
            delete[] data_;
            data_ = fresh;
            capacity_ = bigger;
        }
        data_[size_] = value;
        size_++;
    }

private:
    std::string* data_ = nullptr;
    std::size_t size_ = 0;
    std::size_t capacity_ = 0;
};

int main() {
    Names names;
    names.push_back("Quispe");
    names.push_back(names[0]);
    std::cout << names[1] << "\n";
    return 0;
}

// Error: guarda una referencia a v[0] y luego hace push_back.
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30};
    int& first = v[0];
    v.push_back(40);
    std::cout << first << "\n";
    return 0;
}

// Comprueba con asserts las cuentas de los apuntes.
#include <algorithm>
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <random>
#include <vector>

#include "growth_math.h"
#include "tracked.h"

// La cuenta sin elementos debe coincidir con las copias reales de std::vector
// cuando el elemento no se puede mover con noexcept. Este g++ duplica la capacidad.
void simulated_copies_match_std_vector() {
    for (long n : {1L, 2L, 3L, 16L, 17L, 1000L, 5000L}) {
        std::vector<TrackedRiskyMove> v;
        TrackedRiskyMove::reset();
        for (long i = 0; i < n; i++) {
            v.push_back(TrackedRiskyMove(static_cast<int>(i)));
        }
        assert(TrackedRiskyMove::counts.copies == copies_doubling(n));
    }
}

// std::vector construye en la memoria nueva: nunca construye sin argumentos ni asigna.
void std_vector_builds_in_place() {
    std::vector<Tracked> v;
    Tracked::reset();
    for (int i = 0; i < 16; i++) {
        v.push_back(Tracked(i));
    }
    assert(Tracked::counts.default_built == 0);
    assert(Tracked::counts.moves == 31);
    assert(Tracked::counts.move_built == 31);
}

// De a k, con reserve desde fuera: el mismo vector, otra regla.
void step_copies_match_std_vector() {
    for (long n : {1000L, 1001L, 5000L, 7321L}) {
        std::vector<TrackedRiskyMove> v;
        TrackedRiskyMove::reset();
        for (long i = 0; i < n; i++) {
            if (v.size() == v.capacity()) {
                v.reserve(v.capacity() + 1000);
            }
            v.push_back(TrackedRiskyMove(static_cast<int>(i)));
        }
        assert(TrackedRiskyMove::counts.copies == copies_step(n, 1000));
    }
}

void doubling_bounds() {
    assert(copies_doubling(16) == 15);
    assert(copies_doubling(17) == 31);
    for (long long n = 2; n <= 5000; n++) {
        long long copies = copies_doubling(n);
        assert(copies >= n - 1);
        assert(copies <= 2 * n - 3);
    }
}

// k por m(m + 1)/2, con m = (n - 1) / k.
void step_formula() {
    for (long long k : {1LL, 7LL, 1000LL}) {
        for (long long n = 1; n <= 5000; n += 13) {
            long long m = (n - 1) / k;
            assert(copies_step(n, k) == k * m * (m + 1) / 2);
        }
    }
}

// Al crecer por 3/2 los traslados son como mucho 3n, más lo que se pierde al redondear.
// Basta mirar justo después de cada crecimiento: entre dos crecimientos n sube y los traslados no.
void three_halves_bound() {
    long long worst = 0;
    long long capacity = 1;
    while (capacity < 100000000) {
        worst = std::max(worst, copies_three_halves(capacity + 1) - 3 * (capacity + 1));
        capacity = capacity < 2 ? capacity + 1 : capacity + capacity / 2;
    }
    std::cout << "por 3/2: lo más que se pasa de 3n es " << worst << "\n";
    assert(worst <= 20);
}

// La misma regla de shrink_policies.cpp: encoger al llegar a un cuarto.
void quarter_rule_moves_at_most_two_per_operation() {
    std::mt19937 random(2026);
    for (int round = 0; round < 200; round++) {
        long size = 0, capacity = 0, moved = 0, operations = 0;
        long operations_wanted = 1 + static_cast<long>(random() % 20000);
        int bias = 20 + static_cast<int>(random() % 61);
        while (operations < operations_wanted) {
            bool is_push = size == 0 || static_cast<int>(random() % 100) < bias;
            if (is_push) {
                if (size == capacity) {
                    moved += size;
                    capacity = capacity == 0 ? 1 : 2 * capacity;
                }
                size++;
            } else {
                size--;
                if (capacity > 4 && size * 4 <= capacity) {
                    moved += size;
                    capacity /= 2;
                }
            }
            operations++;
            assert(moved <= 2 * operations);
        }
    }
}

// Subir y bajar todo, varias veces, es la serie que más redimensiona con esta regla.
void quarter_rule_on_full_sweeps() {
    long size = 0, capacity = 0, moved = 0, operations = 0;
    for (int sweep = 0; sweep < 5; sweep++) {
        for (int i = 0; i < 100000; i++) {
            if (size == capacity) {
                moved += size;
                capacity = capacity == 0 ? 1 : 2 * capacity;
            }
            size++;
            operations++;
            assert(moved <= 2 * operations);
        }
        for (int i = 0; i < 100000; i++) {
            size--;
            if (capacity > 4 && size * 4 <= capacity) {
                moved += size;
                capacity /= 2;
            }
            operations++;
            assert(moved <= 2 * operations);
        }
    }
}

int main() {
    simulated_copies_match_std_vector();
    std_vector_builds_in_place();
    step_copies_match_std_vector();
    doubling_bounds();
    step_formula();
    three_halves_bound();
    quarter_rule_moves_at_most_two_per_operation();
    quarter_rule_on_full_sweeps();
    std::cout << "ok\n";
    return 0;
}

"""Comprueba los ejemplos: los programas con errores fallan como dicen los apuntes, y
todo compila sin advertencias."""
import pathlib
import subprocess
import unittest

HERE = pathlib.Path(__file__).parent
FLAGS = ["-Wall", "-Wextra", "-std=c++20", "-g", "-fsanitize=address,undefined", "-I."]
BUILD = HERE / "build"


def run(command):
    return subprocess.run(command, cwd=HERE, text=True, stdin=subprocess.DEVNULL,
                          stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120)


class Examples(unittest.TestCase):
    def test_no_warnings(self):
        sources = sorted(path.name for path in HERE.glob("*.cpp"))
        for source in sources:
            with self.subTest(source=source):
                done = run(["g++", *FLAGS, "-fsyntax-only", source])
                self.assertEqual(done.stdout, "")
                self.assertEqual(done.returncode, 0)

    def test_claims(self):
        done = run(["build/claims_tests"])
        self.assertEqual(done.returncode, 0, done.stdout)
        self.assertTrue(done.stdout.endswith("ok\n"))

    def test_runtime_errors_are_caught_by_asan(self):
        for name in ["stale_reference", "push_in_range_for", "self_push"]:
            with self.subTest(program=name):
                target = BUILD / name
                compiled = run(["g++", *FLAGS, f"errors/{name}.cpp", "-o", str(target)])
                self.assertEqual(compiled.stdout, "", "debe compilar sin advertencias")
                done = run([str(target)])
                self.assertNotEqual(done.returncode, 0)
                self.assertIn("heap-use-after-free", done.stdout)

    def test_new_array_needs_default_constructor(self):
        done = run(["g++", "-std=c++20", "-fsyntax-only", "errors/no_default.cpp"])
        self.assertNotEqual(done.returncode, 0)
        self.assertIn("no matching function", done.stdout)

    def test_programs_finish_cleanly(self):
        for name in ["capacity_growth", "growth_count", "shrink_policies", "move_or_copy",
                     "strong_guarantee", "lifetimes", "stable_refs", "vector_facts",
                     "front_removal", "ring_trace", "copy_block"]:
            with self.subTest(program=name):
                done = run([f"build/{name}"])
                self.assertEqual(done.returncode, 0, done.stdout)

    def test_public_code_has_no_circular_buffer_class(self):
        # El buffer circular se implementa en el laboratorio de la semana 5.
        for path in list(HERE.glob("*.cpp")) + list(HERE.glob("*.h")) + list((HERE / "lab").glob("*")):
            if path.is_file():
                self.assertNotIn("ArrayDeque", path.read_text(encoding="utf-8"))


if __name__ == "__main__":
    unittest.main()

"""Pruebas del laboratorio. LAB_DIR dice qué carpeta se prueba: lab o solution.

Cada prueba de vector_tests corre en un proceso aparte y con sanitizers: una fuga o un
acceso inválido la hace fallar, aunque el resultado parezca correcto."""
import os
import pathlib
import re
import subprocess
import unittest

HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
BUILD = HERE / "build" / LAB_DIR
TEST_SOURCE = HERE / "lab" / "vector_tests.cpp"


def run(command):
    return subprocess.run(command, cwd=HERE, text=True, stdin=subprocess.DEVNULL,
                          stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120)


def short_report(text):
    """Deja lo útil: la aserción, el tipo de error y las líneas de su código."""
    useful = [line for line in text.splitlines()
              if "Assertion" in line or "ERROR:" in line or "SUMMARY:" in line
              or "vector.h" in line or "vector_tests.cpp" in line]
    return "\n".join(useful[:12]) or text.strip()


class VectorTests(unittest.TestCase):
    pass


def make_test(name):
    def test(self):
        done = run([str(BUILD / "vector_tests"), name])
        self.assertEqual(done.returncode, 0, short_report(done.stdout))
    return test


for test_name in re.findall(r'\{"(\w+)", \w+\}', TEST_SOURCE.read_text(encoding="utf-8")):
    setattr(VectorTests, f"test_{test_name}", make_test(test_name))


class Measurement(unittest.TestCase):
    def test_counts_match_the_theory(self):
        done = run([str(BUILD / "growth_bench"), "--counts"])
        self.assertEqual(done.returncode, 0, short_report(done.stdout))
        rows = {}
        for line in done.stdout.splitlines():
            parts = line.split()
            if len(parts) == 3 and parts[0].isdigit():
                rows[int(parts[0])] = (int(parts[1]), int(parts[2]))
        for n, (doubling, step) in rows.items():
            power = 1
            total = 0
            while power < n:
                total += power
                power *= 2
            m = (n - 1) // 1000
            self.assertEqual(doubling, total, f"copias duplicando con n = {n}")
            self.assertEqual(step, 1000 * m * (m + 1) // 2, f"copias de a 1000 con n = {n}")
        self.assertEqual(len(rows), 4)

    def test_report_is_written(self):
        report = HERE / LAB_DIR / "report.md"
        self.assertTrue(report.exists(), f"falta {report.name}")
        self.assertNotIn("(escriban aquí)", report.read_text(encoding="utf-8"))


if __name__ == "__main__":
    unittest.main()

"""Vuelve a correr los comandos que aparecen en los apuntes y en las diapositivas, y
comprueba que el código citado existe de verdad en los archivos públicos de esta carpeta."""
import os
import pathlib
import platform
import re
import subprocess
import unittest

try:
    import pty
except ImportError:
    pty = None

HERE = pathlib.Path(__file__).parent
ROOT = HERE.parent.parent
NOTES = ROOT / "notes" / "week-04.md"
SLIDES = ROOT / "slides" / "week-04.tex"
# Antes de un bloque cuya salida cambia con la máquina, como los tiempos. No se compara.
SYSTEM_DEPENDENT = "<!-- depende del sistema -->"
# Antes de un informe de ASan o de un error del compilador. Puede omitir líneas, pero no
# cambiarlas ni reordenarlas. Las direcciones y los números de proceso no se comparan.
REPORT = "<!-- informe recortado -->"
REPORT_MACHINE = "aarch64"


def normalize(text):
    # Según el idioma del entorno, g++ usa comillas tipográficas o rectas.
    return text.replace("‘", "'").replace("’", "'")


def run_shell(command):
    done = subprocess.run(["bash", "-c", command], cwd=HERE, text=True, encoding="utf-8",
                          stdin=subprocess.DEVNULL, stdout=subprocess.PIPE,
                          stderr=subprocess.STDOUT, timeout=120)
    return normalize(done.stdout)


def clean_lines(text):
    return [line.rstrip() for line in text.splitlines()]


def stable(line):
    """Quita de una línea de informe lo que cambia en cada corrida."""
    line = re.sub(r"0x[0-9a-f]+", "ADDR", line.strip())
    line = re.sub(r"BuildId: [0-9a-f]+", "BuildId: ID", line)
    return re.sub(r"==\d+==", "==N==", line)


def split_commands(lines):
    pairs = []
    for line in lines:
        if line.startswith("$ "):
            pairs.append((line[2:], []))
        elif pairs:
            pairs[-1][1].append(normalize(line.rstrip()))
    return pairs


def note_blocks(language):
    """Devuelve (líneas, marca) de cada bloque de los apuntes."""
    blocks, current, mark, previous = [], None, "", ""
    for raw in NOTES.read_text(encoding="utf-8").splitlines():
        line = re.sub(r"^> ?", "", raw)
        if current is None:
            if line.strip() == "```" + language:
                current, mark = [], previous.strip()
            elif line.strip():
                previous = line
        elif line.strip() == "```":
            blocks.append((current, mark))
            current = None
        else:
            current.append(line)
    return blocks


def slide_blocks(environments):
    text = SLIDES.read_text(encoding="utf-8")
    pattern = r"\\begin\{(?:%s)\}[^\n]*\n(.*?)\\end\{(?:%s)\}" % (environments, environments)
    return [match.group(1).splitlines() for match in re.finditer(pattern, text, re.S)]


def public_code_lines():
    """Solo archivos públicos: citar la solución del laboratorio hace fallar la prueba."""
    sources = list(HERE.glob("*.cpp")) + list(HERE.glob("*.h"))
    sources += list((HERE / "errors").glob("*.cpp"))
    sources += list((HERE / "lab").glob("*.cpp")) + list((HERE / "lab").glob("*.h"))
    lines = set()
    for source in sources:
        lines.update(line.strip() for line in source.read_text(encoding="utf-8").splitlines())
    return lines


class Base(unittest.TestCase):
    def assert_in_order(self, command, expected, actual):
        wanted = [stable(line) for line in expected if line.strip() and line.strip() != "..."]
        real = [stable(line) for line in actual]
        position = 0
        for line in wanted:
            with self.subTest(command=command, line=line):
                found = [i for i in range(position, len(real)) if real[i] == line]
                self.assertTrue(found, f"no aparece en la salida real: {line}")
                if found:
                    position = found[0] + 1


class NotesAreTrue(Base):
    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_terminal_blocks(self):
        checked = 0
        for lines, mark in note_blocks("text"):
            if not lines or not lines[0].startswith("$ ") or mark == REPORT:
                continue
            for command, expected in split_commands(lines):
                actual = clean_lines(run_shell(command))
                checked += 1
                if mark != SYSTEM_DEPENDENT:
                    with self.subTest(command=command):
                        self.assertEqual(actual, expected)
        self.assertGreater(checked, 8)

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    @unittest.skipUnless(platform.machine() == REPORT_MACHINE, "los informes son de aarch64")
    def test_reports(self):
        checked = 0
        for lines, mark in note_blocks("text"):
            if mark != REPORT:
                continue
            for command, expected in split_commands(lines):
                self.assert_in_order(command, expected, clean_lines(run_shell(command)))
                checked += 1
        self.assertGreater(checked, 2)

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_code_blocks_are_public_code(self):
        known = public_code_lines()
        for lines, _ in note_blocks("cpp"):
            for line in lines:
                if line.strip() and line.strip() != "...":
                    with self.subTest(line=line):
                        self.assertIn(line.strip(), known)

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_links_exist(self):
        text = NOTES.read_text(encoding="utf-8")
        for target in re.findall(r"\]\((\.\.?/[^)#\s]+)", text):
            with self.subTest(link=target):
                self.assertTrue((NOTES.parent / target).exists())

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_the_counts_in_the_review_questions(self):
        text = NOTES.read_text(encoding="utf-8")
        self.assertIn("1 + 2 + 4 + 8 = 15", text)
        output = run_shell("build/ring_trace")
        self.assertIn("e0->6 e1->7 e2->0 e3->1", output)


class SlidesAreTrue(Base):
    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    def test_program_output(self):
        for block in slide_blocks("terminal|salida|informe"):
            for command, expected in split_commands(block):
                self.assert_in_order(command, expected, clean_lines(run_shell(command)))

    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    def test_code_blocks_are_public_code(self):
        known = public_code_lines()
        for block in slide_blocks("codigochico|codigomini"):
            for line in block:
                if line.strip() and line.strip() != "...":
                    with self.subTest(line=line):
                        self.assertIn(line.strip(), known)


if __name__ == "__main__":
    unittest.main()