// Pruebas públicas del laboratorio. Cada una es un template: D es ArrayDeque o LinkedDeque.
// No hay clase base: la interfaz común es lo que estas pruebas usan.
#ifndef DEQUE_SUITE_H
#define DEQUE_SUITE_H

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <deque>
#include <memory>
#include <random>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include "alloc_counter.h"
#include "tracked.h"

template <typename D, typename T>
void assert_same(const D& mine, const std::deque<T>& model) {
    mine.check_invariants();
    assert(mine.size() == model.size());
    assert(mine.empty() == model.empty());
    if (!model.empty()) {
        assert(mine.front() == model.front());
        assert(mine.back() == model.back());
    }
    auto expected = model.begin();
    for (const T& value : mine) {
        assert(expected != model.end());
        assert(value == *expected);
        ++expected;
    }
    assert(expected == model.end());
}

template <typename D>
void test_new_is_empty() {
    D deque;
    assert(deque.size() == 0);
    assert(deque.empty());
    deque.check_invariants();
}

template <typename D>
void test_push_back_keeps_order() {
    D deque;
    for (int i = 0; i < 100; i++) {
        deque.push_back(i);
        assert(deque.front() == 0);
        assert(deque.back() == i);
        assert(deque.size() == static_cast<std::size_t>(i) + 1);
    }
    deque.check_invariants();
}

template <typename D>
void test_push_front_reverses() {
    D deque;
    for (int i = 0; i < 100; i++) {
        deque.push_front(i);
        assert(deque.front() == i);
        assert(deque.back() == 0);
    }
    for (int i = 0; i < 100; i++) {
        assert(deque[i] == 99 - i);
    }
    deque.check_invariants();
}

template <typename D>
void test_as_stack() {
    D deque;
    for (int i = 0; i < 50; i++) {
        deque.push_back(i);
    }
    for (int i = 49; i >= 0; i--) {
        assert(deque.back() == i);
        deque.pop_back();
    }
    assert(deque.empty());
    deque.check_invariants();
}

template <typename D>
void test_as_queue() {
    D deque;
    for (int i = 0; i < 50; i++) {
        deque.push_back(i);
    }
    for (int i = 0; i < 50; i++) {
        assert(deque.front() == i);
        deque.pop_front();
    }
    assert(deque.empty());
    deque.check_invariants();
}

// El frente da vueltas por el buffer y además crece: aquí se nota si el buffer se desenrolla mal.
template <typename D>
void test_growth_while_wrapped() {
    D deque;
    std::deque<int> model;
    int next = 0;
    for (int round = 0; round < 200; round++) {
        for (int i = 0; i < 3; i++) {
            deque.push_back(next);
            model.push_back(next);
            next++;
        }
        deque.push_front(next);
        model.push_front(next);
        next++;
        deque.pop_back();
        model.pop_back();
        deque.pop_front();
        model.pop_front();
        assert_same(deque, model);
    }
}

template <typename D>
void test_index_reads_and_writes() {
    D deque;
    for (int i = 0; i < 20; i++) {
        deque.push_back(i);
    }
    for (int i = 0; i < 5; i++) {
        deque.pop_front();
        deque.push_back(100 + i);
    }
    deque[0] = -1;
    deque[19] = -2;
    const D& view = deque;
    assert(view[0] == -1);
    assert(view[1] == 6);
    assert(view[15] == 100);
    assert(view[19] == -2);
}

template <typename D>
void test_range_for() {
    D deque;
    int sum = 0;
    for (int value : deque) {
        sum += value;
    }
    assert(sum == 0);

    for (int i = 1; i <= 10; i++) {
        deque.push_back(i);
    }
    for (int& value : deque) {
        value *= 2;
    }
    const D& view = deque;
    for (const int& value : view) {
        sum += value;
    }
    assert(sum == 110);
}

template <typename D>
void test_iterator_operators() {
    D deque;
    assert(!(deque.begin() != deque.end()));
    assert(deque.begin() == deque.end());

    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    auto it = deque.begin();
    assert(it != deque.end());
    assert(*it == 1);
    assert(*++it == 2);
    *it = 20;
    assert(deque[1] == 20);
    ++(++it);
    assert(it == deque.end());
}

template <typename D>
void test_iterator_after_wrap() {
    D deque;
    for (int i = 0; i < 4; i++) {
        deque.push_back(i);
    }
    deque.pop_front();
    deque.pop_front();
    deque.push_back(4);
    deque.push_back(5);
    deque.push_front(1);
    int expected = 1;
    for (int value : deque) {
        assert(value == expected);
        expected++;
    }
    assert(expected == 6);
}

