// Cuántas veces se llama a operator new al insertar un millón de enteros al final.
// Son conteos, no tiempos. Los de la biblioteca estándar dependen de su implementación.
#include <cstddef>
#include <deque>
#include <iostream>
#include <list>
#include <vector>

#include "alloc_counter.h"
#include "dlist.h"

namespace {

const int N = 1000000;

template <typename Sequence>
std::size_t count_allocations() {
    std::size_t before = allocation_count();
    Sequence sequence;
    for (int i = 0; i < N; i++) {
        sequence.push_back(i);
    }
    return allocation_count() - before;
}

}  // namespace

int main() {
    std::cout << "reservas para " << N << " push_back\n";
    std::cout << "std::vector: " << count_allocations<std::vector<int>>() << "\n";
    std::cout << "std::deque:  " << count_allocations<std::deque<int>>() << "\n";
    std::cout << "std::list:   " << count_allocations<std::list<int>>() << "\n";
    std::cout << "DList:       " << count_allocations<DList<int>>() << "\n";
    return 0;
}

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

// La lista doble: insertar y borrar en cualquier punto, hacia adelante y hacia atrás.
#include <iostream>

#include "dlist.h"

namespace {

void print(const DList<int>& list) {
    std::cout << "adelante:";
    for (int value : list) {
        std::cout << " " << value;
    }
    std::cout << "\natrás:   ";
    auto it = list.end();
    while (it != list.begin()) {
        --it;
        std::cout << " " << *it;
    }
    std::cout << "\n";
}

}  // namespace

int main() {
    DList<int> list;
    list.push_back(20);
    list.push_back(40);
    list.push_front(10);
    print(list);

    // Inserta antes del tercer elemento.
    auto it = list.begin();
    ++it;
    ++it;
    auto thirty = list.insert(it, 30);
    print(list);

    // Borra el 30 y sigue desde el siguiente.
    auto after = list.erase(thirty);
    std::cout << "después de borrar: " << *after << "\n";
    print(list);

    list.pop_front();
    list.pop_back();
    list.pop_back();
    std::cout << "tamaño " << list.size() << ", vacía: " << (list.empty() ? "sí" : "no") << "\n";
    list.check_invariants();
    return 0;
}

// Lista doblemente enlazada con nodo centinela, con iterador.
#ifndef DLIST_H
#define DLIST_H

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <random>
#include <vector>

// Invariantes:
// - sentinel_ nunca es nulo. Su value no es un elemento de la lista.
// - Los nodos forman un ciclo: para todo nodo x, x->next->prev == x y x->prev->next == x.
// - Siguiendo next desde sentinel_ se visitan size_ nodos antes de volver a sentinel_.
//
// T debe tener constructor por defecto, porque el centinela también guarda un T.
template <typename T>
class DList {
    struct Node {
        T value{};
        Node* prev = nullptr;
        Node* next = nullptr;
    };

public:
    // Con V = T se puede escribir el elemento; con V = const T, solo leerlo.
    template <typename V>
    class Iter {
    public:
        V& operator*() const { return node_->value; }
        Iter& operator++() {
            node_ = node_->next;
            return *this;
        }
        Iter& operator--() {
            node_ = node_->prev;
            return *this;
        }
        bool operator==(const Iter& other) const { return node_ == other.node_; }
        bool operator!=(const Iter& other) const { return node_ != other.node_; }

    private:
        friend class DList;
        explicit Iter(Node* node) : node_(node) {}
        Node* node_;
    };

    using iterator = Iter<T>;
    using const_iterator = Iter<const T>;

    DList() : sentinel_(new Node) {
        sentinel_->prev = sentinel_;
        sentinel_->next = sentinel_;
    }

    // La lista es owner de todos sus nodos, también del centinela.
    ~DList() {
        Node* node = sentinel_->next;
        while (node != sentinel_) {
            Node* next = node->next;  // se lee antes de borrar
            delete node;
            node = next;
        }
        delete sentinel_;
    }

    // Copiar y mover quedan prohibidos aquí. La regla de cinco va en el laboratorio.
    DList(const DList&) = delete;
    DList& operator=(const DList&) = delete;

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

    iterator begin() { return iterator(sentinel_->next); }
    iterator end() { return iterator(sentinel_); }
    const_iterator begin() const { return const_iterator(sentinel_->next); }
    const_iterator end() const { return const_iterator(sentinel_); }

