#pragma GCC system_header

#ifndef _LIBCXX_VECTOR
#define _LIBCXX_VECTOR

#include <__config>
#include <iterator>
#include <memory>
#include <utility>

_LIBCXX_BEGIN_NAMESPACE_STD

template <class T, class Allocator = std::allocator<T>>
class vector {
public:
    using value_type = T;
    using allocator_type = Allocator;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = T&;
    using const_reference = const T&;
    using pointer = T*;
    using const_pointer = const T*;
    using iterator = std::__legacy_iter<pointer>;
    using const_iterator = std::__legacy_iter<const_pointer>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    vector()
    {
        grow(16);
    }

    explicit vector(size_type capacity)
    {
        grow(capacity);
    }

    vector(const vector& v)
    {
        grow(v.m_capacity);
        m_size = v.m_size;
        copy(m_data, v.m_data, m_size);
    }

    vector(vector&& v)
    {
        m_size = v.m_size;
        m_capacity = v.m_capacity;
        m_data = v.m_data;
        v.m_size = v.m_capacity = 0;
        v.m_data = nullptr;
    }

    ~vector()
    {
        clear();
    }

    vector& operator=(const vector& v)
    {
        grow(v.m_capacity);
        m_size = v.m_size;
        copy(m_data, v.m_data, m_size);
        return *this;
    }

    vector& operator=(vector&& v)
    {
        if (this != &v) {
            clear();
            m_size = v.m_size;
            m_capacity = v.m_capacity;
            m_data = v.m_data;
            v.m_size = 0;
            v.m_capacity = 0;
            v.m_data = nullptr;
        }
        return *this;
    }

    inline void push_back(value_type&& el)
    {
        ensure_capacity(size() + 1);
        construct_at(&m_data[m_size], std::move(el));
        m_size++;
    }

    inline void push_back(const_reference el)
    {
        push_back(T(el));
    }

    inline void pop_back()
    {
        back().~T();
        --m_size;
    }

    inline const_reference at(size_type i) const
    {
        return data()[i];
    }

    inline reference at(size_type i)
    {
        return data()[i];
    }

    void clear()
    {
        clear_remain_capacity();
        if (m_data) {
            m_allocator.deallocate(m_data, m_capacity);
            m_data = nullptr;
        }
        m_capacity = 0;
    }

    void clear_remain_capacity()
    {
        if (m_data) {
            for (size_type i = 0; i < m_size; ++i) {
                destroy_at(&m_data[i]);
            }
        }
        m_size = 0;
    }

    inline void resize(size_type new_size)
    {
        ensure_capacity(new_size);
        m_size = new_size;
    }

    inline size_t size() const { return m_size; }
    inline size_t capacity() const { return m_capacity; }
    inline bool empty() const { return size() == 0; }

    inline reference operator[](size_t i) { return at(i); }
    inline const_reference operator[](size_t i) const { return at(i); }

    inline reference front() { return at(0); }
    inline const_reference front() const { return at(0); }

    inline reference back() { return at(size() - 1); }
    inline const_reference back() const { return at(size() - 1); }

    inline pointer data() { return m_data; }
    inline const_pointer data() const { return m_data; }

    inline iterator begin() { return iterator(&m_data[0]); }
    inline iterator end() { return iterator(&m_data[m_size]); }

    inline const_iterator cbegin() const { return const_iterator(&m_data[0]); }
    inline const_iterator cend() const { return const_iterator(&m_data[m_size]); }

    inline reverse_iterator rbegin() { return reverse_iterator(&m_data[m_size - 1]); }
    inline reverse_iterator rend() { return reverse_iterator(&m_data[-1]); }

    inline const_reverse_iterator crbegin() const { return const_reverse_iterator(&m_data[m_size - 1]); }
    inline const_reverse_iterator crend() const { return const_reverse_iterator(&m_data[-1]); }

private:
    inline void ensure_capacity(size_type new_size)
    {
        size_type capacity = 16;
        while (new_size > capacity) {
            capacity *= 2;
        }
        grow(capacity);
    }

    void grow(size_type capacity)
    {
        if (capacity <= m_capacity) {
            return;
        }

        if (!m_data) {
            m_data = m_allocator.allocate(capacity);
        } else {
        retry:
            auto new_buf = m_allocator.allocate(capacity);
            if (!new_buf) {
                goto retry;
            }

            for (size_t i = 0; i < m_size; i++) {
                construct_at(&new_buf[i], std::move(at(i)));
                destroy_at(&m_data[i]);
            }
            m_allocator.deallocate(m_data, m_capacity);
            m_data = new_buf;
        }
        m_capacity = capacity;
    }

    void copy(pointer to, const_pointer from, size_type len)
    {
        for (size_type i = 0; i < len; i++) {
            construct_at(to, T(*from));
            to++;
            from++;
        }
    }

    size_type m_size { 0 };
    size_type m_capacity { 0 };
    pointer m_data { nullptr };
    allocator_type m_allocator;
};

_LIBCXX_END_NAMESPACE_STD

#endif // _LIBCXX_VECTOR