Ideone.com

download

copy

#include <memory>
#include <cstddef>
 
template<typename Value,
         typename Alloc = std::allocator<Value>>
struct ListAlloc
{
    using value_type = Value;
 
// ///////////////////////////////////////////////////////////////////////////////////////////
 
    struct NodeBase
    {
		NodeBase *prev,
                 *next;
 
		NodeBase( NodeBase* prev, NodeBase* next ) noexcept :
			prev{prev},
			next{next} {}
 
		NodeBase() noexcept :
			NodeBase{nullptr, nullptr} {}
	} mutable mStart, mEnd;
 
	struct Node : NodeBase
	{
		value_type data;
 
        template<typename... Args>
		Node( NodeBase* prev, NodeBase* next, Args&&... args ) noexcept :
			NodeBase{prev, next},
			data{std::forward<Args>(args)...} {}
 
		Node() noexcept = default;
	};
 
    using allocator_type = typename Alloc::template rebind<Node>::other;
	using allocator_traits = std::allocator_traits<allocator_type>;
 
/// ////////////////////////////
 
	#define takeover( N ) using N = typename allocator_traits::N;
 
	typedef value_type& reference;
	typedef value_type const& const_reference;
 
	takeover(pointer)
	takeover(const_pointer)
 
	takeover(difference_type)
	takeover(size_type)
 
	#undef takeover
 
/// /////////////////////////////
 
	allocator_type mAllocator;
 
	ListAlloc( NodeBase const& start, NodeBase const& end, allocator_type const& alloc = allocator_type{} ):
	    mStart{start}, mEnd{end},
	    mAllocator{alloc} {}
 
    template<typename... Args>
    Node* _alloc_make_node( NodeBase* prev, NodeBase* next, Args&&... args )
    {
        Node* node = allocator_traits::allocate( mAllocator, 1 );
 
        try
        {
            allocator_traits::construct( mAllocator, node, prev, next, std::forward<Args>(args)... );
        }
        catch(...)
        {
            allocator_traits::deallocate( mAllocator, node, 1 );
            throw;
        }
 
        return node;
    }
 
    template<typename... Args>
    Node* _alloc_make_node_notify( NodeBase* prev, NodeBase* next, Args&&... args )
    {
        Node* node = _alloc_make_node( prev, next, std::forward<Args>(args)... );
 
        if( prev )
            prev->next = node;
        if( next )
            next->prev = node;
 
        return node;
    }
 
    void _alloc_destroy_node( Node* ptr )
    {
        allocator_traits::destroy( mAllocator, ptr );
        allocator_traits::deallocate( mAllocator, ptr, 1 );
    }
 
	void _alloc_destroy_all_prev( NodeBase* end, NodeBase* ptr )
    {
        NodeBase* old_ptr;
		while( ptr != end )
		{
			old_ptr = ptr;
			ptr = ptr->prev;
			_alloc_destroy_node( static_cast<Node*>(old_ptr) );
		}
	}
 
private:
 
    template<typename... Func>
    std::pair<Node*, Node*> _alloc_create_impl( size_type n, Func... func )
    {
        if( n == 0 )
            return { nullptr, nullptr };
 
		Node* ptr = _alloc_make_node_notify( ptr, nullptr, func()... );
		Node* const rval = ptr;
 
		while( --n ) try
        {
            ptr = _alloc_make_node_notify( ptr, nullptr, func()... );
        }
        catch(...)
        {
            ptr = ptr->prev;
            _alloc_destroy_all_prev( ptr );
            throw;
        }
 
 
		return {rval, ptr};
    }
 
public:
	std::pair<Node*, Node*> _alloc_fill_n( size_type n )
	{
	    return _alloc_create_impl( n );
	}
 
	std::pair<Node*, Node*> _alloc_fill_n( size_type n, const_reference value )
	{
        return _alloc_create_impl( n, [&]() -> const_reference { return value; } );
	}
 
    template<typename InputIterator>
    std::pair<Node*, Node*> _alloc_copy( size_type n, InputIterator first )
    {
        return _alloc_create_impl( n, [&]() -> const_reference { return *first++; } );
    }
 
// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
    void _alloc_swap( allocator_type& lhs, allocator_type& rhs, std::true_type )
    { std::swap(lhs, rhs); }
    void _alloc_swap( allocator_type&, allocator_type&, std::false_type )
    {}
 
    allocator_type get_allocator() const { return mAllocator; }
 
    size_type max_size() const { return allocator_traits::max_size(mAllocator); }
};
 
#include <type_traits>
 
/// Geborgt von camper - verzeih'
#define TAG_CHECK(It, ItTag) \
           ,typename std::enable_if<std::is_convertible< \
                 typename std::conditional<std::is_class<It>::value || std::is_pointer<It>::value, std::iterator_traits<It>, std::false_type>::type::iterator_category, \
                 ItTag>::value, int>::type = 0
 
#include <iterator>
 
template<typename Value,
         typename Alloc = std::allocator<Value>>
class List : ListAlloc<Value, Alloc>
{
    #define takeover(N) using ListAlloc<Value,Alloc>::N;
 
    takeover(_alloc_copy)
    takeover(_alloc_make_node_notify)
    takeover(_alloc_make_node)
    takeover(_alloc_fill_n)
    takeover(_alloc_swap)
    takeover(_alloc_destroy_all_prev)
    takeover(_alloc_destroy_node)
 
    takeover(mAllocator)
    takeover(mStart)
    takeover(mEnd)
 
    typedef typename List::allocator_traits allocator_traits;
 
public:
 
    takeover( get_allocator )
    takeover( max_size )
 
    #undef takeover
    #define takeover(N) using typename ListAlloc<Value,Alloc>::N;
    takeover(NodeBase)
 
private:
    takeover(Node)
 
public:
    takeover(value_type)
    takeover(reference)
    takeover(const_reference)
    takeover(pointer)
    takeover(const_pointer)
    takeover(difference_type)
    takeover(size_type)
    takeover(allocator_type)
 
 
#define DEFINE_OP( class, mem, ch ) \
    class& operator ch() noexcept \
    { \
        p = p->mem; \
        return *this; \
    }
 
#define DEFINE_POST_OP( class, ch ) \
    class operator ch(int) noexcept \
    { \
        auto rval = *this; \
        ch*this; \
        return rval; \
    }
 
	struct iterator : std::iterator<std::bidirectional_iterator_tag,
	                                value_type,
                                    difference_type,
	                                pointer,
	                                reference>
	{
	private:
 
		friend class List;
		friend class const_iterator;
 
		NodeBase* p;
 
		iterator( NodeBase* p ) noexcept :
			p{p} {}
 
	public:
 
	    iterator() noexcept :
	        iterator{nullptr} {}
 
		reference operator*() noexcept { return static_cast<Node*>(p)->data; }
		pointer operator->() noexcept { return &static_cast<Node*>(p)->data; }
 
		DEFINE_OP( iterator, next, ++ )
		DEFINE_OP( iterator, prev, -- )
		DEFINE_POST_OP( iterator, ++ )
		DEFINE_POST_OP( iterator, -- )
 
		friend bool operator==( iterator lhs, iterator rhs ) noexcept { return lhs.p == rhs.p; }
		friend bool operator!=( iterator lhs, iterator rhs ) noexcept { return !(lhs == rhs); }
	};
 
	struct const_iterator : std::iterator<std::bidirectional_iterator_tag,
	                                      value_type const,
                                          difference_type,
	                                      const_pointer,
	                                      const_reference>
	{
	private:
 
		friend class List;
 
		mutable NodeBase* p;
 
		const_iterator( NodeBase* p ) noexcept :
			p{p} {}
 
	public:
 
	    const_iterator() noexcept :
	        const_iterator{nullptr} {}
 
		const_iterator( iterator it ) noexcept :
			p{it.p} {}
 
		const_reference operator*() noexcept { return static_cast<Node*>(p)->data; }
		const_pointer operator->() noexcept { return &static_cast<Node*>(p)->data; }
 
		DEFINE_OP( const_iterator, next, ++ )
		DEFINE_OP( const_iterator, prev, -- )
		DEFINE_POST_OP( const_iterator, ++ )
		DEFINE_POST_OP( const_iterator, -- )
 
		friend bool operator==( const_iterator lhs, const_iterator rhs ) noexcept { return lhs.p == rhs.p; }
		friend bool operator!=( const_iterator lhs, const_iterator rhs ) noexcept { return !(lhs == rhs); }
	};
 
#undef DEFINE_POST_OP
#undef DEFINE_OP
 
