///////////////////////////////////////////////////////////////////////////////
/// @file deStack.hpp
///
/// @brief Templated Stack/Queue class
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Sept 2001
/// @author Assassin
/// @remarks Creation
///
/// @date Jan 2002
/// @author Assassin
/// @remarks Bug fixes
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DESTACK_HPP
#define DESTACK_HPP


#include "deGlobalTypes.hpp"


// Structures defined in this header

typedef struct StackNode StackNode;



// Enums

#pragma warning (disable : 4710)

/// templated stack (or queue) storage class
template <class T>
class deTStack
{
public:
	enum deStackType
	{
		LIFO_STACK = 0,
		FIFO_STACK = 1,
		StackType_32bit = 0x7fffffff
	};
	deTStack();
	deTStack(deStackType PopOrder);
	deTStack(const deTStack &Stack);
	~deTStack();

	deBoolean	Push(const T& ItemData);
	deBoolean	Push(const T& ItemData, T* &ref);
	deBoolean	Pop();
	deBoolean	Pop(T & target);
	T*			Peek(int ItemOffset);
	T*			Peek();
	deBoolean	Clear();
	deBoolean	isEmpty()	{ return (ItemCount == 0); }
	int	Length(void)	{ return ItemCount; }
	deStackType GetStackType(void) { return StackType; }
	void SetStackType(deStackType PopOrder) { StackType = PopOrder; }
	bool HasData(T & data);

	class TStackNode
	{
	public:
		TStackNode(const T & ref) : Data(ref) {}

		TStackNode * Next;
		TStackNode * Prev;
		T Data;
	};

private:
	TStackNode	*Head;
	TStackNode	*Tail;
	int			ItemCount;
	deStackType	StackType;

	TStackNode *InsertItem(TStackNode *PrevItem, TStackNode *NextItem, const T& ItemData);
	TStackNode *AppendItem(const T& ItemData);
	deBoolean RemoveItem(TStackNode *sn);
	T* GetFirstItem(TStackNode *&sn);
	T* GetLastItem(TStackNode *&sn);
	T* GetNextItem(TStackNode *&sn);
	T* GetPrevItem(TStackNode *&sn);
};


/*********************************************************************/
// templated implementation below
/*********************************************************************/


template <class T>
deTStack<T>::deTStack()
{
   ItemCount = 0;
   Head      = NULL;
   Tail      = NULL;
   StackType = LIFO_STACK;
}

template <class T>
deTStack<T>::deTStack(deStackType PopOrder)
:StackType(PopOrder)
{
   ItemCount = 0;
   Head      = NULL;
   Tail      = NULL;
}

template <class T>
deTStack<T>::deTStack(const deTStack<T> &Stack)
{
   TStackNode *sn;

   ItemCount	= 0;
   Head			= NULL;
   Tail			= NULL;
   StackType	= Stack.StackType;

   if (Stack.Head == NULL)
      return;

   sn = Stack.Head;

   while (sn != NULL)
   {
      AppendItem(sn->Data);
      sn = sn->Next;
   }
}

template <class T>
deTStack<T>::~deTStack()
{
	Clear();
}


template <class T>
deBoolean deTStack<T>::Push(const T& ItemData)
{
	TStackNode *sn;

	sn = AppendItem(ItemData);

	if (sn == NULL)
		return (DE_FALSE);

	return (DE_TRUE);
}

template <class T>
deBoolean deTStack<T>::Push(const T& ItemData, T* &ref)
{
	TStackNode *sn;
	
	sn = AppendItem(ItemData);
	
	if (sn == NULL)
		return (DE_FALSE);

	ref = &(sn->Data);
	return (DE_TRUE);
}

template <class T>
deBoolean deTStack<T>::Pop()
{
	TStackNode *sn = NULL;

	if (ItemCount == 0)
		return DE_FALSE;

	if (StackType == LIFO_STACK)
		GetLastItem(sn);
	else
		GetFirstItem(sn);

	if (!RemoveItem(sn))
	{
		//Need error handling here
	}

	return DE_TRUE;
}

template <class T>
deBoolean deTStack<T>::Pop(T & target)
{
	TStackNode *sn = NULL;
	T *pData = NULL;

	if (ItemCount == 0)
		return DE_FALSE;

	if (StackType == LIFO_STACK)
		pData = GetLastItem(sn);
	else
		pData = GetFirstItem(sn);

	target = *pData;

	if (!RemoveItem(sn))
	{
		//Need error handling here
	}

	return DE_TRUE;
}