    // Inserta antes de pos y devuelve un iterador al elemento nuevo.
    iterator insert(iterator pos, const T& value) {
        Node* after = pos.node_;
        Node* before = after->prev;
        Node* node = new Node{value, before, after};
        before->next = node;
        after->prev = node;
        size_++;
        return iterator(node);
    }

    // Borra el elemento de pos y devuelve un iterador al siguiente.
    iterator erase(iterator pos) {
        assert(pos != end());
        Node* node = pos.node_;
        Node* after = node->next;
        node->prev->next = after;
        after->prev = node->prev;
        delete node;
        size_--;
        return iterator(after);
    }

    void push_front(const T& value) { insert(begin(), value); }
    void push_back(const T& value) { insert(end(), value); }
    void pop_front() { erase(begin()); }
    void pop_back() { erase(iterator(sentinel_->prev)); }

    T& front() {
        assert(!empty());
        return sentinel_->next->value;
    }

    T& back() {
        assert(!empty());
        return sentinel_->prev->value;
    }

    // Vuelve a enlazar los nodos en orden aleatorio, sin moverlos en la memoria.
    // Los elementos quedan en otro orden. Solo sirve para medir.
    void shuffle_nodes(unsigned seed) {
        std::vector<Node*> nodes;
        nodes.reserve(size_);
        for (Node* node = sentinel_->next; node != sentinel_; node = node->next) {
            nodes.push_back(node);
        }
        std::mt19937 rng(seed);
        std::shuffle(nodes.begin(), nodes.end(), rng);
        Node* last = sentinel_;
        for (Node* node : nodes) {
            last->next = node;
            node->prev = last;
            last = node;
        }
        last->next = sentinel_;
        sentinel_->prev = last;
    }

    void check_invariants() const {
        assert(sentinel_ != nullptr);
        std::size_t count = 0;
        const Node* node = sentinel_;
        do {
            assert(node->next->prev == node);
            assert(node->prev->next == node);
            node = node->next;
            count++;
            assert(count <= size_ + 1);
        } while (node != sentinel_);
        assert(count == size_ + 1);
    }

private:
    Node* sentinel_;
    std::size_t size_ = 0;
};

#endif

// Operaciones en un extremo: un arreglo con capacidad que crece frente a una lista doble.
// Compilar con -O2 y sin sanitizers. Los tiempos dependen de la máquina.
#include <cstddef>
#include <cstdio>
#include <vector>

#include "bench.h"
#include "dlist.h"

namespace {

const int REPS = 7;

template <typename Sequence>
double push_then_pop(std::size_t n) {
    double seconds = median_seconds(REPS, [&] {
        Sequence sequence;
        for (std::size_t i = 0; i < n; i++) {
            sequence.push_back(static_cast<int>(i));
        }
        while (!sequence.empty()) {
            keep(sequence.back());
            sequence.pop_back();
        }
    });
    return seconds * 1e9 / static_cast<double>(2 * n);
}

}  // namespace

int main() {
    std::printf("%8s %10s %8s %7s\n", "n", "std::vector", "DList", "razón");
    for (std::size_t n = 10000; n <= 1000000; n *= 10) {
        double array_ns = push_then_pop<std::vector<int>>(n);
        double list_ns = push_then_pop<DList<int>>(n);
        std::printf("%8zu %10.2f %8.2f %6.1f\n", n, array_ns, list_ns, list_ns / array_ns);
    }
    return 0;
}

// Borrar mientras se recorre, de la forma correcta: erase devuelve el siguiente.
#include <iostream>

#include "dlist.h"

int main() {
    DList<int> list;
    for (int i = 1; i <= 8; i++) {
        list.push_back(i);
    }

    auto it = list.begin();
    while (it != list.end()) {
        if (*it % 2 == 0) {
            it = list.erase(it);
        } else {
            ++it;
        }
    }

    for (int value : list) {
        std::cout << value << " ";
    }
    std::cout << "\n";
    list.check_invariants();
    return 0;
}

// Qué sobrevive a una inserción: en una lista y en un arreglo dinámico.
// Se comparan direcciones guardadas como números: nunca se usa un puntero inválido.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

