/*
								+----------------------------------+
								|                                  |
								|  ***  Simple pool template  ***  |
								|                                  |
								|   Copyright © -tHE SWINe- 2013   |
								|                                  |
								|           Segregated.h           |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __LAME_FORWARD_ALLOCATED_POOL_INCLUDED
#define __LAME_FORWARD_ALLOCATED_POOL_INCLUDED

/**
 *	@file Segregated.h
 *	@date 2013
 *	@author -tHE SWINe-
 *	@brief a simple pool template
 */

#include "NewFix.h"
#include <vector>
#include <algorithm>

/*
 *								=== CForwardAllocatedPool ===
 */

/**
 *	@brief a very simple pool storage
 *
 *	@todo This is mostly untested - test it.
 *	@todo This is missing iterators - write iterator classes.
 *	@todo See if MSVC6 can support compile-time fixed page size.
 *	@todo Support memory alignment? Use STL allocator instead?
 *	@todo Put it side by side with SLAM++ fap and see if there are some differences, look for bugs.
 */
template <class CElemType>
class CForwardAllocatedPool {
public:
	typedef CElemType _TyElem; /**< @brief type of the stored element */
	typedef std::vector<_TyElem*> _TyPageList;
	typedef size_t _TyPageSize;

	/**
	 *	@brief constant iterator type
	 */
#if !defined(__FAP_DISABLE_CHECKED_ITERATORS) && defined(_MSC_VER) && !defined(__MWERKS__) && _MSC_VER >= 1400 && _MSC_VER < 1700 // not sure if the max _MSC_VER is low enough; if you get errors on the line below, decrement it
	class CConstIterator : public std::_Ranit<_TyElem, ptrdiff_t, const _TyElem*, const _TyElem&> { // MSVC secure iterator bullshit
#else // __SEGREGATED_MAKE_CHECKED_ITERATORS && _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400 && _MSC_VER < 1700
#if !defined(_MSC_VER) || defined(__MWERKS__) || _MSC_VER >= 1400
	class CConstIterator {
#else // !_MSC_VER || __MWERKS__ || _MSC_VER >= 1400
	class CConstIterator : public std::random_access_iterator<_TyElem, ptrdiff_t> { // msvc 60 needs to have a tag like this
#endif // !_MSC_VER || __MWERKS__ || _MSC_VER >= 1400
#endif // __SEGREGATED_MAKE_CHECKED_ITERATORS && _MSC_VER && !__MWERKS__ && _MSC_VER >= 1400 && _MSC_VER < 1700
#if defined(_MSC_VER) && !defined(__MWERKS__) && _MSC_VER <= 1200
	friend CForwardAllocatedPool; // MSVC 60 would think it is CForwardAllocatedPool::CConstIterator::CForwardAllocatedPool
#else // _MSC_VER && !__MWERKS__ && _MSC_VER <= 1200
	friend class CForwardAllocatedPool;
#endif // _MSC_VER && !__MWERKS__ && _MSC_VER <= 1200
	public:
		typedef _TyElem value_type; /**< @brief data type being accessed */
		typedef ptrdiff_t difference_type; /**< @brief data type for measuring difference between iterators */
		typedef const _TyElem *pointer; /**< @brief pointer to the payload type */
		typedef const _TyElem &reference; /**< @brief reference to the payload type */

#if !defined(_MSC_VER) || defined(__MWERKS__) || _MSC_VER >= 1400
		typedef std::random_access_iterator_tag iterator_category; /**< @brief iterator category (MSVC) */
#if !defined(__FAP_DISABLE_CHECKED_ITERATORS) && _SECURE_SCL && _MSC_VER < 1700 // not sure if the max _MSC_VER is low enough; if you get errors on the line below, decrement it
		typedef std::_Range_checked_iterator_tag _Checked_iterator_category; /**< @brief checked iterator category (MSVC 90) */
#endif // __SEGREGATED_MAKE_CHECKED_ITERATORS && _SECURE_SCL && _MSC_VER < 1700
#endif // !_MSC_VER || __MWERKS__ || _MSC_VER >= 1400
		// more MSVC secure iterator bullshit

	protected:
		typename _TyPageList::iterator m_p_page_it; /**< @brief page iterator */
		_TyPageSize m_n_page_size; /**< @brief current page size */
		ptrdiff_t m_n_page_off; /**< @brief offset in the current page */

	private:
		/**
		 *	@brief gets page iterator
		 *	@return Returns page iterator (used by the insert() and erase() functions).
		 */
		inline typename _TyPageList::iterator p_Page_Iter() const
		{
			return m_p_page_it;
		}

		/**
		 *	@brief gets sub-page offset
		 *	@return Returns sub-page offset (used by the insert() and erase() functions).
		 */
		inline ptrdiff_t n_Page_Offset() const
		{
			return m_n_page_off;
		}

	public:
		/**
		 *	@brief default constructor; initializes a new iterator
		 *
		 *	@param[in] p_page_it is the page iterator, poiniting to the page the element pointed to resides
		 *	@param[in] n_page_size is the page size, in elements
		 *	@param[in] n_page_off is sub-page offset of the element pointed to
		 */
		inline CConstIterator(typename _TyPageList::iterator p_page_it,
			_TyPageSize n_page_size, ptrdiff_t n_page_off)
			:m_p_page_it(p_page_it), m_n_page_size(n_page_size),
			m_n_page_off(n_page_off)
		{}