	typedef std::reverse_iterator<iterator> reverse_iterator;
	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
private:
 
	size_type mSize;
 
/// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
    void _assign_to( std::pair<Node*, Node*> pair )
    {
		mStart.next = pair.first;
		mEnd.prev = pair.second;
    }
 
    template<typename scenario_bool>
	void _swap( List& other )
	{
	    std::swap( mStart, other.mStart );
	    std::swap( mEnd, other.mEnd );
	    std::swap( mSize, other.mSize );
	    _alloc_swap( mAllocator, other.mAllocator, scenario_bool{} );
	}
 
public:
 
	void swap( List& other )
	{
	    _swap<typename allocator_traits::propagate_on_container_swap>(other);
	}
 
	explicit List( allocator_type const& alloc = allocator_type{} ):
		ListAlloc<Value, Alloc>{NodeBase{ nullptr, &mEnd }, // Start-NodeBase
		                        NodeBase{ &mStart, nullptr }, // End-NodeBase
		                        alloc},
		mSize{0} {}
 
	explicit List( size_type count,
				   const_reference value,
				   allocator_type const& alloc = allocator_type{} ):
		ListAlloc<Value, Alloc>{alloc},
		mSize{count}
	{
	    _assign_to( _alloc_fill_n(count, mAllocator.address(value)) );
	}
 
	explicit List( size_type count,
				   allocator_type const& alloc = allocator_type{} ):
		ListAlloc<Value, Alloc>{alloc},
		mSize{count}
	{
	    _assign_to( _alloc_fill_n(count) );
	}
 
	template<typename InputIterator
             TAG_CHECK(InputIterator, std::input_iterator_tag)>
	explicit List( InputIterator first,
                   InputIterator last,
                   allocator_type const& alloc = allocator_type{} ):
       List{alloc}
    {
        assign(first, last);
    }
 
    List( std::initializer_list<value_type> ilist,
          allocator_type const& alloc = allocator_type{} ):
        List(std::begin(ilist), std::end(ilist), alloc) {}
 
    List( List const& l ):
        ListAlloc<Value, Alloc>{ allocator_traits::select_on_container_copy_construction(l.mAllocator) },
        mSize{l.mSize}
    { _assign_to( _alloc_copy( mSize, l.cbegin() ) ); }
 
    List( List const& l, allocator_type const& alloc ):
        ListAlloc<Value, Alloc>{alloc},
        mSize{l.mSize}
    { _assign_to( _alloc_copy( mSize, l.cbegin() ) ); }
 
    List& operator=( List const& l )
    {
        clear();
 
        if( allocator_traits::propagate_on_container_copy_assignment::value )
            mAllocator = l.mAllocator;
 
        _assign_to( _alloc_copy( l.mSize, l.cbegin() ) );
        mSize = l.mSize;
 
        return *this;
    }
 
    List( List&& l ):
		List{}
    { _swap<std::false_type>(l); }
 
    List( List&& l, allocator_type const& alloc ):
        List{alloc}
    { _swap<std::false_type>(l); }
 
    List& operator=( List&& l )
    {
        clear();
        _swap<allocator_traits::propagate_on_container_move_assignment>(l);
    }
 
	~List() // noexcept (ist schon default)
	{
	    clear();
	}
 
    void assign( size_type count, const_reference value )
    {
        clear();
        mSize = count;
        _assign_to( _alloc_fill_n(count, mAllocator.address(value)) );
    }
 
    template<typename InputIterator>
    void assign( InputIterator first, InputIterator last )
    {
        clear();
        insert( cbegin(), first, last );
    }
 
    void assign( std::initializer_list<value_type> ilist )
    {
        assign(std::begin(ilist), std::end(ilist));
    }
 
	size_type size() const { return mSize; }
 
	bool empty() const { return size() == 0; }
 
	void clear()
	{
	    _alloc_destroy_all_prev( &mStart, mEnd.prev );
	    mSize = 0;
	}
 
	iterator begin()              noexcept { return mStart.next ; }
	iterator end()                noexcept { return &mEnd   ; }
	const_iterator begin()  const noexcept { return mStart.next ; }
	const_iterator end()    const noexcept { return &mEnd   ; }
	const_iterator cbegin() const noexcept { return begin(); }
	const_iterator cend()   const noexcept { return end()  ; }
 
	reverse_iterator rbegin()              { return reverse_iterator{begin()}; }
	reverse_iterator rend()                { return reverse_iterator{end()  }; }
	const_reverse_iterator rbegin()  const { return const_reverse_iterator{cbegin()}; }
	const_reverse_iterator rend()    const { return const_reverse_iterator{cend()  }; }
	const_reverse_iterator crbegin() const { return rbegin(); }
	const_reverse_iterator crend()   const { return rend()  ; }
 
	reference front() noexcept { return *begin(); }
	reference back() noexcept { return *--iterator{end()}; }
	const_reference front() const noexcept { return *cbegin(); }
	const_reference back() const noexcept { return *--const_iterator{cend()}; }
 
    template<typename... ValueT>
    iterator emplace( const_iterator it, ValueT&&... v )
    {
        auto node = _alloc_make_node_notify( it.p->prev, it.p, std::forward<ValueT>(v)... );
 
        ++mSize;
 
        return node;
    }
 
    iterator insert( const_iterator it, const_reference value )
    { return emplace(it, value); }
    iterator insert( const_iterator it, value_type&& value )
    { return emplace(it, value); }
 
    iterator insert( const_iterator it, size_type count, const_reference value )
    {
        if( count == 0 )
            return it;
 
        auto rval = insert( it, value );
 
        while( --count )
            insert( it, value );
 
        return rval;
    }
 
    template<typename InputIterator
             TAG_CHECK(InputIterator, std::input_iterator_tag)>
    iterator insert( const_iterator it, InputIterator first, InputIterator last )
    {
        if( first == last )
            return it;
 
        auto rval = insert( it, *first );
 
        while( ++first != last )
            insert( it, *first );
 
        return rval;
    }
 
    iterator insert( const_iterator it, std::initializer_list<value_type> ilist )
    {
        insert( it, std::begin(ilist), std::end(ilist) );
    }
 
    template<typename... Args>
    iterator emplace_back( Args&&... args )
    {
        return emplace( cend(), std::forward<Args>(args)... );
    }
 
    template<typename... Args>
    iterator emplace_front( Args&&... args )
    {
        return emplace( cbegin(), std::forward<Args>(args)... );
    }
 
    void push_back( const_reference v )
    { insert( cend(), v ); }
    void push_back( value_type&& v )
    { insert( cend(), v ); }
 
    void push_front( const_reference v )
    { insert( cbegin(), v ); }
    void push_front( value_type&& v )
    { insert( cbegin(), v ); }
 
    iterator erase( const_iterator it )
    {
        auto rval = it.p->next;
 
        it.p->prev->next = it.p->next;
        it.p->next->prev = it.p->prev;
 
        _alloc_destroy_node( static_cast<Node*>(it.p) );
 
        --mSize;
 
        return rval;
    }
 
    iterator erase( const_iterator first, const_iterator last )
    {
        while( first != last )
            erase( first++ );
 
        return last;
    }
 
    void pop_back()
    { erase( --end() ); }
    void pop_front()
    { erase( begin() ); }
 
private:
 
    template<typename ... Args>
    void _resize_impl( size_type new_size, Args&&... args )
    {
        if( new_size > size() )
            for( size_type n = size(); n != new_size; ++n )
                emplace_back( std::forward<Args>(args)... );
 
        else if( new_size < size() )
            erase( std::next(cbegin(), new_size), cend() );
    }
 
public:
    void resize( size_type new_size, const_reference value )
    { _resize_impl( new_size, value ); }
    void resize( size_type new_size )
    { _resize_impl( new_size ); }
};
 