template <typename D>
void test_copy_is_independent() {
    D first;
    for (int i = 0; i < 20; i++) {
        first.push_back(i);
    }
    first.pop_front();
    first.push_front(100);

    D second(first);
    assert(second.size() == first.size());
    second[0] = -1;
    second.push_back(-2);
    assert(first[0] == 100);
    assert(first.size() == 20);
    first.check_invariants();
    second.check_invariants();

    D third;
    third.push_back(7);
    third = first;
    third[1] = -3;
    assert(first[1] == 1);
    assert(third.size() == 20);
    third.check_invariants();
}

template <typename D>
void test_self_assignment() {
    D deque;
    deque.push_back(1);
    deque.push_back(2);
    D& same = deque;
    deque = same;
    assert(deque.size() == 2);
    assert(deque.front() == 1);
    assert(deque.back() == 2);
    deque.check_invariants();
}

template <typename D>
void test_move_leaves_empty_and_usable() {
    D first;
    for (int i = 0; i < 20; i++) {
        first.push_back(i);
    }
    D second(std::move(first));
    assert(second.size() == 20);
    assert(second.back() == 19);
    assert(first.empty());
    first.check_invariants();
    first.push_back(5);
    first.push_front(4);
    assert(first.front() == 4);
    assert(first.back() == 5);
    first.pop_back();
    first.pop_back();

    D third;
    third.push_back(1);
    third = std::move(second);
    assert(third.size() == 20);
    assert(second.empty());
    second.check_invariants();
    second.push_front(9);
    assert(second.back() == 9);
    third.check_invariants();
}

template <typename D>
void test_no_objects_left_behind() {
    {
        D first;
        for (int i = 0; i < 100; i++) {
            first.push_back(Tracked(i));
            first.push_front(Tracked(-i));
        }
        for (int i = 0; i < 30; i++) {
            first.pop_back();
            first.pop_front();
        }
        D second(first);
        D third;
        third = second;
        D fourth(std::move(second));
        third = std::move(fourth);
    }
    assert(Tracked::counts().live == 0);
}

// Insertar un temporal no copia nunca, ni siquiera cuando el buffer crece.
template <typename D>
void test_rvalue_push_does_not_copy() {
    D deque;
    Tracked::counts().copies = 0;
    for (int i = 0; i < 1000; i++) {
        deque.push_back(Tracked(i));
        deque.push_front(Tracked(i));
    }
    assert(Tracked::counts().copies == 0);
}

template <typename D>
void test_lvalue_push_copies_once() {
    D deque;
    Tracked value(1);
    Tracked::counts().copies = 0;
    for (int i = 0; i < 1000; i++) {
        deque.push_back(value);
        deque.push_front(value);
    }
    assert(Tracked::counts().copies == 2000);
}

// El argumento puede ser un elemento del mismo deque, aunque el buffer tenga que crecer.
template <typename D>
void test_push_own_element() {
    // Por separado: así el crecimiento le toca a cada extremo.
    D by_back;
    D by_front;
    by_back.push_back(std::string(40, 'a'));
    by_front.push_back(std::string(40, 'a'));
    for (int i = 0; i < 200; i++) {
        by_back.push_back(by_back.front());
        by_front.push_front(by_front.back());
    }
    assert(by_back.size() == 201);
    assert(by_front.size() == 201);
    for (const std::string& value : by_back) {
        assert(value == std::string(40, 'a'));
    }
    for (const std::string& value : by_front) {
        assert(value == std::string(40, 'a'));
    }
}

// Sacar un elemento debe soltar lo que guardaba.
template <typename D>
void test_pop_releases_value() {
    auto shared = std::make_shared<int>(1);
    D deque;
    deque.push_back(shared);
    deque.push_front(shared);
    assert(shared.use_count() == 3);
    deque.pop_front();
    assert(shared.use_count() == 2);
    deque.pop_back();
    assert(shared.use_count() == 1);
}

