/* author: syn
 * license: FreeBSD
 */


#pragma once
#include <utility>
#include <iostream>
#include <memory>
#include <vector>
#include <stdexcept>

#define debug(var) std::cerr << "\x1b[33;1m" << __PRETTY_FUNCTION__ << ": \x1b[36;1m " #var "\x1b[0m = " << var << std::endl;

#ifndef LIST_WARN_ON_EMPTY_ERASE
#define LIST_WARN_ON_EMPTY_ERASE 0
#endif

namespace nvs {

template <typename T>
struct list_node {
    list_node<T> * next;
    list_node<T> * prev;
    T* value;
};

template <typename T>
class list_iterator {
public:
    typedef list_iterator<T> self_type;
    typedef typename T::value_type value_type;
    typedef typename T::reference reference;
    typedef typename T::pointer pointer;
    typedef std::forward_iterator_tag iterator_category;
    typedef typename T::difference_type difference_type;

    list_iterator () : ptr_(nullptr) {}
    list_iterator (const self_type& other) : ptr_ (other.ptr_) {}
    list_iterator (list_node <value_type> * ptr) : ptr_(ptr) {}
    list_iterator (self_type&& other) = default;//               { ptr_->value = std::move (other.ptr->value); }
    self_type& operator = (self_type&& other) = default;//   { ptr_->value = std::move (other.ptr_->value); }

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wreturn-local-addr"
    self_type& operator++ ()                     { ptr_ = ptr_->next; return *this; }
    self_type& operator-- ()                     { ptr_ = ptr_->prev; return *this; }
#pragma GCC diagnostic pop

    self_type operator++ (int prefix)           { self_type tmp = *this; ptr_ = ptr_->next; return tmp; }
    self_type operator-- (int prefix)           { self_type tmp = *this; ptr_ = ptr_->prev; return tmp; }
    reference operator*  ()                     { return *(ptr_->value); }
    pointer operator->   ()                     { return ptr_->value; }
    bool operator==      (const self_type& rhs) const { return ptr_ == rhs.ptr_; }
    bool operator!=      (const self_type& rhs) const { return ptr_ != rhs.ptr_; }

    list_node < value_type > * ptr_;
};

/*
 * my::list implements this interface
 */
/*
template < typename T, typename alloc_ = std::allocator <T> >
class list {
    typedef std::allocator_traits <alloc_> alloc_traits;
public:
    typedef list <T, alloc_>                     self_type;
    typedef size_t                                 size_type;
    typedef typename alloc_traits::value_type      value_type;
    typedef typename alloc_traits::pointer         pointer;
    typedef value_type&                            reference;
    typedef const value_type&                      const_reference;
    typedef typename alloc_traits::difference_type difference_type;

    typedef list_iterator <self_type> iterator;
    typedef list_iterator <const self_type> const_iterator;
    typedef std::reverse_iterator <iterator> reverse_iterator;
    typedef std::reverse_iterator <const_iterator> const_reverse_iterator;

    list ();
    list (const list&);
    list (std::initializer_list <T>);
    list (std::vector <T, alloc_>);
    ~list ();

    list& operator = (const list&);

    inline size_type size () const;

    value_type& operator [] (size_type);
    const value_type& operator [] (size_type) const;

    friend bool operator == (const list<T, alloc_>&, const list<T, alloc_>&);
    friend bool operator != (const list<T, alloc_>&, const list<T, alloc_>&);

    iterator       begin   ();
    const_iterator cbegin  () const;
    iterator       rbegin  ();
    const_iterator crbegin ();

    iterator       end   ();
    const_iterator cend  () const;
    iterator       rend  ();
    const_iterator crend () const;

    void push_back (const value_type&);
    void push_front (const value_type&);

    template <typename ... Args>
    void emplace_back (Args&& ...);
    template <typename ... Args>
    void emplace_front (Args&& ...);

    void pop_back ();
    void pop_front ();
    const value_type& back () const;
    const value_type& front () const;

private:
    list_node <T> * first_ptr;
    list_node <T> * last_ptr;
    size_type len;
    alloc_ alloc;
};
*/


template < typename T, typename alloc_ = std::allocator <T> >
class list {
    typedef std::allocator_traits <alloc_> alloc_traits;
public:
    typedef list <T, alloc_>                       self_type;
    typedef size_t                                 size_type;
    typedef typename alloc_traits::value_type      value_type;
    typedef typename alloc_traits::pointer         pointer;
    typedef value_type&                            reference;
    typedef const value_type&                      const_reference;
    typedef typename alloc_traits::difference_type difference_type;

