#pragma once
#include <windows.h>

template <class T>
class DynamicStack
{
	DWORD	m_dwPointer;
	DWORD   m_dwSize;
	T*		m_pStack;

public:

	DynamicStack(void)
	{
		m_pStack = NULL;
		m_dwSize = 0;
		m_dwPointer = 0;
		SetSize(256);
	}

	DynamicStack(DWORD size)
	{
		if (size <= 0)
			size = 1;
		m_pStack = NULL;
		m_dwSize = 0;
		m_dwPointer = 0;
		SetSize(size);
	}

	~DynamicStack(void)
	{
		delete [] m_pStack;
	}

	void SetSize(DWORD size)
	{
		T* newstack = new T[size];
		if(m_pStack)
		{
			memcpy(newstack,m_pStack,sizeof(T)*m_dwSize);
			delete [] m_pStack;
		}
		m_pStack = newstack;
		m_dwSize = size;
	}

	void Push(const T& element)
	{
		if(m_dwPointer >= m_dwSize)
		{
			SetSize(m_dwSize<<1);
		}
		m_pStack[m_dwPointer++] = element;
	}

	T Pop(void)
	{
		return m_pStack[--m_dwPointer];
	}

	DWORD GetSize(void) const
	{
		return m_dwSize;
	}

	DWORD GetElementCount(void) const
	{
		return m_dwPointer;
	}

	T operator [](int n) const
	{
		if(n<m_dwPointer)
			return m_pStack[n];
	}

	void SetN(const T& v, int n)
	{
		if(n < m_dwPointer)
			m_pStack[n] = v;
	}

	void PopAll(void)
	{
		m_dwPointer = 0;
	}

	T* GetStack(void) const
	{
		return m_pStack;
	}

	void Sort(bool(*cmpless)(const T& a, const T& b), bool(*cmpgreater)(const T& a, const T& b))
	{
		if(m_dwPointer > 1) //there have at least to be 2 elements to sort
			QuickSortCustom(0, m_dwPointer-1, cmpless, cmpgreater);//, cmpless, cmpgreater);
	}

	void Sort(void)//bool(*cmpless)(const T& a, const T& b), bool(*cmpgreater)(const T& a, const T& b))
	{
		if(m_dwPointer > 1) //there have at least to be 2 elements to sort
			QuickSort(0, m_dwPointer-1);//, cmpless, cmpgreater);
	}

	void CopyFrom(const DynamicStack<T>& stk)
	{
		if(m_dwSize < stk.GetElementCount())
		{
			SetSize(stk.GetElementCount());
		}
		memcpy(m_pStack, stk.m_pStack, stk.GetElementCount() * sizeof(T));
		m_dwPointer = stk.GetElementCount();
	}

private:

	void QuickSortCustom(const int istart, const int iend, bool(*cmpless)(const T& a, const T& b), bool(*cmpgreater)(const T& a, const T& b))
	{	
	    int i = istart;
		int j = iend;
		T pivot = m_pStack[(istart + iend) >> 1];
		
		//  partition
		do
		{    
			while (cmpless(m_pStack[i], pivot)) i++;
			while (cmpgreater(m_pStack[j], pivot)) j--;

			if (i <= j)
				Swap(i++, j--);
		} 
		while (i <= j);

		//  recursion
		if (istart < j) QuickSortCustom(istart, j, cmpless, cmpgreater);
		if (i < iend) QuickSortCustom(i, iend, cmpless, cmpgreater);
	}

	void QuickSort(const int istart, const int iend)
	{	
	    int i = istart;
		int j = iend;
		T pivot = m_pStack[(istart + iend) >> 1];
		
		//  partition
		do
		{    
			while (m_pStack[i] < pivot) i++;
			while (m_pStack[j] > pivot) j--;

			if ( i<= j)
				Swap(i++, j--);
		} 
		while (i <= j);

		//  recursion
		if (istart < j) QuickSort(istart, j);
		if (i < iend) QuickSort(i, iend);
	
		/*if (iend - istart >= 1) // check that there are at least two elements to sort
        {
			const int pivot = istart;

			int i = istart;
			int j = iend;

			while (j > i)
			{    
				//while ( cmpless(m_pStack[i], m_pStack[pivot])) i++;
				while ( m_pStack[i] <= m_pStack[pivot] && i <= iend && j > i) i++;

				//while ( istart < j && cmpgreater(m_pStack[j], m_pStack[pivot])) j--;
				while ( m_pStack[j] > m_pStack[pivot] && j >= istart && j >= i) j--;

				if (j > i)
					Swap(i, j);
			}

			Swap(pivot, j);
			
			QuickSort(istart, j - 1); //sort left partition
			QuickSort(j + 1, iend); //sort right partition
		}*/
	}

	void Swap(const int a, const int b)
	{
		T h = m_pStack[a];
		m_pStack[a] = m_pStack[b];
		m_pStack[b] = h;
	}
};
