#ifndef VECTOR_H
#define VECTOR_H

#include <algorithm> // std::random_access_iterator_tag
#include <cstddef> // size_t
#include <stdexcept> // std::out_of_range
#include <type_traits> // std::is_same

// https://www.gradescope.com/courses/708488/assignments/3931689/submissions/224735512

// #######################################################################################

template <class T>
class Vector {
public:
    class iterator;
private:
    T* array;
    size_t _capacity, _size;

    void grow(size_t new_capacity) { // doubles the capacity
        T* temp = new T[new_capacity];
        for(size_t i = 0; i < _size; i++) {
            temp[i] = std::move(array[i]);
        }
        delete[] array;
        array = temp;
        _capacity = new_capacity;
    }

public:
    Vector() noexcept {
        _capacity = 0;
        _size = 0;
        array = nullptr;
    }

    Vector(size_t count, const T& value) {
        _capacity = count;
        _size = count;
        array = new T[_capacity];
        for(size_t i = 0; i < _size; i++) { array[i] = value; }
    }
    
    explicit Vector(size_t count) {
        _size = count;
        _capacity = count;
        array = new T[_capacity];
        for (size_t i = 0; i < _size; ++i) {
            array[i] = T();
        }
    }

    Vector(const Vector& other) {
        _capacity = other._capacity;
        _size = other._size;
        array = new T[_capacity];
        for(size_t i = 0; i < _size; i++) {
            array[i] = other.array[i];
        }
    }

    Vector(Vector&& other) noexcept {
        _capacity = other._capacity;
        _size = other._size;
        array = other.array;
        other._capacity = 0;
        other._size = 0;
        other.array = nullptr;
    }

    ~Vector() {
        delete[] array;
    }

    Vector& operator=(const Vector& other) {
        if (this != &other) {
            delete[] array;
            _capacity = other._capacity;
            _size = other._size;
            array = new T[_capacity];
            for(size_t i = 0; i < _size; i++) {
                array[i] = other.array[i];
            }
        }
        return *this;
    }

    Vector& operator=(Vector&& other) noexcept {
        if (this != &other) {
            delete[] array;
            _capacity = other._capacity;
            _size = other._size;
            array = other.array;
            other._capacity = 0;
            other._size = 0;
            other.array = nullptr;
        }
        return *this;
    }

    iterator begin() noexcept {
        return iterator(array);
    }

    iterator end() noexcept {
        return iterator(array + _size);
    }

    [[nodiscard]] bool empty() const noexcept { return _size == 0; }
    size_t size() const noexcept { return _size; }
    size_t capacity() const noexcept { return _capacity; }

    T& at(size_t pos) { 
        if (pos >= _size) { throw std::out_of_range("Index out of range"); }
        return array[pos];
    }

    const T& at(size_t pos) const {
        if (pos >= _size) throw std::out_of_range("Index out of range");
        return array[pos];
    }

    T& operator[](size_t pos) { 
        if (pos >= _size) {
            _size = pos + 1;
            if (_size > _capacity) {
                grow(_size);
            }
        }
        return array[pos]; 
    }
    
    const T& operator[](size_t pos) const { 
        if (pos >= _size) {
            throw std::out_of_range("Index out of range");
        }
        return array[pos];
    }

    T& front() {
        if (_size == 0) throw std::out_of_range("Tried to call front() on empty vector");
        return array[0];
    }

    const T& front() const {
        if (_size == 0) throw std::out_of_range("Tried to call front() on empty vector");
        return array[0];
    }

    T& back() {
        if (_size == 0) throw std::out_of_range("Tried to call back() on empty vector");
        return array[_size - 1];
    }

    const T& back() const {
        if (_size == 0) throw std::out_of_range("Tried to call back() on empty vector");
        return array[_size - 1];
    }

void push_back(const T& value) {
    if (_size == _capacity) {
        grow(_capacity == 0 ? 1 : _capacity * 2);
    }
    array[_size++] = std::move(value);
}

void push_back(T&& value) {
    if (_size == _capacity) {
        grow(_capacity == 0 ? 1 : _capacity * 2);
    }
    array[_size++] = std::move(value);
}

    void pop_back() {
        if (!empty()) _size--;
    }


iterator insert(iterator pos, T&& value) {
    size_t index = pos - begin();
    if (_size == _capacity) grow(_capacity * 2);
    for(size_t i = _size; i > index; i--) {
        array[i] = std::move(array[i - 1]);
    }
    array[index] = std::forward<T>(value);
    _size++;
    return begin() + index;
}


iterator insert(iterator pos, const T& value) {
    size_t index = pos - begin();
    if (_size == _capacity) grow(_capacity * 2);
    for(size_t i = _size; i > index; i--) {
        array[i] = std::move(array[i - 1]);
    }
    array[index] = value;
    _size++;
    return begin() + index;
}

iterator insert(iterator pos, size_t count, const T& value) { // insert multiple

    size_t index = pos - begin();

    if (_size + count > _capacity) grow(_capacity * 2);

    for(size_t i = _size + count - 1; i > index + count - 1; i--) {
        array[i] = std::move(array[i - count]);
    }
    for(size_t i = index; i < index + count; i++) {
        array[i] = value;
    }
    _size += count;
    return begin() + index;
}