#include "dlist.h"

namespace {

std::intptr_t address(const int& value) {
    return reinterpret_cast<std::intptr_t>(&value);
}

const char* yes_no(bool value) {
    return value ? "sí" : "no";
}

}  // namespace

int main() {
    DList<int> list;
    list.push_back(1);
    int* in_list = &list.front();
    auto it = list.begin();
    for (int i = 0; i < 1000; i++) {
        list.push_back(i);
        list.push_front(i);
    }
    std::cout << "lista: el elemento sigue en la misma dirección: " << yes_no(in_list == &*it) << "\n";
    std::cout << "lista: *it = " << *it << ", *in_list = " << *in_list << "\n";

    std::vector<int> grows;
    grows.push_back(1);
    std::intptr_t before = address(grows[0]);
    std::size_t moved_times = 0;
    for (int i = 0; i < 1000; i++) {
        grows.push_back(i);
        if (address(grows[0]) != before) {
            moved_times++;
            before = address(grows[0]);
        }
    }
    std::cout << "vector sin reserve: el bloque cambió de lugar " << moved_times << " veces\n";

    std::vector<int> reserved;
    reserved.reserve(1001);
    reserved.push_back(1);
    before = address(reserved[0]);
    for (int i = 0; i < 1000; i++) {
        reserved.push_back(i);
    }
    std::cout << "vector con reserve: siguió en la misma dirección: "
              << yes_no(address(reserved[0]) == before) << "\n";
    return 0;
}

// Dónde quedan los elementos en la memoria: distancia de cada uno al primero.
// Las distancias dependen de la biblioteca y de la máquina.
#include <cstdint>
#include <iostream>
#include <vector>

#include "dlist.h"

namespace {

std::intptr_t address(const int& value) {
    return reinterpret_cast<std::intptr_t>(&value);
}

void print_offsets(const char* name, const DList<int>& list) {
    std::cout << name << ":";
    std::intptr_t first = address(*list.begin());
    for (const int& value : list) {
        std::cout << " " << address(value) - first;
    }
    std::cout << "\n";
}

}  // namespace

int main() {
    const int n = 6;

    std::vector<int> values(n);
    std::cout << "arreglo:";
    for (const int& value : values) {
        std::cout << " " << address(value) - address(values[0]);
    }
    std::cout << "\n";

    DList<int> list;
    for (int i = 0; i < n; i++) {
        list.push_back(i);
    }
    print_offsets("lista", list);

    // Otras reservas entre nodo y nodo, como en un programa que hace varias cosas a la vez.
    DList<int> mixed;
    std::vector<std::vector<int>> others;
    others.reserve(n);
    for (int i = 0; i < n; i++) {
        mixed.push_back(i);
        others.push_back(std::vector<int>(10 + 10 * i));
    }
    print_offsets("con otras reservas", mixed);

    list.shuffle_nodes(1);
    print_offsets("lista barajada", list);
    return 0;
}

// Una misma prueba para varias representaciones: el template pide operaciones, no una clase base.
#include <cassert>
#include <deque>
#include <iostream>
#include <list>

#include "dlist.h"

// Compila con cualquier D que tenga estas operaciones.
template <typename D>
void test_both_ends() {
    D deque;
    assert(deque.empty());
    deque.push_back(2);
    deque.push_back(3);
    deque.push_front(1);
    assert(deque.size() == 3);
    assert(deque.front() == 1);
    assert(deque.back() == 3);

    int expected = 1;
    for (int value : deque) {
        assert(value == expected);
        expected++;
    }

    deque.pop_front();
    deque.pop_back();
    assert(deque.size() == 1);
    assert(deque.front() == 2);
    assert(deque.back() == 2);
}

int main() {
    test_both_ends<DList<int>>();
    std::cout << "DList: ok\n";
    test_both_ends<std::list<int>>();
    std::cout << "std::list: ok\n";
    test_both_ends<std::deque<int>>();
    std::cout << "std::deque: ok\n";
    return 0;
}

// Una lista simple: insertar y sacar por el inicio, y llegar al elemento i.
#include <cstddef>
#include <iostream>
#include <string>

#include "slist.h"