    typedef list_iterator <self_type> iterator;
    typedef list_iterator <const self_type> const_iterator;
    typedef std::reverse_iterator <iterator> reverse_iterator;
    typedef std::reverse_iterator <const_iterator> const_reverse_iterator;

private:
    list_node<T> * dummy;
    size_type len;
    alloc_ alloc;

public:

    list ():
        dummy (nullptr),
        len        (0),
        alloc      ()
    {
        dummy = new list_node <T>;
        dummy->next = dummy;
        dummy->prev = dummy;
    }


    list (const list<T, alloc_>& other):
        list ()
    {
        for (auto it = other.cbegin (); it != other.cend (); it++) {
            push_back (*it);
        }
    }


    list (std::initializer_list < T > il):
        list ()
    {
        for (auto it = il.begin (); it != il.end (); it++)
            this->push_back (*it);
    }


    list (std::vector<T, alloc_> vec):
        list ()
    {
        for (auto it = vec.begin (); it != vec.end (); it++)
            this->push_back (*it);
    }


    ~list () {
        while (len > 0) this->pop_back ();
        delete dummy;
    }


    self_type& operator = (const list<T, alloc_>& other) {
        while (len > 0) this->pop_back ();
        len = 0;

        for (auto it = other.begin (); it != other.end (); it++)
            push_back (*it);

        return *(this);
    }


    inline size_type size () const {
        return len;
    }


    value_type& operator [] (list<T, alloc_>::size_type idx) {
        auto it = this->begin ();
        for (size_type i = 0; i < idx; i++) it++;
        return *it;
    }


    const value_type& operator [] (list<T, alloc_>::size_type idx) const {
        auto it = this->cbegin ();
        for (size_type i = 0; i < idx; i++) it++;
        return *it;
    }


    friend bool operator == (const list<T, alloc_>& l1, const list<T, alloc_>& l2) {
        if (l1.size () != l2.size ()) return false;
        auto it1 = l1.begin ();
        auto it2 = l2.begin ();
        for (; it1 != l1.end () && it2 != l2.end (); it1++, it2++) {
            if (*it1 != *it2) return false;
        }

        return true;
    }


    friend bool operator != (const list<T, alloc_>& l1, const list<T, alloc_>& l2) {
        return !(l1 == l2);
    }


    iterator               begin   ()       { return iterator (dummy->next); }
    const_iterator         cbegin  () const { return const_iterator (dummy->next); }
    iterator               end   ()         { return iterator (dummy); }
    const_iterator         cend  () const   { return const_iterator (dummy); }

    reverse_iterator       rbegin  ()       { return reverse_iterator (this->end ()); }
    const_reverse_iterator crbegin () const { return const_reverse_iterator (this->cend ()); }
    reverse_iterator       rend  ()         { return reverse_iterator (this->begin ()); }
    const_reverse_iterator crend () const   { return const_reverse_iterator (this->cbegin ()); }


    void push_back (const list<T, alloc_>::value_type& val) {
        this->insert (end (), val);
    }


    template <typename ... Args>
    iterator insert (iterator pos, Args&& ... args) {
        pointer val_copy = alloc.allocate (1);
        alloc.construct (val_copy, args ...);

        auto hooker = new list_node<T>;
        hooker->value = val_copy;

        // hook
        hooker->next = pos.ptr_;
        hooker->prev = pos.ptr_->prev;
        pos.ptr_->prev->next = hooker;
        pos.ptr_->prev = hooker;

        len++;

        return ++pos;
    }


    iterator erase (iterator pos) {
#if LIST_WARN_ON_EMPTY_ERASE
        if (len <= 0) throw std::runtime_error ("Trying to erase from epmty list.");
#endif
        pos++;
        alloc.destroy (pos.ptr_->prev->value);
        alloc.deallocate (pos.ptr_->prev->value, 1);
        auto before = pos.ptr_->prev->prev;
        delete pos.ptr_->prev;
        before->next = pos.ptr_;
        pos.ptr_->prev = before;
        len--;
        return pos;
    }


    void push_front (const list<T, alloc_>::value_type& val) {
        this->insert (begin (), val);
    }


    template <typename ... Args>
    void emplace_back (Args&& ... args) {
        this->insert (end (), args ...);
    }


    template <typename ... Args>
    void emplace_front (Args&& ... args) {
        this->insert (begin (), args ...);
    }


    void pop_back () {
        auto it = end ();
        --it;
        this->erase (it);
    }


    void pop_front () {
        this->erase (begin ());
    }


    const value_type& back () const {
        return *(crbegin ());
    }


    const value_type& front () const {
        return *(cbegin ());
    }

}; // class list

} // namespace nvs