template <typename D, typename T, typename Make>
void random_against_std_deque(unsigned seed, int steps, Make make) {
    std::mt19937 rng(seed);
    D mine;
    std::deque<T> model;
    for (int step = 0; step < steps; step++) {
        T value = make(rng());
        switch (rng() % 8) {
            case 0:
            case 1:
                mine.push_back(value);
                model.push_back(value);
                break;
            case 2:
            case 3:
                mine.push_front(value);
                model.push_front(value);
                break;
            case 4:
                if (!model.empty()) {
                    mine.pop_back();
                    model.pop_back();
                }
                break;
            case 5:
                if (!model.empty()) {
                    mine.pop_front();
                    model.pop_front();
                }
                break;
            case 6:
                if (!model.empty()) {
                    std::size_t i = rng() % model.size();
                    assert(mine[i] == model[i]);
                    mine[i] = value;
                    model[i] = value;
                }
                break;
            default:
                if (step % 50 == 0) {
                    D copy(mine);
                    mine = std::move(copy);
                }
        }
        assert(mine.size() == model.size());
        if (step % 200 == 0) {
            assert_same(mine, model);
        }
    }
    assert_same(mine, model);
}

template <typename ArrayInt>
void test_array_few_allocations() {
    std::size_t before = allocation_count();
    {
        ArrayInt deque;
        for (int i = 0; i < 100000; i++) {
            deque.push_back(i);
        }
    }
    assert(allocation_count() - before <= 25);
}

template <typename ArrayInt>
void test_array_capacity_doubles() {
    ArrayInt deque;
    std::size_t last = deque.capacity();
    for (int i = 0; i < 5000; i++) {
        deque.push_back(i);
        std::size_t now = deque.capacity();
        if (last > 0 && now != last) {
            assert(now == 2 * last);
        }
        last = now;
    }
    assert(last <= 2 * 5000);
}

// Una cola de pocos elementos debe reusar el buffer: si no da la vuelta, la capacidad crece.
template <typename ArrayInt>
void test_array_ring_reuses_space() {
    ArrayInt deque;
    for (int i = 0; i < 4; i++) {
        deque.push_back(i);
    }
    std::size_t capacity = deque.capacity();
    for (int i = 0; i < 100000; i++) {
        deque.push_back(i);
        deque.pop_front();
    }
    assert(deque.capacity() <= 2 * capacity);
    deque.check_invariants();
}

template <typename ArrayInt>
void test_array_move_is_noexcept() {
    static_assert(std::is_nothrow_move_constructible_v<ArrayInt>);
    static_assert(std::is_nothrow_move_assignable_v<ArrayInt>);
}

template <typename LinkedInt>
void test_linked_one_allocation_per_push() {
    LinkedInt deque;
    std::size_t before = allocation_count();
    for (int i = 0; i < 1000; i++) {
        deque.push_back(i);
    }
    assert(allocation_count() - before == 1000);
    before = allocation_count();
    for (int i = 0; i < 1000; i++) {
        deque.pop_front();
    }
    assert(allocation_count() == before);
}

template <typename LinkedInt>
void test_linked_elements_stay_in_place() {
    LinkedInt deque;
    deque.push_back(5);
    int* element = &deque.front();
    auto it = deque.begin();
    for (int i = 0; i < 1000; i++) {
        deque.push_back(i);
        deque.push_front(i);
    }
    assert(&*it == element);
    assert(*it == 5);
    for (int i = 0; i < 1000; i++) {
        deque.pop_back();
        deque.pop_front();
    }
    assert(&deque.front() == element);
}

template <typename LinkedInt>
void test_linked_move_assign_is_noexcept() {
    static_assert(std::is_nothrow_move_assignable_v<LinkedInt>);
}

template <typename LinkedInt>
void test_linked_shuffle_nodes() {
    LinkedInt deque;
    std::vector<const int*> before;
    for (int i = 0; i < 1000; i++) {
        deque.push_back(i);
    }
    for (const int& value : deque) {
        before.push_back(&value);
    }

    deque.shuffle_nodes(7);
    deque.check_invariants();
    assert(deque.size() == 1000);

    std::vector<const int*> after;
    std::vector<int> values;
    for (const int& value : deque) {
        after.push_back(&value);
        values.push_back(value);
        assert(*after.back() == value);
    }
    assert(after != before);
    std::vector<const int*> sorted_before = before;
    std::sort(sorted_before.begin(), sorted_before.end());
    std::vector<const int*> sorted_after = after;
    std::sort(sorted_after.begin(), sorted_after.end());
    assert(sorted_after == sorted_before);
    std::sort(values.begin(), values.end());
    for (int i = 0; i < 1000; i++) {
        assert(values[i] == i);
    }

    deque.push_back(-1);
    deque.push_front(-2);
    assert(deque.back() == -1);
    assert(deque.front() == -2);
    deque.check_invariants();
}

#endif