		/**
		 *	@brief calculates distance between two iterators
		 *	@param[in] r_t_iter is the second iterator
		 *	@return Returns distance between this and r_t_iter, in elements.
		 */
		difference_type operator -(const CConstIterator &r_t_iter) const
		{
			_ASSERTE(m_n_page_size == r_t_iter.m_n_page_size); // iterators should belong to the same pool
			ptrdiff_t n_page_difference = m_p_page_it - r_t_iter.m_p_page_it;
			ptrdiff_t n_subpage_difference = m_n_page_off - r_t_iter.m_n_page_off;
			return n_subpage_difference + n_page_difference * m_n_page_size;
		}

		/**
		 *	@brief compares two iterators for equality
		 *	@param[in] r_t_other is the second iterator
		 *	@return Returns true in case this and r_t_iter point
		 *		to the same element, otherwise returns false.
		 */
		inline bool operator ==(const CConstIterator &r_t_other) const
		{
			_ASSERTE(m_n_page_size == r_t_other.m_n_page_size); // iterators should belong to the same pool
			return m_n_page_off == r_t_other.m_n_page_off && // presumably cheaper
				m_p_page_it == r_t_other.m_p_page_it;
		}

		/**
		 *	@brief compares two iterators for inequality
		 *	@param[in] r_t_other is the second iterator
		 *	@return Returns true in case this iterator points to element that comes
		 *		before the one, pointed to by r_t_iter, otherwise returns false.
		 */
		inline bool operator <(const CConstIterator &r_t_other) const
		{
			_ASSERTE(m_n_page_size == r_t_other.m_n_page_size); // iterators should belong to the same pool
			return m_p_page_it < r_t_other.m_p_page_it ||
				(m_p_page_it == r_t_other.m_p_page_it &&
				m_n_page_off < r_t_other.m_n_page_off);
		}

		/**
		 *	@brief compares two iterators for inequality
		 *	@param[in] r_t_other is the second iterator
		 *	@return Returns false in case this and r_t_iter point
		 *		to the same element, otherwise returns true.
		 */
		inline bool operator !=(const CConstIterator &r_t_other) const
		{
			return !(*this == r_t_other);
		}

		/**
		 *	@brief compares two iterators for inequality
		 *	@param[in] r_t_other is the second iterator
		 *	@return Returns true in case this iterator points to element that comes
		 *		after the one, pointed to by r_t_iter, otherwise returns false.
		 */
		inline bool operator >(const CConstIterator &r_t_other) const
		{
			return (r_t_other < *this);
		}

		/**
		 *	@brief compares two iterators for inequality
		 *	@param[in] r_t_other is the second iterator
		 *	@return Returns true in case this iterator points to element that comes
		 *		not after the one, pointed to by r_t_iter, otherwise returns false.
		 */
		inline bool operator <=(const CConstIterator &r_t_other) const
		{
			return !(*this > r_t_other);
		}

		/**
		 *	@brief compares two iterators for inequality
		 *	@param[in] r_t_other is the second iterator
		 *	@return Returns true in case this iterator points to element that comes
		 *		not before the one, pointed to by r_t_iter, otherwise returns false.
		 */
		inline bool operator >=(const CConstIterator &r_t_other) const
		{
			return !(*this < r_t_other);
		}

		/**
		 *	@brief shifts the iterator to the next element
		 *	@return Returns reference to this iterator.
		 */
		CConstIterator &operator ++()
		{
			if(++ m_n_page_off == m_n_page_size) {
				m_n_page_off = 0; // equivalent to -= m_n_page_size;
				++ m_p_page_it;
			}
			return *this;
		}

		/**
		 *	@brief shifts the iterator to the previous element
		 *	@return Returns reference to this iterator.
		 */
		CConstIterator &operator --()
		{
			if(-- m_n_page_off == -1) {
				m_n_page_off += m_n_page_size;
				-- m_p_page_it;
			}
			return *this;
		}

		/**
		 *	@brief shifts the iterator to the next element
		 *	@return Returns reference to this iterator.
		 *	@note This is the post-increment function.
		 */
		CConstIterator operator ++(int)
		{
			CConstIterator copy = *this;
			++ *this;
			return copy;
		}

		/**
		 *	@brief shifts the iterator to the previous element
		 *	@return Returns reference to this iterator.
		 *	@note This is the post-increment function.
		 */
		CConstIterator operator --(int)
		{
			CConstIterator copy = *this;
			-- *this;
			return copy;
		}

		/**
		 *	@brief calculates an iterator pointing to an element, specified distance away
		 *	@param[in] n_offset is offset, in elements
		 *	@return Returns iterator pointing to the element n_offset elements away from
		 *		the element this iterator points to.
		 */
		CConstIterator operator +(difference_type n_offset) const
		{
			CConstIterator copy = *this;
			return (copy += n_offset);
		}

		/**
		 *	@brief calculates an iterator pointing to an element, specified distance away
		 *	@param[in] n_offset is negative offset, in elements
		 *	@return Returns iterator pointing to the element -n_offset elements away from
		 *		the element this iterator points to.
		 */
		CConstIterator operator -(difference_type n_offset) const
		{
			CConstIterator copy = *this;
			return (copy -= n_offset);
		}

