#pragma once

template<class T>
class LinkedList
{
public:

    LinkedList() : head_(new Node()), rhead_(head_), size_(0) {}

    void insert(const T& val)
    {
        Node* now = head_;
        while (now->next_ != nullptr && now->next_->val_ < val)
        {
            now = now->next_;
        }
        now = new Node(val, now, now->next_);
        now->previous_->next_ = now;
        if (now->next_ != nullptr)
        {
            now->next_->previous_ = now;
        }
        if (rhead_->next_ != nullptr)
        {
            rhead_ = rhead_->next_;
        }
        ++size_;
    }

    const unsigned& size() const
    {
        return size_;
    }

    struct Node;
    class reverse_iterator;

    class iterator
    {
    public:

        iterator(Node* ptr, Node* left, Node* right) : current_(ptr), left_(left), right_(right) {}

        iterator(const iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}

        reverse_iterator getReversible() const
        {
            return reverse_iterator(current_, left_, right_);
        }

        iterator& operator=(const iterator& right)
        {
            current_ = right.current_;
            return *this;
        }

        T* operator->() const
        {
            return current_;
        }

        iterator operator++(int)
        {
            assert(current_ != nullptr);
            iterator res(current_);
            current_ = current_->next_;
            return res;
        }

        iterator operator--(int)
        {
            assert(current_ != left_);
            iterator res(current_);
            current_ = current_->previous;
            return res;
        }

        iterator& operator++()
        {
            assert(current_ != nullptr);
            current_ = current_->next_;
            return *this;
        }

        iterator& operator--()
        {
            assert(current_ != left_);
            current_ = current_->previous_;
            return *this;
        }

        const T& operator*()
        {
            assert(current_ != nullptr);
            return current_->val_;
        }

        const T& operator*() const
        {
            assert(current_ != nullptr);
            return current_->val_;
        }

        bool operator==(const iterator& right)
        {
            return current_ == right.current_;
        }

        bool operator!=(const iterator& right)
        {
            return current_ != right.current_;
        }

    private:
        Node* left_;
        Node* current_;
        Node* right_;
    };

    class reverse_iterator
    {
    public:

        reverse_iterator(Node* ptr, Node* left, Node* right) : current_(ptr), left_(left), right_(right) {}

        reverse_iterator(const reverse_iterator& copy) : current_(copy.current_), left_(copy.left_), right_(copy.right_) {}

        iterator getStraight() const
        {
            return iterator(current_, left_, right_);
        }

        reverse_iterator& operator=(const reverse_iterator& right)
        {
            current_ = right.current_;
            return *this;
        }

        T* operator->() const
        {
            return current_;
        }

        reverse_iterator operator++(int)
        {
            assert(current_ != nullptr);
            reverse_iterator res(current_);
            current_ = current_->previous_;
            return res;
        }

        reverse_iterator operator--(int)
        {
            assert(current_ != right_);
            reverse_iterator res(current_);
            current_ = current_->next_;
            return res;
        }

        reverse_iterator& operator++()
        {
            assert(current_ != nullptr);
            current_ = current_->previous_;
            return *this;
        }

        reverse_iterator& operator--()
        {
            assert(current_ != right_);
            current_ = current_->next_;
            return *this;
        }

        const T& operator*()
        {
            assert(current_ != nullptr);
            return current_->val_;
        }

        const T& operator*() const
        {
            assert(current_ != nullptr);
            return current_->val_;
        }

        bool operator==(const reverse_iterator& right)
        {
            return current_ == right.current_;
        }

        bool operator!=(const reverse_iterator& right)
        {
            return current_ != right.current_;
        }

    private:
        Node* left_;
        Node* current_;
        Node* right_;
    };

    iterator begin() const
    {
        return iterator(head_->next_, head_, (!size_ ? nullptr : rhead_));
    }

    iterator end() const
    {
        return iterator(rhead_->next_, head_, (!size_ ? nullptr : rhead_));
    }

    reverse_iterator rbegin() const
    {
        return reverse_iterator((!size_ ? nullptr : rhead_), head_, (!size_ ? nullptr : rhead_));
    }

    reverse_iterator rend() const
    {
        return reverse_iterator(head_, head_, (!size_ ? nullptr : rhead_));
    }

private:

    Node* head_;
    Node* rhead_;
    unsigned size_;

    struct Node
    {
        Node() : next_(nullptr), previous_(nullptr) {}

        Node(const T& val, Node* previous, Node* next) : val_(val), next_(next), previous_(previous) {}

        T val_;
        Node* previous_;
        Node* next_;
    };
};