#include<iostream>
#include<string>

using namespace std;

template<typename T>
class List {
private:
    class Elem {
    public:
        Elem() {}
        Elem* Next;
        Elem* Prev;
        Elem* Head;
        virtual T* GetVal() {
            return nullptr;
        }
    };

    class Node : public Elem {
    public:
        Node(const T & value) : val(value) {}
        Node(T && value) : val(move(value)) {}
        Node(const Elem& tmp) : val(tmp.val) {}
        Node(Elem && tmp) : val(move(tmp.value)) {}
        T* GetVal() override {
            return &val;
        }
        Node* Nextnode;
        Node* Prevnode;
        T val;
    };

    Elem* Header;
    Node *Beg, *Fin;
    size_t _size;

public:
    List() : Header(new Elem), Beg(nullptr), Fin(nullptr), _size(0) {
        Header->Next = Header;
        Header->Prev = Header;
        Header->Head = Header;
    }

    List(const List& tmp) : Header(new Elem), Beg(nullptr), Fin(nullptr), _size(tmp._size)  {
        Header->Next = Header;
        Header->Prev = Header;
        Header->Head = Header;
        if (tmp.Beg != nullptr) {
            Node* tmp_cur = tmp.Beg;
            Node *cur = new Node(*tmp_cur);
            cur->Next = nullptr;
            cur->Prev = Header;
            cur->Prevnode = nullptr;
            cur->Nextnode = nullptr;
            Beg = cur;
            Node *next = cur;
            while (tmp_cur->Nextnode != nullptr) {
                tmp_cur = tmp_cur->Nextnode;
                next = new Node(*tmp_cur);
                next->Prev = cur;
                next->Prevnode = cur;
                next->Next = nullptr;
                next->Nextnode = nullptr;
                cur->Next = next;
                cur->Nextnode = next;
                cur = next;
            }
            Fin = cur;
            Fin->Next = Header;
            cur = next = nullptr;
            Header->Prev = Fin;
            Header->Next = Beg;
        }
    }

    List& operator = (const List& tmp) {
        ClearNode();
        _size = tmp._size;
        if (tmp.Beg != nullptr) {
            Node* tmp_cur = tmp.Beg;
            Node *cur = new Node(*tmp_cur);
            cur->Next = nullptr;
            cur->Prev = Header;
            cur->Prevnode = nullptr;
            cur->Nextnode = nullptr;
            Beg = cur;
            Node *next = cur;
            while (tmp_cur->Nextnode != nullptr) {
                tmp_cur = tmp_cur->Nextnode;
                next = new Node(*tmp_cur);
                next->Prev = cur;
                next->Prevnode = cur;
                next->Next = nullptr;
                next->Nextnode = nullptr;
                cur->Next = next;
                cur->Nextnode = next;
                cur = next;
            }
            Fin = cur;
            Fin->Next = Header;
            cur = next = nullptr;
            Header->Prev = Fin;
            Header->Next = Beg;
        }
        return *this;
    }

    ~List() {
        ClearNode();
        delete Header;
    }

    void ClearNode() {
        while (Beg != nullptr) {
            if (Beg != Fin) {
                Node *temp = Beg;
                Beg = Beg->Nextnode;
                delete temp;
                Beg->Prev = nullptr;
            } else {
                Beg = nullptr;
                delete Fin;
                Fin = nullptr;
            }
        }
    }

    void push_back(const T& val) {
        Node *temp = new Node(val);
        temp->Head = nullptr;
        temp->Next = Header;
        temp->Nextnode = nullptr;
        temp->Prevnode = Fin;
        if (Beg != nullptr) {
            temp->Prev = Fin;
            Fin->Next = temp;
            Fin->Nextnode = temp;
            if (Beg == Fin) {
                Beg->Next = temp;
                Beg->Nextnode = temp;
            }
            Fin = temp;
        } else {
            temp->Prev = Header;
            Beg = temp;
            Fin = temp;
        }
        Header->Next = Beg;
        Header->Prev = Fin;
        _size++;
    }