namespace {

void print(SinglyList<std::string>& list) {
    std::cout << "[";
    for (std::size_t i = 0; i < list.size(); i++) {
        std::cout << (i == 0 ? "" : " ") << list.at(i);
    }
    std::cout << "] tamaño " << list.size() << "\n";
}

}  // namespace

int main() {
    SinglyList<std::string> list;
    list.push_front("lima");
    list.push_front("cusco");
    list.push_front("puno");
    print(list);

    list.pop_front();
    print(list);

    list.push_back("tacna");
    print(list);
    list.check_invariants();

    std::cout << "at(2) = " << list.at(2) << "\n";
    return 0;
}

// Lista simplemente enlazada, con puntero al primero y al último.
#ifndef SLIST_H
#define SLIST_H

#include <cassert>
#include <cstddef>

// Invariantes:
// - head_ es nulo si y solo si tail_ es nulo si y solo si size_ == 0.
// - Siguiendo next desde head_ se visitan size_ nodos, y el último es tail_.
// - tail_->next es nulo.
template <typename T>
class SinglyList {
public:
    SinglyList() = default;

    // La lista es owner de sus nodos: este ciclo los libera todos.
    ~SinglyList() {
        while (head_ != nullptr) {
            pop_front();
        }
    }

    // Copiar y mover quedan prohibidos para no distraernos. La regla de cinco va en el laboratorio.
    SinglyList(const SinglyList&) = delete;
    SinglyList& operator=(const SinglyList&) = delete;

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

    T& front() {
        assert(!empty());
        return head_->value;
    }

    void push_front(const T& value) {
        head_ = new Node{value, head_};
        if (tail_ == nullptr) {
            tail_ = head_;
        }
        size_++;
    }

    void pop_front() {
        assert(!empty());
        Node* old_head = head_;
        head_ = old_head->next;
        delete old_head;
        if (head_ == nullptr) {
            tail_ = nullptr;
        }
        size_--;
    }

    void push_back(const T& value) {
        Node* node = new Node{value, nullptr};
        if (tail_ == nullptr) {
            head_ = node;
        } else {
            tail_->next = node;
        }
        tail_ = node;
        size_++;
    }

    // Llegar al elemento i cuesta i saltos.
    T& at(std::size_t i) {
        assert(i < size_);
        Node* node = head_;
        for (std::size_t step = 0; step < i; step++) {
            node = node->next;
        }
        return node->value;
    }

    void check_invariants() const {
        assert((head_ == nullptr) == (size_ == 0));
        assert((tail_ == nullptr) == (size_ == 0));
        std::size_t count = 0;
        const Node* last = nullptr;
        for (const Node* node = head_; node != nullptr; node = node->next) {
            last = node;
            count++;
            assert(count <= size_);
        }
        assert(count == size_);
        assert(last == tail_);
    }

private:
    struct Node {
        T value;
        Node* next;
    };

    Node* head_ = nullptr;
    Node* tail_ = nullptr;
    std::size_t size_ = 0;
};

#endif

// Qué llamadas hace realmente un for por rango: un iterador que avisa cada vez que lo usan.
#include <iostream>

namespace {

class TraceIterator {
public:
    explicit TraceIterator(int current) : current_(current) {}

    int operator*() const {
        std::cout << "  operator*\n";
        return current_;
    }
    TraceIterator& operator++() {
        std::cout << "  operator++\n";
        current_++;
        return *this;
    }
    bool operator!=(const TraceIterator& other) const {
        std::cout << "  operator!=\n";
        return current_ != other.current_;
    }

private:
    int current_;
};

class TraceRange {
public:
    explicit TraceRange(int count) : count_(count) {}

    TraceIterator begin() const {
        std::cout << "  begin\n";
        return TraceIterator(0);
    }
    TraceIterator end() const {
        std::cout << "  end\n";
        return TraceIterator(count_);
    }

private:
    int count_;
};

}  // namespace

int main() {
    std::cout << "for por rango:\n";
    for (int value : TraceRange(2)) {
        std::cout << "valor " << value << "\n";
    }

    std::cout << "ciclo equivalente:\n";
    TraceRange range(2);
    auto it = range.begin();
    auto last = range.end();
    for (; it != last; ++it) {
        int value = *it;
        std::cout << "valor " << value << "\n";
    }
    return 0;
}

// Tipo para las pruebas: cuenta cuántos objetos viven y cuántas copias y movimientos hubo.
#ifndef TRACKED_H
#define TRACKED_H

