#include <initializer_list>
#include <type_traits>
#include <utility>
#include <memory>
#include <functional>

template <typename Allocator, typename... Args>
typename Allocator::pointer allocator_new(Allocator& allocator, Args&&... args)
{
    auto dealloc = [&](typename Allocator::pointer p){ std::allocator_traits<Allocator>::deallocate( allocator, p, 1 ); };
    std::unique_ptr<typename Allocator::value_type, decltype( dealloc )> node( std::allocator_traits<Allocator>::allocate( allocator, 1 ), dealloc );
    std::allocator_traits<Allocator>::construct( allocator, node.get(), std::forward<Args>( args )... );
    return node.release();
}

template <typename Allocator>
void allocator_delete(Allocator& allocator, typename Allocator::pointer p) noexcept
{
    std::allocator_traits<Allocator>::destroy( allocator, p );
    std::allocator_traits<Allocator>::deallocate( allocator, p, 1 );
}

class ring_node
{
public:
    struct linkup_tag {};
    ring_node(ring_node* prev, ring_node* next) noexcept
    : next_( next ), prev_( prev ) {}
    ring_node(ring_node* prev, ring_node* next, linkup_tag ) noexcept
    : ring_node( prev, next )
    {
        prev_->next_ = this;
        next_->prev_ = this;
    }

    ring_node(const ring_node&) = delete;
    ring_node& operator=(const ring_node&) = delete;

    ring_node* next() const noexcept { return next_; }
    ring_node* prev() const noexcept { return prev_; }

    friend void link(ring_node* prev, ring_node* next) noexcept
    {
        next->prev_ = prev;
        prev->next_ = next;
    }
    friend void intersect(ring_node* a, ring_node* b) noexcept
    {
        ring_node* a_prev = a->prev();
        link( b->prev(), a );
        link( a_prev, b );
    }
    friend void flip(ring_node* p) noexcept
    {
        std::swap( p->prev_, p->next_ );
    }
private:
    ring_node* next_;
    ring_node* prev_;
};

template <typename T>
class list_node : public ring_node
{
public:
    using type = T;
    T data;

    template <typename... Args>
    list_node(ring_node* next, Args&&... args) noexcept( noexcept( T( std::declval<Args>()... ) ) )
       : ring_node( next->prev(), next, linkup_tag() ), data( std::forward<Args>( args )... )
    {}

    list_node(const list_node&) = delete;
    list_node& operator=(const list_node&) = delete;

    template <typename Allocator, typename... Args>
    static list_node* make(Allocator& alloc, ring_node* next, Args&&... args)
    {
        return allocator_new( alloc, next, std::forward<Args>( args )... );
    }
    template <typename Allocator>
    static void retire(Allocator& alloc, list_node* node) noexcept
    {
        link( node->prev(), node->next() );
        allocator_delete( alloc, node );
    }
};

template <typename Allocator>
class list_iterator;
template <typename Allocator>
class const_list_iterator;
template <typename Allocator>
void iter_splice(const_list_iterator<Allocator> pos, const_list_iterator<Allocator> first, const_list_iterator<Allocator> last) noexcept;
template <typename T, typename Allocator>
class list;

template <typename Allocator>
class const_list_iterator
{
public:
    using value_type = typename std::allocator_traits<Allocator>::value_type::type;
    using difference_type = typename std::allocator_traits<Allocator>::template rebind_traits<value_type>::difference_type;
    using pointer = const value_type*;
    using reference = const value_type&;
    using iterator_category = std::bidirectional_iterator_tag;


    friend class list<value_type, typename std::allocator_traits<Allocator>::template rebind_alloc<value_type>>;
    friend void iter_splice<>(const_list_iterator pos, const_list_iterator first, const_list_iterator last) noexcept;

    const_list_iterator() noexcept {}
    const value_type& operator*()  const noexcept { return static_cast<list_node<value_type>*>( node )->data; }
    const value_type* operator->() const noexcept { return &**this; }
    const_list_iterator& operator++()    noexcept {                 return node = node->next(), *this; }
    const_list_iterator  operator++(int) noexcept { auto x = *this; return node = node->next(), x; }
    const_list_iterator& operator--()    noexcept {                 return node = node->prev(), *this; }
    const_list_iterator  operator--(int) noexcept { auto x = *this; return node = node->prev(), x; }

