#pragma once
#include <vector>
#include <stack>
#include <algorithm>

#include "../../inc/tbb/parallel_sort.h"
#include "BoolArray.h" 
#include "BlockVector.h"
#include "../CollectionHelper.h"

#define USE_BLOCK_VECTOR

// Class for memory efficiency: stores all objects of some type in a vector. Pointers to the object can then be requested.
template<typename T>
class ObjectPool
{
private:
#ifdef USE_BLOCK_VECTOR
	BlockVector<T> mData;
#else
	std::vector<T> mData;
#endif
	BoolArray mMarkedForDeletion;
	const size_t mBaseCapacity = 0;

	bool AnyMarkedForDeletion() const { return !mMarkedForDeletion.Empty(); }
	bool MarkedForDeletion(size_t index) const { return index < mMarkedForDeletion.Size() && mMarkedForDeletion[index]; }
	void MarkForDeletion(size_t index)
	{
		if (index >= mMarkedForDeletion.Size())
			mMarkedForDeletion.Resize(index + 1);
		mMarkedForDeletion.Set(index, true);
	}
public:
	ObjectPool(size_t initialCapacity = 1) :
#ifdef USE_BLOCK_VECTOR
		mData(BlockVector<T>(initialCapacity)),
#else
		mData(std::vector<T>()),
#endif
		mMarkedForDeletion(BoolArray()),
		mBaseCapacity(initialCapacity)
	{
#ifndef USE_BLOCK_VECTOR
		mData.reserve(initialCapacity);
#endif
	}

	// Adds a new item to the pool. 
	template <class... Args>
	T* Create(Args&&... args)
	{
		//// If any nodes are marked for deletion, reuse their position
		//if (!mMarkedForDeletion.empty())
		//{
		//	T* res = &mData[mMarkedForDeletion.top()];
		//	mMarkedForDeletion.pop();
		//	return res;
		//}
		//else // Else, resize the data array to create some space for this new node
		//{
			mData.emplace_back(std::forward<Args>(args)...);
			return &mData[mData.size() - 1];
		//}
	}

	// Moves the node from the given memory position into this pool. Returns the new pointer to this node
	T* Add(T* value)
	{
		mData.emplace_back(std::move(*value));
		return &mData[mData.size() - 1];
	}

	void Delete(size_t i) { MarkForDeletion(i); }

	// Removes all nodes that are marked for deletion.
	void Clean()
	{
		// There is only stuff to clean if there are nodes marked for deletion
		if (!AnyMarkedForDeletion()) return;

		size_t newIdx = 0;
		for (size_t oldIdx = 0; oldIdx < mData.size(); oldIdx++)
			// If this node should not be deleted, move it to the new position.
			if (!MarkedForDeletion(oldIdx))
			{
				if (oldIdx != newIdx)
					mData[newIdx] = std::move(mData[oldIdx]);
					//std::swap(mData[newIdx], mData[oldIdx]);
				newIdx++;
			}
#ifdef USE_BLOCK_VECTOR
		mData.shrink(newIdx);
		mData.reserve(mBaseCapacity);
#else
		mData.erase(mData.begin() + newIdx, mData.end());
		mData.shrink_to_fit();
		mData.reserve(mBaseCapacity);
#endif
		mMarkedForDeletion = BoolArray();
	}

	void Clear()
	{
		mData.clear();
		mMarkedForDeletion.Clear();
	}

	template<typename Comparer = std::less<T>>
	void Sort(size_t startIdx, size_t endIdx, const Comparer& comparer = Comparer())
	{
		// Check if any node are deleted in the range that needs to be sorted:
		if (AnyMarkedForDeletion() && mMarkedForDeletion.Any(startIdx, endIdx))
			Clean();
		tbb::parallel_sort(mData.begin() + startIdx, mData.begin() + endIdx, comparer);
	}

	inline size_t Size() const { return mData.size(); }

	inline const T* operator[](size_t i) const
	{
		if (MarkedForDeletion(i)) return NULL;
		return &mData.at(i);
	}

	inline T* operator[](size_t i)
	{
		if (MarkedForDeletion(i)) return NULL;
		return &mData.at(i);
	}
};