#include <utility>

class Tracked {
public:
    struct Counts {
        long live = 0;
        long copies = 0;
        long moves = 0;
    };

    static Counts& counts() {
        static Counts values;
        return values;
    }

    Tracked() { counts().live++; }
    explicit Tracked(int value) : value_(value) { counts().live++; }
    Tracked(const Tracked& other) : value_(other.value_) {
        counts().live++;
        counts().copies++;
    }
    Tracked(Tracked&& other) noexcept : value_(std::exchange(other.value_, 0)) {
        counts().live++;
        counts().moves++;
    }
    Tracked& operator=(const Tracked& other) {
        value_ = other.value_;
        counts().copies++;
        return *this;
    }
    Tracked& operator=(Tracked&& other) noexcept {
        value_ = std::exchange(other.value_, 0);
        counts().moves++;
        return *this;
    }
    ~Tracked() { counts().live--; }

    int value() const { return value_; }
    bool operator==(const Tracked& other) const { return value_ == other.value_; }

private:
    int value_ = 0;
};

#endif

// Recorre n enteros sumándolos, con cuatro formas de guardarlos o de visitarlos.
// Compilar con -O2 y sin sanitizers. Los tiempos dependen de la máquina.
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"
#include "dlist.h"

namespace {

const int REPS = 5;
// Cada medición toca al menos esta cantidad de elementos, para que dure lo suficiente.
const std::size_t MIN_VISITS = 2000000;
const unsigned SEED = 2026;

template <typename Walk>
double nanos_per_element(std::size_t n, Walk walk) {
    std::size_t passes = std::max<std::size_t>(1, MIN_VISITS / n);
    double seconds = median_seconds(REPS, [&] {
        for (std::size_t pass = 0; pass < passes; pass++) {
            walk();
        }
    });
    return seconds * 1e9 / static_cast<double>(passes * n);
}

// Porcentaje de saltos entre elementos seguidos que avanzan exactamente `gap` bytes.
double percent_adjacent(const DList<int>& list, std::ptrdiff_t gap) {
    std::size_t hits = 0;
    std::size_t hops = 0;
    const int* previous = nullptr;
    for (const int& value : list) {
        if (previous != nullptr) {
            auto jump = reinterpret_cast<std::intptr_t>(&value) - reinterpret_cast<std::intptr_t>(previous);
            hits += jump == gap ? 1 : 0;
            hops++;
        }
        previous = &value;
    }
    return 100.0 * static_cast<double>(hits) / static_cast<double>(hops);
}

void measure(std::size_t n) {
    std::vector<int> values(n);
    std::iota(values.begin(), values.end(), 0);

    std::vector<std::size_t> order(n);
    std::iota(order.begin(), order.end(), std::size_t{0});
    std::mt19937 rng(SEED);
    std::shuffle(order.begin(), order.end(), rng);

    DList<int> list;
    for (std::size_t i = 0; i < n; i++) {
        list.push_back(values[i]);
    }

    long long expected = 0;
    for (int value : values) {
        expected += value;
    }

    auto sum_array = [&] {
        long long sum = 0;
        for (int value : values) {
            sum += value;
        }
        keep(sum);
    };
    auto sum_array_shuffled = [&] {
        long long sum = 0;
        for (std::size_t i : order) {
            sum += values[i];
        }
        keep(sum);
    };
    auto sum_list = [&] {
        long long sum = 0;
        for (int value : list) {
            sum += value;
        }
        keep(sum);
    };

    double array_ns = nanos_per_element(n, sum_array);
    double array_shuffled_ns = nanos_per_element(n, sum_array_shuffled);
    double list_ns = nanos_per_element(n, sum_list);
    double adjacent = percent_adjacent(list, 32);

    list.shuffle_nodes(SEED);
    list.check_invariants();
    double list_shuffled_ns = nanos_per_element(n, sum_list);
    double adjacent_shuffled = percent_adjacent(list, 32);

    long long check = 0;
    for (int value : list) {
        check += value;
    }

    std::printf("%8zu %8.2f %9.2f %8.2f %9.2f %8.1f %9.1f %7.1f%% %7.1f%% %s\n",
                n, array_ns, array_shuffled_ns, list_ns, list_shuffled_ns,
                list_ns / array_ns, list_shuffled_ns / list_ns,
                adjacent, adjacent_shuffled, check == expected ? "ok" : "MAL");
}

}  // namespace

