/*
 * pool.h
 *
 *  Created on: Feb 11, 2018
 *      Author: gregor
 */

#ifndef GLTB_POOL_H_
#define GLTB_POOL_H_

#include <vector>
#include <cassert>
#include <cstdlib>

#include "GLTB/exception.h"

namespace gltb {
    template<typename elementType>
	class PoolRegion {
	public:
        // this default constructor is required by std::vector, but must never be called
        PoolRegion() { assert(false); }

        PoolRegion(size_t numElements)
            : firstFreeElement(0), regionSize(numElements), usedElements(0)
        {
            region = (PoolElement*) aligned_alloc(16, numElements * sizeof(PoolElement));

            // initialize free list
            for (size_t i = 0; i < regionSize; i++) {
                region[i].nextFreeElement = i + 1;
            }
        }

        // required when move constructor is present, but must never be called
        PoolRegion(const PoolRegion &other) noexcept { assert(false); }

        PoolRegion(PoolRegion &&other) noexcept
        {
            copyFrom(other);

            other.region = nullptr;
            other.firstFreeElement = 0;
            other.regionSize = 0;
            other.usedElements = 0;
        }

        ~PoolRegion() noexcept
        {
            if(region != nullptr) {
                ::free(region);
            }
        }

        template<typename... constructorArgs>
        elementType *allocate(constructorArgs... arguments)
        {
            if (firstFreeElement >= regionSize) {
                return nullptr;
            }

            size_t elementIndex = firstFreeElement;

            firstFreeElement = region[elementIndex].nextFreeElement;
            elementType *result = &(region + elementIndex)->element;

            // initialize object using placement new
            new(result) elementType(arguments...);

            usedElements++;
            return result;
        }

        void free(elementType *element)
        {
        	// element is at EOL, so an explicit destructor call is required (counterpart to placement new in allocate())
        	element->~elementType();

            PoolElement *poolElement = (PoolElement*) element;
            size_t elementIndex = poolElement - region;

            poolElement->nextFreeElement = firstFreeElement;
            firstFreeElement = elementIndex;
            usedElements--;
        }

        size_t size() const { return regionSize; }
        size_t elements() const { return usedElements; }

        bool empty() const { return usedElements == 0; }

        bool full() const { return usedElements >= regionSize; }

        bool contains(elementType *element) const
        {
            return ((PoolElement*)element) >= region && ((PoolElement*)element) < region + regionSize;
        }

        // required when move constructor is present
        PoolRegion &operator =(const PoolRegion &other) { copyFrom(other); }

	private:
        union PoolElement {
            size_t nextFreeElement;
            elementType element;
        };

        PoolElement *region;
        size_t firstFreeElement;

        size_t regionSize;
        size_t usedElements;

        void copyFrom(const PoolRegion &other)
        {
            region = other.region;
            firstFreeElement = other.firstFreeElement;
            regionSize = other.regionSize;
            usedElements = other.usedElements;
        }
    };

    template<typename elementType>
    class Pool {
    public:
        Pool() {}

        template<typename... constructorArgs>
        elementType *allocate(constructorArgs... arguments)
        {
            for(size_t i = 0; i < regions.size(); i++) {
                if(!regions[i].full()) {
                    return regions[i].allocate(arguments...);
                }
            }

            // all regions are full - allocate new one
            size_t regionSize;
            if(regions.size() == 0) {
                regionSize = 128;
            } else {
                // TODO check if this isn't too wasteful
                regionSize = 2 * regions[regions.size() - 1].size();
            }
            regions.emplace_back(regionSize);
            return regions[regions.size() - 1].allocate(arguments...);
        }

        void free(elementType *element)
        {
            for(size_t i = 0; i < regions.size(); i++) {
                if(regions[i].contains(element)) {
                    regions[i].free(element);

                    // free largest free pool lazily when there it is empty and there is enough spare capacity in the rest
                    if(regions.size() > 2 && regions[regions.size() - 1].empty() &&
                       regions[regions.size() - 2].size() / regions[regions.size() - 2].elements() > 2) {
                        regions.resize(regions.size() - 1);
                    }

                    return;
                }
            }
            throw gltb::Exception("trying to free a non-pool-allocated element", "mlmesh::Pool::free()");
        }

	private:
        std::vector<PoolRegion<elementType> > regions;
	};
}

#endif /* GLTB_POOL_H_ */