		/**
		 *	@brief shifts this iterator to point to an element, specified distance away
		 *	@param[in] n_offset is offset, in elements
		 *	@return Returns reference to this.
		 */
		CConstIterator &operator +=(difference_type n_offset)
		{
			if(m_n_page_off + n_offset >= 0) {
				m_n_page_off += n_offset;
				m_p_page_it += m_n_page_off / m_n_page_size;
				m_n_page_off %= m_n_page_size;
			} else {
				m_n_page_off += n_offset;
				m_p_page_it += (m_n_page_off - difference_type(m_n_page_size) + 1) / difference_type(m_n_page_size);
				m_n_page_off = m_n_page_off % difference_type(m_n_page_size) +
					((m_n_page_off % difference_type(m_n_page_size))? difference_type(m_n_page_size) : 0);
			}
			return *this;
		}

		/**
		 *	@brief shifts this iterator to point to an element, specified distance away
		 *	@param[in] n_offset is negative offset, in elements
		 *	@return Returns reference to this.
		 */
		inline CConstIterator &operator -=(difference_type n_offset)
		{
			return (*this += -n_offset);
		}

		/**
		 *	@brief dereferences the iterator
		 *	@return Returns a reference to the element this iterator points to.
		 */
		inline reference operator *() const
		{
			_ASSERTE(m_n_page_off >= 0 && size_t(m_n_page_off) < m_n_page_size);
			return (*m_p_page_it)[m_n_page_off];
		}

		/**
		 *	@brief dereferences the iterator
		 *	@return Returns a pointer to the element this iterator points to.
		 */
		inline pointer operator->() const
		{
			return &**this;
		}
	};

	/**
	 *	@brief iterator type
	 */
	class CIterator : public CConstIterator {
	public:
		typedef _TyElem *pointer; /**< @brief pointer to the payload type */
		typedef _TyElem &reference; /**< @brief reference to the payload type */

	public:
		/**
		 *	@copydoc CConstIterator::CConstIterator()
		 */
		inline CIterator(typename _TyPageList::iterator p_page_it,
			_TyPageSize t_page_size, ptrdiff_t n_page_off)
			:CConstIterator(p_page_it, t_page_size, n_page_off)
		{}

		/**
		 *	@brief calculates distance between two iterators
		 *	@param[in] r_t_iter is the second iterator
		 *	@return Returns distance between this and r_t_iter, in elements.
		 */
		inline typename CConstIterator::difference_type operator -(const CConstIterator &r_t_iter) const
		{
			return CConstIterator::operator -(r_t_iter); // don't repeat code
		}

		/**
		 *	@copydoc CConstIterator::operator ==()
		 */
		inline bool operator ==(const CConstIterator &r_t_other) const
		{
			return CConstIterator::operator ==(r_t_other); // don't repeat code
		}

		/**
		 *	@copydoc CConstIterator::operator <()
		 */
		inline bool operator <(const CConstIterator &r_t_other) const
		{
			return CConstIterator::operator <(r_t_other); // don't repeat code
		}

		/**
		 *	@copydoc CConstIterator::operator !=()
		 */
		inline bool operator !=(const CConstIterator &r_t_other) const
		{
			return !(*this == r_t_other);
		}

		/**
		 *	@copydoc CConstIterator::operator >()
		 */
		inline bool operator >(const CConstIterator &r_t_other) const
		{
			return (r_t_other < *this);
		}

		/**
		 *	@copydoc CConstIterator::operator <=()
		 */
		inline bool operator <=(const CConstIterator &r_t_other) const
		{
			return !(*this > r_t_other);
		}

		/**
		 *	@copydoc CConstIterator::operator >=()
		 */
		inline bool operator >=(const CConstIterator &r_t_other) const
		{
			return !(*this < r_t_other);
		}

		/**
		 *	@copydoc CConstIterator::operator ++()
		 */
		inline CIterator &operator ++()
		{
			CConstIterator::operator ++(); // don't repeat code
			return *this;
		}

		/**
		 *	@brief shifts the iterator to the previous element
		 *	@return Returns reference to this iterator.
		 */
		inline CIterator &operator --() // copydoc fails here
		{
			CConstIterator::operator --(); // don't repeat code
			return *this;
		}

		/**
		 *	@copydoc CConstIterator::operator ++(int)
		 */
		CIterator operator ++(int)
		{
			CIterator copy = *this;
			++ *this;
			return copy;
		}

		/**
		 *	@brief shifts the iterator to the previous element
		 *	@return Returns reference to this iterator.
		 *	@note This is the post-increment function.
		 */
		CIterator operator --(int) // copydoc fails here
		{
			CIterator copy = *this;
			-- *this;
			return copy;
		}

		/**
		 *	@copydoc CConstIterator::operator +()
		 */
		CIterator operator +(typename CConstIterator::difference_type n_offset) const
		{
			CIterator copy = *this;
			return (copy += n_offset);
		}

		/**
		 *	@brief calculates an iterator pointing to an element, specified distance away
		 *	@param[in] n_offset is negative offset, in elements
		 *	@return Returns iterator pointing to the element -n_offset elements away from
		 *		the element this iterator points to.
		 */
		CIterator operator -(typename CConstIterator::difference_type n_offset) const
		{
			CIterator copy = *this;
			return (copy -= n_offset);
		}

		/**
		 *	@copydoc CConstIterator::operator +=()
		 */
		CIterator &operator +=(typename CConstIterator::difference_type n_offset)
		{
			CConstIterator::operator +=(n_offset);
			return *this;
		}