    iterator erase(iterator pos) {
        size_t index = pos - begin();
        for(size_t i = index; i < _size - 1; i++) {
            array[i] = std::move(array[i + 1]);
        }
        array[_size - 1].~T();
        _size--;
        return begin() + index;
    }

iterator erase(iterator first, iterator last) {
    size_t indexFirst = first - begin();
    size_t indexLast = last - begin();
    size_t numErased = indexLast - indexFirst;

    for (size_t i = indexFirst; i < _size - numErased; ++i) {
        array[i] = std::move(array[i + numErased]);
    }
    _size -= numErased;

    return begin() + indexFirst;
}

    class iterator {
    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type        = T;
        using difference_type   = ptrdiff_t;
        using pointer           = T*;
        using reference         = T&;
    private:
        // Points to some element in the vector (or nullptr)
        T* _ptr;

    public:
        iterator() : _ptr(nullptr) {}
        iterator(T* ptr) : _ptr(ptr) {}
        ~iterator() {} // Destructor

        // This assignment operator is done for you, please do not add more
        iterator& operator=(const iterator&) noexcept = default;

        [[nodiscard]] reference operator*() const noexcept { return *_ptr; }

        [[nodiscard]] pointer operator->() const noexcept { return _ptr; }

        // Prefix Increment: ++a
        iterator& operator++() noexcept {
            _ptr++;
            return *this;
        }
        // Postfix Increment: a++
        iterator operator++(int) noexcept {
            iterator temp = *this;
            _ptr++;
            return temp;
        }
        // Prefix Decrement: --a
        iterator& operator--() noexcept {
            _ptr--;
            return *this;
        }
        // Postfix Decrement: a--
        iterator operator--(int) noexcept {
            iterator temp = *this;
            _ptr--;
            return temp;
        }

        iterator& operator+=(difference_type offset) noexcept {
            _ptr += offset;
            return *this;
        }
        [[nodiscard]] iterator operator+(difference_type offset) const noexcept {
            iterator temp = *this;
            temp += offset;
            return temp;
        }
        
        iterator& operator-=(difference_type offset) noexcept {
            _ptr -= offset;
            return *this;
        }

        [[nodiscard]] iterator operator-(difference_type offset) const noexcept {
            iterator temp = *this;
            temp -= offset;
            return temp;
        }

        [[nodiscard]] difference_type operator-(const iterator& rhs) const noexcept {
            return _ptr - rhs._ptr;
        }

        [[nodiscard]] reference operator[](difference_type offset) const noexcept {
            return *(_ptr + offset);
        }

        [[nodiscard]] bool operator==(const iterator& rhs) const noexcept { return _ptr == rhs._ptr; }
        [[nodiscard]] bool operator!=(const iterator& rhs) const noexcept { return !(*this == rhs); }
        [[nodiscard]] bool operator<(const iterator& rhs) const noexcept { return _ptr < rhs._ptr; }
        [[nodiscard]] bool operator>(const iterator& rhs) const noexcept { return rhs < *this; }
        [[nodiscard]] bool operator<=(const iterator& rhs) const noexcept { return !(rhs < *this); }
        [[nodiscard]] bool operator>=(const iterator& rhs) const noexcept { return !(*this < rhs); }
    };


    void clear() noexcept {
        _size = 0;
    }
};

// This ensures at compile time that the deduced argument _Iterator is a Vector<T>::iterator
// There is no way we know of to back-substitute template <typename T> for external functions
// because it leads to a non-deduced context
namespace {
    template <typename _Iterator>
    using is_vector_iterator = std::is_same<typename Vector<typename _Iterator::value_type>::iterator, _Iterator>;
}

template <typename _Iterator, bool _enable = is_vector_iterator<_Iterator>::value>
[[nodiscard]] _Iterator operator+(typename _Iterator::difference_type offset, const _Iterator& iterator) noexcept {
    _Iterator result = iterator;
    result += offset;
    return result;
}

#endif

// resources:

/*
https://en.cppreference.com/w/cpp/container/vector
*/

#include "executable.h"

#include <string>
#include <cmath>
#include <memory>
#include <vector>

#include "box.h"

TEST(insert_multiple) {
    Typegen t;

    for(int j = 0; j < 200; j++) {
        size_t sz = t.range<size_t>(1, 0xFF);

        Vector<Box<int>> vec(sz);
        
        using iter = typename Vector<Box<int>>::iterator;
        
        std::vector<Box<int>> gt(sz);
        
        for(size_t i = 0; i < sz; i++) {
            vec[i] = gt[i] = t.get<int>();
        }
        
        int insert_el = t.get<int>();
        ptrdiff_t i = t.range<ptrdiff_t>(0, sz);
        size_t count = t.range<size_t>(0, 0xFF);

        gt.insert(gt.begin() + i, count, insert_el);

        size_t init_cap = vec.capacity();
        {
            Memhook mh;

            iter pos = vec.insert(vec.begin() + i, count, insert_el);
            
            size_t wanted_allocs = 0;
            
            if(sz + count > init_cap) 
                wanted_allocs = std::ceil(std::log2(static_cast<double>(init_cap + count) / static_cast<double>(init_cap)));
            
            // Copy in adds one copy
            wanted_allocs += count + 1;

            ASSERT_EQ(i, static_cast<ptrdiff_t>(pos - vec.begin()));
            ASSERT_LE(wanted_allocs, mh.n_allocs());
        }

        ASSERT_EQ(gt.size(), vec.size());
        
        for(size_t i = 0; i < gt.size(); i++)
            ASSERT_TRUE(*gt[i] == *vec[i]);
    }
}

[==========] Running 1 test cases.
[ RUN      ] VECTOR.insert_multiple
make: *** [run/vector_insert_multiple] Segmentation fault: 11

explain