template <class T>
T* deTStack<T>::Peek(int ItemOffset)
{
	if (ItemCount == 0)
	  return NULL;

	if ((ItemCount < (ItemOffset + 1)) || (ItemOffset < 0))
		return NULL;
	
	TStackNode *sn = NULL;
	T* pData = NULL;
	int i;
	
	if (StackType == LIFO_STACK)
	{
		pData = GetLastItem(sn);

		for (i = ItemOffset; i > 0; i--)
		{
			pData = GetPrevItem(sn);
		}
	}
	else
	{
		pData = GetFirstItem(sn);

		for (i = ItemOffset; i > 0; i--)
		{
			pData = GetNextItem(sn);
		}
	}

	return pData;
}

template <class T>
T* deTStack<T>::Peek()
{
	if (ItemCount == 0)
		return NULL;
	
	TStackNode * sn = NULL;
	if (StackType == LIFO_STACK)
	{
		return GetLastItem(sn);
	}
	else
	{
		return GetFirstItem(sn);
	}
}

template <class T>
deBoolean deTStack<T>::Clear()
{
   TStackNode *sn;
   TStackNode *Nextsn;

   sn = Head;

   while (sn != NULL)
   {
      Nextsn = sn->Next;
      delete sn;
      --ItemCount;
      sn = Nextsn;
	}

   Head = NULL;
   Tail = NULL;

   if (ItemCount != 0)
   {
	   //assert(NULL == "Failed to remove number of nodes matching internal counter in deTStack");
	   return DE_FALSE;
   }
   return DE_TRUE;
}

template <class T>
typename deTStack<T>::TStackNode * deTStack<T>::InsertItem(TStackNode *PrevItem, TStackNode *NextItem, const T& ItemData)
{
   TStackNode *NewNode;

   NewNode = new TStackNode(ItemData);

   if (NewNode == NULL)
   {
      //Need error handling here
      return NULL;
   }

   NewNode->Data = ItemData;
   NewNode->Prev = PrevItem;
   NewNode->Next = NextItem;

   // Append
   if (NextItem == NULL)
      Tail = NewNode;

   // Prepend
   if (PrevItem == NULL)
      Head = NewNode;

   //Set Prev/Next pointers
   if (PrevItem != NULL)
      PrevItem->Next = NewNode;

   if (NextItem != NULL)
      NextItem->Prev = NewNode;

   // Increment node count
   ++ItemCount;

   return NewNode;
}

template <class T>
typename deTStack<T>::TStackNode * deTStack<T>::AppendItem(const T& ItemData)
{
   return InsertItem(Tail, NULL, ItemData);
}

template <class T>
deBoolean deTStack<T>::RemoveItem(TStackNode *sn)
{
	// Unlink the node
	if (Head == sn)
	{
		if (sn->Prev == NULL)
		{
			Head = sn->Next;
			if (Head != NULL)
				Head->Prev = NULL;
		}
		else
		{
			//Need error handling here
			return DE_FALSE;
		}
	}
	if (Tail == sn)
	{
	if (sn->Next == NULL)
	{
		Tail = sn->Prev;
		if (Tail != NULL)
			Tail->Next = NULL;
	}
	else
	{
		//Need error handling here
		return DE_FALSE;
	}
	}
	else
	{
		if (sn->Prev != NULL)
		{
			sn->Prev->Next = sn->Next;
		}
		else
		{
			//Need error handling here
			return DE_FALSE;
		}

		if (sn->Next != NULL)
		{
			sn->Next->Prev = sn->Prev;
		}
		else
		{
			//Need error handling here
			return DE_FALSE;
		}
	}

	// Deallocate the node
	delete sn;

	--ItemCount;

	return DE_TRUE;
}

template <class T>
bool deTStack<T>::HasData(T & data)
{
	TStackNode * n = Head;
	while (n)
	{
		if (n->Data == data)
			return true;
		n = n->Next;
	}
	return false;
}

template <class T>
T* deTStack<T>::GetFirstItem(TStackNode *&sn)
{
	if (Head == NULL)
	{
		sn = NULL;
		return NULL;
	}

	sn = Head;

	return &(sn->Data);
}

template <class T>
T* deTStack<T>::GetLastItem(TStackNode *&sn)
{
	if (Tail == NULL)
	{
		sn = NULL;
		return NULL;
	}

	sn = Tail;

	return &(sn->Data);
}

template <class T>
T* deTStack<T>::GetNextItem(TStackNode *&sn)
{
	if (sn == NULL)
		return NULL;

	if (sn->Next == NULL)
	{
		sn = NULL;
		return NULL;
	}

	sn = sn->Next;

	return &(sn->Data);
}

template <class T>
T* deTStack<T>::GetPrevItem(TStackNode *&sn)
{
	if (sn == NULL)
		return NULL;

	if (sn->Prev == NULL)
	{
		sn = NULL;
		return NULL;
	}

	sn = sn->Prev;

	return &(sn->Data);
}

//#pragma warning (default : 4710)

#endif  // End DESTACK_HPP