int main() {
    std::printf("%8s %8s %9s %8s %9s %8s %9s %8s %8s\n",
                "n", "arreglo", "arr.baraj", "lista", "lis.baraj",
                "lis/arr", "lb/lista", "cont", "cont.b");
    for (std::size_t n = 1024; n <= 4194304; n *= 4) {
        measure(n);
    }
    return 0;
}

// Error a propósito: borrar el nodo actual dentro de un for por rango.
#include "../dlist.h"

int main() {
    DList<int> list;
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    auto it = list.begin();
    for (int value : list) {
        if (value == 1) {
            list.erase(it);  // el ++ oculto del for lee el next del nodo borrado
        }
    }
    return 0;
}

// Error a propósito: al insertar se olvida actualizar el prev del siguiente nodo.
// La lista se ve bien hacia adelante; check_invariants lo descubre.
#include <cassert>
#include <iostream>

class BrokenList {
    struct Node {
        int value = 0;
        Node* prev = nullptr;
        Node* next = nullptr;
    };

public:
    BrokenList() : sentinel_(new Node) {
        sentinel_->prev = sentinel_;
        sentinel_->next = sentinel_;
    }
    BrokenList(const BrokenList&) = delete;
    BrokenList& operator=(const BrokenList&) = delete;
    ~BrokenList() {
        Node* node = sentinel_->next;
        while (node != sentinel_) {
            Node* next = node->next;
            delete node;
            node = next;
        }
        delete sentinel_;
    }

    void push_front(int value) {
        Node* first = sentinel_->next;
        Node* node = new Node{value, sentinel_, first};
        sentinel_->next = node;
        // falta: first->prev = node;
    }

    void print() const {
        for (const Node* node = sentinel_->next; node != sentinel_; node = node->next) {
            std::cout << node->value << " ";
        }
        std::cout << std::endl;
    }

    void check_invariants() const {
        const Node* node = sentinel_;
        do {
            assert(node->next->prev == node);
            assert(node->prev->next == node);
            node = node->next;
        } while (node != sentinel_);
    }

private:
    Node* sentinel_;
};

int main() {
    BrokenList list;
    list.push_front(2);
    list.push_front(1);
    list.print();
    list.check_invariants();
    return 0;
}

// Error a propósito: usar un iterador de un vector después de que creció.
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values = {1, 2, 3};
    auto it = values.begin();
    values.push_back(4);  // la capacidad era 3: el bloque cambia de lugar
    std::cout << *it << "\n";
    return 0;
}

// Error a propósito: el destructor lee node->next después de borrar node.
struct Node {
    int value;
    Node* next;
};

class BadList {
public:
    BadList() = default;
    BadList(const BadList&) = delete;
    BadList& operator=(const BadList&) = delete;

    ~BadList() {
        for (Node* node = head_; node != nullptr; node = node->next) {
            delete node;
        }
    }

    void push_front(int value) { head_ = new Node{value, head_}; }

private:
    Node* head_ = nullptr;
};

int main() {
    BadList list;
    list.push_front(1);
    list.push_front(2);
    return 0;
}

"""Corre los ejemplos de la semana y comprueba lo que se puede contar: nunca tiempos absolutos."""
import pathlib
import re
import subprocess
import unittest

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


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


class Examples(unittest.TestCase):
    def test_list_tests_pass(self):
        done = run("build/test_structures")
        self.assertEqual(done.returncode, 0, done.stdout)

    def test_programs_exit_cleanly(self):
        for name in ["slist_demo", "dlist_demo", "trace_range", "invalidation", "erase_evens",
                     "same_interface", "alloc_count", "node_addresses"]:
            with self.subTest(program=name):
                done = run(f"build/{name}")
                self.assertEqual(done.returncode, 0, done.stdout)

    def test_allocations_are_counted(self):
        lines = dict(line.split(": ") for line in run("build/alloc_count").stdout.splitlines()
                     if ": " in line)
        self.assertEqual(int(lines["DList"]), 1000001)
        self.assertEqual(int(lines["std::list"]), 1000000)
        self.assertLess(int(lines["std::vector"]), 40)

    def test_shuffle_really_scatters_the_nodes(self):
        """Los porcentajes de nodos seguidos son conteos, y las sumas deben coincidir."""
        rows = run("build/traversal_bench").stdout.splitlines()[1:]
        self.assertEqual(len(rows), 7)
        for row in rows:
            fields = row.split()
            with self.subTest(n=fields[0]):
                self.assertEqual(fields[-1], "ok")
                self.assertGreater(float(fields[-3].rstrip("%")), 95.0)
                self.assertLess(float(fields[-2].rstrip("%")), 5.0)


