//Syed Rais Ahmad
//Assignment # 5 Quest 3
//Empty,insert remove of dyna Priority pQueue

#include<iostream.h>

//A node in a queue
class llistItem
{
public:
	int item;
	llistItem * nxtItem;
};


//pQueue
class pQueue
{
private:
	llistItem *rear;
public:
	pQueue(); 
	~pQueue() {delete rear;}; 

	bool Insert(int);
	int Remove();
	bool Empty();
};


//create rear and put NULL values in it.
pQueue::pQueue()
{
	rear = new llistItem;
	rear->nxtItem=NULL;//Empty pQueue
}



//Return an item is on stack Top. -1 if stack is empty
int pQueue::Remove()
{
	
	if (!Empty())
	{
		llistItem * front,* temp;
		int i=0;
//front gets the address of next node from rear		
		front=rear->nxtItem->nxtItem;
//if only one node is remaining then front = rear;
		if (front==rear->nxtItem) 
		{
			i=front->item; 
			delete front;
			rear->nxtItem=NULL; //empty the pQueue
			return i;
		}
//temp gets the about-to-be front node's address.
		temp=front->nxtItem;
		i=front->item;
//rear node now points to a new front node.
		rear->nxtItem->nxtItem=temp;
		delete front;
		return i;
		
	}
	return -1;
}



//Insert an int to a pQueue
bool pQueue::Insert(int insInt)
{
	llistItem * ptr,*temp,*temp2;
//insert will always need new node with new integer value in it.		
	ptr=new llistItem;
	ptr->item=insInt;

	if (Empty())
	{
//node points to itself
		ptr->nxtItem=ptr;
		rear->nxtItem=ptr;
		
	}
	else 
	{
		//if new int is > rear element
		if (insInt >= rear->nxtItem->item)
		{
			temp=rear->nxtItem->nxtItem;
			rear->nxtItem->nxtItem=ptr;
			ptr->nxtItem=temp;
			rear->nxtItem=ptr;

		}
		else
		{
			temp2=rear->nxtItem;
			temp=rear->nxtItem->nxtItem;
			while(temp->item<insInt) { temp2=temp;temp=temp->nxtItem;}
			temp=temp2->nxtItem;
			temp2->nxtItem=ptr;
			ptr->nxtItem=temp;

			
		}
	}
		return true;
}

//is pQueue Empty
bool pQueue::Empty()
{
	return (rear->nxtItem==NULL)? true : false;
}


//------- Program's main flow starts ---------------------------

main()
{
	pQueue q;

	q.Insert(1);
	q.Insert(3);
	q.Insert(22);
	q.Insert(0);
	q.Insert(99);

	cout << "\nInserted 1,3,22,0,99 to a Priority Queue.\n";
	cout << "\n1st Remove returns: " << q.Remove();
	cout << "\n2nd Remove returns: " << q.Remove();
	cout << "\n3rd Remove returns: " << q.Remove();
	cout << "\n4th Remove returns: " << q.Remove() ;
	cout << "\n5th Remove returns: " << q.Remove() ;
	cout << "\n6th Remove returns: " << q.Remove() << '\n';

	return 0;

}