#ifndef _VECTOR_
#define _VECTOR_
#include<cmath>
using u16 = unsigned int;
template<class T>
void swap(T&a,T&b){
    T c(std::move(a));
    a = std::move(b);
    b = std::move(c);
}
template<class T, size_t N>
void swap(T(&a)[N], T(&b)[N]) {
    for (size_t i = 0; i < N; ++i)
    {
        swap(a[i], b[i]);
    }
}
template<class T>
struct ItemWrapper {
    T* data() { return reinterpret_cast<T*>(buffer); }
    const T* data()const { return reinterpret_cast<const T*>(buffer); }
private:
    char buffer[sizeof(T)];
};
template<class T>
class Vector {
    ItemWrapper<T>* memory;
    u16 length;
    u16 allocated;
    void check_index(const u16 index) const {
        if (length == 0) {
            std::cerr << "Error: cannot erase/insert at position different than 0/get/set when there are no elements\n"; std::exit(1);
        }
        if (index > length - 1)
        {
            std::cerr << "Error: invalid index, index should be less than the number of elements!\n"; std::exit(1);
        }
    }
    void move_right_by_one(const u16 index) {
        if (length >= allocated) {
            this->reserve(allocated * 2);
        }
        length++;
        for (u16 itr = index; itr < length - 1; ++itr) {
            const auto src = memory[itr].data();
            const auto dst = memory[itr + 1].data();
            new(reinterpret_cast<void*>(dst))T(std::move(*src));
        }
    }
public:
    Vector() :length(0), allocated(0) {
        this->reserve(1);
    }
    Vector(const u16 new_capacity) :length(0), allocated(0) {
        float power = log2(new_capacity);
        if (int(power) != power)
            power++;
        this->reserve(pow(2, power));
    }
    ~Vector() {
        delete[]memory;
        length = 0;
        allocated = 0;
        memory = nullptr;
    }
    T* begin() { return memory->data(); }
    int count() const{ return length; }
    T* end() { return (memory + length)->data(); }
    T back() {
        if (length > 0)
            return (*this)[length - 1];
        else return T();
    }
    T front() {
        if (length > 0)
            return (*this)[0];
        else return T();
    }
    //Vector<T>& operator=(const Vector<T>&object) {}
    //Vector(const Vector<T>& object){}
    bool empty()const {
        return (length == 0);
    }
    u16 capacity()const {
        return allocated;
    }
    void pop_back() {
        if (length == 0)return;
        const auto last_element = memory[--length].data();
        last_element->~T();
        if (2 * length == allocated) {
            allocated /= 2;
            this->reserve(allocated);
        }
    }
    //copy construct new item
    void push_back(const T& value) {
        if (length >= allocated) { //in case big bad voodoo
            this->reserve(allocated * 2);
        }
        const auto dst = memory[length++].data();
        new(reinterpret_cast<void*>(dst))T(value);
    }
    //move construct new item
    void push_back(const T&& value) {
        if (length >= allocated) { //in case big bad voodoo
            this->reserve(allocated * 2);
        }
        const auto dst = memory[length++].data();
        new(reinterpret_cast<void*>(dst))T(std::move(value));
    }
    void reserve(const u16 newCapacity) {
        if (newCapacity <= allocated)return;//the call to reserve is redundant
        const auto old_memory = memory;
        memory = new ItemWrapper<T>[newCapacity]; //allocation of memory
        allocated = newCapacity; //assign allocated
        for (u16 index = 0; index < length; ++index) {
            const auto src = old_memory[index].data();
            const auto dst = memory[index].data();
            new(reinterpret_cast<void*>(dst))T(std::move(*src)); //force move constructor
            src->~T(); //being sure the the old data is manually destroyed
        }
        if (old_memory) delete[]old_memory; // deallocating the old memory;
    }
    void clear() {
        if (length > 0) {
            delete[]memory;
            length = 0;
            allocated = 0;
            this->reserve(1);
        }
    }
    void insert(const u16 index, const T& value) {
        if (index == 0 && length == 0) {
            (*this)->push_back(value);
        }
        check_index(index);
        move_right_by_one(index);
        const auto dst = memory[index].data();
        new(reinterpret_cast<void*>(dst))T(value);
    }
    void insert(const u16 index, const T&& value) {
        if (index == 0 && length == 0) {
            (*this)->push_back(value);
        }
        check_index(index);
        move_right_by_one(index);
        const auto dst = memory[index].data();
        new(reinterpret_cast<void*>(dst))T(std::move(value));
    }
    void erase(const u16 index) {
        check_index(index);
        for (u16 itr = index; itr < length - 1; ++itr) {
            const auto dst = memory[itr].data();
            const auto src = memory[itr + 1].data();
            new(reinterpret_cast<void*>(dst))T(std::move(*src));
        }
        this->pop_back();
    }
    void erase(const u16 start_point, const u16 end_point) {
        check_index(start_point);
        check_index(end_point);
        if (start_point > end_point) {
            std::cerr << "start_point must be lower or equal to end_point!";
            std::exit(1);
        }
        if (start_point == end_point) {
            this->erase(start_point);
        }
        const u16 step = end_point - start_point;
        for (u16 itr = start_point; itr < length - step; ++itr) {
            const auto dst = memory[itr].data();
            const auto src = memory[itr + step].data();
            new(reinterpret_cast<void*>(dst))T(std::move(*src));
        }
        for (u16 itr = 0; itr < step; ++itr) {
            this->pop_back();
        }
    }
    T& get(const u16 index) {
        check_index(index);
        return (*this)[index];
    }
    const T& get(const u16 index)const {
        check_index(index);
        return (*this)[index];
    }
    void set(const u16 index, const T& value) {
        check_index(index);
        const auto dst = memory[index].data();
        new(reinterpret_cast<void*>(dst))T(value);
    }
    void set(const u16 index, const T&& value) {
        check_index(index);
        const auto dst = memory[index].data();
        new(reinterpret_cast<void*>(dst))T(std::move(value));
    }
    T& operator[](const u16 index) {
        check_index(index);
        return *((memory + index)->data());
    }
    const T& operator[](const u16 index)const {
        check_index(index);
        return *((memory + index)->data());
    }
    template<class MYCALLBACK>
    void sort(MYCALLBACK callback=nullptr) {
        for (u16 i = 0; i < length - 1; ++i) {
            for (u16 j = i+1; j < length; ++j) {
                if (callback != nullptr) {
                    if (callback(this->get(i), this->get(j))) {
                    swap(memory[i], memory[j]);
                    }
                }
                else {
                    if (this->get(i) > this->get(j)) {
                        swap(memory[i], memory[j]);
                    }
                }
            }
        }
    }
    void sort() {
        typedef bool (*empty)(const T&, const T&);
        //sort<bool(*)(const T&, const T&);
        sort <empty> (nullptr);
    }
    template<class MYCALLBACK>
    int firstIndexOf(const T& object2,MYCALLBACK callback = nullptr) {
        for (u16 i = 0; i < length; ++i) {
            if (callback != nullptr) {
                if (callback(this->get(i), object2)) {
                    return i;
                }
            }
            else {
                if (this->get(i) == object2) {
                    return i;
                }
            }
        }
        return -1;
    }
    int firstIndexOf() {
        typedef bool (*empty)(const T&, const T&);
        firstIndexOf<empty>(nullptr);
    }
};
#endif