		/**
		 *	@copydoc CConstIterator::operator -=()
		 */
		inline CIterator &operator -=(typename CConstIterator::difference_type n_offset)
		{
			return (*this += -n_offset);
		}

		/**
		 *	@copydoc CConstIterator::operator *()
		 */
		inline reference operator *()
		{
			_ASSERTE(CConstIterator::m_n_page_off >= 0 &&
				unsigned(CConstIterator::m_n_page_off) < CConstIterator::m_n_page_size);
			return (*CConstIterator::m_p_page_it)[CConstIterator::m_n_page_off];
		}

		/**
		 *	@copydoc CConstIterator::operator ->()
		 */
		inline pointer operator->()
		{
			return &**this;
		}
	};

protected:
	_TyPageSize m_n_page_size; /**< @brief size of a single page */
	size_t m_n_last_page_used; /**< @brief index of the first unused element in the last page */
	_TyPageList m_page_list; /**< @brief list of pages */

public:
	/**
	 *	@brief default constructor
	 *	@param[in] n_page_size is number of elements in a single page
	 *		(bigger pages are better, but may lead to memory thrashing)
	 */
	CForwardAllocatedPool(_TyPageSize n_page_size = 1024)
		:m_n_page_size(n_page_size), m_n_last_page_used(n_page_size)
	{
		_ASSERTE(n_page_size > 0); // won't work otherwise
	}

	/**
	 *	@brief copy constructor
	 *	@param[in] r_other is the pool to copy from
	 *	@note This function throws std::bad_alloc.
	 */
	CForwardAllocatedPool(const CForwardAllocatedPool &r_other) // throw(std::bad_alloc)
		:m_n_page_size(r_other.m_n_page_size), m_n_last_page_used(r_other.m_n_last_page_used),
		m_page_list(r_other.m_page_list.size())
	{
		typename std::vector<_TyElem*>::const_iterator p_dest_it = m_page_list.begin();
		for(typename std::vector<_TyElem*>::const_iterator p_page_it = r_other.m_page_list.begin(),
		   p_end_it = r_other.m_page_list.end(); p_page_it != p_end_it; ++ p_page_it, ++ p_dest_it) {
			_TyElem *p_page = new(std::nothrow) _TyElem[m_n_page_size];
			if(!p_page) {
				m_page_list.erase(p_dest_it, m_page_list.end()); // don't leave invalid pages
				throw std::bad_alloc(); // rethrow
			}
			*p_dest_it = p_page; // allocated? put it there
			// allocates pages

			try {
				std::copy(*p_page_it, (*p_page_it) + m_n_page_size, p_page); 
				// note that this might throw
			} catch(std::bad_alloc &r_exc) {
				m_page_list.erase(p_dest_it, m_page_list.end()); // don't leave invalid pages
				throw r_exc; // rethrow
			}
			// copy all the elements (don't use memcpy, the elems may have copy operators!)
		}
	}

	/**
	 *	@brief destructor; deletes the pages in use
	 */
	~CForwardAllocatedPool()
	{
		std::for_each(m_page_list.begin(), m_page_list.end(), _DeletePage);
	}

	/**
	 *	@brief copy-operator
	 *	@param[in] r_other is the pool to copy from
	 *	@note This function throws std::bad_alloc.
	 */
	CForwardAllocatedPool &operator =(const CForwardAllocatedPool &r_other) // throw(std::bad_alloc)
	{
		// what should be the behavior here? leave the allocated elems and overwrite tham?
		// what does vector do? probably yes

		if(r_other.m_n_page_size != m_n_page_size)
			Clear(); // choose not to copy anything in this case and allocate from scratch (have to)
		m_n_page_size = r_other.m_n_page_size;
		// tricky behavior

		size_t n_old_size = m_page_list.size();
		size_t n_new_size = r_other.m_page_list.size();
		size_t n_copy_old = std::min(n_old_size, n_new_size);

		typename std::vector<_TyElem*>::const_iterator p_dest_it = m_page_list.begin();
		for(typename std::vector<_TyElem*>::const_iterator p_page_it = r_other.m_page_list.begin(),
		   p_end_it = r_other.m_page_list.begin() + n_copy_old; p_page_it != p_end_it;
		   ++ p_page_it, ++ p_dest_it) {
			std::copy(*p_page_it, (*p_page_it) + m_n_page_size, *p_dest_it); 
			// note that this might throw
		}
		// copy the elements in the first pages

		if(n_new_size < n_old_size) {
			std::for_each(m_page_list.begin() + n_new_size, m_page_list.end(), _DeletePage);
			m_page_list.erase(m_page_list.begin() + n_new_size, m_page_list.end());
			// contract the page list, if required
		} else {
			m_page_list.resize(n_new_size);
			typename std::vector<_TyElem*>::const_iterator p_dest_it =
				m_page_list.begin() + n_old_size; // mind invalidation
			for(typename std::vector<_TyElem*>::const_iterator p_page_it =
			   r_other.m_page_list.begin() +  n_old_size, p_end_it = r_other.m_page_list.end();
			   p_page_it != p_end_it; ++ p_page_it, ++ p_dest_it) {
				_TyElem *p_page = new(std::nothrow) _TyElem[m_n_page_size];
				if(!p_page) {
					m_page_list.erase(p_dest_it, m_page_list.end()); // don't leave invalid pages
					throw std::bad_alloc(); // rethrow
				}
				*p_dest_it = p_page; // allocated? put it there
				// allocates pages

				try {
					std::copy(*p_page_it, (*p_page_it) + m_n_page_size, p_page); 
					// note that this might throw
				} catch(std::bad_alloc &r_exc) {
					m_page_list.erase(p_dest_it, m_page_list.end()); // don't leave invalid pages
					throw r_exc; // rethrow
				}
				// copy all the elements (don't use memcpy, the elems may have copy operators!)
			}
		}

		return *this;
	}