    friend bool operator==(const_list_iterator a, const_list_iterator b) noexcept { return a.node == b.node; }
    friend bool operator!=(const_list_iterator a, const_list_iterator b) noexcept { return !( a == b ); }
protected:
    const_list_iterator(ring_node* node) noexcept
    : node( node )
    {}
    ring_node* node;
};

template <typename Allocator>
class list_iterator
: public const_list_iterator<Allocator>
{
public:
    using value_type = typename std::allocator_traits<Allocator>::value_type::type;
    using difference_type = typename std::allocator_traits<Allocator>::template rebind_traits<value_type>::difference_type;
    using pointer = value_type*;
    using reference = value_type&;
    using iterator_category = std::bidirectional_iterator_tag;

template <typename, typename> friend class list;
//    friend class list<value_type, typename std::allocator_traits<Allocator>::template rebind_alloc<value_type>>;

    list_iterator() noexcept {}
private:
    list_iterator(ring_node* node) noexcept
    : const_list_iterator<Allocator>( node )
    {}
public:
    value_type& operator*()  const noexcept { return static_cast<list_node<value_type>*>( this->node )->data; }
    value_type* operator->() const noexcept { return &**this; }
    list_iterator& operator++()    noexcept {                 return this->node = this->node->next(), *this; }
    list_iterator  operator++(int) noexcept { auto x = *this; return this->node = this->node->next(), x; }
    list_iterator& operator--()    noexcept {                 return this->node = this->node->prev(), *this; }
    list_iterator  operator--(int) noexcept { auto x = *this; return this->node = this->node->prev(), x; }
};

template <typename Allocator>
void iter_splice(const_list_iterator<Allocator> pos, const_list_iterator<Allocator> first, const_list_iterator<Allocator> last) noexcept
{
    intersect( pos.node, first.node );
    intersect( pos.node, last.node );
}
template <typename Allocator>
void iter_splice(const_list_iterator<Allocator> pos, const_list_iterator<Allocator> i) noexcept
{
    iter_splice( pos, i, std::next( i ) );
}

template <typename T, typename Allocator = std::allocator<T>>
class list_base : protected std::allocator_traits<Allocator>::template rebind_alloc<list_node<T>>
{
protected:
    using node_allocator_type = typename std::allocator_traits<Allocator>::template rebind_alloc<list_node<T>>;
    mutable ring_node anchor;

    explicit list_base(const Allocator& allocator) noexcept
    : node_allocator_type( allocator ), anchor( &anchor, &anchor )
    {}

    ~list_base() noexcept
    {
        for ( ring_node* p = anchor.prev(); p != &anchor; )
        {
            list_node<T>* q = static_cast<list_node<T>*>( p );
            p = p->prev();
            allocator_delete<node_allocator_type>( *this, q );
        }
    }
};