#include <iostream>
#include <iterator>
#include <cassert>
#include <string>
 
int main()
{
#define check(s) assert(std::string(l.begin(), l.end()) == s)
 
  List<char> l;
  l.push_back('m');  check("m");
  l.push_back('z');  check("mz");
  l.push_front('a'); check("amz");
  l.erase(l.begin());check("mz");
  l.insert(l.begin(), 'a');check("amz");
  l.insert(l.end(), '!');  check("amz!");
  l.pop_front();     check("mz!");
  l.pop_back();      check("mz");
  List<char>::iterator i=l.begin(); i++;
  i = l.insert(i, '-'); check("m-z");
  i = l.erase(i);       check("mz");
  l.erase(i);           check("m");
  l.push_front('a');    check("am");
  l.push_back('z');     check("amz");
  i=l.end(); i--; i--;
  i=l.erase(i);         check("az");
}

I2luY2x1ZGUgPG1lbW9yeT4KI2luY2x1ZGUgPGNzdGRkZWY+Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBWYWx1ZSwKICAgICAgICAgdHlwZW5hbWUgQWxsb2MgPSBzdGQ6OmFsbG9jYXRvcjxWYWx1ZT4+CnN0cnVjdCBMaXN0QWxsb2MKewogICAgdXNpbmcgdmFsdWVfdHlwZSA9IFZhbHVlOwoKLy8gLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwoKICAgIHN0cnVjdCBOb2RlQmFzZQogICAgewoJCU5vZGVCYXNlICpwcmV2LAogICAgICAgICAgICAgICAgICpuZXh0OwoKCQlOb2RlQmFzZSggTm9kZUJhc2UqIHByZXYsIE5vZGVCYXNlKiBuZXh0ICkgbm9leGNlcHQgOgoJCQlwcmV2e3ByZXZ9LAoJCQluZXh0e25leHR9IHt9CgoJCU5vZGVCYXNlKCkgbm9leGNlcHQgOgoJCQlOb2RlQmFzZXtudWxscHRyLCBudWxscHRyfSB7fQoJfSBtdXRhYmxlIG1TdGFydCwgbUVuZDsKCglzdHJ1Y3QgTm9kZSA6IE5vZGVCYXNlCgl7CgkJdmFsdWVfdHlwZSBkYXRhOwoKICAgICAgICB0ZW1wbGF0ZTx0eXBlbmFtZS4uLiBBcmdzPgoJCU5vZGUoIE5vZGVCYXNlKiBwcmV2LCBOb2RlQmFzZSogbmV4dCwgQXJncyYmLi4uIGFyZ3MgKSBub2V4Y2VwdCA6CgkJCU5vZGVCYXNle3ByZXYsIG5leHR9LAoJCQlkYXRhe3N0ZDo6Zm9yd2FyZDxBcmdzPihhcmdzKS4uLn0ge30KCgkJTm9kZSgpIG5vZXhjZXB0ID0gZGVmYXVsdDsKCX07CgogICAgdXNpbmcgYWxsb2NhdG9yX3R5cGUgPSB0eXBlbmFtZSBBbGxvYzo6dGVtcGxhdGUgcmViaW5kPE5vZGU+OjpvdGhlcjsKCXVzaW5nIGFsbG9jYXRvcl90cmFpdHMgPSBzdGQ6OmFsbG9jYXRvcl90cmFpdHM8YWxsb2NhdG9yX3R5cGU+OwoKLy8vIC8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCgkjZGVmaW5lIHRha2VvdmVyKCBOICkgdXNpbmcgTiA9IHR5cGVuYW1lIGFsbG9jYXRvcl90cmFpdHM6Ok47CgoJdHlwZWRlZiB2YWx1ZV90eXBlJiByZWZlcmVuY2U7Cgl0eXBlZGVmIHZhbHVlX3R5cGUgY29uc3QmIGNvbnN0X3JlZmVyZW5jZTsKCgl0YWtlb3Zlcihwb2ludGVyKQoJdGFrZW92ZXIoY29uc3RfcG9pbnRlcikKCgl0YWtlb3ZlcihkaWZmZXJlbmNlX3R5cGUpCgl0YWtlb3ZlcihzaXplX3R5cGUpCgoJI3VuZGVmIHRha2VvdmVyCgovLy8gLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCglhbGxvY2F0b3JfdHlwZSBtQWxsb2NhdG9yOwoKCUxpc3RBbGxvYyggTm9kZUJhc2UgY29uc3QmIHN0YXJ0LCBOb2RlQmFzZSBjb25zdCYgZW5kLCBhbGxvY2F0b3JfdHlwZSBjb25zdCYgYWxsb2MgPSBhbGxvY2F0b3JfdHlwZXt9ICk6CgkgICAgbVN0YXJ0e3N0YXJ0fSwgbUVuZHtlbmR9LAoJICAgIG1BbGxvY2F0b3J7YWxsb2N9IHt9CgogICAgdGVtcGxhdGU8dHlwZW5hbWUuLi4gQXJncz4KICAgIE5vZGUqIF9hbGxvY19tYWtlX25vZGUoIE5vZGVCYXNlKiBwcmV2LCBOb2RlQmFzZSogbmV4dCwgQXJncyYmLi4uIGFyZ3MgKQogICAgewogICAgICAgIE5vZGUqIG5vZGUgPSBhbGxvY2F0b3JfdHJhaXRzOjphbGxvY2F0ZSggbUFsbG9jYXRvciwgMSApOwoKICAgICAgICB0cnkKICAgICAgICB7CiAgICAgICAgICAgIGFsbG9jYXRvcl90cmFpdHM6OmNvbnN0cnVjdCggbUFsbG9jYXRvciwgbm9kZSwgcHJldiwgbmV4dCwgc3RkOjpmb3J3YXJkPEFyZ3M+KGFyZ3MpLi4uICk7CiAgICAgICAgfQogICAgICAgIGNhdGNoKC4uLikKICAgICAgICB7CiAgICAgICAgICAgIGFsbG9jYXRvcl90cmFpdHM6OmRlYWxsb2NhdGUoIG1BbGxvY2F0b3IsIG5vZGUsIDEgKTsKICAgICAgICAgICAgdGhyb3c7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gbm9kZTsKICAgIH0KCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZS4uLiBBcmdzPgogICAgTm9kZSogX2FsbG9jX21ha2Vfbm9kZV9ub3RpZnkoIE5vZGVCYXNlKiBwcmV2LCBOb2RlQmFzZSogbmV4dCwgQXJncyYmLi4uIGFyZ3MgKQogICAgewogICAgICAgIE5vZGUqIG5vZGUgPSBfYWxsb2NfbWFrZV9ub2RlKCBwcmV2LCBuZXh0LCBzdGQ6OmZvcndhcmQ8QXJncz4oYXJncykuLi4gKTsKCiAgICAgICAgaWYoIHByZXYgKQogICAgICAgICAgICBwcmV2LT5uZXh0ID0gbm9kZTsKICAgICAgICBpZiggbmV4dCApCiAgICAgICAgICAgIG5leHQtPnByZXYgPSBub2RlOwoKICAgICAgICByZXR1cm4gbm9kZTsKICAgIH0KCiAgICB2b2lkIF9hbGxvY19kZXN0cm95X25vZGUoIE5vZGUqIHB0ciApCiAgICB7CiAgICAgICAgYWxsb2NhdG9yX3RyYWl0czo6ZGVzdHJveSggbUFsbG9jYXRvciwgcHRyICk7CiAgICAgICAgYWxsb2NhdG9yX3RyYWl0czo6ZGVhbGxvY2F0ZSggbUFsbG9jYXRvciwgcHRyLCAxICk7CiAgICB9CgoJdm9pZCBfYWxsb2NfZGVzdHJveV9hbGxfcHJldiggTm9kZUJhc2UqIGVuZCwgTm9kZUJhc2UqIHB0ciApCiAgICB7CiAgICAgICAgTm9kZUJhc2UqIG9sZF9wdHI7CgkJd2hpbGUoIHB0ciAhPSBlbmQgKQoJCXsKCQkJb2xkX3B0ciA9IHB0cjsKCQkJcHRyID0gcHRyLT5wcmV2OwoJCQlfYWxsb2NfZGVzdHJveV9ub2RlKCBzdGF0aWNfY2FzdDxOb2RlKj4ob2xkX3B0cikgKTsKCQl9Cgl9Cgpwcml2YXRlOgoKICAgIHRlbXBsYXRlPHR5cGVuYW1lLi4uIEZ1bmM+CiAgICBzdGQ6OnBhaXI8Tm9kZSosIE5vZGUqPiBfYWxsb2NfY3JlYXRlX2ltcGwoIHNpemVfdHlwZSBuLCBGdW5jLi4uIGZ1bmMgKQogICAgewogICAgICAgIGlmKCBuID09IDAgKQogICAgICAgICAgICByZXR1cm4geyBudWxscHRyLCBudWxscHRyIH07CgoJCU5vZGUqIHB0ciA9IF9hbGxvY19tYWtlX25vZGVfbm90aWZ5KCBwdHIsIG51bGxwdHIsIGZ1bmMoKS4uLiApOwoJCU5vZGUqIGNvbnN0IHJ2YWwgPSBwdHI7CgoJCXdoaWxlKCAtLW4gKSB0cnkKICAgICAgICB7CiAgICAgICAgICAgIHB0ciA9IF9hbGxvY19tYWtlX25vZGVfbm90aWZ5KCBwdHIsIG51bGxwdHIsIGZ1bmMoKS4uLiApOwogICAgICAgIH0KICAgICAgICBjYXRjaCguLi4pCiAgICAgICAgewogICAgICAgICAgICBwdHIgPSBwdHItPnByZXY7CiAgICAgICAgICAgIF9hbGxvY19kZXN0cm95X2FsbF9wcmV2KCBwdHIgKTsKICAgICAgICAgICAgdGhyb3c7CiAgICAgICAgfQoKCgkJcmV0dXJuIHtydmFsLCBwdHJ9OwogICAgfQoKcHVibGljOgoJc3RkOjpwYWlyPE5vZGUqLCBOb2RlKj4gX2FsbG9jX2ZpbGxfbiggc2l6ZV90eXBlIG4gKQoJewoJICAgIHJldHVybiBfYWxsb2NfY3JlYXRlX2ltcGwoIG4gKTsKCX0KCglzdGQ6OnBhaXI8Tm9kZSosIE5vZGUqPiBfYWxsb2NfZmlsbF9uKCBzaXplX3R5cGUgbiwgY29uc3RfcmVmZXJlbmNlIHZhbHVlICkKCXsKICAgICAgICByZXR1cm4gX2FsbG9jX2NyZWF0ZV9pbXBsKCBuLCBbJl0oKSAtPiBjb25zdF9yZWZlcmVuY2UgeyByZXR1cm4gdmFsdWU7IH0gKTsKCX0KCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBJbnB1dEl0ZXJhdG9yPgogICAgc3RkOjpwYWlyPE5vZGUqLCBOb2RlKj4gX2FsbG9jX2NvcHkoIHNpemVfdHlwZSBuLCBJbnB1dEl0ZXJhdG9yIGZpcnN0ICkKICAgIHsKICAgICAgICByZXR1cm4gX2FsbG9jX2NyZWF0ZV9pbXBsKCBuLCBbJl0oKSAtPiBjb25zdF9yZWZlcmVuY2UgeyByZXR1cm4gKmZpcnN0Kys7IH0gKTsKICAgIH0KCi8vIC8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCiAgICB2b2lkIF9hbGxvY19zd2FwKCBhbGxvY2F0b3JfdHlwZSYgbGhzLCBhbGxvY2F0b3JfdHlwZSYgcmhzLCBzdGQ6OnRydWVfdHlwZSApCiAgICB7IHN0ZDo6c3dhcChsaHMsIHJocyk7IH0KICAgIHZvaWQgX2FsbG9jX3N3YXAoIGFsbG9jYXRvcl90eXBlJiwgYWxsb2NhdG9yX3R5cGUmLCBzdGQ6OmZhbHNlX3R5cGUgKQogICAge30KCiAgICBhbGxvY2F0b3JfdHlwZSBnZXRfYWxsb2NhdG9yKCkgY29uc3QgeyByZXR1cm4gbUFsbG9jYXRvcjsgfQoKICAgIHNpemVfdHlwZSBtYXhfc2l6ZSgpIGNvbnN0IHsgcmV0dXJuIGFsbG9jYXRvcl90cmFpdHM6Om1heF9zaXplKG1BbGxvY2F0b3IpOyB9Cn07CgojaW5jbHVkZSA8dHlwZV90cmFpdHM+CgovLy8gR2Vib3JndCB2b24gY2FtcGVyIC0gdmVyemVpaCcKI2RlZmluZSBUQUdfQ0hFQ0soSXQsIEl0VGFnKSBcCiAgICAgICAgICAgLHR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmPHN0ZDo6aXNfY29udmVydGlibGU8IFwKICAgICAgICAgICAgICAgICB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsPHN0ZDo6aXNfY2xhc3M8SXQ+Ojp2YWx1ZSB8fCBzdGQ6OmlzX3BvaW50ZXI8SXQ+Ojp2YWx1ZSwgc3RkOjppdGVyYXRvcl90cmFpdHM8SXQ+LCBzdGQ6OmZhbHNlX3R5cGU+Ojp0eXBlOjppdGVyYXRvcl9jYXRlZ29yeSwgXAogICAgICAgICAgICAgICAgIEl0VGFnPjo6dmFsdWUsIGludD46OnR5cGUgPSAwCgojaW5jbHVkZSA8aXRlcmF0b3I+Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBWYWx1ZSwKICAgICAgICAgdHlwZW5hbWUgQWxsb2MgPSBzdGQ6OmFsbG9jYXRvcjxWYWx1ZT4+CmNsYXNzIExpc3QgOiBMaXN0QWxsb2M8VmFsdWUsIEFsbG9jPgp7CiAgICAjZGVmaW5lIHRha2VvdmVyKE4pIHVzaW5nIExpc3RBbGxvYzxWYWx1ZSxBbGxvYz46Ok47CgogICAgdGFrZW92ZXIoX2FsbG9jX2NvcHkpCiAgICB0YWtlb3ZlcihfYWxsb2NfbWFrZV9ub2RlX25vdGlmeSkKICAgIHRha2VvdmVyKF9hbGxvY19tYWtlX25vZGUpCiAgICB0YWtlb3ZlcihfYWxsb2NfZmlsbF9uKQogICAgdGFrZW92ZXIoX2FsbG9jX3N3YXApCiAgICB0YWtlb3ZlcihfYWxsb2NfZGVzdHJveV9hbGxfcHJldikKICAgIHRha2VvdmVyKF9hbGxvY19kZXN0cm95X25vZGUpCgogICAgdGFrZW92ZXIobUFsbG9jYXRvcikKICAgIHRha2VvdmVyKG1TdGFydCkKICAgIHRha2VvdmVyKG1FbmQpCgogICAgdHlwZWRlZiB0eXBlbmFtZSBMaXN0OjphbGxvY2F0b3JfdHJhaXRzIGFsbG9jYXRvcl90cmFpdHM7CgpwdWJsaWM6CgogICAgdGFrZW92ZXIoIGdldF9hbGxvY2F0b3IgKQogICAgdGFrZW92ZXIoIG1heF9zaXplICkKCiAgICAjdW5kZWYgdGFrZW92ZXIKICAgICNkZWZpbmUgdGFrZW92ZXIoTikgdXNpbmcgdHlwZW5hbWUgTGlzdEFsbG9jPFZhbHVlLEFsbG9jPjo6TjsKICAgIHRha2VvdmVyKE5vZGVCYXNlKQoKcHJpdmF0ZToKICAgIHRha2VvdmVyKE5vZGUpCgpwdWJsaWM6CiAgICB0YWtlb3Zlcih2YWx1ZV90eXBlKQogICAgdGFrZW92ZXIocmVmZXJlbmNlKQogICAgdGFrZW92ZXIoY29uc3RfcmVmZXJlbmNlKQogICAgdGFrZW92ZXIocG9pbnRlcikKICAgIHRha2VvdmVyKGNvbnN0X3BvaW50ZXIpCiAgICB0YWtlb3ZlcihkaWZmZXJlbmNlX3R5cGUpCiAgICB0YWtlb3ZlcihzaXplX3R5cGUpCiAgICB0YWtlb3ZlcihhbGxvY2F0b3JfdHlwZSkKCgojZGVmaW5lIERFRklORV9PUCggY2xhc3MsIG1lbSwgY2ggKSBcCiAgICBjbGFzcyYgb3BlcmF0b3IgY2goKSBub2V4Y2VwdCBcCiAgICB7IFwKICAgICAgICBwID0gcC0+bWVtOyBcCiAgICAgICAgcmV0dXJuICp0aGlzOyBcCiAgICB9CgojZGVmaW5lIERFRklORV9QT1NUX09QKCBjbGFzcywgY2ggKSBcCiAgICBjbGFzcyBvcGVyYXRvciBjaChpbnQpIG5vZXhjZXB0IFwKICAgIHsgXAogICAgICAgIGF1dG8gcnZhbCA9ICp0aGlzOyBcCiAgICAgICAgY2gqdGhpczsgXAogICAgICAgIHJldHVybiBydmFsOyBcCiAgICB9CgoJc3RydWN0IGl0ZXJhdG9yIDogc3RkOjppdGVyYXRvcjxzdGQ6OmJpZGlyZWN0aW9uYWxfaXRlcmF0b3JfdGFnLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZV90eXBlLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaWZmZXJlbmNlX3R5cGUsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBvaW50ZXIsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlZmVyZW5jZT4KCXsKCXByaXZhdGU6CgoJCWZyaWVuZCBjbGFzcyBMaXN0OwoJCWZyaWVuZCBjbGFzcyBjb25zdF9pdGVyYXRvcjsKCgkJTm9kZUJhc2UqIHA7CgoJCWl0ZXJhdG9yKCBOb2RlQmFzZSogcCApIG5vZXhjZXB0IDoKCQkJcHtwfSB7fQoKCXB1YmxpYzoKCgkgICAgaXRlcmF0b3IoKSBub2V4Y2VwdCA6CgkgICAgICAgIGl0ZXJhdG9ye251bGxwdHJ9IHt9CgoJCXJlZmVyZW5jZSBvcGVyYXRvciooKSBub2V4Y2VwdCB7IHJldHVybiBzdGF0aWNfY2FzdDxOb2RlKj4ocCktPmRhdGE7IH0KCQlwb2ludGVyIG9wZXJhdG9yLT4oKSBub2V4Y2VwdCB7IHJldHVybiAmc3RhdGljX2Nhc3Q8Tm9kZSo+KHApLT5kYXRhOyB9CgoJCURFRklORV9PUCggaXRlcmF0b3IsIG5leHQsICsrICkKCQlERUZJTkVfT1AoIGl0ZXJhdG9yLCBwcmV2LCAtLSApCgkJREVGSU5FX1BPU1RfT1AoIGl0ZXJhdG9yLCArKyApCgkJREVGSU5FX1BPU1RfT1AoIGl0ZXJhdG9yLCAtLSApCgoJCWZyaWVuZCBib29sIG9wZXJhdG9yPT0oIGl0ZXJhdG9yIGxocywgaXRlcmF0b3IgcmhzICkgbm9leGNlcHQgeyByZXR1cm4gbGhzLnAgPT0gcmhzLnA7IH0KCQlmcmllbmQgYm9vbCBvcGVyYXRvciE9KCBpdGVyYXRvciBsaHMsIGl0ZXJhdG9yIHJocyApIG5vZXhjZXB0IHsgcmV0dXJuICEobGhzID09IHJocyk7IH0KCX07CgoJc3RydWN0IGNvbnN0X2l0ZXJhdG9yIDogc3RkOjppdGVyYXRvcjxzdGQ6OmJpZGlyZWN0aW9uYWxfaXRlcmF0b3JfdGFnLAoJICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2YWx1ZV90eXBlIGNvbnN0LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaWZmZXJlbmNlX3R5cGUsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnN0X3BvaW50ZXIsCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnN0X3JlZmVyZW5jZT4KCXsKCXByaXZhdGU6CgoJCWZyaWVuZCBjbGFzcyBMaXN0OwoKCQltdXRhYmxlIE5vZGVCYXNlKiBwOwoKCQljb25zdF9pdGVyYXRvciggTm9kZUJhc2UqIHAgKSBub2V4Y2VwdCA6CgkJCXB7cH0ge30KCglwdWJsaWM6CgoJICAgIGNvbnN0X2l0ZXJhdG9yKCkgbm9leGNlcHQgOgoJICAgICAgICBjb25zdF9pdGVyYXRvcntudWxscHRyfSB7fQoKCQljb25zdF9pdGVyYXRvciggaXRlcmF0b3IgaXQgKSBub2V4Y2VwdCA6CgkJCXB7aXQucH0ge30KCgkJY29uc3RfcmVmZXJlbmNlIG9wZXJhdG9yKigpIG5vZXhjZXB0IHsgcmV0dXJuIHN0YXRpY19jYXN0PE5vZGUqPihwKS0+ZGF0YTsgfQoJCWNvbnN0X3BvaW50ZXIgb3BlcmF0b3ItPigpIG5vZXhjZXB0IHsgcmV0dXJuICZzdGF0aWNfY2FzdDxOb2RlKj4ocCktPmRhdGE7IH0KCgkJREVGSU5FX09QKCBjb25zdF9pdGVyYXRvciwgbmV4dCwgKysgKQoJCURFRklORV9PUCggY29uc3RfaXRlcmF0b3IsIHByZXYsIC0tICkKCQlERUZJTkVfUE9TVF9PUCggY29uc3RfaXRlcmF0b3IsICsrICkKCQlERUZJTkVfUE9TVF9PUCggY29uc3RfaXRlcmF0b3IsIC0tICkKCgkJZnJpZW5kIGJvb2wgb3BlcmF0b3I9PSggY29uc3RfaXRlcmF0b3IgbGhzLCBjb25zdF9pdGVyYXRvciByaHMgKSBub2V4Y2VwdCB7IHJldHVybiBsaHMucCA9PSByaHMucDsgfQoJCWZyaWVuZCBib29sIG9wZXJhdG9yIT0oIGNvbnN0X2l0ZXJhdG9yIGxocywgY29uc3RfaXRlcmF0b3IgcmhzICkgbm9leGNlcHQgeyByZXR1cm4gIShsaHMgPT0gcmhzKTsgfQoJfTsKCiN1bmRlZiBERUZJTkVfUE9TVF9PUAojdW5kZWYgREVGSU5FX09QCgoJdHlwZWRlZiBzdGQ6OnJldmVyc2VfaXRlcmF0b3I8aXRlcmF0b3I+IHJldmVyc2VfaXRlcmF0b3I7Cgl0eXBlZGVmIHN0ZDo6cmV2ZXJzZV9pdGVyYXRvcjxjb25zdF9pdGVyYXRvcj4gY29uc3RfcmV2ZXJzZV9pdGVyYXRvcjsKCnByaXZhdGU6CgoJc2l6ZV90eXBlIG1TaXplOwoKLy8vIC8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCiAgICB2b2lkIF9hc3NpZ25fdG8oIHN0ZDo6cGFpcjxOb2RlKiwgTm9kZSo+IHBhaXIgKQogICAgewoJCW1TdGFydC5uZXh0ID0gcGFpci5maXJzdDsKCQltRW5kLnByZXYgPSBwYWlyLnNlY29uZDsKICAgIH0KCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBzY2VuYXJpb19ib29sPgoJdm9pZCBfc3dhcCggTGlzdCYgb3RoZXIgKQoJewoJICAgIHN0ZDo6c3dhcCggbVN0YXJ0LCBvdGhlci5tU3RhcnQgKTsKCSAgICBzdGQ6OnN3YXAoIG1FbmQsIG90aGVyLm1FbmQgKTsKCSAgICBzdGQ6OnN3YXAoIG1TaXplLCBvdGhlci5tU2l6ZSApOwoJICAgIF9hbGxvY19zd2FwKCBtQWxsb2NhdG9yLCBvdGhlci5tQWxsb2NhdG9yLCBzY2VuYXJpb19ib29se30gKTsKCX0KCnB1YmxpYzoKCgl2b2lkIHN3YXAoIExpc3QmIG90aGVyICkKCXsKCSAgICBfc3dhcDx0eXBlbmFtZSBhbGxvY2F0b3JfdHJhaXRzOjpwcm9wYWdhdGVfb25fY29udGFpbmVyX3N3YXA+KG90aGVyKTsKCX0KCglleHBsaWNpdCBMaXN0KCBhbGxvY2F0b3JfdHlwZSBjb25zdCYgYWxsb2MgPSBhbGxvY2F0b3JfdHlwZXt9ICk6CgkJTGlzdEFsbG9jPFZhbHVlLCBBbGxvYz57Tm9kZUJhc2V7IG51bGxwdHIsICZtRW5kIH0sIC8vIFN0YXJ0LU5vZGVCYXNlCgkJICAgICAgICAgICAgICAgICAgICAgICAgTm9kZUJhc2V7ICZtU3RhcnQsIG51bGxwdHIgfSwgLy8gRW5kLU5vZGVCYXNlCgkJICAgICAgICAgICAgICAgICAgICAgICAgYWxsb2N9LAoJCW1TaXplezB9IHt9CgoJZXhwbGljaXQgTGlzdCggc2l6ZV90eXBlIGNvdW50LAoJCQkJICAgY29uc3RfcmVmZXJlbmNlIHZhbHVlLAoJCQkJICAgYWxsb2NhdG9yX3R5cGUgY29uc3QmIGFsbG9jID0gYWxsb2NhdG9yX3R5cGV7fSApOgoJCUxpc3RBbGxvYzxWYWx1ZSwgQWxsb2M+e2FsbG9jfSwKCQltU2l6ZXtjb3VudH0KCXsKCSAgICBfYXNzaWduX3RvKCBfYWxsb2NfZmlsbF9uKGNvdW50LCBtQWxsb2NhdG9yLmFkZHJlc3ModmFsdWUpKSApOwoJfQoKCWV4cGxpY2l0IExpc3QoIHNpemVfdHlwZSBjb3VudCwKCQkJCSAgIGFsbG9jYXRvcl90eXBlIGNvbnN0JiBhbGxvYyA9IGFsbG9jYXRvcl90eXBle30gKToKCQlMaXN0QWxsb2M8VmFsdWUsIEFsbG9jPnthbGxvY30sCgkJbVNpemV7Y291bnR9Cgl7CgkgICAgX2Fzc2lnbl90byggX2FsbG9jX2ZpbGxfbihjb3VudCkgKTsKCX0KCgl0ZW1wbGF0ZTx0eXBlbmFtZSBJbnB1dEl0ZXJhdG9yCiAgICAgICAgICAgICBUQUdfQ0hFQ0soSW5wdXRJdGVyYXRvciwgc3RkOjppbnB1dF9pdGVyYXRvcl90YWcpPgoJZXhwbGljaXQgTGlzdCggSW5wdXRJdGVyYXRvciBmaXJzdCwKICAgICAgICAgICAgICAgICAgIElucHV0SXRlcmF0b3IgbGFzdCwKICAgICAgICAgICAgICAgICAgIGFsbG9jYXRvcl90eXBlIGNvbnN0JiBhbGxvYyA9IGFsbG9jYXRvcl90eXBle30gKToKICAgICAgIExpc3R7YWxsb2N9CiAgICB7CiAgICAgICAgYXNzaWduKGZpcnN0LCBsYXN0KTsKICAgIH0KCiAgICBMaXN0KCBzdGQ6OmluaXRpYWxpemVyX2xpc3Q8dmFsdWVfdHlwZT4gaWxpc3QsCiAgICAgICAgICBhbGxvY2F0b3JfdHlwZSBjb25zdCYgYWxsb2MgPSBhbGxvY2F0b3JfdHlwZXt9ICk6CiAgICAgICAgTGlzdChzdGQ6OmJlZ2luKGlsaXN0KSwgc3RkOjplbmQoaWxpc3QpLCBhbGxvYykge30KCiAgICBMaXN0KCBMaXN0IGNvbnN0JiBsICk6CiAgICAgICAgTGlzdEFsbG9jPFZhbHVlLCBBbGxvYz57IGFsbG9jYXRvcl90cmFpdHM6OnNlbGVjdF9vbl9jb250YWluZXJfY29weV9jb25zdHJ1Y3Rpb24obC5tQWxsb2NhdG9yKSB9LAogICAgICAgIG1TaXple2wubVNpemV9CiAgICB7IF9hc3NpZ25fdG8oIF9hbGxvY19jb3B5KCBtU2l6ZSwgbC5jYmVnaW4oKSApICk7IH0KCiAgICBMaXN0KCBMaXN0IGNvbnN0JiBsLCBhbGxvY2F0b3JfdHlwZSBjb25zdCYgYWxsb2MgKToKICAgICAgICBMaXN0QWxsb2M8VmFsdWUsIEFsbG9jPnthbGxvY30sCiAgICAgICAgbVNpemV7bC5tU2l6ZX0KICAgIHsgX2Fzc2lnbl90byggX2FsbG9jX2NvcHkoIG1TaXplLCBsLmNiZWdpbigpICkgKTsgfQoKICAgIExpc3QmIG9wZXJhdG9yPSggTGlzdCBjb25zdCYgbCApCiAgICB7CiAgICAgICAgY2xlYXIoKTsKCiAgICAgICAgaWYoIGFsbG9jYXRvcl90cmFpdHM6OnByb3BhZ2F0ZV9vbl9jb250YWluZXJfY29weV9hc3NpZ25tZW50Ojp2YWx1ZSApCiAgICAgICAgICAgIG1BbGxvY2F0b3IgPSBsLm1BbGxvY2F0b3I7CgogICAgICAgIF9hc3NpZ25fdG8oIF9hbGxvY19jb3B5KCBsLm1TaXplLCBsLmNiZWdpbigpICkgKTsKICAgICAgICBtU2l6ZSA9IGwubVNpemU7CgogICAgICAgIHJldHVybiAqdGhpczsKICAgIH0KCiAgICBMaXN0KCBMaXN0JiYgbCApOgoJCUxpc3R7fQogICAgeyBfc3dhcDxzdGQ6OmZhbHNlX3R5cGU+KGwpOyB9CgogICAgTGlzdCggTGlzdCYmIGwsIGFsbG9jYXRvcl90eXBlIGNvbnN0JiBhbGxvYyApOgogICAgICAgIExpc3R7YWxsb2N9CiAgICB7IF9zd2FwPHN0ZDo6ZmFsc2VfdHlwZT4obCk7IH0KCiAgICBMaXN0JiBvcGVyYXRvcj0oIExpc3QmJiBsICkKICAgIHsKICAgICAgICBjbGVhcigpOwogICAgICAgIF9zd2FwPGFsbG9jYXRvcl90cmFpdHM6OnByb3BhZ2F0ZV9vbl9jb250YWluZXJfbW92ZV9hc3NpZ25tZW50PihsKTsKICAgIH0KCgl+TGlzdCgpIC8vIG5vZXhjZXB0IChpc3Qgc2Nob24gZGVmYXVsdCkKCXsKCSAgICBjbGVhcigpOwoJfQoKICAgIHZvaWQgYXNzaWduKCBzaXplX3R5cGUgY291bnQsIGNvbnN0X3JlZmVyZW5jZSB2YWx1ZSApCiAgICB7CiAgICAgICAgY2xlYXIoKTsKICAgICAgICBtU2l6ZSA9IGNvdW50OwogICAgICAgIF9hc3NpZ25fdG8oIF9hbGxvY19maWxsX24oY291bnQsIG1BbGxvY2F0b3IuYWRkcmVzcyh2YWx1ZSkpICk7CiAgICB9CgogICAgdGVtcGxhdGU8dHlwZW5hbWUgSW5wdXRJdGVyYXRvcj4KICAgIHZvaWQgYXNzaWduKCBJbnB1dEl0ZXJhdG9yIGZpcnN0LCBJbnB1dEl0ZXJhdG9yIGxhc3QgKQogICAgewogICAgICAgIGNsZWFyKCk7CiAgICAgICAgaW5zZXJ0KCBjYmVnaW4oKSwgZmlyc3QsIGxhc3QgKTsKICAgIH0KCiAgICB2b2lkIGFzc2lnbiggc3RkOjppbml0aWFsaXplcl9saXN0PHZhbHVlX3R5cGU+IGlsaXN0ICkKICAgIHsKICAgICAgICBhc3NpZ24oc3RkOjpiZWdpbihpbGlzdCksIHN0ZDo6ZW5kKGlsaXN0KSk7CiAgICB9CgoJc2l6ZV90eXBlIHNpemUoKSBjb25zdCB7IHJldHVybiBtU2l6ZTsgfQoKCWJvb2wgZW1wdHkoKSBjb25zdCB7IHJldHVybiBzaXplKCkgPT0gMDsgfQoKCXZvaWQgY2xlYXIoKQoJewoJICAgIF9hbGxvY19kZXN0cm95X2FsbF9wcmV2KCAmbVN0YXJ0LCBtRW5kLnByZXYgKTsKCSAgICBtU2l6ZSA9IDA7Cgl9CgoJaXRlcmF0b3IgYmVnaW4oKSAgICAgICAgICAgICAgbm9leGNlcHQgeyByZXR1cm4gbVN0YXJ0Lm5leHQgOyB9CglpdGVyYXRvciBlbmQoKSAgICAgICAgICAgICAgICBub2V4Y2VwdCB7IHJldHVybiAmbUVuZCAgIDsgfQoJY29uc3RfaXRlcmF0b3IgYmVnaW4oKSAgY29uc3Qgbm9leGNlcHQgeyByZXR1cm4gbVN0YXJ0Lm5leHQgOyB9Cgljb25zdF9pdGVyYXRvciBlbmQoKSAgICBjb25zdCBub2V4Y2VwdCB7IHJldHVybiAmbUVuZCAgIDsgfQoJY29uc3RfaXRlcmF0b3IgY2JlZ2luKCkgY29uc3Qgbm9leGNlcHQgeyByZXR1cm4gYmVnaW4oKTsgfQoJY29uc3RfaXRlcmF0b3IgY2VuZCgpICAgY29uc3Qgbm9leGNlcHQgeyByZXR1cm4gZW5kKCkgIDsgfQoKCXJldmVyc2VfaXRlcmF0b3IgcmJlZ2luKCkgICAgICAgICAgICAgIHsgcmV0dXJuIHJldmVyc2VfaXRlcmF0b3J7YmVnaW4oKX07IH0KCXJldmVyc2VfaXRlcmF0b3IgcmVuZCgpICAgICAgICAgICAgICAgIHsgcmV0dXJuIHJldmVyc2VfaXRlcmF0b3J7ZW5kKCkgIH07IH0KCWNvbnN0X3JldmVyc2VfaXRlcmF0b3IgcmJlZ2luKCkgIGNvbnN0IHsgcmV0dXJuIGNvbnN0X3JldmVyc2VfaXRlcmF0b3J7Y2JlZ2luKCl9OyB9Cgljb25zdF9yZXZlcnNlX2l0ZXJhdG9yIHJlbmQoKSAgICBjb25zdCB7IHJldHVybiBjb25zdF9yZXZlcnNlX2l0ZXJhdG9ye2NlbmQoKSAgfTsgfQoJY29uc3RfcmV2ZXJzZV9pdGVyYXRvciBjcmJlZ2luKCkgY29uc3QgeyByZXR1cm4gcmJlZ2luKCk7IH0KCWNvbnN0X3JldmVyc2VfaXRlcmF0b3IgY3JlbmQoKSAgIGNvbnN0IHsgcmV0dXJuIHJlbmQoKSAgOyB9CgoJcmVmZXJlbmNlIGZyb250KCkgbm9leGNlcHQgeyByZXR1cm4gKmJlZ2luKCk7IH0KCXJlZmVyZW5jZSBiYWNrKCkgbm9leGNlcHQgeyByZXR1cm4gKi0taXRlcmF0b3J7ZW5kKCl9OyB9Cgljb25zdF9yZWZlcmVuY2UgZnJvbnQoKSBjb25zdCBub2V4Y2VwdCB7IHJldHVybiAqY2JlZ2luKCk7IH0KCWNvbnN0X3JlZmVyZW5jZSBiYWNrKCkgY29uc3Qgbm9leGNlcHQgeyByZXR1cm4gKi0tY29uc3RfaXRlcmF0b3J7Y2VuZCgpfTsgfQoKICAgIHRlbXBsYXRlPHR5cGVuYW1lLi4uIFZhbHVlVD4KICAgIGl0ZXJhdG9yIGVtcGxhY2UoIGNvbnN0X2l0ZXJhdG9yIGl0LCBWYWx1ZVQmJi4uLiB2ICkKICAgIHsKICAgICAgICBhdXRvIG5vZGUgPSBfYWxsb2NfbWFrZV9ub2RlX25vdGlmeSggaXQucC0+cHJldiwgaXQucCwgc3RkOjpmb3J3YXJkPFZhbHVlVD4odikuLi4gKTsKCiAgICAgICAgKyttU2l6ZTsKCiAgICAgICAgcmV0dXJuIG5vZGU7CiAgICB9CgogICAgaXRlcmF0b3IgaW5zZXJ0KCBjb25zdF9pdGVyYXRvciBpdCwgY29uc3RfcmVmZXJlbmNlIHZhbHVlICkKICAgIHsgcmV0dXJuIGVtcGxhY2UoaXQsIHZhbHVlKTsgfQogICAgaXRlcmF0b3IgaW5zZXJ0KCBjb25zdF9pdGVyYXRvciBpdCwgdmFsdWVfdHlwZSYmIHZhbHVlICkKICAgIHsgcmV0dXJuIGVtcGxhY2UoaXQsIHZhbHVlKTsgfQoKICAgIGl0ZXJhdG9yIGluc2VydCggY29uc3RfaXRlcmF0b3IgaXQsIHNpemVfdHlwZSBjb3VudCwgY29uc3RfcmVmZXJlbmNlIHZhbHVlICkKICAgIHsKICAgICAgICBpZiggY291bnQgPT0gMCApCiAgICAgICAgICAgIHJldHVybiBpdDsKCiAgICAgICAgYXV0byBydmFsID0gaW5zZXJ0KCBpdCwgdmFsdWUgKTsKCiAgICAgICAgd2hpbGUoIC0tY291bnQgKQogICAgICAgICAgICBpbnNlcnQoIGl0LCB2YWx1ZSApOwoKICAgICAgICByZXR1cm4gcnZhbDsKICAgIH0KCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBJbnB1dEl0ZXJhdG9yCiAgICAgICAgICAgICBUQUdfQ0hFQ0soSW5wdXRJdGVyYXRvciwgc3RkOjppbnB1dF9pdGVyYXRvcl90YWcpPgogICAgaXRlcmF0b3IgaW5zZXJ0KCBjb25zdF9pdGVyYXRvciBpdCwgSW5wdXRJdGVyYXRvciBmaXJzdCwgSW5wdXRJdGVyYXRvciBsYXN0ICkKICAgIHsKICAgICAgICBpZiggZmlyc3QgPT0gbGFzdCApCiAgICAgICAgICAgIHJldHVybiBpdDsKCiAgICAgICAgYXV0byBydmFsID0gaW5zZXJ0KCBpdCwgKmZpcnN0ICk7CgogICAgICAgIHdoaWxlKCArK2ZpcnN0ICE9IGxhc3QgKQogICAgICAgICAgICBpbnNlcnQoIGl0LCAqZmlyc3QgKTsKCiAgICAgICAgcmV0dXJuIHJ2YWw7CiAgICB9CgogICAgaXRlcmF0b3IgaW5zZXJ0KCBjb25zdF9pdGVyYXRvciBpdCwgc3RkOjppbml0aWFsaXplcl9saXN0PHZhbHVlX3R5cGU+IGlsaXN0ICkKICAgIHsKICAgICAgICBpbnNlcnQoIGl0LCBzdGQ6OmJlZ2luKGlsaXN0KSwgc3RkOjplbmQoaWxpc3QpICk7CiAgICB9CgogICAgdGVtcGxhdGU8dHlwZW5hbWUuLi4gQXJncz4KICAgIGl0ZXJhdG9yIGVtcGxhY2VfYmFjayggQXJncyYmLi4uIGFyZ3MgKQogICAgewogICAgICAgIHJldHVybiBlbXBsYWNlKCBjZW5kKCksIHN0ZDo6Zm9yd2FyZDxBcmdzPihhcmdzKS4uLiApOwogICAgfQoKICAgIHRlbXBsYXRlPHR5cGVuYW1lLi4uIEFyZ3M+CiAgICBpdGVyYXRvciBlbXBsYWNlX2Zyb250KCBBcmdzJiYuLi4gYXJncyApCiAgICB7CiAgICAgICAgcmV0dXJuIGVtcGxhY2UoIGNiZWdpbigpLCBzdGQ6OmZvcndhcmQ8QXJncz4oYXJncykuLi4gKTsKICAgIH0KCiAgICB2b2lkIHB1c2hfYmFjayggY29uc3RfcmVmZXJlbmNlIHYgKQogICAgeyBpbnNlcnQoIGNlbmQoKSwgdiApOyB9CiAgICB2b2lkIHB1c2hfYmFjayggdmFsdWVfdHlwZSYmIHYgKQogICAgeyBpbnNlcnQoIGNlbmQoKSwgdiApOyB9CgogICAgdm9pZCBwdXNoX2Zyb250KCBjb25zdF9yZWZlcmVuY2UgdiApCiAgICB7IGluc2VydCggY2JlZ2luKCksIHYgKTsgfQogICAgdm9pZCBwdXNoX2Zyb250KCB2YWx1ZV90eXBlJiYgdiApCiAgICB7IGluc2VydCggY2JlZ2luKCksIHYgKTsgfQoKICAgIGl0ZXJhdG9yIGVyYXNlKCBjb25zdF9pdGVyYXRvciBpdCApCiAgICB7CiAgICAgICAgYXV0byBydmFsID0gaXQucC0+bmV4dDsKCiAgICAgICAgaXQucC0+cHJldi0+bmV4dCA9IGl0LnAtPm5leHQ7CiAgICAgICAgaXQucC0+bmV4dC0+cHJldiA9IGl0LnAtPnByZXY7CgogICAgICAgIF9hbGxvY19kZXN0cm95X25vZGUoIHN0YXRpY19jYXN0PE5vZGUqPihpdC5wKSApOwoKICAgICAgICAtLW1TaXplOwoKICAgICAgICByZXR1cm4gcnZhbDsKICAgIH0KCiAgICBpdGVyYXRvciBlcmFzZSggY29uc3RfaXRlcmF0b3IgZmlyc3QsIGNvbnN0X2l0ZXJhdG9yIGxhc3QgKQogICAgewogICAgICAgIHdoaWxlKCBmaXJzdCAhPSBsYXN0ICkKICAgICAgICAgICAgZXJhc2UoIGZpcnN0KysgKTsKCiAgICAgICAgcmV0dXJuIGxhc3Q7CiAgICB9CgogICAgdm9pZCBwb3BfYmFjaygpCiAgICB7IGVyYXNlKCAtLWVuZCgpICk7IH0KICAgIHZvaWQgcG9wX2Zyb250KCkKICAgIHsgZXJhc2UoIGJlZ2luKCkgKTsgfQoKcHJpdmF0ZToKCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSAuLi4gQXJncz4KICAgIHZvaWQgX3Jlc2l6ZV9pbXBsKCBzaXplX3R5cGUgbmV3X3NpemUsIEFyZ3MmJi4uLiBhcmdzICkKICAgIHsKICAgICAgICBpZiggbmV3X3NpemUgPiBzaXplKCkgKQogICAgICAgICAgICBmb3IoIHNpemVfdHlwZSBuID0gc2l6ZSgpOyBuICE9IG5ld19zaXplOyArK24gKQogICAgICAgICAgICAgICAgZW1wbGFjZV9iYWNrKCBzdGQ6OmZvcndhcmQ8QXJncz4oYXJncykuLi4gKTsKCiAgICAgICAgZWxzZSBpZiggbmV3X3NpemUgPCBzaXplKCkgKQogICAgICAgICAgICBlcmFzZSggc3RkOjpuZXh0KGNiZWdpbigpLCBuZXdfc2l6ZSksIGNlbmQoKSApOwogICAgfQoKcHVibGljOgogICAgdm9pZCByZXNpemUoIHNpemVfdHlwZSBuZXdfc2l6ZSwgY29uc3RfcmVmZXJlbmNlIHZhbHVlICkKICAgIHsgX3Jlc2l6ZV9pbXBsKCBuZXdfc2l6ZSwgdmFsdWUgKTsgfQogICAgdm9pZCByZXNpemUoIHNpemVfdHlwZSBuZXdfc2l6ZSApCiAgICB7IF9yZXNpemVfaW1wbCggbmV3X3NpemUgKTsgfQp9OwoKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aXRlcmF0b3I+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8c3RyaW5nPgoKaW50IG1haW4oKQp7CiNkZWZpbmUgY2hlY2socykgYXNzZXJ0KHN0ZDo6c3RyaW5nKGwuYmVnaW4oKSwgbC5lbmQoKSkgPT0gcykKCiAgTGlzdDxjaGFyPiBsOwogIGwucHVzaF9iYWNrKCdtJyk7ICBjaGVjaygibSIpOwogIGwucHVzaF9iYWNrKCd6Jyk7ICBjaGVjaygibXoiKTsKICBsLnB1c2hfZnJvbnQoJ2EnKTsgY2hlY2soImFteiIpOwogIGwuZXJhc2UobC5iZWdpbigpKTtjaGVjaygibXoiKTsKICBsLmluc2VydChsLmJlZ2luKCksICdhJyk7Y2hlY2soImFteiIpOwogIGwuaW5zZXJ0KGwuZW5kKCksICchJyk7ICBjaGVjaygiYW16ISIpOwogIGwucG9wX2Zyb250KCk7ICAgICBjaGVjaygibXohIik7CiAgbC5wb3BfYmFjaygpOyAgICAgIGNoZWNrKCJteiIpOwogIExpc3Q8Y2hhcj46Oml0ZXJhdG9yIGk9bC5iZWdpbigpOyBpKys7CiAgaSA9IGwuaW5zZXJ0KGksICctJyk7IGNoZWNrKCJtLXoiKTsKICBpID0gbC5lcmFzZShpKTsgICAgICAgY2hlY2soIm16Iik7CiAgbC5lcmFzZShpKTsgICAgICAgICAgIGNoZWNrKCJtIik7CiAgbC5wdXNoX2Zyb250KCdhJyk7ICAgIGNoZWNrKCJhbSIpOwogIGwucHVzaF9iYWNrKCd6Jyk7ICAgICBjaGVjaygiYW16Iik7CiAgaT1sLmVuZCgpOyBpLS07IGktLTsKICBpPWwuZXJhc2UoaSk7ICAgICAgICAgY2hlY2soImF6Iik7Cn0K

Success #stdin #stdout 0s 3028KB

stdin

copy

Standard input is empty

stdout

copy

Standard output is empty

https://ideone.com/2jXHS8

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language