#ifndef __RECYCLE_STACK_H__
#define __RECYCLE_STACK_H__

#if _MSC_VER >= 1000
#pragma once
#endif // _MSC_VER >= 1000

/*
	Yet another conversation with friends that turned into a coding exercise

	Knowing that allocs/reallocs are expensive, we need a high performance 
	stack structure for ints that is extreemly memory efficient

	The first draft solution was a collection of some straight C functions 
	and a transparent stack struct that over realloced in 16 node blocks

	This is a little bit different, 
	1) we make two simple singly linked lists, one is the active stack and 
	   the other is the recycle stack
	2) every time we "pop" from the active stack, we move the node object 
	   onto the recycle stack
	3) when adding a node to the active stack, we check if we can take one 
	   from the recycle stack before allocating more memory
	4) It's templatized so we're no longer limited to ints

	-Jason De Arte, September 20, 2005
*/

// For my own debugging
static long sSingleLinkListStackAllocCount = 0;

template <class T>
class CSingleLinkListStack
{
public:
	struct Node {
		Node * next;
		T      data;
	};

protected:
	Node * m_root;     // starting point for the linked list
	int    m_depth;    // keep track of how many elements there are
	static long s_allocs;

	// Shared copy function
	void Copy(const CSingleLinkListStack & aCopy)
	{
		ATLASSERT(!"NOT FULLY IMPLEMENTED NOR TESTED - This code Should be unreachable.  Why are you using it? -Jason");
		return;

		// When copying a list over we will need to clear out our existing 
		// list, but let's be smart about it 
		// if both lists are the same length
		//    straight copy of Node.data from one to the other
		// if our list is shorter than their list
		//    copy over the nodes that we can & then create new nodes
		// if our list is longer than their list
		//    copy over the Node.data and delete the rest

		// TODO: Implement the above logic
	}

	void init()
	{
		m_root = NULL;
		m_depth = 0;
	}

	static Node * createNode(const T & data)
	{
		Node * node = new Node;
		node->next = NULL;
		node->data = data;
		sSingleLinkListStackAllocCount++;
		return node;
	}

	static void destroyNode(Node * node)
	{
		if(node)
			sSingleLinkListStackAllocCount--;
		delete node;
	}

public:
	CSingleLinkListStack()
	{
		init();
	}

protected:
	CSingleLinkListStack( const CSingleLinkListStack & aCopy )
	{
		ATLASSERT(!"NOT FULLY IMPLEMENTED NOR TESTED - This code Should be unreachable.  Why are you using it? -Jason");
		init();
		Copy(aCopy); 
	}

protected:
	CSingleLinkListStack operator=(const CSingleLinkListStack& aCopy)
	{
		ATLASSERT(!"NOT FULLY IMPLEMENTED NOR TESTED - This code Should be unreachable.  Why are you using it? -Jason");
		Copy(aCopy);
		return this;
	}

public:
	~CSingleLinkListStack()
	{
		DeleteStack();
	}
	
	void DeleteStack()
	{
		while( m_root )
		{
			destroyNode( PopNode() );
		}
	}

	// Place a pre-allocated node on the stack
	void PushNode(Node * node)
	{
		if(!node)
		{
			ATLASSERT(!"PushNode, can't push a null node on the stack");
			return;
		}

		// set node as the new root
		if( !m_root )
		{
			m_root = node;
			m_root->next = NULL;
		}
		else
		{
			node->next = m_root;
			m_root = node;
		}
		m_depth++;
	}

	// Push data on the stack
	void PushData(const T & data)
	{
		PushNode(createNode(data));
	}

	// Non-distructivly pop a node off the stack
	Node * PopNode()
	{
		if( !m_root )
			return NULL;

		Node * node = m_root;
		m_root = m_root->next;
		node->next = NULL;
		m_depth--;

		return node;
	}

	// Pop data off the stack, node* will be deleted
	bool PopData(T * data)
	{
		Node * node = PopNode();
		if(!node)
			return false;
		if(data)
			data = node->data;
		destroyNode(node);
		return true;
	}

	// just in case you were wondering how many elements were in the stack
	int count()
	{
		return m_depth;
	}
};

template <class T>
class CRecycleStack
{
protected:
	CSingleLinkListStack<T> m_workingStack;
	CSingleLinkListStack<T> m_recycleStack;
	typedef CSingleLinkListStack<T>::Node* NodePtr;

	CRecycleStack( const CRecycleStack & aCopy )
	{
		ATLASSERT(!"NOT FULLY IMPLEMENTED NOR TESTED - This code Should be unreachable.  Why are you using it? -Jason"); 
	}

	CRecycleStack operator=(const CRecycleStack& aCopy)
	{
		ATLASSERT(!"NOT FULLY IMPLEMENTED NOR TESTED - This code Should be unreachable.  Why are you using it? -Jason");
	}

public:
	
	CRecycleStack(int preAlloc = 0) 
	{
		growFreeSpace(preAlloc);
	}

	~CRecycleStack() {}

	void Push(const T & data)
	{
		//
		// Try to take a node from the recycle list and repurpose it in the 
		//  working stack before creating a new element
		//
		NodePtr node = m_recycleStack.PopNode();
		if(!node)
		{
			m_workingStack.PushData(data);
		}
		else
		{
			node->data = data;
			m_workingStack.PushNode(node);
		}
	}

	bool Pop(T & data)
	{
		// 
		// Instead of just getting the data, get the node and move it to the 
		//  recycler so we may use it again
		//
		NodePtr node = m_workingStack.PopNode();
		if( !node )
			return false;

		data = node->data;
		node->data = NULL;
		m_recycleStack.PushNode(node);
		return true;
	}

	// Sort of a Pre-Alloc
	void growFreeSpace(unsigned int nodes)
	{
		for( unsigned int idx = 0; idx < nodes; idx++ )
		{
			m_recycleStack.PushData(0);
		}
	}
	
	// Keep that free space in check
	void compactFreeSpace(unsigned int minimumFreeNodes = 0)
	{
		while( m_recycleStack.count() > minimumFreeNodes )
		{
			m_recycleStack.PopNode(NULL);
		}
	}

	// Number of elements in the working stack
	int count()
	{
		return m_workingStack.count();
	}

	// Number of elements in the recycle stack
	int recycleCount()
	{
		return m_recycleStack.count();
	}
};


#endif //__RECYCLE_STACK_H__