template <typename T, typename Allocator = std::allocator<T>>
class list : private list_base<T, Allocator>
{
    using base = list_base<T, Allocator>;
    using node_type = list_node<T>;
    using node_allocator_type = typename std::allocator_traits<Allocator>::template rebind_alloc<node_type>;
public:
    // types:
    using value_type             = T;
    using allocator_type         = Allocator;
    static_assert( std::is_same<T, typename std::allocator_traits<Allocator>::value_type>::value, "Allocator does not match value_type" );
    using reference              = value_type&;
    using const_reference        = const value_type&;
    using pointer                = typename std::allocator_traits<allocator_type>::pointer;
    using const_pointer          = typename std::allocator_traits<allocator_type>::const_pointer;
    using size_type              = typename std::allocator_traits<allocator_type>::size_type;
    using difference_type        = typename std::allocator_traits<allocator_type>::difference_type;
    using iterator               = list_iterator<node_allocator_type>;
    using const_iterator         = const_list_iterator<node_allocator_type>;
    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

// construct/copy/destroy:
    explicit list(const allocator_type& allocator = allocator_type()) noexcept
        : base( allocator )
    {}
    explicit list(size_type n, const value_type& value = value_type(), const allocator_type& allocator = allocator_type())
        : list( allocator )
    {
        while ( n-- )
           push_back( value );
    }
    template <typename InputIterator, typename std::enable_if<!std::is_fundamental<InputIterator>::value, int>::type = 0>
    list(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type())
        : list( allocator )
    {
        for ( ; first != last; ++first )
            push_back( *first );
    }
    list(const list& other)
        : list( other.begin(), other.end(), std::allocator_traits<node_allocator_type>::select_on_container_copy_construction( other.node_alloc() ) )
    {}
    list(list&& other) noexcept
        : base( other.node_alloc() )
    {
        swap( other );
    }
    list(const list& other, const allocator_type& allocator) noexcept
        : list( other.begin(), other.end(), allocator )
    {}
    list(list&& other, const allocator_type& allocator) noexcept
        : list( allocator )
    {
        swap( other );
    }
    list(std::initializer_list<T> init_list, const allocator_type& allocator = allocator_type())
        : list( init_list.begin(), init_list.end(), allocator )
    {}

    list& operator=(const list& rhs) { return list( rhs ).swap( *this ), *this; }

    list& operator=(list&& rhs) noexcept { return swap( rhs ), *this; }

    list& operator=(std::initializer_list<T> init_list) { return assign( init_list ), *this; }

    template <typename InputIterator, typename std::enable_if<!std::is_fundamental<InputIterator>::value, int>::type = 0>
    void assign(InputIterator first, InputIterator last)
    {
        for ( auto it = begin(); it != end(); ++it )
            if ( first == last )
                return (void)erase( it, end() );
            else
                *it = *first++;
        insert( end(), first, last );
    }
    void assign(size_type n, const value_type& value)
    {
        for ( auto it = begin(); it != end(); ++it )
            if ( n-- == 0 )
                return (void)erase( it, end() );
            else
                *it = value;
        insert( end(), n, value );
    }
    void assign(std::initializer_list<T> init) { assign( init.begin(), init.end() ); }

    allocator_type get_allocator() const noexcept { return node_alloc(); }

// iterators:
    iterator begin() noexcept                       { return this->anchor.next(); }
    const_iterator begin() const noexcept           { return cbegin(); }
    const_iterator cbegin() const noexcept          { return this->anchor.next(); }
    iterator end() noexcept                         { return &this->anchor; }
    const_iterator end() const noexcept             { return cend(); }
    const_iterator cend() const noexcept            { return &this->anchor; }
    reverse_iterator rbegin() noexcept              { return reverse_iterator( begin() ); }
    const_reverse_iterator rbegin() const noexcept  { return crbegin(); }
    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator( cbegin() ); }
    reverse_iterator rend() noexcept                { return reverse_iterator( end() ); }
    const_reverse_iterator rend() const noexcept    { return crend(); }
    const_reverse_iterator crend() const noexcept   { return const_reverse_iterator( cend() ); }

// 23.3.5.3, capacity:
    bool empty() const noexcept                     { return cbegin() == cend(); }
    size_type size() const noexcept                 { return std::distance( cbegin(), cend() ); }
    size_type max_size() const noexcept             { return node_alloc().max_size(); }
    void resize(size_type n)                        { return resize( n, value_type() ); }
    void resize(size_type n, const value_type& value)
    {
        for ( auto it = begin(); it != end(); ++it )
            if ( n-- == 0 )
                return (void)erase( it, end() );
        while ( n-- != 0 )
            push_back( value );
    }

