/*
	Trampoline Sim.
	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_STACK_H
#define GAME_STACK_H

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

#include "Base\Assertion.h"
#include <cstring>

#ifdef DEBUG

	#include <list>

#endif

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

namespace Game
{
	//=================================================================================================================
	/// @brief		This class is used as a fast temporary storage area for data. The main reason this has been 
	///				created (rather than use the regular stack) is because it allows for a variable amount of parameters
	///				to be pushed onto it- making it perfect for temporary lists of objects without the overhead or 
	///				loss of cache coherency that the 'new' operator brings. It also allows for temporary variables 
	///				to be returned from functions, unlike the regular stack.
	/// @remarks	In debug mode the stack will validate usage of the stack, however in release this will not happen.
	///				All entries shall be aligned to 4 byte boundaries for maximum read/write efficiency.
	/// @remarks	This class is only intended to be used with primitive types (or structs) and a shallow copy of 
	///				all data is only done for write operations. This class is not suitable where C++ operators such
	///				as the copy constructor and the assignment operators are required. 
	/// @remarks	The direction of the stack is the same as a normal array- in contrary to the real stack which
	///				operates in reverse. This is to allow primitives to be pushed onto the stack for later rendering 
	///				from memory. It also makes manipulating stack memory far less confusing!
	//=================================================================================================================
	
	class Stack
	{
		public:

			//=========================================================================================================
			// Functions
			//=========================================================================================================

				/// Creates the stack with the specified size
				
				Stack( unsigned size );
				
				/// Destroys the stack
				
				~Stack();

				//=====================================================================================================
				/// @brief		Gives a pointer to the current location on the stack.
				/// @remarks	The stack pointer works like the real stack in that the pointer is always ahead of the 
				///				last element written. If a pointer is needed to this element, you may need to move the 
				///				stack pointer and use functions like GetAlignedSize to move the correct amount of bytes
				/// @post		There must not be a stack underflow. Pointer must be in a valid location.
				/// @post		There must not be a stack overflow. Pointer must be in a valid location.
				/// @post		The stack pointer must be aligned to 4 byte boundaries.
				//=====================================================================================================

				inline void * GetPointer()
				{ 
					// Check for over/underflows
					
					ENSURE( m_current <  m_end					, "There must not be a stack underflow. Pointer must be in a valid location."	);
					ENSURE( m_current >= m_stack_memory_aligned	, "There must not be a stack overflow. Pointer must be in a valid location."	);
					ENSURE( (((unsigned)(m_current)) & 3 ) == 0	, "The stack pointer must be aligned to 4 byte boundaries."						);
				
					return m_current; 
				}
				
				//=====================================================================================================
				/// @brief		Sets the current stack pointer.
				/// @param		p - new stack pointer 
				/// @remarks	The stack pointer works like the real stack in that the pointer is always ahead of the 
				///				last element written. Bear this in mind when writing pointers. Also bear in mind that
				///				you will need to get the aligned size of the element (with extra alignment padding) to
				///				account for the true size of the object on the stack.
				/// @pre		There must not be a stack underflow. Pointer must be in a valid location.
				/// @pre		There must not be a stack overflow. Pointer must be in a valid location.
				/// @pre		The stack pointer must be aligned to 4 byte boundaries.
				//=====================================================================================================
				
				inline void SetPointer( void * p )
				{
					// Set:
					
					m_current = p;
				
					// Check for over/underflows
					
					ENSURE( m_current <  m_end					, "There must not be a stack underflow. Pointer must be in a valid location."	);
					ENSURE( m_current >= m_stack_memory_aligned	, "There must not be a stack overflow. Pointer must be in a valid location."	);
					ENSURE( (((unsigned)(m_current)) & 3) == 0	, "The stack pointer must be aligned to 4 byte boundaries."						);					
				}				
				
				//=====================================================================================================
				/// @brief		Gives a pointer to the current location on the stack.
				/// @remarks	The stack pointer works like the real stack in that the pointer is always ahead of the 
				///				last element written. If a pointer is needed to this element, you may need to move the 
				///				stack pointer and use functions like GetAlignedSize to move the correct amount of bytes
				//=====================================================================================================

				inline void * GetStackPointer(){ return m_current; }				
				
				//=====================================================================================================
				/// @brief		Gets the size of the stack or the total amount of RAM available on it.
				///	@remarks	The actual amount of ram used by allocs may vary however because of the need to pad and
				///				align data, so take this with a pinch of salt if using to ensure there is enough
				///				memory to alloc.
				//=====================================================================================================
				
				inline unsigned GetSize() const { return (unsigned)(m_end) - (unsigned)(m_stack_memory_aligned); }

				//=====================================================================================================
				/// @brief		Gets the offset of the stack pointer in relation to the beginning of the stack.
				/// @returns	Returns the offset of the stack pointer from the beginning of the stack
				//=====================================================================================================

				inline unsigned GetOffset()
				{
					return ((int)(m_current)) - ((int)(m_stack_memory_aligned));
				}

				//=====================================================================================================
				/// @brief		Moves the stack pointer forwards or backwards by the given amount.
				/// @param		offset - Amount to move stack pointer by
				/// @pre		Given amount to move must be in multiples of 4
				/// @pre		There must not be a stack underflow. Pointer must be in a valid location.
				/// @pre		There must not be a stack overflow. Pointer must be in a valid location.
				/// @remarks	This function does not validate where the stack pointer is. Use GetOffset() in 
				///				conjunction with GetSize() to ensure that the pointer is within range.
				//=====================================================================================================

				inline void Offset( int offset )
				{
					// Make sure ok:

					ENSURE( ( offset & 3 ) == 0 , "Given amount to move must be in multiples of 4" );

					// Move our stack pointer by the given amount

					m_current = (void*)(((unsigned)(m_current)) + offset);
					
					// Check for over/underflows
					
					ENSURE( m_current <  m_end					, "There must not be a stack underflow. Pointer must be in a valid location."	);
					ENSURE( m_current >= m_stack_memory_aligned	, "There must not be a stack overflow. Pointer must be in a valid location."	);					
				}
				
				//=====================================================================================================
				/// @brief		Returns the size of a given variable on the stack when alignment padding is taken into
				///				account.
				/// @param		v - type to get the size for
				/// @returns	Size of a given variable in the stack when alignment is taken into account
				/// @remarks	Returned size will always be greater than or equal to it's real size.
				///				This variable can safely be used to move past a variable on the stack if required.
				//=====================================================================================================
				
				#pragma warning(disable:4100)
				
				template<class T> inline unsigned GetAlignedSize( const T & v ) const
				{
					// Return its size
					
					return ( sizeof(T) + 3 ) & 0xfffffffc;
				}
				
				#pragma warning(default:4100)
				
				//=====================================================================================================
				/// @brief		Tells if a read function for a given variable would result in a stack-underflow
				/// @param		v - type to check for a stack underflow with
				/// @returns	True if reading the given type would result in a stack underflow
				/// @remarks	This function can be used to validate stack reads if required.
				/// @pre		The stack pointer must be aligned on 4 byte boundaries			
				//=====================================================================================================
				
				template<class T> inline bool CanRead( const T & v ) const
				{
					// Make sure the stack pointer is ok:
					
					ENSURE( ( m_current & 0x3 ) == 0 , "The stack pointer must be aligned on 4 byte boundaries" );					
				
					// Get the address that we would have to move to in order to read:
					
					void * addr = (void*)((unsigned)(m_current) - GetAlignedSize(v));
					
					// See if it is before the start of the stack
					
					if ( addr < m_stack_memory_aligned ) return false; else return true;
				}
				
				//=====================================================================================================
				/// @brief		Tells if a write function for a given variable would result in a stack-overflow
				/// @param		v - type to check for a stack overflow with
				/// @returns	True if writing the given type would result in a stack overflow
				/// @remarks	This function can be used to validate stack reads if required.
				/// @pre		The stack pointer must be aligned on 4 byte boundaries				
				//=====================================================================================================
				
				template<class T> inline bool CanWrite( const T & v ) const
				{
					// Make sure the stack pointer is ok:
					
					ENSURE( (void*)((unsigned)(m_current) & 0x3 ) == 0 , "The stack pointer must be aligned on 4 byte boundaries" );					
				
					// Get the address that we would have to move to in order to write:
					
					void * addr = (void*)((unsigned)(m_current) + GetAlignedSize(v));
					
					// See if it is after the end of the stack
					
					if ( addr > m_end ) return false; else return true;
				}				
				
				//=====================================================================================================
				/// @brief		Pushes the given structure onto the stack, using memcpy() internally to do the transfer
				/// @param		v - element to be pushed onto the stack
				/// @pre		There must not be a stack overflow. There must be enough room on the stack.
				/// @pre		The stack pointer must be aligned on 4 byte boundaries
				/// @pre		There cannot be a current stack overflow
				/// @pre		There cannot be a current stack underflow
				/// @remarks	This function peforms a shallow copy only. Do not use with objects that require 
				///				copy constructors etc.
				/// @remarks	This function uses memcpy() internally and thus is suitable for copying entire 
				///				structures onto the stack, since memcpy() is optimised for copying large amounts of
				///				data. However, Push() is more suitable for pushing primitives onto the stack since 
				///				it avoids the call to memcpy() and uses simple assignment instead.
				//=====================================================================================================
				
				template<class T> inline void PushStructure( const T & v )
				{
					// Check for over/underflows
					
					ENSURE( m_current <  m_end					, "There cannot be a current stack overflow"	);
					ENSURE( m_current >= m_stack_memory_aligned	, "There cannot be a current stack underflow"	);				
				
					// Make sure we have enough room left on the stack
					
					ENSURE
					( 
						CanWrite(v) , "There must not be a stack overflow. There must be enough room on the stack."
					)				
					
					// Make sure this is ok:
					
					ENSURE( ((unsigned)(m_current) & 0x3 ) == 0 , "The stack pointer must be aligned on 4 byte boundaries" );
					
					// Copy the object onto the stack
					
					memcpy( m_current , &v , sizeof(T) );
					
					// Move on the stack pointer:
					
					m_current = (void*)( (unsigned)(m_current) + GetAlignedSize(v) );
				}
				
				//=====================================================================================================
				/// @brief		Pushes the given element onto the stack
				/// @param		v - element to be pushed onto the stack
				/// @pre		There must not be a stack overflow. There must be enough room on the stack.
				/// @pre		The stack pointer must be aligned on 4 byte boundaries
				/// @pre		There cannot be a current stack overflow
				/// @pre		There cannot be a current stack underflow
				/// @remarks	Although this function uses an assignment operator (as opposed to memcpy) and may call 
				///				a C++ assignment operator, do not use with objects that store pointers to memory resource 
				///				since the objects on the stack are not deleted after use. Using this function with such
				///				objects may result in leaked memory resources.
				/// @remarks	For pushing entire structures, see the PushStructure() function which may be more 	
				//=====================================================================================================
				
				template<class T> inline void Push( const T & v )
				{
					// Check for over/underflows
					
					ENSURE( m_current <  m_end					, "There cannot be a current stack overflow"	);
					ENSURE( m_current >= m_stack_memory_aligned	, "There cannot be a current stack underflow"	);				
				
					// Make sure we have enough room left on the stack
					
					ENSURE
					( 
						CanWrite(v) , "There must not be a stack overflow. There must be enough room on the stack."
					)				
					
					// Make sure this is ok:
					
					ENSURE( ((unsigned)(m_current) & 0x3 ) == 0 , "The stack pointer must be aligned on 4 byte boundaries" );
					
					// Copy the object onto the stack
					
					*((T*)(m_current)) = v;
					
					// Move on the stack pointer:
					
					m_current = (void*)( (unsigned)(m_current) + GetAlignedSize(v) );
				}				
				
				//=====================================================================================================
				/// @brief		Peeks the current entry in the stack but does not modify the stack pointer
				/// @returns	A reference to the requested type off the stack
				/// @pre		There must be data on the stack
				/// @pre		The stack pointer must be aligned on 4 byte boundaries
				/// @pre		There cannot be a current stack underflow
				/// @pre		There cannot be a current stack overflow
				/// @pre		The read operation must not result in a stack underflow
				/// @remarks	Even though the stack pointer is not modified, we still need to check for a stack
				///				undeflow in debug, because the memory returned might be before the start of memory on
				///				the stack.
				//=====================================================================================================
				
				template<class T> inline T & Peek()
				{
					// Make sure there is data on the stack
					
					ENSURE( m_end > m_stack_memory_aligned	, "There must be data on the stack" );
					
					// Check for over/underflows
					
					ENSURE( m_current <  m_end					, "There cannot be a current stack overflow"	);
					ENSURE( m_current >= m_stack_memory_aligned	, "There cannot be a current stack underflow"	);
					
					// Make sure the stack pointer is ok:
					
					ENSURE( ( m_current & 0x3 ) == 0 , "The stack pointer must be aligned on 4 byte boundaries" );							
					
					// Ensure that we can do a read
					
					ENSURE( (void*)((unsigned)(m_current) - (( sizeof(T) + 3 ) & 0xfffffffc) ) >= m_stack_memory_aligned , "The read operation must not result in a stack underflow" );
					
					// Return the given variable
					
					return * ((T*)((unsigned)(m_current) - (( sizeof(T) + 3 ) & 0xfffffffc ) ));
				}
				
				//=====================================================================================================
				/// @brief		Pops an element off the stack and returns a reference to it. This is similar to peek
				///				except it modifies the stack pointer.
				/// @returns	A reference to the requested type off the stack
				/// @pre		There must be data on the stack
				/// @pre		The stack pointer must be aligned on 4 byte boundaries
				/// @pre		The size of the type requested off the stack must match the size of the of the 
				///				element at the current stack pointer.
				/// @pre		There cannot be a current stack underflow
				/// @pre		There cannot be a current stack overflow
				/// @pre		The read operation must not result in a stack underflow
				/// @remarks	The element 'Poped' off the stack is of course left in the stack memory, so if it is
				///				certain that it has not been overwritten since it can always be retrieved later.
				//=====================================================================================================
				
				template<class T> inline T & Pop()
				{
					// Make sure there is data on the stack
					
					ENSURE( m_end > m_stack_memory_aligned , "There must be data on the stack" );
					
					// Check for over/underflows
					
					ENSURE( m_current <  m_end					, "There cannot be a current stack overflow"	);
					ENSURE( m_current >= m_stack_memory_aligned	, "There cannot be a current stack underflow"	);
					
					// Make sure the stack pointer is ok:
					
					ENSURE( (void*)((unsigned)(m_current) & 0x3 ) == 0 , "The stack pointer must be aligned on 4 byte boundaries" );

					// Ensure that we can do a read
					
					ENSURE( (void*)((unsigned)(m_current) - (( sizeof(T) + 3 ) & 0xfffffffc) ) >= m_stack_memory_aligned , "The read operation must not result in a stack underflow" );
					
					// Modify the stack pointer:
					
					m_current = (void*)((unsigned)(m_current) - ((sizeof(T) + 3 ) & 0xfffffffc ));
					
					// Return the given variable
					
					return * ((T*)(m_current));
				}
				
				//=====================================================================================================
				/// @brief		Rewinds the stack pointer back to the very start of the stack.		
				//=====================================================================================================
				
				inline void Rewind(){ m_current = m_stack_memory_aligned; }				
				
		private:
			
			//=========================================================================================================
			// Variables
			//=========================================================================================================
			
				/// The memory used by the stack
				
				void * m_stack_memory;
				
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				/// The start of the memory that we will use: this might be the same as m_stack_memory but since the 
				/// C++ implementation might not return an aligned memory address (to 4 byte boundaries) we will 
				/// allocate a little extra RAM and do the alignment ourselves.
				//'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
				
				void * m_stack_memory_aligned;
				
				/// The current stack pointer: this must be aligned to four byte boundaries at all times
				
				void * m_current;
				
				/// The current end pointer marking the end of the stack's allocated memory
				
				void * m_end;
	};

};

#endif 