	/**
	 *	@brief removes all elements from the pool and deallocates all memory
	 */
	void Clear()
	{
		std::for_each(m_page_list.begin(), m_page_list.end(), _DeletePage);
		m_page_list.clear();
		m_n_last_page_used = m_n_page_size; // all used
	}

	/**
	 *	@brief swaps contents of two pools
	 *	@param[in,out] r_other is the other pool to swap with
	 */
	void Swap(CForwardAllocatedPool<_TyElem> &r_other)
	{
		std::swap(m_n_page_size, r_other.m_n_page_size);
		std::swap(m_n_last_page_used, r_other.m_n_last_page_used);
		m_page_list.swap(r_other.m_page_list);
	}

	/**
	 *	@brief determines if the pool is empty
	 *	@return Returns true if the pool is empty, otherwise returns false.
	 */
	inline bool b_Empty() const
	{
		_ASSERTE(m_n_last_page_used > 0);
		_ASSERTE((m_page_list.empty() && n_Size() == 0) || (!m_page_list.empty() && n_Size() > 0));
		return m_page_list.empty();
	}

	/**
	 *	@brief gets pool size
	 *	@return Returns number of currently allocated elements.
	 */
	inline size_t n_Size() const
	{
		_ASSERTE(m_n_last_page_used > 0);
		_ASSERTE(!m_page_list.empty() || m_n_last_page_used == m_n_page_size); // if empty, last page should be empty as well ...
		return m_page_list.size() * m_n_page_size + m_n_last_page_used - m_n_page_size; // avoids underflow and branch
	}

	/**
	 *	@brief gets pool page size
	 *	@return Returns pool page size, in elements.
	 */
	inline _TyPageSize n_Page_Size() const
	{
		return m_n_page_size;
	}

	/**
	 *	@brief gets number of pool pages
	 *	@return Returns number of currently allocated pages.
	 */
	inline size_t n_Page_Num() const
	{
		return m_page_list.size();
	}

	/**
	 *	@brief gets pool capacity
	 *	@return Returns number of elements that can be allocated without allocating a new page.
	 */
	inline size_t n_Capacity() const
	{
		_ASSERTE(m_n_last_page_used > 0);
		_ASSERTE(!m_page_list.empty() || m_n_last_page_used == m_n_page_size); // if empty, last page should be empty as well ...
		return m_page_list.size() * m_n_page_size;
	}

	/**
	 *	@brief gets element by index
	 *	@param[in] n_index is a zero-based index selecting an element
	 *	@return Returns reference to the selected element.
	 */
	inline _TyElem &operator [](size_t n_index)
	{
		_ASSERTE(m_n_last_page_used > 0);
		_ASSERTE(n_index < n_Size());
		return *(m_page_list[n_index / m_n_page_size] + n_index % m_n_page_size);
	}

	/**
	 *	@brief gets element by index
	 *	@param[in] n_index is a zero-based index selecting an element
	 *	@return Returns const reference to the selected element.
	 */
	inline const _TyElem &operator [](size_t n_index) const
	{
		_ASSERTE(m_n_last_page_used > 0);
		_ASSERTE(n_index < n_Size());
		return *(m_page_list[n_index / m_n_page_size] + n_index % m_n_page_size);
	}

	/**
	 *	@brief gets the first element in the pool
	 *	@return Returns reference to the first element.
	 */
	inline _TyElem &r_Front()
	{
		_ASSERTE(!b_Empty());
		return *m_page_list.front();
	}

	/**
	 *	@brief gets the first element in the pool
	 *	@return Returns const reference to the first element.
	 */
	inline const _TyElem &r_Front() const
	{
		_ASSERTE(!b_Empty());
		return *m_page_list.front();
	}

	/**
	 *	@brief gets the last element in the pool
	 *	@return Returns reference to the last element.
	 */
	inline _TyElem &r_Back()
	{
		_ASSERTE(!b_Empty());
		return m_page_list.back()[m_n_last_page_used - 1];
	}

	/**
	 *	@brief gets the last element in the pool
	 *	@return Returns const reference to the last element.
	 */
	inline const _TyElem &r_Back() const
	{
		_ASSERTE(!b_Empty());
		return m_page_list.back()[m_n_last_page_used - 1];
	}

	/**
	 *	@brief gets constant iterator, pointing to the first element in the pool
	 *	@return Returns constant iterator, pointing to the first element in the pool.
	 */
	inline CConstIterator p_Begin_it() const
	{
		return CConstIterator(const_cast<_TyPageList&>(m_page_list).begin(), m_n_page_size, 0);
	}

	/**
	 *	@brief gets constant iterator, pointing to one past the last element in the pool
	 *	@return Returns constant iterator, pointing to one past the last element in the pool.
	 *	@note This iterator can not be dereferenced.
	 */
	inline CConstIterator p_End_it() const
	{
		return (m_n_last_page_used == m_n_page_size)?
			CConstIterator(const_cast<_TyPageList&>(m_page_list).end(), m_n_page_size, 0) :
			CConstIterator(const_cast<_TyPageList&>(m_page_list).end() - 1, m_n_page_size, m_n_last_page_used);
	}

