#ifndef TCG_POOL_H

#define TCG_POOL_H

// STD includes

#include "assert.h"

#include <vector></vector>

#include <algorithm></algorithm>

#include <functional></functional>

// Discriminate rvalues support - either use Boost's config.hpp for automatic lookup,

// or deal with it manually

#ifndef TCG_RVALUES_SUPPORT

#include <boost config.hpp=""></boost>

#ifdef BOOST_NO_RVALUE_REFERENCES

#define TCG_RVALUES_SUPPORT 0

#else

#define TCG_RVALUES_SUPPORT 1

#endif

#endif

/*!

  \file     pool.h

  \brief    This file contains an implementation of the \a pool container concept.

  \details  A pool is a container that supports two fundamental operations, acquire() and

            release(), whose purpose is that of marking access operations to a resource

            that should not be destroyed when the access operation ends.

            Creation and destruction of resources can be a time-consuming task that could

            be avoided when it is known that resources could be reused - which is the very

            reason why caching can be a useful approach to some problems.

            The classical cache concept is nothing more than that of a standard associative

            map, tweaked to accomodate specific commodities - such as managing the cache

            size.

            However, sometimes resources could be considered to be effectively indentical,

            to the point that assigning a key is merely a way to keep the objects

            distinct in the cache. Users are in the condition to require only two functions,

            one to acquire() a resource, the other to release() it.

            The Pool concept we are introducing satisfies the following ruleset:

            
 The pool is a dynamical container which allocates resources by invoking the

                 objects' default constructor. 

            
 Objects in the pool are \b not destructed, except when the pool is explicitly

                 \a squeezed by the user.

            
 Keys are indices, returned by the pool with an incremental ordering. 

            
 An object which has been acquired cannot be acquired again until it has been

                 released 

*/

namespace tcg

{

//****************************************************************************

//    TCG Indices Pool  class

//****************************************************************************

template <typename cont="std::vector&lt;T" t="size_t," typename="">></typename>

class indices_pool

{

public:

	typedef T value_type;

	typedef Cont container_type;

private:

	T m_start;				//!< First index to be acquired

	T m_size;				//!< Current indices count

	Cont m_releasedIndices; //!< Priority queue of released indices

public:

	indices_pool(value_type start = 0) : m_start(start), m_size(0) {}

	~indices_pool() {}

	template <typename iter=""></typename>

	indices_pool(value_type size, iter releasedBegin, iter releasedEnd, value_type start = 0)

		: m_start(start), m_size(size), m_releasedIndices(releasedBegin, releasedEnd)

	{

		std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(), std::greater<t>());</t>

	}

	template <typename iter=""></typename>

	indices_pool(iter acquiredBegin, iter acquiredEnd, value_type start = 0)

		: m_start(start)

