// ListDeque.h
#ifndef ListDequeH
#define ListDequeH
// ---------------------------------------------------------------------------

#include <stdexcept>

template<typename T>
class ListDeque {
    /* header:

     // construct/copy/destroy:
     ListDeque(const ListDeque& x);
     ListDeque(ListDeque&& x);
     ~ListDeque();
     ListDeque& operator=(const ListDeque& x);
     ListDeque& operator=(ListDeque&& x);

     // capacity:
     int size() const;
     bool empty() const;

     // element access:
     T& operator[](int n);
     const T& operator[](int n) const;
     T& at(int n);
     const T& at(int n) const;
     T& front();
     const T& front() const;
     T& back();
     const T& back() const;

     // modifiers:
     void push_front(const T& x);
     void push_front(T&& x);
     void push_back(const T& x);
     void push_back(T&& x);
     void pop_front();
     void pop_back();
     void swap(ListDeque& x);
     void swap(ListDeque& x, ListDeque& y);
     void clear();

     // operators
     bool operator==(const ListDeque& x) const;
     bool operator!=(const ListDeque& x) const;

     */

    public:
    class Node {
        public:
        T value;
        Node* next;
        Node* prev;

        Node(const T value, Node* prev = nullptr, Node* next = nullptr)
            : value(value), prev(prev), next(next) {}

        Node(T && value, Node* prev = nullptr, Node* next = nullptr)
            : value(value), prev(prev), next(next) {}
    };

    int count = 0;
    Node* first = nullptr;
    Node* last = nullptr;

    // construct/copy/destroy:
    ListDeque() = default;

    ListDeque(const ListDeque& x) {
        for (Node * n = x.first; n; n = n->next) {
            push_front(n->value);
        }
    }

    ListDeque(ListDeque && x) {
        swap(x);
    }

    ~ListDeque() {
        clear();
    }
    ListDeque& operator = (const ListDeque & x) {
        for (Node * n = x.first; n; n = n->next) {
            push_front(n->value);
        }
        return* this;
    }
    ListDeque& operator = (ListDeque && x) {
        swap(x);
        return* this;
    }

    // capacity:
    int size() const {
        return count;
    }

    bool empty() const {
        return !count;
    }

    // element access:
    T& operator[](int n) {
        Node* x = first;
        while (x && n-- > 0) {
            x = x->next;
        }
        return x->value;
    }

    const T& operator[](int n) const {
        Node* x = first;
        while (x && n-- > 0) {
            x = x->next;
        }
        return x->value;
    }

    T& at(int n) {
        if (n > count || n < 0)
            throw std::out_of_range("Deque index is out of bounds");

        Node* x = first;
        while (x && n-- > 0) {
            x = x->next;
        }
        return x->value;
    }

    const T& at(int n) const {
        if (n > count || n < 0)
            throw std::out_of_range("Deque index is out of bounds");

        Node* x = first;
        while (x && --n) {
            x = x->next;
        }
        return x->value;
    }

    T& front() {
        return first->value;
    }

    const T& front() const {
        return first->value;
    }

    T& back() {
        return last->value;
    }

    const T& back() const {
        return last->value;
    }

    // modifiers:
    void push_front(const T& x) {
        if (last)
            last = last->next = new Node(x, last, nullptr);
        else
            last = first = new Node(x, nullptr, nullptr);
        count++;
    }

    void push_front(T && x) {
        if (last)
            last = last->next = new Node(x, last, nullptr);
        else
            last = first = new Node(x, nullptr, nullptr);
        count++;
    }

    void push_back(const T& x) {
        if (first)
            first = first->prev = new Node(x, nullptr, first);
        else
            first = last = new Node(x, nullptr, nullptr);
        count++;
    }

    void push_back(T && x) {
        if (first)
            first = first->prev = new Node(x, nullptr, first);
        else
            first = last = new Node(x, nullptr, nullptr);
        count++;
    }

    void pop_back() {
        if (!first)
            return;
        Node* temp = first;
        first = first->next;
        if (--count) {
            first->prev = nullptr;
        } else {
            last = nullptr;
        }
        delete temp;
    }

    void pop_front() {
        if (!last)
            return;
        Node* temp = last;
        last = last->prev;
        if (--count) {
            last->next = nullptr;
        } else {
            first = nullptr;
        }
        delete temp;
    }

    void swap(ListDeque& x) {
        std::swap(first, x.first);
        std::swap(last, x.last);
        std::swap(count, x.count);
    }

    friend void swap(ListDeque& x, ListDeque& y) {
        x.swap(y);
    }

    void clear() {
        if (!first)
            return;
        for (Node * n = first->next; n; n = n->next) {
            delete n->prev;
        }
        delete last;
        first = nullptr;
        last = nullptr;
        count = 0;
    }

    // operators
    bool operator == (const ListDeque& x) const {
        if (count != x.count)
            return false;
        Node* n = first, *n2 = x.first;
        while (n && n->value == n2->value) {
            n = n->next; n2 = n2->next;
        }
        return !n && !n2;
    }

    bool operator != (const ListDeque& x) const {
        return !(*this == x);
    }

};

// ---------------------------------------------------------------------------
#endif