#include <iostream>
#include <vector>
#include <cstdlib>
#include <exception>
#include <map>
#include <list>
#include <chrono>


template <class T>
class myContainer {
private:
    T* container_;
    bool* free_chunks_;
    size_t size_;
    size_t count_free_chunks_;
    size_t index_for_fill_;
public:
    myContainer() {
        size_ = 0;
        count_free_chunks_ = 0;
        index_for_fill_ = 0;
        container_ = nullptr;
        free_chunks_ = nullptr;
    }

    void resize(size_t elementCount) {
        delete[] container_;
        delete[] free_chunks_;
        free_chunks_ = new bool[elementCount];
        container_ = new T[elementCount];

        size_ = elementCount;
        count_free_chunks_ = elementCount;

        for(size_t i = 0; i < elementCount; i++) {
            free_chunks_[i] = true;
        }
    }

    void fill(T element_for_fill) {
        container_[index_for_fill_++] = element_for_fill;
    }

    void pushFreeChunk(T elementForPush) {
        for (int i = 0; i < size_ ; i++) {
            if (container_[i] == elementForPush) {
                free_chunks_[i] = true;
                count_free_chunks_++;
                return;
            }
        }
    }

    T GetFreeChunk() {
        for (size_t i = 0; i < size_; i++) {
            if (free_chunks_[i]) {
                free_chunks_[i] = false;
                --count_free_chunks_;
                return container_[i];
            }
        }
    }

    size_t GetCountFreeChunks() const {
        return count_free_chunks_;
    }

    size_t size() const {
        return size_;
    }
};


class Group {
private:
    size_t usedChunksCount_;
    size_t chunksCount_;
    size_t size_;
    myContainer<void*> freeChunksStack_;

public:
    Group(): usedChunksCount_(0), chunksCount_(0), size_(0) {}

    Group(size_t chunksCount, size_t size): chunksCount_(chunksCount), size_(size), usedChunksCount_(0) {

        freeChunksStack_.resize(chunksCount_);
        auto* chunk = (char*)(malloc(chunksCount_ * size_));

        for (size_t i = 0; i < chunksCount_; ++i) {
            freeChunksStack_.fill(chunk);
            if (i != chunksCount_ - 1) {
                chunk += size_;
            }
        }
    }

    bool havePlace() const {
        return (usedChunksCount_ < chunksCount_&& freeChunksStack_.GetCountFreeChunks() > 0);
    }

    void* getFreeChunk() {
        auto *res = freeChunksStack_.GetFreeChunk();
        return res;
    }

    void* allocateInGroup() {
        ++usedChunksCount_;
        return getFreeChunk();
    }

    void deallocateInGroup(void* chunk, size_t size) {
        --usedChunksCount_;
        freeChunksStack_.pushFreeChunk(chunk);
    }

    size_t getChunkSize() const {
        return size_;
    }

    size_t getChunksCount() const {
        return chunksCount_;
    }
};



bool cmp(const std::pair<size_t, Group>& l, const std::pair<size_t, Group>& r) {
    return l.first < r.first;
}



template <class T>
class PoolAllocator {
private:
    size_t groupsNumber_;

    size_t binSearch(std::vector<std::pair<size_t, Group>>& arr, size_t x) {
        size_t sz = arr.size();
        size_t l = 0;
        size_t h = sz;
        while (l < h) {
            size_t mid = l + (h - l) / 2;
            if (x <= arr[mid].first) {
                h = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;

    static std::vector<std::pair<size_type, Group>> allGroups_;
    static std::map<pointer, int> positionToAllocatePointer_;


    template<typename T2>
    explicit PoolAllocator(PoolAllocator<T2> const& other) noexcept {
        for (auto group : other.allGroups_) {
            Group newGr(group.second.getChunksCount(), group.first);
            allGroups_.push_back({group.first, newGr});
        }
        groupsNumber_ = other.getGroupsNumber();
    }

    PoolAllocator() = default;

    PoolAllocator(std::vector<std::pair<int, size_type>>& memoryToAllocate) {
        groupsNumber_ = memoryToAllocate.size();
        for (size_t i = 0; i < groupsNumber_; ++i)
            allGroups_.push_back({ memoryToAllocate[i].second,Group(memoryToAllocate[i].first, memoryToAllocate[i].second) });

        sort(allGroups_.begin(), allGroups_.end(), cmp);
    }

    ~PoolAllocator() {
        allGroups_.clear();
    }

    pointer allocate(size_type chunksNum) {
        size_t pastePosition = binSearch(allGroups_, chunksNum * sizeof(value_type));

        if (pastePosition < allGroups_.size()) {
            auto& GroupToPaste = allGroups_[pastePosition];
            if (GroupToPaste.second.havePlace()) {
                auto ptr = (pointer)GroupToPaste.second.allocateInGroup();
                positionToAllocatePointer_[ptr] = pastePosition;
                return ptr;
            }

            else {
                for (size_t i = pastePosition; i < allGroups_.size(); i++)
                    if (allGroups_[i].second.havePlace()) {
                        auto *ptr = (pointer)allGroups_[i].second.allocateInGroup();
                        positionToAllocatePointer_[ptr] = i;
                        return ptr;
                    }
                throw std::bad_alloc();
            }

        }
        else
            throw std::bad_alloc();
    }

    void deallocate(pointer ptr, size_type elementsCount) {
        int deallocPos = positionToAllocatePointer_[ptr];
        positionToAllocatePointer_.erase(ptr);
        auto& GroupToDeallocate = allGroups_[deallocPos];
        GroupToDeallocate.second.deallocateInGroup(ptr, elementsCount);
    }

    size_type getGroupsNumber() const {
        return groupsNumber_;
    }
};


template <class T>
std::vector<std::pair<size_t, Group>> PoolAllocator<T>::allGroups_;

template <class T>
std::map<T*, int> PoolAllocator<T>::positionToAllocatePointer_;




template <class T, class T2>
bool operator==(const PoolAllocator <T>& first, const PoolAllocator <T2>& second) {
    return (first.allGroups_ == second.allGroups_ && first.getGroupsNumber() == second.getGroupsNumber());
}

template <class T, class T2>
bool operator!=(const PoolAllocator <T>& first, const PoolAllocator <T2>& second) {
    return (first.allGroups_ != second.allGroups_ || first.getGroupsNumber() != second.getGroupsNumber());
}

int main() {

    std::vector<std::pair<int, size_t>> groups;
    groups.resize(4);
    groups[1].second = 2000; groups[1].first = 1000;
    groups[2].second = 1000; groups[2].first = 1000;
    groups[0].second = 2000; groups[0].first = 1000;
    groups[3].second = 330000; groups[3].first = 2;

    PoolAllocator<int>testAlloc(groups);

    std::vector<int, PoolAllocator<int>> v1(testAlloc);

    auto start1 = std::chrono::system_clock::now();

    for (int i = 0; i < 10000; i++) {
        v1.push_back(i);
    }

    auto end1 = std::chrono::system_clock::now();


    std::vector<int> v2;
    auto start2 = std::chrono::system_clock::now();

    for (int i = 0; i < 10000; i++) {
        v2.push_back(i);
    }
    auto end2 = std::chrono::system_clock::now();

    auto res1 = std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1).count();
    auto res2 = std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count();



    std::cout << "\nThe time with MyAlloc: " << res1 << " ms\n";
    std::cout << "\nThe time without MyAlloc: " << res2 << " ms\n";


    return 0;
}