// element access:
    value_type& front() noexcept             { return *begin(); }
    const value_type& front() const noexcept { return *begin(); }
    value_type& back() noexcept              { return *std::prev( end() ); }
    const value_type& back() const noexcept  { return *std::prev( end() ); }

    void pop_front() noexcept                { erase( begin() ); }
    template <typename... Args>
    void emplace_front(Args&&... args)       { return emplace( cbegin(), std::forward<Args>( args )... ); }
    void push_front(const value_type& value) { insert( cbegin(), value ); }
    void push_front(value_type&& value)      { insert( cbegin(), std::move( value ) ); }
    void pop_back() noexcept                 { erase( std::prev( end() ) ); }
    template <typename... Args>
    void emplace_back(Args&&... args)        { return emplace( cend(), std::forward<Args>( args )... ); }
    void push_back(const value_type& value)  { insert( cend(), value ); }
    void push_back(value_type&& value)       { insert( cend(), std::move( value ) ); }


    template <typename... Args>
    iterator emplace(const_iterator position, Args&&... args)
    {
        return node_type::make( node_alloc(), position.node, std::forward<Args>( args )... );
    }
    iterator insert(const_iterator position, const T& value) { return emplace( position, value ); }
    iterator insert(const_iterator position, T&& x)          { return emplace( position, std::move( x ) ); }
    iterator insert(const_iterator position, size_type n, const T& x)
    {
        return splice( position--, list( n, x, get_allocator() ) ), position.node->next();
    }

    template <typename InputIterator, typename std::enable_if<!std::is_fundamental<InputIterator>::value, int>::type = 0>
    iterator insert(const_iterator position, InputIterator first, InputIterator last)
    {
        return splice( position--, list( first, last, get_allocator() ) ), position.node->next();
    }

    iterator insert(const_iterator position, std::initializer_list<T> il)
    {
        return splice( position--, list( il.begin(), il.end(), get_allocator() ) ), position.node.next();
    }

    iterator erase(const_iterator position) noexcept
    {
        return node_type::retire( node_alloc(), static_cast<node_type*>( position++.node ) ), position.node;
    }
    iterator erase(const_iterator position, const_iterator last) noexcept
    {
        return iter_splice( list( get_allocator() ).cend(), position, last ), last.node;
    }

    void swap(list& other) noexcept
    {
        intersect( &this->anchor, &other.anchor );
        intersect( this->anchor.next(), other.anchor.next() );
    }
    friend void swap(list& a, list& b) noexcept { a.swap( b ); }

    void clear() noexcept { erase( begin(), end() ); }

// 23.3.5.5, list operations:
    void splice(const_iterator position, list& x) noexcept                                             { iter_splice( position, x.cbegin(), x.cend() ); }
    void splice(const_iterator position, list&& x) noexcept                                            { iter_splice( position, x.cbegin(), x.cend() ); }
    void splice(const_iterator position, list& x, const_iterator i) noexcept                           { iter_splice( position, i ); }
    void splice(const_iterator position, list&& x, const_iterator i) noexcept                          { iter_splice( position, i ); }
    void splice(const_iterator position, list& x, const_iterator first, const_iterator last) noexcept  { iter_splice( position, first, last ); }
    void splice(const_iterator position, list&& x, const_iterator first, const_iterator last) noexcept { iter_splice( position, first, last ); }

    void remove(const T& value) { remove_if( [&](const T& v) { return v == value; } ); }

    template <typename Predicate>
    void remove_if(Predicate pred) noexcept
    {
         for ( auto it = begin(); it != end(); )
             if ( pred( *it ) )
                 it = erase( it );
             else
                 ++it;
    }

    void unique() noexcept { unique( std::equal_to<T>() ); }
    template <typename BinaryPredicate>
    void unique(BinaryPredicate binary_pred) noexcept
    {
         auto it = cbegin();
         if ( it == cend() )
             return;
         for ( auto it2 = it; ++it2 != cend(); it2 = it )
             if ( binary_pred( *it, *it2 ) )
                 erase( it2 );
             else
                 it = it2;
    }

    void merge(list& x)  noexcept { merge( x, std::less<T>() ); }
    void merge(list&& x) noexcept { merge( x ); }
    template <typename Compare>
    void merge(list& x, Compare comp) noexcept
    {
        auto it = cbegin();
        if ( it == cend() )
            return splice( it, x );
        auto it2 = x.cbegin();
        if ( it2 == x.cend() )
            return;
        for ( ;; )
        {
            while ( !comp( *it2, *it ) )
                if ( ++it == cend() )
                    return splice( it, x );
            iter_splice( it, it2++ );
            if ( it2 == x.cend() )
                return;
        }
    }
    template <typename Compare>
    void merge(list&& x, Compare comp) noexcept { merge( x, comp ); };

    void reverse() noexcept
    {
        ring_node* p = const_cast<ring_node*>( &this->anchor );
        do {
            flip( p );
            p = p->next();
        } while ( p != &this->anchor );
    }

    void sort() noexcept { sort( std::less<T>() ); }
    template <typename Compare>
    void sort(Compare comp) noexcept
    {
        list tmp[64];
        list* last = tmp;

        while ( !empty() )
        {
            iter_splice( tmp[0].begin(), begin() );
            auto p = tmp;
            for( ;; ++p )
            {
                bool empty = p[1].empty();
                p[1].merge( p[0] );
                if ( empty )
                    break;
            }
            if ( p == last )
                ++last;
        }
        while ( last != tmp )
            merge( *last-- );
    }
