#pragma once

#include <cstddef>
#include <memory>
#include <type_traits>
#include <cstring>
#include <algorithm>

namespace ext
{
template<typename T>
class tvector final
{
        static_assert(std::is_trivially_copyable<T>::value,
                      "Type must be trivially copyable");
public:
        using value_type = T;
        using size_type	= std::size_t;
        using difference_type = std::ptrdiff_t;
        using reference	 = value_type&;
        using const_reference = const value_type&;
        using pointer = value_type*;
        using const_pointer = const value_type*;
        using iterator = pointer;
        using const_iterator = const_pointer;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;

        tvector()
        : mem_(nullptr),
          capacity_(1),
          size_(0)
        {
                reallocate();
        }

        explicit
        tvector(size_t count, const T& value = T())
                : mem_(nullptr),
                  capacity_(count),
                  size_(0)
        {
                reallocate();

                T* p = mem_;
                for(size_t i = 0; i < count; ++i)
                        *p++ = value;

                size_ = capacity_;
        }

        template<typename InputIt>
        tvector(InputIt first, InputIt last)
         : mem_(nullptr)
        {
                capacity_ = 4;
                size_ = 0;

                reallocate();

                while(first != last)
                        push_back(*first++);
        }

        tvector(const tvector& o)
                : mem_(nullptr),
                  size_(o.size_),
                  capacity_(o.capacity_)
        {
                mem_ = malloc(size_ * sizeof(T));
                memcpy(mem_, o.mem_, size_ * sizeof(T));
        }

        tvector(tvector&& o) noexcept
        : mem_(std::move(o.mem_)),
          size_(std::move(o.size_)),
          capacity_(std::move(o.capacity_))
        {
        }

