/*
	Lan Wars.
	Copyright (c) 2009, 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 GAME_HEAP_H
#define GAME_HEAP_H

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

namespace Game
{
	//=================================================================================================================
	/// @brief		Class representing a heap data structure. Can be used to maintain a priority queue.
	///				The reason why this class was created is because STL priority queues do not allow control over the 
	///				preallocation of memory, as this class does. STL priority queues also fail and cause crashes when
	///				the heap invariant is violated; this class does not mind. This can be useful in some circumstances.
	/// @remarks	Because the heap invariant is allowed to be violated, this class cannot ensure that the heap will
	///				always be perfectly sorted. Examples of where this might happen is where heap objects use pointers
	///				to objects as the basis of their comparison, and where the objects are modified externally. 
	///				Users should be aware of this when indirectly modifing the contents of the heap in this manner.
	/// @remarks	This heap sorts the smallest items to be at the top of the heap. It only uses '<' operator during
	///				comparison also.
	//=================================================================================================================

	template<class T> class Heap : public ReferencedObject
	{	
		public:
		
			//=========================================================================================================
			// Functions
			//=========================================================================================================
			
				//=====================================================================================================
				/// @brief		Creates the heap
				/// @param		reserve_size - the number of elements to reserve on the heap. Set this to improve 
				///				performance where you know in advance how many elements (or roughly how many) will be
				///				required.
				/// @pre		Reserve size must be at least 1
				/// @remarks	The actual amount of memory allocated may not match the reserve size given. The heap
				///				is restricted to it's capacity being a power of two- hence the reason for the mismatch.
				///				What is guaranteed however is that the capacity chosen for the heap will at least match
				///				the capacity specified.
				//=====================================================================================================
				
				Heap( unsigned reserve_size = 512 )
				{
					// Make sure ok
					
					ENSURE( reserve_size >= 1 , "Reserve size must be at least 1" )
					
					// Pick a power of two size that at least encapsulates the required size
					
					unsigned size = 0; while ( ( unsigned(1) << size ) < reserve_size ){ size++; } size = 1 << size;
					
					// Initialise these:
					
					m_memory	= 0;
					m_size		= 0;
					m_capacity	= 0;
					
					// Reserve the required amount of memory
					
					Resize(size);
				}
				
				//=====================================================================================================
				/// @brief		Destroys the heap
				//=====================================================================================================
				
				inline ~Heap()
				{
					// Free the heap memory
					
					delete[] m_memory;
				}
				
				//=====================================================================================================
				/// @brief		Returns the number of elements currently in the heap				
				/// @returns	Number of elements in the heap
				//=====================================================================================================
				
				inline unsigned GetSize() const { return m_size; }

				//=====================================================================================================
				/// @brief		Returns the capacity of the heap, or the maximum number of elements that can be put 
				///				on the heap without a reallocation being required.
				/// @returns	Current capacity of the heap
				//=====================================================================================================
				
				inline unsigned GetCapacity() const { return m_capacity; }
				
				//=====================================================================================================
				/// @brief		Returns the maximum depth of the heap, or the maximum number of levels in the heap tree.
				/// @returns	Maximum number of levels in the heap tree
				//=====================================================================================================
				
				inline unsigned GetDepth() const 
				{ 
					// Get the highest bit of the capacity:
					
					unsigned highest_bit = 0;
					
					for ( unsigned i = 0 ; i < 32 ; ++i )
					{
						if ( ( m_capacity & ( 1 << i ) ) != 0 ) highest_bit = 1;
					}
					
					// Return the depth:
					
					return highest_bit + 1;
				}
				
				//=====================================================================================================
				/// @brief		Adds an element into the heap
				/// @param		v - element to add into the heap
				//=====================================================================================================
				
				inline void Push( const T & v )
				{
					// See if we are at our capacity:
					
					if ( m_capacity == m_size )
					{
						// Resize the heap to cope with the new addition
						
						Resize( m_capacity << 1 );
					}
					
					// Add the element as the deepest right-most element in the heap
					
					m_memory[m_size] = v; 
					
					// Increase size
					
					m_size++;
					
					// Perform up-heap bubbling to restore the heap invariant (higher up items in tree are bigger)
					
					Upheap();
				}
				
				//=====================================================================================================
				/// @brief		Returns the top element on the heap.
				/// @returns	The top element on the heap.
				/// @pre		The heap size must be at least 1. I.E there must be an element on the heap.
				//=====================================================================================================
				
				inline const T & GetTop() const
				{
					// Make sure ok
					
					ENSURE( m_size >= 1 , "The heap size must be at least 1. I.E there must be an element on the heap." )
					
					// Return the top element of the heap:
					
					return m_memory[0];
				}
				
				//=====================================================================================================
				/// @brief		Pops the top element off the heap.
				/// @pre		The heap size must be at least 1. I.E there must be an element on the heap.
				//=====================================================================================================
				
				inline void Pop()
				{
					// Make sure ok
					
					ENSURE( m_size >= 1 , "The heap size must be at least 1. I.E there must be an element on the heap." )
				
					// See if we are sized greater than 1:
					
					if ( m_size > 1 ) 
					{
						// Swap the deepest rightmost node into the top of the heap:
						
						m_memory[0] = m_memory[m_size-1];
						
						// Reduce the size of the heap
						
						m_size--;
						
						// Perform down-heap bubbling to restore the heap invariant
						
						Downheap();						
					}
					else
					{
						// Reduce the size of the heap
						
						m_size--;					
					}					
				}
				
				//=====================================================================================================
				/// @brief		Clears the heap.
				//=====================================================================================================
				
				void Clear(){ m_size = 0; }
				
		private:
		
			//=========================================================================================================
			// Functions
			//=========================================================================================================
			
				//=====================================================================================================
				/// @brief		Performs up-heap bubbling of the deepest rightmost node in the heap, restoring the 
				///				heap invariant.
				/// @remarks	If other parts of the heap do not respect the heap invariant due to external 
				///				modification, then the heap may not necessarily be perfectly sorted.
				/// @pre		The size of the heap must be at least 1
				//=====================================================================================================
				
				inline void Upheap()
				{
					// Make sure ok
					
					ENSURE( m_size >= 1 , "The size of the heap must be at least 1" )
				
					// Get the index of the deepest right-most node in the tree
					
					unsigned sort_index = m_size - 1;
					
					//-------------------------------------------------------------------------------------------------
					// Stop when we reach the top of the heap, or when the heap invariant is restored (as far as we can see)
					//-------------------------------------------------------------------------------------------------
					
					while ( sort_index > 0 )
					{
						//---------------------------------------------------------------------------------------------
						// Get the index of the parent of this object:
						//---------------------------------------------------------------------------------------------
						
						unsigned parent_index = sort_index >> 1;
						
						//---------------------------------------------------------------------------------------------
						// See if we are bigger or equal to our parent: if this is the case then we are ok and do not 
						// need to do anything further ...
						//---------------------------------------------------------------------------------------------
						
						if ( m_memory[sort_index] < m_memory[parent_index] )
						{
							// Need to swap with our parent:
							
							T temp = m_memory[sort_index];
							
							// Do the swap:
							
							m_memory[sort_index] = m_memory[parent_index]; m_memory[parent_index] = temp;
							
							// Get the indexes of our previous left and right children: if there is any
							
							unsigned lchild_index = sort_index << 1;			
							unsigned rchild_index = lchild_index + 1;
							
							// See if we have a right child firstly:
							
							if ( rchild_index < m_size )
							{
								//-------------------------------------------------------------------------------------
								// Have both a left and right child: see which is smallest
								//-------------------------------------------------------------------------------------
								
								if ( m_memory[lchild_index] < m_memory[rchild_index] )
								{
									//---------------------------------------------------------------------------------
									// Left child is smallest. See if it is smaller than our previous parent.
									//---------------------------------------------------------------------------------
									
									if ( m_memory[lchild_index] < m_memory[sort_index] )
									{
										// Need to swap the left child into the position we put the parent in
										
										temp = m_memory[sort_index];
										
										// Do the swap:
										
										m_memory[sort_index] = m_memory[lchild_index]; m_memory[lchild_index] = temp;
									}
								}
								else
								{
									//---------------------------------------------------------------------------------
									// Right child is smallest or equal. See if it is smaller than our previous parent.
									//---------------------------------------------------------------------------------
									
									if ( m_memory[rchild_index] < m_memory[sort_index] )
									{
										// Need to swap the right child into the position we put the parent in
										
										temp = m_memory[sort_index];
										
										// Do the swap:
										
										m_memory[sort_index] = m_memory[rchild_index]; m_memory[rchild_index] = temp;
									}									
								}
							}
							else if ( lchild_index < m_size )
							{
								//-------------------------------------------------------------------------------------
								// Only have a left child: see if the left child is smaller than the parent we swapped
								// with. If so then we need to swap the left child to restore the heap invariant.
								//-------------------------------------------------------------------------------------
								
								if ( m_memory[lchild_index] < m_memory[sort_index] )
								{
									// Need to swap the left child into the position we put the parent in
									
									temp = m_memory[sort_index];
									
									// Do the swap:
									
									m_memory[sort_index] = m_memory[lchild_index]; m_memory[lchild_index] = temp;
								}
							}
						}
						else
						{
							//-----------------------------------------------------------------------------------------
							// Done: heap invariant is restored. We are bigger or equal to our parent
							//-----------------------------------------------------------------------------------------
							
							break;
						}
						
						//---------------------------------------------------------------------------------------------
						// We are now one level higher in the heap: continue until the heap invariant is restored
						//---------------------------------------------------------------------------------------------
						
						sort_index >>= 1;
					}
				}
				
				//=====================================================================================================
				/// @brief		Performs down-heap bubbling of the top node in the tree, restoring the heap invariant.
				///				This is performed after a removal.
				/// @remarks	If other parts of the heap do not respect the heap invariant due to external 
				///				modification, then the heap may not necessarily be perfectly sorted.
				/// @pre		The size of the heap must be at least 1
				//=====================================================================================================
				
				inline void Downheap()
				{
					// Make sure ok
					
					ENSURE( m_size >= 1 , "The size of the heap must be at least 1" )
					
					// This is the index of the element we are down-heaping:
					
					unsigned sort_index = 0;
					
					// If this is true then we continue sorting:
					
					bool continue_sorting = true;
					
					// Continue until we reach the bottom of the heap:
					
					while ( continue_sorting )
					{
						// Get the index of our right and left children:
						
						unsigned lchild_index = sort_index << 1;
						unsigned rchild_index = lchild_index + 1;
						
						// See if we have a left and right child:
						
						if ( rchild_index < m_size )
						{
							//-----------------------------------------------------------------------------------------
							// Have a left and right child: see which is smaller
							//-----------------------------------------------------------------------------------------
							
							if ( m_memory[lchild_index] < m_memory[rchild_index] )
							{
								//-------------------------------------------------------------------------------------
								// Left child is smaller or equal to the right child: see if it is smaller than us
								//-------------------------------------------------------------------------------------
								
								if ( m_memory[lchild_index] < m_memory[sort_index] )
								{
									//---------------------------------------------------------------------------------
									// Need to swap with the left child:
									//---------------------------------------------------------------------------------
									
									T temp = m_memory[sort_index];
									
									// Do the swap:
									
									m_memory[sort_index] = m_memory[lchild_index]; m_memory[lchild_index] = temp;
									
									// We are now at the index of the left child
									
									sort_index = lchild_index;
								}
								else
								{
									//---------------------------------------------------------------------------------
									// Done: smallest child is not smaller than us. 
									//---------------------------------------------------------------------------------
									
									continue_sorting = false;
								}
							}
							else
							{
								//-------------------------------------------------------------------------------------
								// Right child is smaller or equal to the left child: see if it is smaller than us
								//-------------------------------------------------------------------------------------
								
								if ( m_memory[rchild_index] < m_memory[sort_index] )
								{
									//---------------------------------------------------------------------------------
									// Need to swap with the right child:
									//---------------------------------------------------------------------------------
									
									T temp = m_memory[sort_index];
									
									// Do the swap:
									
									m_memory[sort_index] = m_memory[rchild_index]; m_memory[rchild_index] = temp;
									
									// We are now at the index of the right child
									
									sort_index = rchild_index;
								}
								else
								{
									//---------------------------------------------------------------------------------
									// Done: smallest child is not smaller than us. 
									//---------------------------------------------------------------------------------
									
									continue_sorting = false;
								}	
							}
						}
						else if ( lchild_index < m_size )
						{
							//-----------------------------------------------------------------------------------------
							// Only have a left child. See if it is smaller than us
							//-----------------------------------------------------------------------------------------
							
							if ( m_memory[lchild_index] < m_memory[sort_index] )
							{
								//-------------------------------------------------------------------------------------
								// Left child is smaller than us: need to swap
								//-------------------------------------------------------------------------------------
								
								T temp = m_memory[sort_index];
								
								// Do the swap:
								
								m_memory[sort_index] = m_memory[lchild_index]; m_memory[lchild_index] = temp;
								
								// We are now at the index of the left child
								
								sort_index = lchild_index;
							}
							else
							{
								//-------------------------------------------------------------------------------------
								// Done: left child is not smaller than us so the heap invariant has been restored
								//-------------------------------------------------------------------------------------
								
								continue_sorting = false;
							}
						}
						else
						{
							//-----------------------------------------------------------------------------------------
							// No left or right children. Done. At the bottom level of the heap.
							//-----------------------------------------------------------------------------------------
							
							continue_sorting = false;
						}
					}	
				}
			
				//=====================================================================================================
				/// @brief		Resizes the heap to the given size
				/// @param		new_size - new capacity of the heap
				/// @pre		The chosen size for the heap must be a power of two
				/// @pre		The chosen size must be bigger than the previous size
				//=====================================================================================================
				
				inline void Resize( unsigned new_size )
				{
					// Debug only:
					
					#ifdef DEBUG
					
						// Get the highest bit in the size
						
						unsigned highest_bit = 0;
						
						for ( unsigned i = 0 ; i < 32 ; ++i )
						{
							if ( ( new_size & ( 1 << i ) ) != 0 ) highest_bit = i;
						}
						
						// Now make sure the size is a power of two
						
						ENSURE( new_size - ( 1 << highest_bit ) == 0 , "The chosen size for the heap must be a power of two" )
					
					#endif
					
					// Make sure new size is bigger than old size
					
					ENSURE( new_size > m_size , "The chosen size must be bigger than the previous size" )
					
					// Allocate the new array for the heap:
					
					T * new_array = new T[new_size];
					
					// Copy the old elements into the new heap array:
					
					if ( m_memory )
					{										
						for ( unsigned i = 0 ; i < m_capacity ; ++i ) new_array[i] = m_memory[i];
					}
					
					// Delete the old array:
					
					delete[] m_memory;
					
					// Save new array and capacity:
					
					m_memory = new_array; m_capacity = new_size;
				}
			
				//=====================================================================================================
				/// @brief		Copying is disallowed.
				/// @param		other - other object to copy from
				//=====================================================================================================
				
				inline Heap( const Heap<T> & other );

				//=====================================================================================================
				/// @brief		Copying is disallowed.
				/// @param		other - other object to copy from
				//=====================================================================================================
				
				inline Heap<T> & operator = ( const Heap<T> & other );
				
			//=========================================================================================================
			// Variables
			//=========================================================================================================
			
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				/// This is the heap memory: the heap tree is stored internally as a flattened tree whereby the first
				/// level of the tree is first in the array, and the second level second and so on. Each level has 
				/// twice as many nodes as the previous level (binary tree).
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				
				T * m_memory;
				
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				/// This is the current capacity of the heap, or the maximum number of elements that can be stored on
				/// the heap.
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				
				unsigned m_capacity;
				
				/// This is the number of elements on the heap currently.
				
				unsigned m_size;
	};
};

#endif 