class DeliberateErrors(unittest.TestCase):
    def build(self, name):
        binary = f"build/{name}"
        done = run(*SAN, f"errors/{name}.cpp", "-o", binary)
        self.assertEqual(done.returncode, 0, done.stdout)
        return run(binary)

    def test_use_after_delete(self):
        done = self.build("use_after_delete")
        self.assertNotEqual(done.returncode, 0)
        self.assertIn("heap-use-after-free", done.stdout)
        self.assertIn("errors/use_after_delete.cpp:14", done.stdout)

    def test_erase_in_range_for(self):
        done = self.build("erase_in_range_for")
        self.assertNotEqual(done.returncode, 0)
        self.assertIn("heap-use-after-free", done.stdout)
        self.assertRegex(done.stdout, re.compile(r"operator\+\+"))

    def test_stale_vector_iterator(self):
        done = self.build("stale_vector_iterator")
        self.assertNotEqual(done.returncode, 0)
        self.assertIn("heap-use-after-free", done.stdout)

    def test_forgot_prev_is_found_by_invariants(self):
        done = self.build("forgot_prev")
        self.assertNotEqual(done.returncode, 0)
        self.assertIn("1 2", done.stdout)
        self.assertIn("check_invariants", done.stdout)
        self.assertNotIn("AddressSanitizer", done.stdout)


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

"""Pruebas del laboratorio. LAB_DIR dice dónde están los deques: lab o solution.

Cada prueba corre en su propio proceso, con sanitizers: una fuga o un acceso inválido
la hace fallar aunque el resultado parezca correcto. Las dos representaciones pasan
por las mismas pruebas comunes, escritas como templates en lab/tests/deque_suite.h.
"""
import os
import pathlib
import re
import subprocess
import unittest

HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
BINARY = HERE / "build" / LAB_DIR / "deque_tests"
COMMON = [
    "new_is_empty", "push_back_keeps_order", "push_front_reverses", "as_stack", "as_queue",
    "growth_while_wrapped", "index_reads_and_writes", "range_for", "iterator_operators",
    "iterator_after_wrap", "copy_is_independent", "self_assignment",
    "move_leaves_empty_and_usable", "no_objects_left_behind", "rvalue_push_does_not_copy",
    "lvalue_push_copies_once", "push_own_element", "pop_releases_value", "random_ints",
    "random_strings",
]
ONLY_ARRAY = ["few_allocations", "capacity_doubles", "ring_reuses_space", "move_is_noexcept"]
ONLY_LINKED = ["one_allocation_per_push", "elements_stay_in_place", "move_assign_is_noexcept",
               "shuffle_nodes"]


def short_report(text):
    """Deja lo útil de un informe: el tipo de error y las líneas de sus archivos."""
    if "ERROR:" not in text and "runtime error" not in text:
        return text.strip()
    useful = [line.strip() for line in text.splitlines()
              if "ERROR:" in line or "SUMMARY:" in line or "runtime error" in line
              or re.search(r"(array_deque|linked_deque|deque_suite)\.h:\d+", line)]
    return "\n".join(useful[:12])


def build():
    done = subprocess.run(
        ["make", "--no-print-directory", f"LAB_DIR={LAB_DIR}", f"build/{LAB_DIR}/deque_tests"],
        cwd=HERE, text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
    )
    return done.returncode, done.stdout


def run_case(testcase, kind, name):
    done = subprocess.run(
        [str(BINARY), kind, name], cwd=HERE, text=True,
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120,
    )
    testcase.assertEqual(done.returncode, 0, short_report(done.stdout))


def add_cases(cls, kind, names):
    for name in names:
        def case(self, name=name):
            run_case(self, kind, name)
        setattr(cls, f"test_{name}", case)
    return cls