    void push_front(const T& val) {
        Node *temp = new Node(val);
        temp->Head = nullptr;
        temp->Prev = Header;
        temp->Prevnode = nullptr;
        temp->Nextnode = Beg;
        if (Beg != nullptr) {
            temp->Next = Beg;
            Beg->Prev = temp;
            Beg->Prevnode = temp;
            if (Beg == Fin) {
                Fin->Prev = temp;
                Fin->Prevnode = temp;
            }
            Beg = temp;
        } else {
            temp->Next = Header;
            Beg = temp;
            Fin = temp;
        }
        Header->Next = Beg;
        Header->Prev = Fin;
        _size++;
    }

    void push_back(T&& val) {
        Node *temp = new Node(move(val));
        temp->Head = nullptr;
        temp->Next = Header;
        temp->Nextnode = nullptr;
        temp->Prevnode = Fin;
        if (Beg != nullptr) {
            temp->Prev = Fin;
            Fin->Next = temp;
            Fin->Nextnode = temp;
            if (Beg == Fin) {
                Beg->Next = temp;
                Beg->Nextnode = temp;
            }
            Fin = temp;
        } else {
            temp->Prev = Header;
            Beg = temp;
            Fin = temp;
        }
        Header->Next = Beg;
        Header->Prev = Fin;
        _size++;
    }

    void push_front(T&& val) {
        Node *temp = new Node(move(val));
        temp->Head = nullptr;
        temp->Prev = Header;
        temp->Prevnode = nullptr;
        temp->Nextnode = Beg;
        if (Beg != nullptr) {
            temp->Next = Beg;
            Beg->Prev = temp;
            Beg->Prevnode = temp;
            if (Beg == Fin) {
                Fin->Prev = temp;
                Fin->Prevnode = temp;
            }
            Beg = temp;
        } else {
            temp->Next = Header;
            Beg = temp;
            Fin = temp;
        }
        Header->Next = Beg;
        Header->Prev = Fin;
        _size++;
    }


    void pop_back() {
        if (Beg != nullptr) {
            if (Beg != Fin) {
                Node *temp = Fin;
                Fin = Fin->Prevnode;
                delete temp;
                Fin->Next = Header;
                Header->Prev = Fin;
            } else {
                Beg = nullptr;
                delete Fin;
                Fin = nullptr;
                Header->Next = Header;
                Header->Prev = Header;
            }

            _size--;
        } else {
            cout << "pop_front FALSE list empty\n";
        }
    }

    void pop_front() {
        if (Beg != nullptr) {
            if (Beg != Fin) {
                Node *temp = Beg;
                Beg = Beg->Nextnode;
                delete temp;
                Beg->Prev = Header;
                Header->Next = Beg;
            } else {
                Beg = nullptr;
                delete Fin;
                Fin = nullptr;
                Header->Next = Header;
                Header->Prev = Header;
            }
            _size--;
        } else {
            cout << "pop_front FALSE list empty\n";
        }
    }

    const size_t size() const {
        return _size;
    }


    class Iterator{
    public:
        Elem* ptr;
        Iterator(Elem* ptr = NULL) : ptr(ptr) {
        }
        Iterator& operator++(void) {
            ptr = ptr->Next;
            return *this;
        }
        Iterator operator++(int) {
            Elem* result;
            result = ptr;
            ptr = ptr->Next;
            return result;
        }

        Iterator& operator--(void) {
            ptr = ptr->Prev;
            return *this;
        }

        Iterator operator--(int) {
            Elem* result;
            result = ptr;
            ptr = ptr->Prev;
            return result;
        }

        const T operator* () const {
            try {
                if (ptr != nullptr && ptr->Head == nullptr) {
                    return *(ptr->GetVal());
                } else {
                    cout << "Aborted! Dereference of NULLptr!\n";
                    throw;
                }
            }
            catch (...) {
                throw;
            }
        }

        bool operator==(Iterator b) {
            return (this->ptr == b.ptr);
        }

        bool operator!=(Iterator b) {
            return !(*this == b);
        }
    };

    const Iterator begin() const {
        return Beg;
    }

    const Iterator rbegin() const {
        return Fin;
    }

    const Iterator end() const{
        if (Beg == nullptr) {
            return Beg;
        } else {
            return Header;
        }
    }
};