//
//	p.305
//	Goal: with circular 
//


#include <iostream>
using namespace std;

struct NodeType
{	
	int info;
	NodeType* next;
};

class QueType
{
	NodeType* rear;
public:
	QueType()	// p.303
	{
		rear = NULL;
	}
	void MakeEmpty()
	{
		// use rear;
		if ( rear != NULL )
		{
			NodeType* t1 = rear->next;
			NodeType* t2 = rear->next;	
			while( t1 !=rear )
			{	t1 = t1->next;
				delete t2;
			}	
			delete rear;
			rear = NULL;
		}
	}	
	~QueType()
	{
		MakeEmpty();
	}
	bool IsEmpty()	const
	{	return rear == NULL;
	}
	void Enqueue(int newItem)	// p.304
	{
		// empty -> add one node
		if( rear == NULL )
		{	NodeType* temp = new NodeType;
			temp->info = newItem;
			temp->next = temp;
			rear = temp;
		}	
		else
		{
			NodeType* temp = new NodeType;
			temp->info = newItem;	// fill the value
			temp->next = rear->next;// circular
			rear->next = temp;	// enqueue to the rear
			rear = temp;		// let rear point to the new
		}
	}
	void Dequeue(int& item)
	{	
		// empty
		if( rear == NULL )	cout << "\n\nEmpty queue. Can't deq. \n\n";
		else if ( rear == rear->next )
		{	item = rear->info;
			delete rear;
			rear = NULL;
		}
		else
		{	NodeType* front = rear->next;	// front node
			item = front->info;
			// move the front 
			rear->next = front->next;
			delete front;
		}
	}
	void Print() const
	{	
	   if( rear != NULL )
	   {
		NodeType* temp = rear->next;
		while(temp != rear) 
		{
			cout << temp->info << " ";
			temp = temp->next;
		}
		cout << rear->info << " ";
		cout << "\n";
	   }
	   else
	   {	cout << "\n\nEmpty queue.\n\n";    }
	}
};

void menu();

int main()
{
	QueType me;
	int item;
	char ch;

	menu();
	cin >> ch;
	while(tolower(ch) != 'q')
	{
		if ( tolower(ch) == 'e')
		{
			cout << "\nInput the new value: ";
			cin >> item;
			me.Enqueue(item);
			cout << "Enqueue " << item << " successfully.\n\n";
		}
		else if ( tolower(ch) == 'd')
		{
			if( ! me.IsEmpty() )
			{
				me.Dequeue(item);
				cout << "\n\n" << item << " is deq. \n\n";
			}
			else	cout << "\n\nEmpty. \n\n";
		}	
		else if ( tolower(ch) == 'p')
		{
			cout << "\nThe queue is: " ;
			me.Print();
		}
		menu();
		cin >> ch;
	}

	cout << "\n\nDone.\n\n";
	return 0;
}

void menu()
{
	cout << "\n\n Queue with Circular List\n";
	cout << "===============================\n";
	cout << "E	Enqueue an item.\n";
	cout << "D	Dequeue.\n";
	cout << "P	Print.\n";
	cout << "Q	Quit.\n";
	cout << "===============================\n";
	cout << "Your selection: ";
}