        tvector(std::initializer_list<T> init)
        : mem_(nullptr),
          size_(0),
          capacity_(2)
        {
                reallocate();

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

        ~tvector()
        {
                free(mem_);

                mem_ = nullptr;
                capacity_ = 0;
                size_ = 0;
        }

        tvector& operator=(const tvector& o)
        {
                if(&o == this)
                        return *this;

                this->~tvector();

                size_ = o.size_;
                capacity_ = o.capacity_;

                mem_ = malloc(size_ * sizeof(T));
                memcpy(mem_, o.mem_, size_ * sizeof(T));

                return *this;
        }

        tvector& operator=(tvector&& o) noexcept
        {
                if(&o == this)
                        return *this;

                this->~tvector();

                swap(o);

                return *this;
        }

        tvector& operator=(std::initializer_list<T> ilist)
        {
                assign(ilist);

                return *this;
        }

        void assign(size_type count, const T& value)
        {
                this->~tvector();

                capacity_ = count;
                size_ = capacity_;

                reallocate();

                T* p = mem_;
                for(size_t i = 0; i < count; ++i)
                        *p++ = value;
        }

        template<typename InputIt>
        void assign(InputIt first, InputIt last)
        {
                this->~tvector();

                capacity_ = 4;

                reallocate();

                while(first != last)
                        push_back(*first++);
        }

        void assign(std::initializer_list<T> ilist)
        {
                this->~tvector();

                capacity_ = 4;

                reallocate();

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

        reference at(size_type pos)
        {
                return mem_[pos];
        }

        const_reference at(size_type pos) const
        {
                return mem_[pos];
        }

        reference operator[]( size_type pos )
        {
                return at(pos);
        }

        const_reference operator[](size_type pos) const
        {
                return at(pos);
        }

        T* data() noexcept { return mem_; }
        const T* data() const noexcept { return mem_; }

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

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

        iterator begin() noexcept { return mem_; }
        const_iterator begin() const noexcept { return mem_; }
        const_iterator cbegin() const noexcept { return mem_; };

        iterator end() noexcept { return mem_ + size_; }
        const_iterator end() const noexcept { return mem_ + size_; }
        const_iterator cend() const noexcept { return mem_ + size_; };

        reverse_iterator rbegin() noexcept
        {
                return std::reverse_iterator<iterator>(end());
        }

        const_reverse_iterator rbegin() const noexcept
        {
                return std::reverse_iterator<iterator>(end());
        }

        const_reverse_iterator crbegin() const noexcept
        {
                return std::reverse_iterator<const_iterator>(end());
        }

        reverse_iterator rend() noexcept
        {
                return std::reverse_iterator<iterator>(begin());
        }

        const_reverse_iterator rend() const noexcept
        {
                return std::reverse_iterator<iterator>(begin());
        }

        const_reverse_iterator crend() const noexcept
        {
                return std::reverse_iterator<iterator>(begin());
        }

        bool empty() const noexcept { return size_ == 0; }

        size_type size() const noexcept { return size_; }

        void reserve(size_type new_cap)
        {
                capacity_ = new_cap;
                reallocate();
        }

        size_type capacity() const noexcept { return capacity_; }

        void shrink_to_fit()
        {
                capacity_ = std::max(size_, size_t(1));
                reallocate();
        }

        void clear() noexcept
        {
                size_ = 0;
        }

        iterator insert(const_iterator pos, const T& value)
        {
                iterator first = const_cast<iterator>(pos);
                iterator last  = first + 1;

                auto p = std::distance(begin(), first);

                move(first, last, 1);
                size_++;

                mem_[p] = value;

                return &mem_[p];
        }

        iterator insert(const_iterator pos, T&& value)
        {
                iterator first = const_cast<iterator>(pos);
                iterator last  = first + 1;

                auto p = std::distance(begin(), first);

                move(first, last, 1);

                size_++;

                mem_[p] = std::move(value);

                return &mem_[p];
        }

        iterator insert(const_iterator pos, size_type count, const T& value)
        {
                if(count == 0)
                        return const_cast<iterator>(pos);

                iterator first = const_cast<iterator>(pos);
                iterator last  = first + count;

                auto p = std::distance(begin(), first);

                move(first, last, count);

                size_ += count;

                for(auto i = p; i < count; ++i)
                        mem_[i] = value;
        }

        template<typename InputIt >
        iterator insert(const_iterator pos, InputIt first, InputIt last )
        {
                if(first == last)
                        return const_cast<iterator>(pos);

                auto count = std::distance(first, last);

                iterator v_first = const_cast<iterator>(pos);
                iterator v_last  = end();

                auto p = std::distance(begin(), v_first);

                move(v_first, v_last, count);

                size_ += count;

                auto* mem = &mem_[p];
                while(first != last)
                        *mem++ = *first++;

                return &mem_[p];
        }

        iterator insert(const_iterator pos, std::initializer_list<T> ilist)
        {
                return insert(pos, ilist.begin(), ilist.end());
        }

        template<typename... Args>
        iterator emplace(const_iterator pos, Args&&... args)
        {
                iterator first = const_cast<iterator>(pos);
                iterator last  = end();

                auto p = std::distance(begin(), first);

                move(first, last, 1);

                auto* mem = &mem_[p];

                auto ptr = new(mem) T(std::forward<Args>(args)...);

                size_++;

                return ptr;
        }

        iterator erase(const_iterator pos)
        {
                iterator first = const_cast<iterator>(pos) + 1;
                iterator last  = end();

                if(first == last)
                {
                        size_--;
                        return end();
                }

                auto p = std::distance(begin(), pos);

                move(first, last, -1);

                size_--;

                return &mem_[p];
        }

        iterator erase(const_iterator first, const_iterator last)
        {
                auto count = std::distance(first, last);

                if(last == end())
                {
                        size_ -= count;
                        return end();
                }

                iterator v_first = const_cast<iterator>(last) - 1;
                iterator v_last  = end();

                auto p = std::distance(begin(), last);

                move(v_first, v_last, -count);

                size_ -= count;

                return &mem_[p];
        }

        void push_back(T&& value)
        {
                _emplace_back(std::move(value));
        }

        void push_back(const T& value)
        {
                _emplace_back(value);
        }

        template<typename... Args>
        reference emplace_back(Args&&... args)
        {
                return _emplace_back(std::forward<Args>(args)...);
        }

        void pop_back()
        {
                size_ = size_ != 0 ? size_ - 1 : 0;
        }

        void resize(size_type count)
        {
                resize(count, T());
        }

        void resize(size_type count, const value_type& value)
        {
                if(count < capacity_)
                        size_ = count;
                else if(count > capacity_)
                {
                        grow_up(count);

                        T* p = &mem_[size_];
                        for(size_t i = 0; i < (count - size_); ++i)
                                *p++ = value;

                        size_ = count;
                }
        }

        void swap(tvector& other) noexcept
        {
                std::swap(mem_, other.mem_);
                std::swap(size_, other.size_);
                std::swap(capacity_, other.capacity_);
        }
private:
        void move(iterator first, iterator last, ssize_t to)
        {
                auto mv_sz = std::distance(first, last);

                if(to > 0)
                {
                        auto nsz = size_ + to;
                        grow_up(nsz);
                }

                memmove(first + to, first, mv_sz * sizeof(T));
        }

        void grow_up(size_t new_size)
        {
                if(new_size < capacity_)
                        return;

                while(new_size > capacity_)
                        capacity_ *= 2;

                reallocate();
        }

        template<typename... Args>
        T& _emplace_back(Args&&... args)
        {
                if(size_ + 1 > capacity_)
                {
                        capacity_ *= 2;
                        reallocate();
                }

                T* mem = mem_ + size_;

                T& ref = *new(mem) T(std::forward<Args>(args)...);

                size_++;

                return ref;
        }

        void reallocate()
        {
                mem_ = (T*)realloc(mem_, capacity_ * sizeof(T));
        }

private:
        T* mem_;
        size_t capacity_;
        size_t size_;
};

}