	/**
	 *	@brief gets iterator, pointing to the first element in the pool
	 *	@return Returns iterator, pointing to the first element in the pool.
	 */
	inline CIterator p_Begin_it()
	{
		return CIterator(m_page_list.begin(), m_n_page_size, 0);
	}

	/**
	 *	@brief gets iterator, pointing to one past the last element in the pool
	 *	@return Returns iterator, pointing to one past the last element in the pool.
	 *	@note This iterator can not be dereferenced.
	 */
	inline CIterator p_End_it()
	{
		return (m_n_last_page_used == m_n_page_size)?
			CIterator(m_page_list.end(), m_n_page_size, 0) :
			CIterator(m_page_list.end() - 1, m_n_page_size, m_n_last_page_used);
	}

	/**
	 *	@brief deletes a range of elements between a given iterator and the end of the storage
	 *	@param[in] p_begin_it is an iterator that points to the first element to be deleted
	 */
	void Erase_Back(CConstIterator p_begin_it)
	{
		_ASSERTE(p_begin_it >= p_Begin_it() && p_begin_it <= p_End_it()); // make sure it's in the valid range
		size_t n_new_size = p_begin_it - p_Begin_it();
		_ASSERTE(n_new_size <= n_Size());
		//Resize(n_new_size); // could do that

		typename _TyPageList::iterator p_page_iter = p_begin_it.p_Page_Iter();

		//size_t n_page_num = p_page_iter - m_page_list.begin();
		// calculate how many pages do we need in total, the last one might not be fully used

		size_t n_last_page_needed = p_begin_it.n_Page_Offset();
		// calculate how many vertices should be in the last page

		if(!n_last_page_needed)
			n_last_page_needed = m_n_page_size;
		else
			++ p_page_iter;

		std::for_each(p_page_iter, m_page_list.end(), _DeletePage);
		m_page_list.erase(p_page_iter, m_page_list.end());
		// contract the page list

		m_n_last_page_used = n_last_page_needed;
		_ASSERTE(m_n_last_page_used > 0);

		_ASSERTE(n_Size() == n_new_size);
	}

	/**
	 *	@brief inserts a range of elements at the end of the pool
	 *
	 *	@tparam CInputIterator is input iterator type
	 *	@param[in] p_begin_it is an iterator that points to the first element to be inserted
	 *	@param[in] p_end_it is an iterator that points one past the last element to be inserted
	 *
	 *	@note This function throws std::bad_alloc.
	 *	@note The iterators must not point to this pool.
	 */
	template <class CInputIterator>
	inline void Insert_Back(CInputIterator p_begin_it, CInputIterator p_end_it) // throw(std::bad_alloc)
	{
		size_t n_add_elem_num = p_end_it - p_begin_it;
		size_t n_old_size = n_Size();
		Reserve(n_old_size + n_add_elem_num);
		std::copy(p_begin_it, p_end_it, p_Begin_it() + n_old_size);
	}

	/**
	 *	@brief inserts a number of copies of a value at the end of the pool
	 *
	 *	@param[in] n_add_elem_num is number of copies to be inserted
	 *	@param[in] t_value is the value of the element(s) to be inserted
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	inline void Insert_Back(size_t n_add_elem_num, _TyElem t_value) // throw(std::bad_alloc)
	{
		size_t n_old_size = n_Size();
		Reserve(n_old_size + n_add_elem_num);
		std::fill(p_Begin_it() + n_old_size, p_End_it(), t_value);
	}

	/**
	 *	@brief gets index of an element inside this storage
	 *	@param[in] p_elem is an element to calculate index of
	 *	@return Returns index of the given element, or -1 in case the element is not in the pool.
	 */
	size_t n_IndexOf(const _TyElem *p_elem) const
	{
		typename std::vector<_TyElem*>::const_iterator p_page_it =
			std::find_if(m_page_list.begin(), m_page_list.end(),
			CFindPage(p_elem, m_n_page_size));
		if(p_page_it == m_page_list.end())
			return size_t(-1); // not found

		_ASSERTE(p_elem >= *p_page_it);
		size_t n_page_index = p_elem - *p_page_it;
		_ASSERTE(n_page_index >= 0 && n_page_index < m_n_page_size);
		// calculate index in the page

		return n_page_index + (p_page_it - m_page_list.begin()) * m_n_page_size;
		// global index is page index + number of vertices in preceding pages
	}

	/**
	 *	@brief resizes the pool
	 *	@param[in] n_size is the required size of the pool
	 *	@note This function throws std::bad_alloc.
	 */
	void Resize(size_t n_size) // throw(std::bad_alloc)
	{
		size_t n_page_num = (n_size + (m_n_page_size - 1)) / m_n_page_size;
		// calculate how many pages do we need in total, the last one might not be fully used

		size_t n_last_page_needed = n_size - (n_page_num - 1) * m_n_page_size;
		// calculate how many vertices should be in the last page

		size_t n_cur_page_num;
		if((n_cur_page_num = m_page_list.size()) < n_page_num) {
			m_page_list.resize(n_page_num);
			for(size_t i = n_cur_page_num; i < n_page_num; ++ i) {
				_TyElem *p_page;
				if(!(p_page = new(std::nothrow) _TyElem[m_n_page_size])) {
					m_page_list.resize(i); // make sure there are no invalid pages in the list
					throw std::bad_alloc(); // rethrow
				}
				// alloc new page

				m_page_list[i] = p_page;
				// put the new page into the list
			}
		} else {
			std::for_each(m_page_list.begin() + n_page_num, m_page_list.end(), _DeletePage);
			m_page_list.erase(m_page_list.begin() + n_page_num, m_page_list.end());
		}
		// contract or expand the page list

		m_n_last_page_used = n_last_page_needed;
		_ASSERTE(m_n_last_page_used > 0);
	}

