/**
 * mempool.h - memory allocation structure that allocates blocks of memory at a time
 * Copyright (C) 2015 Jonah Schreiber ([email protected])
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#pragma once

#define DEFAULT_POOL_SIZE 10000

#include <algorithm>
#include <cassert>
#include <vector>
#include <iterator>

template <typename T>
class MemoryPool {
public:
    typedef T              *pointer;
    typedef T              &reference;
    typedef const T        &const_reference;
    typedef size_t          size_type;
    typedef std::ptrdiff_t  difference_type;

    template <typename elem_type = T, typename elem_type_nonconst = T, typename pool_type = MemoryPool<elem_type> >
    class mempool_iterator : std::iterator<std::random_access_iterator_tag,
                                           elem_type,
                                           difference_type> {
        friend class mempool_iterator<const T, T, const MemoryPool>;
    public:
        inline mempool_iterator() : mParent(nullptr), mIndex(0) {}
        inline mempool_iterator(pool_type *parent, size_type index) : mParent(parent), mIndex(index) {}
        inline mempool_iterator(const mempool_iterator<T, T, MemoryPool> &other) :
            mParent(other.mParent), mIndex(other.mIndex) {}
        inline elem_type &operator*()  { return (*mParent)[mIndex]; }
        inline elem_type *operator->() { return &(operator*()); }
        inline mempool_iterator &operator++() { ++mIndex; return *this; }
        inline mempool_iterator operator++(int) { mempool_iterator tmp(*this); ++(*this); return tmp; }
        inline mempool_iterator &operator--() { --mIndex; return *this; }
        inline mempool_iterator operator--(int) { mempool_iterator tmp(*this); ++(*this); return tmp; }
        inline mempool_iterator operator+(difference_type n) const { mempool_iterator tmp(*this); tmp += n; return tmp; }
        inline mempool_iterator &operator+=(difference_type n) { mIndex += n; return *this; }
        inline mempool_iterator operator-(difference_type n) const { mempool_iterator tmp(*this); tmp -= n; return tmp; }
        inline mempool_iterator &operator-=(difference_type n) { mIndex -= n; return *this; }
        inline bool operator==(const mempool_iterator &other) const { return mIndex == other.mIndex; }
        inline bool operator!=(const mempool_iterator &other) const { return mIndex != other.mIndex; }
    private:
        pool_type *mParent;
        size_type mIndex;
    };

    friend class mempool_iterator<>;

    explicit inline MemoryPool(size_type poolSize = DEFAULT_POOL_SIZE) :
        mPoolSize(poolSize), mMemIndex(poolSize), mTotalSize(0) {}

    inline MemoryPool(const MemoryPool &other) :
        mPoolSize(other.mPoolSize), mMemIndex(other.mMemIndex), mTotalSize(other.mTotalSize) {

        mPools.reserve(mPoolSize);
        for (auto &&pool : other.mPools) {
            T *block = new T[mPoolSize];
            std::copy(pool, pool + mPoolSize, block);
            mPools.push_back(block);
        }
    }

    inline MemoryPool(MemoryPool &&other) noexcept :
        mPoolSize(other.mPoolSize), mMemIndex(other.mMemIndex), mTotalSize(other.mTotalSize) {

        mPools = other.mPools;
        other.mPools.clear();
    }

    inline ~MemoryPool() noexcept {
        for (auto &&pool : mPools) {
            delete[] pool;
        }
    }

    inline MemoryPool &operator=(const MemoryPool &other) {
        MemoryPool tmp(other); // re-use copy-constructor
        *this = std::move(tmp); // re-use move-assignment
        return *this;
    }

    inline MemoryPool &operator=(MemoryPool &&other) noexcept {
        std::swap(mPools, other.mPools);
        std::swap(mMemIndex, other.mMemIndex);
        std::swap(mPoolSize, other.mPoolSize);
        std::swap(mTotalSize, other.mTotalSize);
        return *this;
    }

    inline size_type size() const {
        return mTotalSize;
    }

    inline bool empty() const {
        return mTotalSize == 0;
    }

    inline reference operator[](size_type n) {
        return (mPools[n / mPoolSize])[n % mPoolSize];
    }

    inline const_reference operator[](size_type n) const {
        return (mPools[n / mPoolSize])[n % mPoolSize];
    }

    typedef mempool_iterator<T, T, MemoryPool> iterator;
    inline iterator begin() { return iterator(this, 0); }
    inline iterator end()   { return iterator(this, size()); }

    typedef mempool_iterator<const T, T, const MemoryPool> const_iterator;
    inline const_iterator begin() const { return const_iterator(this, 0); }
    inline const_iterator end()   const { return const_iterator(this, size()); }

    inline pointer allocate() {
        assert(mMemIndex <= mPoolSize);
        if (mMemIndex == mPoolSize) {
            mPools.push_back(new T[mPoolSize]);
            mMemIndex = 0;
        }
        mTotalSize++;
        return &mPools[mPools.size() - 1][mMemIndex++];
    }

    template <typename U>
    inline pointer allocate(U &&item) {
        static_assert(std::is_same<T, typename std::decay<U>::type>::value, "item must be of type T");
        assert(mMemIndex <= mPoolSize);
        if (mMemIndex == mPoolSize) {
            mPools.push_back(new T[mPoolSize]);
            mMemIndex = 0;
        }
        mPools[mPools.size() - 1][mMemIndex] = std::forward<U>(item);
        mTotalSize++;
        return &mPools[mPools.size() - 1][mMemIndex++];
    }

protected:
    std::vector<T*> mPools;
    size_type mPoolSize, mMemIndex, mTotalSize;
};

template <typename T>
class BaseMemoryPool : public MemoryPool<char> {
public:
    explicit inline BaseMemoryPool(size_type poolSize = DEFAULT_POOL_SIZE) : MemoryPool(poolSize) {}

    template <typename U>
    inline T *construct(U &&item) {
        static_assert(std::is_base_of<T, typename std::decay<U>::type>::value, "item must be of or derived of type T");
        assert(mMemIndex <= mPoolSize && sizeof(U) <= mPoolSize);
        if (mMemIndex + sizeof(U) > mPoolSize) {
            mPools.push_back(new T[mPoolSize]);
            mMemIndex = 0;
        } // only got so far!
        mPools[mPools.size() - 1][mMemIndex] = std::forward<U>(item);
        mTotalSize++;
        return &mPools[mPools.size() - 1][mMemIndex++];
    }
};