#include <cassert>
#include <cstddef>
#include <utility>
#include <new>
#include <string>
#include <vector>

template <std::size_t nbytes>
class StackPool
{
public:

    StackPool()
    {
        for (std::size_t i { 0 }; i < nbytes; ++i)
            used[i] = false;
    }

    template <typename T, typename... Args>
    T* allocate(Args&&... args)
    {
        static_assert( sizeof(T) < nbytes );
        if (sizeof(T) > free_bytes())
            return nullptr;

        // mark these bytes as used
        for (std::size_t i { 0 }; i < sizeof(T); ++i)
            used[head + i] = true;

        char* location { &buffer[head] };
        head += sizeof(T);

        return (new (location) T { std::forward<Args>(args)... });
    }

    template <typename T>
    void deallocate(T* obj)
    {
        auto ptr = reinterpret_cast<char*>(obj);

        // call destructor
        obj->~T();

        // find what position his object started at
        std::size_t index = ptr - &buffer[0];

        // mark these bytes as unused
        for (std::size_t i { 0 }; i < sizeof(T); ++i)
            used[index + i] = false;

        // decrease head until it neighbours a used byte (or is the beginning)
        if (head > 0)
        {
            while (not used[head - 1] and head > 0)
                --head;
        }
    }

    std::size_t free_bytes() const
    {
        return nbytes - head;
    }

private:

    char buffer[nbytes];
    bool used[nbytes] { };
    
    std::size_t head { 0 };

};

int main()
{
    // Test basic functionality
    {
        constexpr std::size_t const size { sizeof(int) + sizeof(double) + 2*sizeof(int) };

        StackPool<size> pool { };
        assert(( pool.free_bytes() == size ));

        auto i1 { pool.allocate<int>(1) };
        assert(( *i1 == 1 ));

        auto d { pool.allocate<double>(2.5) };
        assert(( *d == 2.5 ));

        auto i2 { pool.allocate<int>(4) };
        assert(( *i2 == 4 ));

        assert(( pool.free_bytes() == sizeof(int) ));

        // remove from middle, meaning it won't release the memory until
        // anything after is deallocated
        pool.deallocate(d);
        assert(( pool.free_bytes() == sizeof(int) ));

        // remove the latest, will make this value and anything removed directly
        // before it (d in this case).
        pool.deallocate(i2);
        assert(( pool.free_bytes() == sizeof(double) + 2*sizeof(int) ));

        pool.deallocate(i1);
        assert(( pool.free_bytes() == size ));
    }

    // Test that complex objects work (check for no memory leaks)
    {
        constexpr std::size_t const size { 
            2*sizeof(std::vector<std::string>) 
        };

        StackPool<size> pool { };
        assert(( pool.free_bytes() == size ));

        auto v1 = pool.allocate<std::vector<std::string>>(100ull, "-");
        assert(( *v1 == std::vector<std::string>(100ull, "-") ));

        assert(( pool.free_bytes() == sizeof(std::vector<std::string>) ));

        auto v2 = pool.allocate<std::vector<std::string>>("a", "b", "c");
        assert(( *v2 == std::vector<std::string>{ "a", "b", "c" } ));

        assert(( pool.free_bytes() == 0 ));

        // ensure we cannot allocate more than what fits
        auto doesnt_fit = pool.allocate<int>(5);
        assert(( doesnt_fit == nullptr ));

        pool.deallocate(v2);

        assert(( pool.free_bytes() == sizeof(std::vector<std::string>) ));

        auto v3 = pool.allocate<std::vector<int>>(1,2,3,4);
        assert(( *v3 == std::vector<int>{ 1, 2, 3, 4 } ));

        pool.deallocate(v3);
        pool.deallocate(v1);
    }
}