private:
    node_allocator_type& node_alloc() noexcept { return *this; }
    const node_allocator_type& node_alloc() const noexcept { return *this; }
};

#include <iostream>
#include <iterator>
#include <algorithm>

struct foo_t {

    unsigned value;

    foo_t() : value() {}
    foo_t( unsigned value ) : value( value ) {}
    operator unsigned() const { return value; }

    void tell() { std::cout << value; }
};

int main()
{
    // ein paar Tests ...

    list< foo_t > list_1;

    for( unsigned i = 0; i < 20; ++i )
        list_1.push_back( foo_t( i ) );

    for( auto it = list_1.begin(); it != list_1.end(); ++it ) {

        it->tell();
        std::cout << " ";
    }
    std::cout.put( '\n' );

    list< foo_t > list_2;

    std::copy( list_1.begin(), list_1.end(), std::back_inserter( list_2 ) );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    std::for_each( std::begin( list_2 ), std::end( list_2 ), []( foo_t &foo ) { foo.value *= 2; } );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    auto list_x = list_1;
    auto list_y = list_2;
    list_x.merge( list_y );
    std::copy( list_x.begin(), list_x.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_1 = list_2;
    std::copy( list_1.begin(), list_1.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_1.reverse();
    std::copy( list_1.begin(), list_1.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    auto head = list_1.cbegin();
    auto tail = list_1.cend();

    for( unsigned i = 0; i < 3; ++i ) {

        ++head;
        --tail;
    }

    list_1.erase( head, tail );
    std::copy( list_1.begin(), list_1.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_1.resize( 12, 42 );
    std::copy( list_1.begin(), list_1.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_1.resize( 7 );
    std::copy( list_1.begin(), list_1.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_1.erase( list_1.cbegin() );
    std::copy( list_1.begin(), list_1.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_1.erase( --list_1.cend() );
    std::copy( list_1.begin(), list_1.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    auto it = list_2.begin();
    while( it != list_2.end() ) {

        if( *it > 15 )
            it = list_2.erase( it );
        else
            ++it;
    }
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    std::vector< foo_t > vec( list_2.cbegin(), list_2.cend() );
    std::copy( vec.begin(), vec.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( ++list_2.cbegin(), 1 );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( --list_2.cend(), 13 );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( list_2.cbegin(), 4, foo_t( 42 ) );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( list_2.cend(), 4, foo_t( 42 ) );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( ++list_2.cbegin(), 3, foo_t( 17 ) );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( --list_2.cend(), 2, foo_t( 17 ) );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( --list_2.cend(), vec.cbegin(), vec.cend() );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.insert( list_2.cbegin(), --vec.cend(), vec.cend() );
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list_2.sort();
    std::copy( list_2.begin(), list_2.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );

    list< foo_t > list_3( vec.cbegin(), vec.cend() );
    std::copy( list_3.begin(), list_3.end(), std::ostream_iterator< unsigned >( std::cout, " " ) );
    std::cout.put( '\n' );
}