#include <cstddef>
#include <new>
#include <utility>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include <iostream>
#include <string>

namespace getcracked {

template <typename T>
class vector {
private:
    std::size_t m_size{0};
    std::size_t m_cap{0};
    T* p_arr{nullptr};

    // allocate raw memory (uninitialized)
    static T* allocate(std::size_t n) {
        if (n == 0) return nullptr;
        return static_cast<T*>(::operator new(sizeof(T) * n));
    }

    // destroy all elements and free memory
    void destroy_and_free() noexcept {
        if (p_arr) {
            std::destroy_n(p_arr, m_size);
            ::operator delete(p_arr);
        }
        p_arr = nullptr;
        m_size = 0;
        m_cap = 0;
    }

    // reallocate with move semantics
    void grow(std::size_t new_cap) {
        T* new_arr = allocate(new_cap);
        std::size_t i = 0;
        try {
            for (; i < m_size; ++i)
                std::construct_at(new_arr + i, std::move_if_noexcept(p_arr[i]));
        } catch (...) {
            // rollback on exception
            std::destroy_n(new_arr, i);
            ::operator delete(new_arr);
            throw;
        }

        std::destroy_n(p_arr, m_size);
        ::operator delete(p_arr);
        p_arr = new_arr;
        m_cap = new_cap;
    }

public:
    vector() = default;

    explicit vector(std::size_t count, const T& value = T())
        : m_size(count), m_cap(count), p_arr(allocate(count))
    {
        std::uninitialized_fill_n(p_arr, count, value);
    }

    // copy constructor
    vector(const vector& other)
        : m_size(other.m_size), m_cap(other.m_size), p_arr(allocate(other.m_size))
    {
        std::uninitialized_copy_n(other.p_arr, other.m_size, p_arr);
    }

    // move constructor
    vector(vector&& other) noexcept
        : m_size(other.m_size), m_cap(other.m_cap), p_arr(other.p_arr)
    {
        other.p_arr = nullptr;
        other.m_size = other.m_cap = 0;
    }

    // destructor
    ~vector() { destroy_and_free(); }

    // copy assignment
    vector& operator=(const vector& other) {
        if (this == &other) return *this;
        destroy_and_free();
        m_size = other.m_size;
        m_cap = other.m_size;
        p_arr = allocate(m_cap);
        std::uninitialized_copy_n(other.p_arr, other.m_size, p_arr);
        return *this;
    }

    // move assignment
    vector& operator=(vector&& other) noexcept {
        if (this == &other) return *this;
        destroy_and_free();
        m_size = other.m_size;
        m_cap = other.m_cap;
        p_arr = other.p_arr;
        other.p_arr = nullptr;
        other.m_size = other.m_cap = 0;
        return *this;
    }

    template <typename U>
    void push_back(U&& value) {
        if (m_size == m_cap)
            grow(m_cap == 0 ? 1 : m_cap * 2);

        std::construct_at(p_arr + m_size, std::forward<U>(value));
        ++m_size;
    }

    void pop_back() {
        if (m_size == 0) return;
        --m_size;
        std::destroy_at(p_arr + m_size);
    }

    const T& at(std::size_t index) const {
        if (index >= m_size) throw std::out_of_range("index out of range");
        return p_arr[index];
    }

    T& at(std::size_t index) {
        if (index >= m_size) throw std::out_of_range("index out of range");
        return p_arr[index];
    }

    std::size_t size() const noexcept { return m_size; }
    std::size_t capacity() const noexcept { return m_cap; }

    void reserve(std::size_t new_cap) {
        if (new_cap > m_cap)
            grow(new_cap);
    }

    void shrink_to_fit() {
        if (m_cap > m_size)
            grow(m_size);
    }
};

} // namespace getcracked