// Pruebas de las listas de los apuntes: casos dirigidos y operaciones al azar con semilla fija.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <list>
#include <random>
#include <string>
#include <vector>

#include "dlist.h"
#include "slist.h"
#include "tracked.h"

namespace {

template <typename T>
std::vector<T> as_vector(const DList<T>& list) {
    std::vector<T> values;
    for (const T& value : list) {
        values.push_back(value);
    }
    return values;
}

void test_singly_list() {
    SinglyList<int> list;
    assert(list.empty());
    list.check_invariants();
    list.push_front(2);
    list.push_front(1);
    list.push_back(3);
    list.check_invariants();
    assert(list.size() == 3);
    assert(list.at(0) == 1);
    assert(list.at(1) == 2);
    assert(list.at(2) == 3);
    list.pop_front();
    list.pop_front();
    list.pop_front();
    list.check_invariants();
    assert(list.empty());
    list.push_back(9);  // al vaciarse, tail_ debió volver a nulo
    assert(list.front() == 9);
    list.check_invariants();
}

void test_singly_list_frees_everything() {
    {
        SinglyList<Tracked> list;
        for (int i = 0; i < 100; i++) {
            list.push_front(Tracked(i));
        }
        assert(Tracked::counts().live == 100);
    }
    assert(Tracked::counts().live == 0);
}

void test_dlist_empty() {
    DList<int> list;
    assert(list.empty());
    assert(!(list.begin() != list.end()));
    list.check_invariants();
}

void test_dlist_insert_erase() {
    DList<int> list;
    list.push_back(1);
    list.push_back(3);
    auto it = list.begin();
    ++it;
    auto two = list.insert(it, 2);
    assert(*two == 2);
    assert(as_vector(list) == (std::vector<int>{1, 2, 3}));
    auto three = list.erase(two);
    assert(*three == 3);
    assert(as_vector(list) == (std::vector<int>{1, 3}));
    list.check_invariants();
}

void test_iterator_survives_other_changes() {
    DList<int> list;
    list.push_back(5);
    auto it = list.begin();
    int* element = &*it;
    for (int i = 0; i < 100; i++) {
        list.push_front(i);
        list.push_back(i);
    }
    assert(*it == 5);
    assert(&*it == element);
    list.erase(list.begin());
    list.pop_back();
    assert(*it == 5);
    list.check_invariants();
}

void test_write_through_iterator() {
    DList<int> list;
    list.push_back(1);
    list.push_back(2);
    for (int& value : list) {
        value *= 10;
    }
    const DList<int>& view = list;
    assert(as_vector(view) == (std::vector<int>{10, 20}));
}

void test_shuffle_keeps_nodes() {
    DList<int> list;
    std::vector<const int*> before;
    for (int i = 0; i < 1000; i++) {
        list.push_back(i);
    }
    for (const int& value : list) {
        before.push_back(&value);
    }
    list.shuffle_nodes(7);
    list.check_invariants();

    std::vector<const int*> after;
    long long sum = 0;
    for (const int& value : list) {
        after.push_back(&value);
        sum += value;
    }
    assert(sum == 999 * 1000 / 2);
    assert(after != before);
    std::sort(before.begin(), before.end());
    std::sort(after.begin(), after.end());
    assert(after == before);
}

void test_dlist_frees_everything() {
    {
        DList<Tracked> list;
        for (int i = 0; i < 100; i++) {
            list.push_back(Tracked(i));
        }
        assert(Tracked::counts().live == 101);  // 100 elementos y el centinela
        list.erase(list.begin());
    }
    assert(Tracked::counts().live == 0);
}

// Operaciones al azar, comparando contra std::list.
void test_dlist_random() {
    std::mt19937 rng(2026);
    DList<std::string> mine;
    std::list<std::string> model;
    for (int step = 0; step < 20000; step++) {
        std::string value = std::to_string(rng() % 1000);
        switch (rng() % 6) {
            case 0:
                mine.push_front(value);
                model.push_front(value);
                break;
            case 1:
                mine.push_back(value);
                model.push_back(value);
                break;
            case 2:
                if (!model.empty()) {
                    mine.pop_front();
                    model.pop_front();
                }
                break;
            case 3:
                if (!model.empty()) {
                    mine.pop_back();
                    model.pop_back();
                }
                break;
            case 4: {
                auto a = mine.begin();
                auto b = model.begin();
                for (unsigned skip = rng() % (model.size() + 1); skip > 0; skip--) {
                    ++a;
                    ++b;
                }
                auto inserted_a = mine.insert(a, value);
                auto inserted_b = model.insert(b, value);
                assert(*inserted_a == *inserted_b);
                break;
            }
            default:
                if (!model.empty()) {
                    auto a = mine.begin();
                    auto b = model.begin();
                    for (unsigned skip = rng() % model.size(); skip > 0; skip--) {
                        ++a;
                        ++b;
                    }
                    mine.erase(a);
                    model.erase(b);
                }
        }
        assert(mine.size() == model.size());
        if (step % 100 == 0) {
            mine.check_invariants();
            std::vector<std::string> expected(model.begin(), model.end());
            assert(as_vector(mine) == expected);
        }
    }
}

}  // namespace

int main() {
    test_singly_list();
    test_singly_list_frees_everything();
    test_dlist_empty();
    test_dlist_insert_erase();
    test_iterator_survives_other_changes();
    test_write_through_iterator();
    test_shuffle_keeps_nodes();
    test_dlist_frees_everything();
    test_dlist_random();
    std::cout << "pruebas de las listas: ok\n";
    return 0;
}