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