	{

		if (acquiredBegin == acquiredEnd)

			m_size = 0;

		else {

			// Sort the acquired indices

			std::vector<t> acquired(acquiredBegin, acquiredEnd);</t>

			std::sort(acquired.begin(), acquired.end());

			assert(acquired.front() >= m_start);

			// Scan them, adding holes in the acquired sequence to released indices

			m_size = acquired.back() - m_start + 1;

			assert(m_size >= (T)acquired.size());

			m_releasedIndices.reserve(m_size - acquired.size());

			T curIdx = m_start;

			typename std::vector<t>::iterator at, aEnd(acquired.end());</t>

			for (at = acquired.begin(); at != aEnd; ++at, ++curIdx)

				for (; curIdx != *at; ++curIdx)

					m_releasedIndices.push_back(curIdx);

			std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(), std::greater<t>());</t>

		}

	}

	value_type size() const { return m_size; }

	value_type releasedSize() const { return m_releasedIndices.size(); }

	value_type acquiredSize() const { return size() - releasedSize(); }

	const container_type &releasedIndices() const { return m_releasedIndices; }

	value_type acquire()

	{

		if (!m_releasedIndices.empty()) {

			value_type idx = m_releasedIndices.front();

			pop_heap(m_releasedIndices.begin(), m_releasedIndices.end(), std::greater<t>());</t>

			m_releasedIndices.pop_back();

			return idx;

		}

		return m_start + m_size++;

	}

	void release(value_type idx)

	{

		m_releasedIndices.push_back(idx);

		push_heap(m_releasedIndices.begin(), m_releasedIndices.end(), std::greater<t>());</t>

	}

	void clear()

	{

		m_size = 0;

		m_releasedIndices.clear();

	}

	//! Removes pool entries whose index is beyond that of the last acquired one.

	void squeeze()

	{

		if (m_releasedIndices.empty())

			return;

		std::sort_heap(m_releasedIndices.begin(), m_releasedIndices.end(), std::greater<t>()); // O(n logn)</t>

		// Decrease the pool size as long as the back items are unused

		T lastIndex = m_start + m_size - 1;

		typename Cont::iterator ut, uEnd(m_releasedIndices.end());

		for (ut = m_releasedIndices.begin(); ut != uEnd && *ut == lastIndex; ++ut)

			--lastIndex, --m_size;

		if (ut != m_releasedIndices.begin())

			m_releasedIndices.swap(Cont(ut, uEnd));

		std::make_heap(m_releasedIndices.begin(), m_releasedIndices.end(), std::greater<t>()); // O(n)</t>

	}

#if (TCG_RVALUES_SUPPORT > 0)

	indices_pool(const indices_pool &other)

		: m_start(other.m_start), m_size(other.m_size), m_releasedIndices(other.m_releasedIndices)

	{

	}

	indices_pool &operator=(const indices_pool &other)

	{

		m_start = other.m_start, m_size = other.m_size, m_releasedIndices = other.m_releasedIndices;

		return *this;

	}

	indices_pool(indices_pool &&other)

		: m_start(other.m_start), m_size(other.m_size), m_releasedIndices(std::forward<container_type &&="">(other.m_releasedIndices)) {}</container_type>

	indices_pool &operator=(indices_pool &&other)

	{

		m_start = other.m_start, m_size = other.m_size;

		m_releasedIndices = std::forward<container_type &&="">(other.m_releasedIndices);</container_type>

		return *this;

	}

#endif

};

//----------------------------------------------------------------

template <typename cont="std::vector&lt;T" t,="" typename="">></typename>

class pool

{

public:

	typedef T value_type;

	typedef Cont container_type;

	typedef size_t size_type;

private:

	Cont m_objects;						 //!< Objects in the pool

	tcg::indices_pool<size_t> m_indices; //!< Indices Pool representing m_objects</size_t>

public:

	pool() {}

	~pool() {}

	const tcg::indices_pool<size_t> &indices() const { return m_indices; }</size_t>

	size_type size() const

	{

		assert(m_indices.size() <= m_objects.size());

		return m_objects.size();

	}

	size_type releasedSize() const { return m_objects.size() - m_indices.acquiredSize(); }

	size_type acquiredSize() const { return m_indices.acquiredSize(); }

	const value_type &operator[](size_type idx) const { return m_objects[idx]; }

	value_type &operator[](size_type idx) { return m_objects[idx]; }

	size_type acquire()

	{

		size_t result = m_indices.acquire();

		if (result >= m_objects.size()) {

			assert(result == m_objects.size());

			m_objects.push_back(T());

		}

		return result;

	}

	void release(size_type idx) { m_indices.release(idx); }

	void releaseAll() { m_indices.clear(); }

	void clear()

	{

		releaseAll();

		m_objects.clear();

	}

	//! Removes pool entries whose index is beyond that of the last acquired one.

	void squeeze()

	{

		m_indices.squeeze();

		m_objects.resize(m_indices.size());

	}

};

} // namespace tcg

#endif // TCG_POOL_H