#pragma once

//===========================================================================//
// File:	 GQueue.h													     //
// Project:  gosGml				                                         //
// Contents:																 //
//---------------------------------------------------------------------------//
// Date      Who    Modification                                             //
// 4/10/00   DP     Created													 //
//---------------------------------------------------------------------------//
// Copyright (C) 2000 Microsoft Corp.						                 //
// All Rights reserved worldwide                                             //
// This unpublished sourcecode is PROPRIETARY and CONFIDENTIAL               //
//===========================================================================//


template<class T> class GQueue{
	public:
		GQueue();
		~GQueue();
		void Push(T* Obj);
		T* Pop();
		void Clear();

		//////////////////////////////////
		//why do this?					//
		//////////////////////////////////
		void RPush(T* Obj); //reverse push


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//Only call anything below here if you care about every clock cycle. There is a complete interface above.                //
		//The interface below is possibly faster, it gives you more control but it takes more work, and you can cause it to fail.//
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


		void FPush(T* Obj); //fast but dangerous pop. queue must not be empty. ALSO must use Push() to push the last item or the queue will be corrupt.
		T* FPop(); //fast but dangerous pop. queue must not be empty.
		bool IsEmpty();//true if queue is empty. If you find yourself using this perhaps the above interface is better for you?

	private:
		struct QueueNode{
			T* Data;
			QueueNode* Prev;
		};
		QueueNode* Bottom; //our latest push
		QueueNode* Top; //our pop victim

		GQueue(GQueue const &);//don't call this
		GQueue& operator= (GQueue const &); //don't call the assignment operator
};

template<class T> GQueue<T>::GQueue():Top(NULL),Bottom(NULL)
{
}

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

template<class T> void  GQueue<T>::Clear()
{
	while(Top)
	{
		QueueNode* Victim=Top;
		Top=Top->Prev;
		delete Victim->Data;
		delete Victim;
	}
	Bottom=0;
}

template<class T> void  GQueue<T>::Push(T* Obj)
{
	QueueNode* Temp=new QueueNode;
	Temp->Data=Obj;
	if(Bottom) //usually the case
		Bottom->Prev=Temp;
	else //rarely the case, eg the queue is empty
		Top=Temp;
	Bottom=Temp;
	Temp->Prev=NULL;
}

template<class T> void GQueue<T>::RPush(T* Obj)
{
	QueueNode* Temp=new QueueNode;
	Temp->Data=Obj;
	Temp->Prev=Top;
	Top=Temp;
	if(!Bottom)
		Bottom=Top;
}

template<class T> void  GQueue<T>::FPush(T* Obj)
{
	QueueNode* Temp=new QueueNode;
	Temp->Data=Obj;
	Bottom->Prev=Temp;
	Bottom=Temp;
	//Temp->Prev=NULL;
}

template<class T> T*  GQueue<T>::Pop()
{
	if(!Top)
		return 0;
	QueueNode* Victim = Top;
	T* Data = Victim->Data;
	Top=Top->Prev;
	if(!Top) Bottom=NULL;
	delete Victim; //delete victim, we only need the data out.
	return Data;
}

template<class T> T*  GQueue<T>::FPop()
{
	QueueNode* Victim = Top;
	T* Data = Victim->Data;
	Top=Top->Prev;
	delete Victim; //delete victim, we only need the data out.
	return Data;
}

template<class T> bool  GQueue<T>::IsEmpty()
{
	return (bool)!Bottom;
}

