// Deque sobre una lista doble con centinela. Completen cada método marcado con not_implemented.
#ifndef LINKED_DEQUE_H
#define LINKED_DEQUE_H

#include <cassert>
#include <cstddef>
#include <utility>

#include "not_implemented.h"

// Invariantes:
// - sentinel_ nunca es nulo, y su value no es un elemento del deque.
// - 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 LinkedDeque {
    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 { not_implemented("Iter::operator*"); }
        Iter& operator++() { not_implemented("Iter::operator++"); }
        bool operator==(const Iter& other) const { return node_ == other.node_; }
        bool operator!=(const Iter& other) const { return node_ != other.node_; }

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

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

    LinkedDeque() { not_implemented("LinkedDeque()"); }
    ~LinkedDeque() { not_implemented("~LinkedDeque"); }

    LinkedDeque(const LinkedDeque&) { not_implemented("constructor de copia"); }
    LinkedDeque& operator=(const LinkedDeque&) { not_implemented("asignación de copia"); }
    // Al mover, el origen queda vacío y se puede seguir usando: también necesita un centinela.
    // Por eso este constructor reserva memoria y no es noexcept.
    LinkedDeque(LinkedDeque&&) { not_implemented("constructor de movimiento"); }
    LinkedDeque& operator=(LinkedDeque&&) noexcept { not_implemented("asignación de movimiento"); }

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

    void push_front(const T&) { not_implemented("push_front(const T&)"); }
    void push_front(T&&) { not_implemented("push_front(T&&)"); }
    void push_back(const T&) { not_implemented("push_back(const T&)"); }
    void push_back(T&&) { not_implemented("push_back(T&&)"); }

    // Precondición: no está vacío.
    void pop_front() { not_implemented("pop_front"); }
    void pop_back() { not_implemented("pop_back"); }

    T& front() { not_implemented("front"); }
    const T& front() const { not_implemented("front const"); }
    T& back() { not_implemented("back"); }
    const T& back() const { not_implemented("back const"); }

    // Precondición: i < size(). Parte del extremo más cercano.
    T& operator[](std::size_t) { not_implemented("operator[]"); }
    const T& operator[](std::size_t) const { not_implemented("operator[] const"); }

    iterator begin() { not_implemented("begin"); }
    iterator end() { not_implemented("end"); }
    const_iterator begin() const { not_implemented("begin const"); }
    const_iterator end() const { not_implemented("end const"); }

    // 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) { not_implemented("shuffle_nodes"); }

    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_ = nullptr;
    std::size_t size_ = 0;
};

#endif