	/**
	 *	@brief resizes the pool to the maximum of the current size and the required minimal size
	 *	@param[in] n_min_size is the minimal required size of the pool
	 *	@note This function throws std::bad_alloc.
	 */
	void Reserve(size_t n_min_size) // throw(std::bad_alloc)
	{
		size_t n_cur_size = n_Size();
		if(n_cur_size >= n_min_size)
			return;
		// calculate current size and see if it suffices

		size_t n_page_num = (n_min_size + (m_n_page_size - 1)) / m_n_page_size;
		// calculate how many pages do we need in total, the last one might not be fully used

		size_t n_last_page_needed = n_min_size - (n_page_num - 1) * m_n_page_size;
		// calculate how many vertices should be in the last page

		size_t n_cur_page_num = m_page_list.size();
		m_page_list.resize(n_page_num);
		// make sure theres space for new pages in the pool

		for(size_t i = n_cur_page_num; i < n_page_num; ++ i) {
			_TyElem *p_page;
			if(!(p_page = new(std::nothrow) _TyElem[m_n_page_size])) {
				m_page_list.resize(i); // make sure there are no invalid pages in the list
				throw std::bad_alloc(); // rethrow
			}
			// alloc new page

			m_page_list[i] = p_page;
			// put the new page into the list
		}
		// alloc all the pages

		m_n_last_page_used = n_last_page_needed;
		_ASSERTE(m_n_last_page_used > 0);
		// calculate how many vertices will be used in the last page
	}

	/**
	 *	@brief allocates a single element at the end of the storage
	 *	@return Returns pointer to the new element.
	 *	@note This function throws std::bad_alloc.
	 */
	_TyElem *p_GetSingle() // throw(std::bad_alloc)
	{
		if(m_n_last_page_used != m_n_page_size) {
			_TyElem *p_result = m_page_list.back() + m_n_last_page_used;
			++ m_n_last_page_used;
			return p_result;
		}
		// just return next elem

		_TyElem *p_page = 0;
		try {
			p_page = new _TyElem[m_n_page_size];
			// alloc new page (do throw)

			m_page_list.push_back(p_page);
			// put the new page into the list

			m_n_last_page_used = 1;
			// we use the first elem right away
		} catch(std::bad_alloc &r_exc) {
			if(p_page)
				delete[] p_page;
			throw r_exc;
		}
		// need to alloc a new page

		return p_page;
	}

	/**
	 *	@brief allocates a block of elements at the end of the storage
	 *	@param[in] n_size is number of elements to allocate (must not exceed page size)
	 *	@return Returns pointer to the first element of the block.
	 *	@note This function throws std::bad_alloc.
	 *	@note This function may leave unused space at the end of the last page
	 *		if the block wouldn't fit.
	 */
	_TyElem *p_GetRange(size_t n_size) // throw(std::bad_alloc)
	{
		if(n_size > m_n_page_size) // allocating a bigger page would break n_Size()
			throw std::bad_alloc(); // won't fit
		if(m_n_last_page_used <= m_n_page_size - n_size) {
			_TyElem *p_result = m_page_list.back() + m_n_last_page_used;
			m_n_last_page_used += n_size;
			return p_result;
		}
		// just return next elem

		_TyElem *p_page = 0;
		try {
			p_page = new _TyElem[m_n_page_size]; // allocating a bigger page would break n_Size()
			// alloc new page (do throw)

			m_page_list.push_back(p_page);
			// put the new page into the list

			m_n_last_page_used = n_size;
			// we use the first n_size elements right away
		} catch(std::bad_alloc &r_exc) {
			if(p_page)
				delete[] p_page;
			throw r_exc;
		}
		// need to alloc a new page

		return p_page;
	}

