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