#include <iostream>
#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 p = std::allocator_traits<Allocator>::allocate( allocator, 1 );
    try
    {
        std::allocator_traits<Allocator>::construct( allocator, p , std::forward<Args>( args )... );
    }
    catch (...)
    {
        std::allocator_traits<Allocator>::destroy( allocator, p );
        throw;
    }
    return p;
}

template <typename Allocator>
void allocator_delete(Allocator& allocator, typename Allocator::pointer p)
{
    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)
    {
        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 )... )
    {}

    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)
    {
        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 splice(const_list_iterator<Allocator> pos, const_list_iterator<Allocator> first, const_list_iterator<Allocator> last);

template <typename Allocator>
class const_list_iterator
: public std::iterator<std::bidirectional_iterator_tag,
                       typename Allocator::value_type::type,
                       typename Allocator::difference_type,
                       typename Allocator::value_type::type*,
                       typename Allocator::value_type::type&>
{
    template <typename, typename> friend class list;
    friend void splice<>(const_list_iterator, const_list_iterator, const_list_iterator);
public:
    using value_type = typename Allocator::value_type::type;
    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  { return node = node->next(), node->prev(); }
    const_list_iterator& operator--() noexcept    { return node = node->prev(), *this; }
    const_list_iterator operator--(int) noexcept  { return node = node->prev(), node->next(); }

    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>
{
    template <typename, typename> friend class list;
public:
    using value_type = typename Allocator::value_type::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  { return this->node = this->node->next(), this->node->prev(); }
    list_iterator& operator--() noexcept    { return this->node = this->node->prev(), *this; }
    list_iterator operator--(int) noexcept  { return this->node = this->node->prev(), this->node->next(); }
};

template <typename Allocator>
void splice(const_list_iterator<Allocator> pos, const_list_iterator<Allocator> first, const_list_iterator<Allocator> last)
{
    intersect( last.node, pos.node );
    intersect( last.node, first.node );
}
template <typename Allocator>
void splice(const_list_iterator<Allocator> pos, const_list_iterator<Allocator> i)
{
    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>>;
    ring_node anchor;
    explicit list_base(const Allocator& allocator)
    : 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:
    typedef T value_type;
    typedef Allocator allocator_type;
    typedef typename allocator_type::reference reference;
    typedef typename allocator_type::const_reference const_reference;
    typedef typename allocator_type::pointer pointer;
    typedef typename allocator_type::const_pointer const_pointer;
    typedef typename allocator_type::size_type size_type;
    typedef typename allocator_type::difference_type difference_type;
    typedef list_iterator<node_allocator_type> iterator;
    typedef list_iterator<node_allocator_type> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

// construct/copy/destroy:
    explicit list(const allocator_type& allocator = allocator_type())
        : 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_arithmetic<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)
        : base( other.node_alloc() )
    {
        swap( other );
    }
    list(const list& other, const allocator_type& allocator)
        : list( other.begin(), other.end(), allocator )
    {}
    list(list&& other, const allocator_type& allocator)
        : 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=(list rhs) noexcept
    {
        swap( rhs );
        return *this;
    }

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

    template <typename InputIterator, typename std::enable_if<!std::is_arithmetic<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 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 this->anchor.next(); }
    const_iterator cbegin() const noexcept          { return this->anchor.next(); }
    iterator end() noexcept                         { return &this->anchor; }
    const_iterator end() const noexcept             { return const_cast<ring_node*>( &this->anchor ); }
    const_iterator cend() const noexcept            { return const_cast<ring_node*>( &this->anchor ); }
    reverse_iterator rbegin() noexcept              { return reverse_iterator( begin() ); }
    const_reverse_iterator rbegin() const noexcept  { return const_reverse_iterator( begin() ); }
    const_reverse_iterator crbegin() const noexcept { return crbegin(); }
    reverse_iterator rend() noexcept                { return reverse_iterator( end() ); }
    const_reverse_iterator rend() const noexcept    { return const_reverse_iterator( end() ); }
    const_reverse_iterator crend() const noexcept   { return crend(); }

// 23.3.5.3, capacity:
    bool empty() const noexcept { return begin() == end(); }
    size_type size() const noexcept { return std::distance( begin(), end() ); }
    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()                         { erase( begin() ); }
    template <class... 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()                          { erase( std::prev( end() ) ); }
    template <class... 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 <class... Args>
    iterator emplace(const_iterator position, Args&&... args)
    {
        return node_type::make( node_alloc(), position.node, std::forward<Args>( args )... );
    }
    iterator insert(const_iterator pos, const T& value) { return emplace( pos, 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;
    }

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

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

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

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

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

// 23.3.5.5, list operations:
    friend void splice(const_iterator pos, list& x)
    {
        splice( pos, x.begin(), x.end() );
    }
    friend void splice(const_iterator pos, list&& x)
    {
        splice( pos, x.begin(), x.end() );
    }

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

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

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

    void merge(list& x) { merge( x, std::less<T>() ); }
    void merge(list&& x) { merge( x ); }
    template <typename Compare>
    void merge(list& x, Compare comp)
    {
        auto it = cbegin(), it2 = x.cbegin();
        for ( ;; )
        {
            if ( it == cend() )
                return splice( it, x );
            else if ( it2 == x.cend() )
                return;
            else if ( !comp( *it2, *it ) )
                ++it;
            else
                splice( it, it2++ );
        }
    }
    template <typename Compare>
    void merge(list&& x, Compare comp) { 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() { sort( std::less<T>() ); }
    template <typename Compare>
    void sort(Compare comp);
private:
    node_allocator_type& node_alloc()
    {
        return *this;
    }
    const node_allocator_type& node_alloc() const
    {
        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' );

    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< 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' );
}