	/**
	 *	@brief optimized for-each function
	 *
	 *	@tparam CFunctor is function object type
	 *	@param[in] n_begin is zero-based index of the first element to be processed
	 *	@param[in] n_end is zero-based index of one past the last element to be processed (or -1 for the end of the pool)
	 *	@param[in] functor is function object instance
	 *
	 *	@return Returns the value of the function object, after passing the vertices to it.
	 *
	 *	@note This should be faster than std::for_each() on the pool iterators.
	 */
	template <class CFunctor>
	CFunctor ForEach(size_t n_begin, size_t n_end, CFunctor functor)
	{
		_ASSERTE(((n_end == size_t(-1) && n_begin == n_Size()) ||
			(n_end != size_t(-1) && n_begin == n_end)) || n_begin < n_Size()); // either an empty range, or begin must be a valid index
		_ASSERTE(n_end == size_t(-1) || (n_end <= n_Size() && n_end >= n_begin)); // begin must be before or equal to end
		size_t n_first_page = n_begin / m_n_page_size;
		size_t n_first_index = n_begin % m_n_page_size;
		size_t n_last_page = (n_end == size_t(-1))? m_page_list.size() : n_end / m_n_page_size;
		size_t n_last_index = (n_end == size_t(-1))? 0 : n_end % m_n_page_size;

		if(n_first_page == n_last_page) {
			if(n_first_index == n_last_index)
				return functor; // otherwise m_page_list[n_first_page]; can dereference empty list
			_TyElem *p_page = m_page_list[n_first_page];
			return std::for_each(p_page + n_first_index, p_page + n_last_index, functor);
			// cycle trough all vertices in the only page (n_first_index to n_last_index)
		} else {
			_ASSERTE(n_begin < n_end || n_end == size_t(-1));
			// the following branch is correct for non empty intervals only

			if(n_first_index > 0) {
				_TyElem *p_page = m_page_list[n_first_page];
				functor = std::for_each(p_page + n_first_index, p_page + m_n_page_size, functor);
				++ n_first_page;
			}
			// cycle trough all vertices in the first page (n_first_index to page end)

			for(typename _TyPageList::iterator p_page_it = m_page_list.begin() + n_first_page,
			   p_end_it = m_page_list.begin() + n_last_page; p_page_it != p_end_it; ++ p_page_it) {
				_TyElem *p_page = *p_page_it;
				functor = std::for_each(p_page, p_page + m_n_page_size, functor);
			}
			// cycle trough all vertices in the other pages (0 to page end)

			if(n_last_index > 0) {
				_TyElem *p_page = m_page_list[n_last_page];
				return std::for_each(p_page, p_page + n_last_index, functor);
			} else
				return functor;
			// cycle trough all vertices in the last page (0 to n_last_index)
		}
	}

	/**
	 *	@copydoc ForEach()
	 */
	template <class CFunctor>
	CFunctor ForEach(size_t n_begin, size_t n_end, CFunctor functor) const
	{
		_ASSERTE(((n_end == size_t(-1) && n_begin == n_Size()) ||
			(n_end != size_t(-1) && n_begin == n_end)) || n_begin < n_Size()); // either an empty range, or begin must be a valid index
		_ASSERTE(n_end == size_t(-1) || (n_end <= n_Size() && n_end >= n_begin)); // begin must be before or equal to end
		size_t n_first_page = n_begin / m_n_page_size;
		size_t n_first_index = n_begin % m_n_page_size;
		size_t n_last_page = (n_end == size_t(-1))? m_page_list.size() : n_end / m_n_page_size;
		size_t n_last_index = (n_end == size_t(-1))? 0 : n_end % m_n_page_size;

		if(n_first_page == n_last_page) {
			if(n_first_index == n_last_index)
				return functor; // otherwise m_page_list[n_first_page]; can dereference empty list
			const _TyElem *p_page = m_page_list[n_first_page];
			return std::for_each(p_page + n_first_index, p_page + n_last_index, functor);
			// cycle trough all vertices in the only page (n_first_index to n_last_index)
		} else {
			_ASSERTE(n_begin < n_end || n_end == size_t(-1));
			// the following branch is correct for non empty intervals only

			if(n_first_index > 0) {
				const _TyElem *p_page = m_page_list[n_first_page];
				functor = std::for_each(p_page + n_first_index, p_page + m_n_page_size, functor);
				++ n_first_page;
			}
			// cycle trough all vertices in the first page (n_first_index to page end)

			for(typename _TyPageList::const_iterator p_page_it = m_page_list.begin() + n_first_page,
			   p_end_it = m_page_list.begin() + n_last_page; p_page_it != p_end_it; ++ p_page_it) {
				const _TyElem *p_page = *p_page_it;
				functor = std::for_each(p_page, p_page + m_n_page_size, functor);
			}
			// cycle trough all vertices in the other pages (0 to page end)

			if(n_last_index > 0) {
				const _TyElem *p_page = m_page_list[n_last_page];
				return std::for_each(p_page, p_page + n_last_index, functor);
			} else
				return functor;
			// cycle trough all vertices in the last page (0 to n_last_index)
		}
	}

protected:
	static inline void _DeletePage(_TyElem *p_vertex_page)
	{
		_ASSERTE(p_vertex_page);
		delete[] p_vertex_page;
	}

	class CFindPage {
	protected:
		const _TyElem *m_p_begin, *m_p_end;

	public:
		CFindPage(const _TyElem *p_elem, size_t n_page_size)
			:m_p_begin(p_elem), m_p_end(p_elem - n_page_size) // rather cunning, uses inverse test
		{}

		inline bool operator ()(const _TyElem *p_page) const
		{
			return m_p_begin >= p_page && m_p_end < p_page;
		}
	};
};

namespace std {

/**
 *	@brief swaps values of two bit references (not the references themselves)
 *
 *	Overrides std::swap to swap two forward allocated pools using the swap() method.
 *
 *	@param[in] r_a is the first pool reference
 *	@param[in] r_b is the second pool reference
 */
template <class T>
inline void swap(CForwardAllocatedPool<T> &r_a, CForwardAllocatedPool<T> &r_b)
{
	r_a.Swap(r_b);
}

} // ~std

/*
 *								=== ~CForwardAllocatedPool ===
 */

#endif // !__LAME_FORWARD_ALLOCATED_POOL_INCLUDED