@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class Builds(unittest.TestCase):
    def test_builds_without_warnings(self):
        BINARY.unlink(missing_ok=True)
        code, output = build()
        self.assertEqual(code, 0, output)
        self.assertNotIn("warning", output)


@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestArrayDeque(unittest.TestCase):
    @classmethod
    def setUpClass(cls):
        code, output = build()
        if code != 0:
            raise AssertionError(output)


@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestLinkedDeque(unittest.TestCase):
    @classmethod
    def setUpClass(cls):
        code, output = build()
        if code != 0:
            raise AssertionError(output)


add_cases(TestArrayDeque, "array", COMMON + ONLY_ARRAY)
add_cases(TestLinkedDeque, "linked", COMMON + ONLY_LINKED)


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 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-05.md"
SLIDES = ROOT / "slides" / "week-05.tex"
# Antes de un bloque cuya salida cambia con el sistema. Se corre, pero no se compara.
SYSTEM_DEPENDENT = "<!-- depende del sistema -->"
# Antes de un informe de ASan. Puede omitir líneas, pero no cambiarlas ni reordenarlas.
# Las direcciones y los números de proceso no se comparan.
REPORT = "<!-- informe recortado -->"
# Los informes se capturaron en esta arquitectura: en otra cambian líneas de las bibliotecas.
REPORT_MACHINE = "aarch64"


def normalize(text):
    # Según el idioma del entorno, gcc 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 run_in_terminal(command):
    """Corre el comando en una terminal de verdad: así se intercala la salida del programa
    con el informe, igual que cuando ustedes lo corren."""
    master, slave = pty.openpty()
    process = subprocess.Popen(
        ["bash", "-c", command], cwd=HERE, stdin=subprocess.DEVNULL, stdout=slave, stderr=slave,
    )
    os.close(slave)
    data = b""
    while True:
        try:
            chunk = os.read(master, 4096)
        except OSError:
            break
        if not chunk:
            break
        data += chunk
    os.close(master)
    process.wait(timeout=120)
    text = data.decode("utf-8", errors="replace").replace("\r", "")
    return normalize(re.sub(r"\x1b\[[0-9;]*[mK]", "", text))


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())
    return re.sub(r"==\d+==", "==N==", line)


def split_commands(lines):
    """Parte un bloque de terminal en pares (comando, líneas de salida)."""
    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 known_code_lines():
    lines = set()
    sources = list(HERE.glob("*.cpp")) + list(HERE.glob("*.h")) + list((HERE / "errors").glob("*.cpp"))
    sources += list((HERE / "lab").glob("*.h")) + list((HERE / "lab" / "tests").glob("*"))
    for source in sources:
        lines.update(line.strip() for line in source.read_text(encoding="utf-8").splitlines())
    return lines


class ReportCheck(unittest.TestCase):
    def assert_in_order(self, command, expected, actual):
        """Las líneas esperadas aparecen en la salida real, en orden. '...' marca un recorte."""
        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(ReportCheck):
    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_terminal_blocks_in_notes(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, 5)

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

    @unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
    def test_code_blocks_in_notes_exist(self):
        known = known_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)


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

    # Algunos informes usan programas que compiló la prueba de los apuntes, que corre antes.
    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    @unittest.skipUnless(pty and platform.machine() == REPORT_MACHINE, "los informes son de aarch64")
    def test_reports_in_slides(self):
        for block in slide_blocks("informe"):
            for command, expected in split_commands(block):
                self.assert_in_order(command, expected, clean_lines(run_in_terminal(command)))

    @unittest.skipUnless(NOTES.exists() and SLIDES.exists(), "faltan los apuntes o las diapositivas")
    def test_measurements_in_slides_come_from_notes(self):
        """Los tiempos dependen de la máquina: las diapositivas copian los de los apuntes."""
        notes = NOTES.read_text(encoding="utf-8").splitlines()
        blocks = slide_blocks("medicion")
        self.assertGreater(len(blocks), 2)
        for block in blocks:
            for line in block:
                with self.subTest(line=line):
                    self.assertIn(line, notes)

    @unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
    def test_code_blocks_in_slides_exist(self):
        known = known_code_lines()
        for block in slide_blocks("codigo|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()