/*
	Trig Wars.
	Copyright (c) 2008, Darragh Coy.
	All rights reserved.
	Original work(s), source code & author(s) details available at: http://www.darraghcoy.com

	Redistribution and use in source and binary forms, with or without modification, are permitted 
	provided that the following conditions are met:

		* 	Redistributions of source code must retain the above copyright notice, this list of 
			conditions and the following disclaimer.
		* 	Redistributions in binary form must reproduce the above copyright notice, this list of 
			conditions and the following disclaimer in the documentation.
		* 	Neither the name of the author nor the names of contributors may be used to endorse or 
			promote products derived from this software without specific prior written permission.
		* 	The use of any third party libraries, modules or data files provided with the source 
			form of the program must follow and respect the individual licensing terms of these 
			components. You do not have permission to modify or circumvent the licensing terms for 
			provided third party components unless the third party licenses specifically allow this. 
			If you do not agree to the terms of provided third party components then you do not have 
			permission to use them in your derived work(s).
		* 	The terms of this license do not apply to separate (but related) distributions if supplied 
			by the author(s), only to the contents of this source distribution, derived works, and the 
			binaries produced by either modified or unmodified versions of the source code. The terms 
			of this license do not also apply to any third party libraries or components provided with 
			the source distribution. Such third party elements are licensed under their own separate 
			agreements.

	THIS SOFTWARE IS PROVIDED BY DARRAGH COY ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, 
	BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
	ARE DISCLAIMED. IN NO EVENT SHALL DARRAGH COY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
	EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
	OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 
	OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 
	IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef POOL_H
#define POOL_H

//=====================================================================================================================
//=====================================================================================================================

#include <vector>
#include "Base\Assertion.h"
#include "Base\Poolable.h"
#include "Base\Stack.h"

//=====================================================================================================================
//=====================================================================================================================

namespace Game
{
	//=================================================================================================================
	//=================================================================================================================
	
	class Poolable;

	//=================================================================================================================
	/// @brief		Base class for a pooling system. This class takes objects of a exclusive given type and pools
	///				them.. allowing them to be reused.
	///	@remarks	MEMORY OWNERSHIP: To enable the pool to work with ReferenceObject type objects, it does
	///				not take repsonsibility for newing / deleting any of the objects it has been passed.
	///				It is up to the caller (or otherwise) to clean up all resources that have been given 
	///				to the pool.
	///
	///				It is also up to the owner to ensure that Pool objects remain valid whilst the Pool is in use.
	//=================================================================================================================

	template<typename ConcreteType = Poolable> class Pool : public ReferencedObject
	{
		public:
		
			//=========================================================================================================
			// Classes
			//=========================================================================================================
			
				//=====================================================================================================
				/// @brief		This simple class is used to iterate through elements in the pool, either in the 
				///				free list or in the used list.
				/// @remarks	For the sake of speed, the enumerator does not add/remove references to objects pointed
				///				to. Therefore the code using this enumerator should not delete the pool while it is 
				///				being iterated through. Doing so may cause the enumerator to point to an invalidated
				///				element.
				//=====================================================================================================
				
				class Enumerator
				{
					public:
				
						//=============================================================================================
						// Functions
						//=============================================================================================
						
							//=========================================================================================
							/// @brief		Constructor. Makes the enumerator point to the given element.
							/// @param		elem - element to point to initially
							//=========================================================================================
							
							inline Enumerator( ConcreteType * elem ) : m_element(elem){}
							
							//=========================================================================================
							/// @brief		Copy constructor. Makes the enumerator from another enumerator.
							/// @param		other - other poolable object to create from
							//=========================================================================================
							
							inline Enumerator( const Enumerator & other ) : m_element(other.m_element){}
							
							//=========================================================================================
							/// @brief		Assignment operator. Assigns the given enumerator to this one.
							/// @param		other - other poolable object to create from
							/// @returns	This enumerator
							//=========================================================================================
							
							inline Enumerator & operator = ( const Enumerator & other )
							{
								this->m_element = other.m_element; return * this;
							}
							
							//=========================================================================================
							/// @brief		Dererence operator. Gives the object pointed by the enumerator.
							/// @pre		This enumerator must not point to an invalid element.
							/// @returns	Object pointed to by the enumerator
							//=========================================================================================
							
							inline ConcreteType * operator * ()
							{
								// Debug check:
								
								ENSURE( m_element != 0 , "This enumerator must not point to an invalid element." );
								
								// Return the object:
								
								return m_element;
							}							
							
							//=========================================================================================
							/// @brief		Pre increment operator. Moves onto the next element.
							/// @pre		This enumerator must not point to an invalid element.
							/// @returns	This element
							//=========================================================================================
							
							inline Enumerator & operator ++ ( int )
							{
								// Debug check:
								
								ENSURE( m_element != 0 , "This enumerator must not point to an invalid element." );
								
								// Move on:
								
								m_element = (ConcreteType*) m_element->m_poolable_next;
								
								// Return this object
								
								return * this;
							}					
							
							//=========================================================================================
							/// @brief		Post increment operator. Moves onto the next element.
							/// @pre		This enumerator must not point to an invalid element.
							/// @returns	Previous element pointed to 
							//=========================================================================================
							
							inline Enumerator operator ++ ()
							{
								// Debug check:
								
								ENSURE( m_element != 0 , "This enumerator must not point to an invalid element." );
								
								// Store previous element:
								
								ConcreteType * previous = m_element;
								
								// Move on:
								
								m_element = (ConcreteType*) m_element->m_poolable_next;
								
								// Return previous element
								
								return Enumerator(previous);
							}	
							
							//=========================================================================================
							/// @brief		Pre decrement operator. Moves onto the previous element.
							/// @pre		This enumerator must not point to an invalid element.
							/// @returns	This element
							//=========================================================================================
							
							inline Enumerator & operator -- ( int )
							{
								// Debug check:
								
								ENSURE( m_element != 0 , "This enumerator must not point to an invalid element." );
								
								// Move on:
								
								m_element = (ConcreteType*) m_element->m_poolable_prev;
								
								// Return this object
								
								return * this;
							}
							
							//=========================================================================================
							/// @brief		Post decrement operator. Moves onto the previous element.
							/// @pre		This enumerator must not point to an invalid element. 
							/// @returns	Previous value of the enumerator
							//=========================================================================================
							
							inline Enumerator operator -- ()
							{
								// Debug check:
								
								ENSURE( m_element != 0 , "This enumerator must not point to an invalid element." );
								
								// Store previous element:
								
								ConcreteType * previous = m_element;
								
								// Move on:
								
								m_element = m_element->m_poolable_prev;
								
								// Return previous element
								
								return Enumerator(previous);								
							}																
							
							//=========================================================================================
							/// @brief		Compares enumerators for equality.
							/// @param		other - other poolable object to compare to
							/// @returns	True if the iterators point to the same object
							//=========================================================================================
							
							inline bool operator == ( const Enumerator & other ) const 
							{
								return other.m_element == this->m_element;
							}
							
							//=========================================================================================
							/// @brief		Compares enumerators for inequality.
							/// @param		other - other poolable object to compare to
							/// @returns	True if the iterators don't point to the same object
							//=========================================================================================
							
							inline bool operator != ( const Enumerator & other ) const 
							{
								return other.m_element != this->m_element;
							}							
					
					private:
					
						//=============================================================================================
						// Variables
						//=============================================================================================
						
							/// Pointer to the current object in the list
							
							ConcreteType * m_element;
							
				};		// end of class Enumerator
			
			//=========================================================================================================
			// Functions
			//=========================================================================================================
					    
				//=====================================================================================================
				/// @brief		Creates the pool and uses the given objects as the stock for the pooling system. 
				/// @param		stock_objects - These are the objects that are to be pooled for later use and re-use.
				/// @pre		There must be at least one object in the given pool of stock objects
				/// @pre		There must be no null objects in the given pool of stock objects
				/// @pre		No objects can alreadybe contained in another pool
				/// @remarks	The pool is designed to work with any type that supports the Poolable interface, so 
				///				it does not take responsibility for freeing pooled objects when it is destroyed. 
				///				Hence it can work with ReferencedObject types or more basic types. 
				///				However this means that the caller must ensure that these objects are properly cleaned
				///				up and that they are not deleted during the lifetime of the pool.
				//=====================================================================================================
			    
				Pool( std::vector<ConcreteType*> & stock_objects )
				{
					// Make sure there is at least one object:
					
					ENSURE( stock_objects.size() > 0 , "There must be at least one object in the given pool of stock objects" );
					
					// Make sure there are no null objects: 
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < stock_objects.size() ; ++i )
						{
							ENSURE( stock_objects[i] != 0 , "There must be no null objects in the given pool of stock objects" );
						}
					
					#endif
					
					// Make sure no objects are already in a pool:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < stock_objects.size() ; ++i )
						{
							ENSURE( stock_objects[i]->m_poolable_parent == 0 , "No objects can already be contained in another pool" );
							ENSURE( stock_objects[i]->m_poolable_next	== 0 , "No objects can already be contained in another pool" );
							ENSURE( stock_objects[i]->m_poolable_prev	== 0 , "No objects can already be contained in another pool" );
						}
					
					#endif
					
					// In debug fill out all the debug fields on each object:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < stock_objects.size() ; ++i )
						{
							stock_objects[i]->m_poolable_parent			= (Pool<Poolable>*)(this);
							stock_objects[i]->m_poolable_in_free_list	= true;
						}
					
					#endif		
					
					// Save the size of the pool:
					
					m_pool_size = stock_objects.size();									
									
					// Assign the free head:
			        
					m_free_head = stock_objects[0]; 
					
					m_free_head->m_poolable_prev = 0;
			        
					// Calculate the end of the array:
			        
					int end = stock_objects.size() - 1;
			        
					// Assign the free tail:
			        
					m_free_tail = stock_objects[end]; 
					
					m_free_tail->m_poolable_next = 0;
			        
					// Next pointer for first element:
			        
					if ( stock_objects.size() > 1 )
					{        
						m_free_head->m_poolable_next = stock_objects[1];
					}				
			        
					// Set the previous and next pointers for all objects in the array:
			        
					for ( int i = 1 ; i < end ; ++i )
					{   
						// Get:
			            
						ConcreteType * p = stock_objects[i];
			            
						// Assign references:
			            
						p->m_poolable_prev = stock_objects[i-1];
						p->m_poolable_next = stock_objects[i+1];
					}
			        
					// Previous pointer for last element:
			        
					if ( stock_objects.size() > 1 )
					{        
						m_free_tail->m_poolable_prev = stock_objects[end-1];
					}
					
					// No objects in use:
					
					m_used_head		= 0;
					m_used_tail		= 0;
					m_used_count	= 0;					
				}
				
				//=====================================================================================================
				/// @brief		Creates the pool and uses the given objects as the stock for the pooling system. 
				/// @param		stock_objects - These are the objects that are to be pooled for later use and re-use.
				/// @param		count - the number of objects there are in the given stack
				/// @pre		Given array of stock objects cannot be null
				/// @pre		There must be at least one object in the given pool of stock objects
				/// @pre		There must be no null objects in the given pool of stock objects
				/// @pre		No objects can already be contained in another pool
				/// @remarks	The pool is designed to work with any type that supports the Poolable interface, so 
				///				it does not take responsibility for freeing pooled objects when it is destroyed. 
				///				Hence it can work with ReferencedObject types or more basic types. 
				///				However this means that the caller must ensure that these objects are properly cleaned
				///				up and that they are not deleted during the lifetime of the pool.				
				//=====================================================================================================
			    
				Pool( ConcreteType * stock_objects , unsigned count )
				{
					// Make sure this is ok:
					
					ENSURE( stock_objects , "Given array of stock objects cannot be null" );
				
					// Make sure there is at least one object:
					
					ENSURE( count > 0 , "There must be at least one object in the given pool of stock objects" );					
					
					// Make sure no objects are already in a pool:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < count ; ++i )
						{
							ENSURE( stock_objects[i].m_poolable_parent	== 0 , "No objects can already be contained in another pool" );
							ENSURE( stock_objects[i].m_poolable_next	== 0 , "No objects can already be contained in another pool" );
							ENSURE( stock_objects[i].m_poolable_prev	== 0 , "No objects can already be contained in another pool" );
						}
					
					#endif
					
					// In debug fill out all the debug fields on each object:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < count ; ++i )
						{
							// Fill in this object's fields:
						
							stock_objects[i].m_poolable_parent			= (Pool<Poolable>*)(this);
							stock_objects[i].m_poolable_in_free_list	= true;
						}
					
					#endif		
					
					// Save the size of the pool:
					
					m_pool_size = count;									
									
					// Assign the free head:
			        
					m_free_head = &stock_objects[0]; m_free_head->m_poolable_prev = 0;
			        
					// Calculate the end of the array:
			        
					int end = count - 1;
			        
					// Assign the free tail:
			        
					m_free_tail = &stock_objects[end]; m_free_tail->m_poolable_next = 0;
			        
					// Next pointer for first element:
			        
					if ( count > 1 )
					{        
						m_free_head->m_poolable_next = &stock_objects[1];
					}				
			        
					// Set the previous and next pointers for all objects in the array:
			        
					for ( int i = 1 ; i < end ; ++i )
					{   
						// Get:
			            
						ConcreteType * p = &stock_objects[i];
			            
						// Assign references:
			            
						p->m_poolable_prev = &stock_objects[i-1];
						p->m_poolable_next = &stock_objects[i+1];
					}
			        
					// Previous pointer for last element:
			        
					if ( count > 1 )
					{        
						m_free_tail->m_poolable_prev = &stock_objects[end-1];
					}
					
					// No objects in use:
					
					m_used_head		= 0;
					m_used_tail		= 0;
					m_used_count	= 0;					
				}
				
				//=====================================================================================================
				/// @brief		Creates the pool and uses the given objects pointed to by entries in the stack as
				///				the stock objects for the pooling system.
				/// @param		stack - This holds pointers to each object (ConcreteType*) that will be used by the 
				///				pooling system. The function expects the specified number of objects to be present on 
				///				the stack and will pop each pointer off the stack until it is finished.
				/// @param		count - number of objects there are on the stack for the pool to use
				/// @pre		There must be at least one object in the given pool of stock objects
				/// @pre		There must be no null objects in the given pool of stock objects
				/// @pre		No objects can already be contained in another pool
				/// @remarks	The pool is designed to work with any type that supports the Poolable interface, so 
				///				it does not take responsibility for freeing pooled objects when it is destroyed. 
				///				Hence it can work with ReferencedObject types or more basic types. 
				///				However this means that the caller must ensure that these objects are properly cleaned
				///				up and that they are not deleted during the lifetime of the pool.				
				//=====================================================================================================
			    
				Pool( Stack & stack , unsigned count )
				{
					// Make sure there is at least one object:
					
					ENSURE( count > 0 , "There must be at least one object in the given pool of stock objects" );					
					
					// Make sure no objects are already in a pool:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < count ; ++i )
						{
							// Get the current item on the stack:
							
							ConcreteType * obj = stack.Pop<ConcreteType*>();
						
							ENSURE( obj->m_poolable_parent	== 0 , "No objects can already be contained in another pool" );
							ENSURE( obj->m_poolable_next	== 0 , "No objects can already be contained in another pool" );
							ENSURE( obj->m_poolable_prev	== 0 , "No objects can already be contained in another pool" );
						}
						
						// Move the stack pointer back to where it was
						
						stack.Offset( sizeof(void*) * count );
					
					#endif
					
					// In debug fill out all the debug fields on each object:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < count ; ++i )
						{
							// Get the current item on the stack:
							
							ConcreteType * obj = stack.Pop<ConcreteType*>();
							
							// Fill in its fields					
						
							obj->m_poolable_parent			= (Pool<Poolable>*)(this);
							obj->m_poolable_in_free_list	= true;
						}
						
						// Move the stack pointer back to where it was
						
						stack.Offset( sizeof(void*) * count );						
					
					#endif		
					
					// Save the size of the pool:
					
					m_pool_size = count;													
									
					// Assign the free head:
			        
					m_free_head = stack.Pop<ConcreteType*>(); m_free_head->m_poolable_prev = 0;
					
					// Make the free head the free tail:
					
					m_free_tail = m_free_head; m_free_tail->m_poolable_next = 0;
					
					// Do all the items in the middle:
					
					if ( count > 1 )
					{
						// Add every single item into the stack
						
						for ( unsigned i = count - 1 ; i != 0 ; --i )
						{
							// Get this item:
							
							ConcreteType * obj = stack.Pop<ConcreteType*>();
							
							// Link with the current tail:
							
							m_free_tail->m_poolable_next = obj; obj->m_poolable_prev = m_free_tail;
							
							// Make it the new tail:
							
							m_free_tail = obj; obj->m_poolable_next = 0;
						}		
					}											
			        
					// No objects in use:
					
					m_used_head		= 0;
					m_used_tail		= 0;
					m_used_count	= 0;				
				}							
				
				//=====================================================================================================
				/// @brief		Grows the pool. Adds the given objects to the list of objects in the pool.
				/// @param		allocated - an array of allocated objects
				/// @param		count - number of allocated allocated objects in the array
				/// @pre		The objects given must not be in a pool already
				/// @pre		The number of objects given must be greater than zero
				//=====================================================================================================
				
				void Grow( ConcreteType * allocated , unsigned count )
				{
					// Make sure ok:
					
					ENSURE( count > 0 , "The number of objects given must be greater than zero" );				
				
					// Make sure ok:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < count ; ++i )
						{
							ENSURE( allocated[i].m_poolable_parent	== 0	, "The objects given must not be in a pool already" );
							ENSURE( allocated[i].m_poolable_next	== 0	, "The objects given must not be in a pool already" );
							ENSURE( allocated[i].m_poolable_prev	== 0	, "The objects given must not be in a pool already" );
						}
					
					#endif				
					
					// Get the head and tail of the allocated list:
					
					ConcreteType * alloced_head = allocated;
					ConcreteType * alloced_tail = allocated + count - 1;
					
					// Right: see if there are any objects in the free list
					
					if ( m_free_tail )
					{
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						// There are objects in the free list: Add in the 1st new object.. 
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						
						m_free_tail->m_poolable_next	= allocated;
						alloced_head->m_poolable_prev	= m_free_tail;
						
						#ifdef DEBUG
						
							// These are only there in debug
						
							alloced_head->m_poolable_parent			= (Pool<Poolable>*)(this);
							alloced_head->m_poolable_in_free_list	= true;
							
						#endif
						
						if ( count > 1 )
						{
							alloced_head->m_poolable_next = alloced_head + 1;
						}
						
						// Add in the last free object:
						
						alloced_tail->m_poolable_next = 0;
						
						#ifdef DEBUG
						
							// These are only there in debug
						
							alloced_tail->m_poolable_parent			= (Pool<Poolable>*)(this);
							alloced_tail->m_poolable_in_free_list	= true;
							
						#endif
						
						if ( count > 1 )
						{
							alloced_tail->m_poolable_prev = alloced_tail - 1;
						}
						
						// Add in all the objects in between:
						
						for ( unsigned i = 1 ; i < count - 1 ; ++i )
						{
							// Get this object:
							
							ConcreteType * alloced = allocated + i;
							
							// Set its fields:
							
							alloced->m_poolable_next = alloced + 1;
							alloced->m_poolable_prev = alloced - 1;
							
							// Debug fields:
							
							#ifdef DEBUG
							
								alloced->m_poolable_parent			= (Pool<Poolable>*)(this);
								alloced->m_poolable_in_free_list	= true;						
							
							#endif
						}
						
						// Set the new tail of the free list
						
						m_free_tail = alloced_tail;
					}
					else
					{
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						// There are no obejcts in the free list: Add in the 1st new object.. 
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
										
						alloced_head->m_poolable_prev = 0;
						
						#ifdef DEBUG
						
							// These are only there in debug
						
							alloced_head->m_poolable_parent			= (Pool<Poolable>*)(this);
							alloced_head->m_poolable_in_free_list	= true;
							
						#endif
						
						if ( count > 1 )
						{
							alloced_head->m_poolable_next = alloced_head + 1;
						}
						
						// Add in the last free object:
						
						alloced_tail->m_poolable_next = 0;
						
						#ifdef DEBUG
						
							// These are only there in debug
						
							alloced_tail->m_poolable_parent			= (Pool<Poolable>*)(this);
							alloced_tail->m_poolable_in_free_list	= true;
							
						#endif
						
						if ( count > 1 )
						{
							alloced_tail->m_poolable_prev = alloced_tail - 1;
						}
						
						// Add in all the objects in between:
						
						for ( unsigned i = 1 ; i < count - 1 ; ++i )
						{
							// Get this object:
							
							ConcreteType * alloced = allocated + i;
							
							// Set its fields:
							
							alloced->m_poolable_next = alloced + 1;
							alloced->m_poolable_prev = alloced - 1;
							
							// Debug fields:
							
							#ifdef DEBUG
							
								alloced->m_poolable_parent			= (Pool<Poolable>*)(this);
								alloced->m_poolable_in_free_list	= true;								
							
							#endif
						}
						
						// Set the head and tail of the free list:
						
						m_free_head = alloced_head;
						m_free_tail = alloced_tail;
					}
					
					// Grow the pool size:
					
					m_pool_size += count;
				}
				
				//=====================================================================================================
				/// @brief		Grows the pool. Adds the given objects (stored as ConcreteType* pointers in the 
				///				given stack) to the list of objects in the pool.
				/// @param		stack - This holds pointers to each object (ConcreteType*) that will be used by the 
				///				pooling system. The function expects the specified number of objects to be present on 
				///				the stack and will pop each pointer off the stack until it is finished.
				/// @param		count - number of allocated allocated objects in the array
				/// @pre		The objects given must not be in a pool already
				/// @pre		The number of objects given must be greater than zero
				//=====================================================================================================
				
				void Grow( Stack & stack , unsigned count )
				{
					// Make sure ok:
					
					ENSURE( count > 0 , "The number of objects given must be greater than zero" );				
				
					// Make sure ok:
					
					#ifdef DEBUG
					
						for ( unsigned i = 0 ; i < count ; ++i )
						{
							// Pop this object off the stack
							
							ConcreteType * obj = stack.Pop<ConcreteType*>();
							
							// Make sure ok:
						
							ENSURE( obj->m_poolable_parent	== 0	, "The objects given must not be in a pool already" );
							ENSURE( obj->m_poolable_next	== 0	, "The objects given must not be in a pool already" );
							ENSURE( obj->m_poolable_prev	== 0	, "The objects given must not be in a pool already" );
						}
						
						// Move stack pointer back to where it was
						
						stack.Offset( sizeof(void*) * count );
					
					#endif				
					
					// Get the head and tail of the allocated list:
					
					ConcreteType * alloced_head = allocated;
					ConcreteType * alloced_tail = allocated + count - 1;
					
					// Right: see if there are any objects in the free list
					
					if ( m_free_tail )
					{
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						// There are objects in the free list: link with all of the objects given
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						
						// Keep going until the stack is empty:
						
						for ( unsigned i = count ; i != 0 ; --i )
						{
							// Get this object off the stack:
							
							ConcreteType * obj = stack.Pop<ConcreteType*>();
							
							// Link with the current tail
							
							m_free_tail->m_poolable_next = obj; obj->m_poolable_prev = obj;
							
							// Make the new tail:
							
							m_free_tail = obj; obj->m_poolable_next = 0;							
						
							#ifdef DEBUG
							
								// These are only there in debug
							
								m_free_tail->m_poolable_parent			= (Pool<Poolable>*)(this);
								m_free_tail->m_poolable_in_free_list	= true;
								
							#endif
						}
					}
					else
					{
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						// There are no obejcts in the free list: Add in the 1st new object.. 
						//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
						
						// Add in the head and make it the tail also
						
						m_free_tail = m_free_head = stack.Pop<ConcreteType*>();
						
						// Set it's previous and next pointers
						
						m_free_tail->m_poolable_next = 0;
						m_free_tail->m_poolable_prev = 0;
						
						// Debug fields:
						
						#ifdef DEBUG
						
							m_free_tail->m_poolable_parent			= (Pool<Poolable>*)(this);
							m_free_tail->m_poolable_in_free_list	= true;								
						
						#endif						
						
						// Right: see if there is more than one object
						
						if ( count > 1 )
						{
							// Keep going until the stack is empty:
							
							for ( unsigned i = count - 1; i != 0 ; --i )
							{
								// Get this object off the stack:
								
								ConcreteType * obj = stack.Pop<ConcreteType*>();
								
								// Link with the current tail
								
								m_free_tail->m_poolable_next = obj; obj->m_poolable_prev = obj;
								
								// Make the new tail:
								
								m_free_tail = obj; obj->m_poolable_next = 0;							
							
								#ifdef DEBUG
								
									// These are only there in debug
								
									m_free_tail->m_poolable_parent			= (Pool<Poolable>*)(this);
									m_free_tail->m_poolable_in_free_list	= true;
									
								#endif
							}						
						}
					}
					
					// Grow the pool size:
					
					m_pool_size += count;
				}				
				
				//=====================================================================================================
				/// @brief		Destructor. Destroys the pool.
			    //=====================================================================================================
			    
			    virtual ~Pool()
			    {
					// Run through the used objects list and cleanup:
										
					{
						// Get head:
					
						ConcreteType * p = m_used_head;
						
						// Run through the list:
						
						while ( p )
						{
							// Need to make a temporary:
							
							ConcreteType * t = p;
						
							// Next object:
							
							p = (ConcreteType*) p->m_poolable_next;
							
							// Cleanup:
							
							t->m_poolable_next = 0;
							t->m_poolable_prev = 0;
							
							// Debug only cleanup:
							
							#ifdef DEBUG
							
								t->m_poolable_parent = 0;
								
							#endif						
						}						
					}
					
					// Run through the free objects list and cleanup:
										
					{
						// Get head:
					
						ConcreteType * p = m_free_head;
						
						// Run through the list:
						
						while ( p )
						{
							// Need to make a temporary:
							
							ConcreteType * t = p;
						
							// Next object:
							
							p = (ConcreteType*) p->m_poolable_next;
							
							// Cleanup:
							
							t->m_poolable_next = 0;
							t->m_poolable_prev = 0;
							
							// Debug only cleanup:
							
							#ifdef DEBUG
							
								t->m_poolable_parent = 0;
								
							#endif
						}						
					}					
			    }
				
				//=====================================================================================================
				/// @brief		Gets the size of the pool, or the number of objects that can be in use at any one time.
				///	@returns	Amount of objects in the pool.
			    //=====================================================================================================
			    
			    inline unsigned GetSize() const { return m_pool_size; }
			    
				//=====================================================================================================
				/// @brief		Returns the number of objects currently in use by the pool.
				///	@returns	Number of object's in use by the pool.
			    //=====================================================================================================
			    
			    inline unsigned GetUsedCount() const { return m_used_count; }
				
				//=====================================================================================================
				/// @brief		Gets an object from the pool. If there is none free then the oldest
				///				object allocated which is currently used is returned.
				///	@returns	A Poolable type object for use. Application should call Dealloc()
				///				when done with this object.
				/// @pre		The head of the free list should have it's previous pointer as null
				/// @pre		The tail of the free list should have it's next pointer as null
				/// @pre		The head of the used list should have it's previous pointer as null
				/// @pre		The tail of the used list should have it's next pointer as null
			    //=====================================================================================================
			    
				ConcreteType * Alloc()
				{
					// This is the object to be returned:
			        
					ConcreteType * r = m_free_head;
			        
					// If there are no objects free then free the tail of the used list and return it:
			        
					if ( r == 0 )
					{
						Dealloc( m_used_tail ); return Alloc();
					}
					
					// Make sure all these are ok:
					
					#ifdef DEBUG
					
						if ( m_free_head ) ENSURE( m_free_head->m_poolable_prev == 0, "The head of the free list should have it's previous pointer as null" );
						if ( m_free_tail ) ENSURE( m_free_tail->m_poolable_next == 0, "The tail of the free list should have it's next pointer as null" );					
						if ( m_used_head ) ENSURE( m_used_head->m_poolable_prev == 0, "The head of the used list should have it's previous pointer as null" );
						if ( m_used_tail ) ENSURE( m_used_tail->m_poolable_next == 0, "The tail of the used list should have it's next pointer as null" );
											
					#endif					
					
					// In debug, mark the object as no longer being in the free list:
					
					#ifdef DEBUG
					
						r->m_poolable_in_free_list = false;
					
					#endif
			        
					// Update next object in the free list:
			        
					m_free_head = (ConcreteType*) r->m_poolable_next;
			        
					// No object before this any more:
			        
					if ( m_free_head != 0 )
					{
						// Wipe:
			            
						m_free_head->m_poolable_prev = 0;
					}
					else
					{
						// No objects left: so set the tail of the list to null also
			            
						m_free_tail = 0;
					}
			        
					// Put the object into the top of the allocated objects list:
			        
					if ( m_used_head != 0 )
					{            
						m_used_head->m_poolable_prev = r;
					}
					else
					{
						// No objects in used list: so set this as the tail of the list also
			            
						m_used_tail = r;
					}
			        
					r->m_poolable_next = m_used_head;
			        
					// Set as the head of the used list:
			        
					m_used_head = r;
					
					// Increment the number of objects in use:
					
					m_used_count++;
			        
					// Return the new object:
			        
					return r;
				}

				//=====================================================================================================
				/// @brief		Reallocates a previously deallocated node. Use with caution and only if you know that
				///				the previously deallocated object has not yet been allocated by something else.
				/// @param		p - object that was previously allocated
				/// @returns	The object passed into the function
				/// @pre		Given object cannot be null
				/// @pre		Given object must belong to this pool
				/// @pre		Given object must currently be deallocated or not in use
				/// @pre		The head of the free list should have it's previous pointer as null
				/// @pre		The tail of the free list should have it's next pointer as null
				/// @pre		The head of the used list should have it's previous pointer as null
				/// @pre		The tail of the used list should have it's next pointer as null				
				//=====================================================================================================

				ConcreteType * Realloc( ConcreteType * p )
				{
					// Debug safety checks
				
					ENSURE( p != 0 													, "Given object cannot be null"									);
					ENSURE( (Pool<ConcreteType>*) p->m_poolable_parent	==	this	, "Given object must belong to this pool"						);
					ENSURE( p->IsDealloced() == true								, "Given object must currently be deallocated or not in use"	);
					
					// Make sure all these are ok:
					
					#ifdef DEBUG
					
						if ( m_free_head ) ENSURE( m_free_head->m_poolable_prev == 0, "The head of the free list should have it's previous pointer as null" );
						if ( m_free_tail ) ENSURE( m_free_tail->m_poolable_next == 0, "The tail of the free list should have it's next pointer as null" );					
						if ( m_used_head ) ENSURE( m_used_head->m_poolable_prev == 0, "The head of the used list should have it's previous pointer as null" );
						if ( m_used_tail ) ENSURE( m_used_tail->m_poolable_next == 0, "The tail of the used list should have it's next pointer as null" );
											
					#endif							

					// See if it has a next node:
					
					if ( p->m_poolable_next )
					{
						// Set the pointer for the next element
						
						p->m_poolable_next->m_poolable_prev = (ConcreteType*) p->m_poolable_prev;
					}
					else
					{
						// Set the new tail node for the free list
						
						m_free_tail = (ConcreteType*) p->m_poolable_prev;
					}
					
					// See if it has a previous node:
					
					if ( p->m_poolable_prev )
					{
						// Set the next pointer for the previous element
						
						p->m_poolable_prev->m_poolable_next = (ConcreteType*) p->m_poolable_next;
					}
					else
					{
						// Set the new head node for the free list
						
						m_free_head = (ConcreteType*) p->m_poolable_next;
					}
					
					// In debug mode set this flag:
					
					#ifdef DEBUG
					
						p->m_poolable_in_free_list = false;
					
					#endif
					
					// See if there is a used head:
					
					if ( m_used_head )
					{
						// Set it's previous pointer
						
						m_used_head->m_poolable_prev = (ConcreteType*) p;					
					}
					else
					{
						// Nothing in the list: this object is the tail also
						
						m_used_tail = p;
					}
					
					// Make the node point to the used head
					
					p->m_poolable_next = m_used_head;
					
					// No previous pointer
					
					p->m_poolable_prev = 0;
					
					// This is the new head of the used list
					
					m_used_head = p;
					
					// Increment the number of objects in use:
					
					m_used_count++;					
					
					// Return the object
					
					return p;
				}
				
				//=====================================================================================================
				///	@brief		Free's up a poolable object. Adding it back into the list of free objects.
				///				This function assumes the object is actually in the pool to begin with, 
				///				and that it has not already been freed.
				///	@param		p - Object to release from the used pool of objects. This object 
				///				is subsequently made available for later re-use.				
				/// @pre		The used count should not be zero
				/// @pre		The object must be contained in this pool
				/// @pre		The object must not be in the free list, or de-allocated already
				/// @pre		The tail of the free list must have a next pointer of null if there
				/// @pre		If there is no free tail, there should be no free head
				/// @pre		The head of the free list should have it's previous pointer as null
				/// @pre		The tail of the free list should have it's next pointer as null
				/// @pre		The head of the used list should have it's previous pointer as null
				/// @pre		The tail of the used list should have it's next pointer as null					
			    //=====================================================================================================
			    
				void Dealloc( ConcreteType * p )
				{
					// Make sure this is ok:
					
					ENSURE( m_used_count > 0										, "The used count should not be zero"									);
					ENSURE( (Pool<ConcreteType>*) p->m_poolable_parent	==	this	, "The object must be contained in this pool"							);
					ENSURE( p->m_poolable_in_free_list	==	false					, "The object must not be in the free list, or de-allocated already"	);
					
					// Make sure all these are ok:
					
					#ifdef DEBUG
					
						if ( m_free_head ) ENSURE( m_free_head->m_poolable_prev == 0, "The head of the free list should have it's previous pointer as null" );
						if ( m_free_tail ) ENSURE( m_free_tail->m_poolable_next == 0, "The tail of the free list should have it's next pointer as null" );					
						if ( m_used_head ) ENSURE( m_used_head->m_poolable_prev == 0, "The head of the used list should have it's previous pointer as null" );
						if ( m_used_tail ) ENSURE( m_used_tail->m_poolable_next == 0, "The tail of the used list should have it's next pointer as null" );
											
					#endif						
					
					// Mark the object as now being in the free list in debug:
					
					#ifdef DEBUG
					
						p->m_poolable_in_free_list = true;
					
					#endif
									
					// See if it has a next object:
			        
					if ( p->m_poolable_next != 0 )
					{
						// Set it's reference
			            
						p->m_poolable_next->m_poolable_prev = p->m_poolable_prev;
					}
					else
					{
						// This is the tail object: set the new tail of the list
			            
						m_used_tail = (ConcreteType*) p->m_poolable_prev;
					}
			        
					// See if it has a previous object:
			        
					if ( p->m_poolable_prev != 0 )
					{
						// Set it's reference
			            
						p->m_poolable_prev->m_poolable_next = p->m_poolable_next;
					}
					else
					{
						// This is the head object: set the new head of the list
			            
						m_used_head = (ConcreteType*) p->m_poolable_next;
					}
			        
					// Add into the tail of the free list:
			        
					if ( m_free_tail != 0 )
					{
						// Make sure ok:
						
						ENSURE( m_free_tail->m_poolable_next == 0 , "The object must not be in the free list, or de-allocated already" );
						
						// Free tail: set it's previous reference
			            
						m_free_tail->m_poolable_next = p;
			            
						// Set previous and next references on p
			            
						p->m_poolable_next = 0;
						p->m_poolable_prev = m_free_tail;
			            
						// Set new tail:
			            
						m_free_tail = p;
					}
					else
					{
						// Make sure ok:
						
						ENSURE( m_free_head == 0 , "If there is no free tail, there should be no free head" );
					
						// No free tail: therefore this object is both head and tail of the new list
			            
						m_free_head = p;
						m_free_tail = p;
			            
						p->m_poolable_next = 0;
						p->m_poolable_prev = 0;
					}
					
					// Decrease the object usage count
					
					m_used_count--;     
				}										
				
				//=====================================================================================================
				/// @brief		Returns an enumerator into the free objects list.
				/// @returns	Enumerator into the free objects list
				//=====================================================================================================
				
				inline Enumerator FreeObjects(){ return Enumerator(m_free_head); }
				
				//=====================================================================================================
				/// @brief		Returns an enumerator into the used objects list.
				/// @returns	Enumerator into the used objects list
				//=====================================================================================================
				
				inline Enumerator UsedObjects(){ return Enumerator(m_used_head); }				
				
				//=====================================================================================================
				/// @brief		Returns an invalid enumerator, which points to nothing. This can be used for loops to 
				///				know when to stop iterating.
				/// @returns	An invalid iterator
				//=====================================================================================================
				
				inline Enumerator ListEnd(){ return Enumerator(0); }
			
		private:
		
			//=========================================================================================================
			// Variables
			//=========================================================================================================			
		
				/// Head of the list of objects that are free for use
			    
				ConcreteType * m_free_head;
    
				/// Tail of the list of objects that are free for use. This is the object used last.
    
				ConcreteType * m_free_tail;
    
				/// Head of the list of objects that are used. This is the most recently allocated object.
    
				ConcreteType * m_used_head;
    
				/// Tail of the list of objects that are used. This is the least recently allocated object.
    
				ConcreteType * m_used_tail;
				
				/// The number of objects in the pool
				
				unsigned m_pool_size;
				
				/// The number of objects currently in use by the pool
	    
				unsigned m_used_count;
	};
};

#endif 
