#include <stdlib.h>

/*	Queue ADT Type Defintions
	Source: G & F
	Modification: Peter Brusilovsky
*/


struct intqueue {
		int *queueAry;
		int maxSize;
		int count;
		int front;
		int rear;
};		
		
/*	Prototype Declarations */
	struct intqueue *createQueue  ( int maxSize );
	struct intqueue *destroyQueue (  struct intqueue *queue );

	int   dequeue    ( struct intqueue *queue, int *dataOutPtr );
	int   enqueue    ( struct intqueue *queue, int datain );
	int   queueFront ( struct intqueue *queue, int *dataOutPtr );
	int   queueRear  ( struct intqueue *queue, int *dataOutPtr );
	int   queueCount ( struct intqueue *queue );
	
	int   emptyQueue ( struct intqueue *queue );
	int   fullQueue  ( struct intqueue *queue ); 

/*	End of Queue ADT Definitions */


/*	=============== createQueue ==============	*
/*	Allocates memory for a queue head node from dynamic 
	memory and returns its address to the caller.
	Pre    nothing.
	Post   head has been allocated and initialized
	Return headŐs address if successful, null if overflow 
*/
struct intqueue  *createQueue (int maxSize)
{
	struct intqueue   *queue;

	queue = (struct intqueue  *) malloc (sizeof (struct intqueue));
	if (queue != NULL) {
	/* head structure created. Now allocate queue */
		queue->queueAry = (int *) malloc(maxSize * sizeof(int));
		queue->front   = -1;
		queue->rear    = -1;
		queue->count   =  0;
		queue->maxSize = maxSize;
	}
	return queue;
}	/* createQueue */

/*	=============== enqueue ============== */
/*	This algorithm inserts data into a queue.
	    Pre    queue has been created
	    Post   data have been inserted
	    Return true if successful, false if overflow. 
*/
int enqueue (struct intqueue  *queue, 
             int   datain)
{
	if (queue->count == queue->maxSize)
		return 0;
		
	(queue->rear)++;
	if (queue->rear  == queue->maxSize)
	    /* Queue wraps to element 0 */
	    queue->rear  =  0;
	queue->queueAry[queue->rear] = datain; 
		 
	if (queue->count == 0)
		{
		 /* Inserting into null queue */
		 queue->front  = 0;
		 queue->count  = 1;
		} /* if */
	else
		 (queue->count)++;

	return 1;
}	/* enqueue */

/*	=============== dequeue ============== */
/*	This algorithm deletes a node from the link list.
	    Pre    Queue has been created.
	    Post   Data at front of queue returned to user 
	    Return boolean true if successful, false if underflow. 
*/
int dequeue (struct intqueue *queue, 
             int *dataOutPtr) 
{
	if (!queue->count)
		return 0;
	 
	*dataOutPtr = queue->queueAry[queue->front];
	(queue->front)++;
	if (queue->front == queue->maxSize)
	    /* queue front has wrapped to element 0 */
	    queue->front =  0;
	if (queue->count == 1)
	    /* Deleted only item in queue */
	    queue->rear = queue->front = -1;
	(queue->count)--;

	return 1;
}	/* dequeue */

/*	=============== queueFront ============== */
/*	Retrieve the data at the front of the queue
	without changing the queue contents. 
	    Pre    queue is a pointer to an initialized queue.
	    Post   Data (pointer) passed back to caller
	    Return true if successful, false if underflow. 
*/
int queueFront (struct intqueue  *queue,
                int *dataOutPtr) { 
	if (!queue->count) 
	    return 0;
	else {    
		*dataOutPtr = queue->queueAry[queue->front];
      	return 1;
     } /* else */
}	/* queueFront */

/*	=============== queueRear ============== */
/*	This algorithm retrieves the data at the rear of the 
	queue without changing the queue contents. 
	Pre    queue is a pointer to an initialized queue.
	Post   Data passed back to caller
	Return boolean true if successful, false if underflow. 
*/
int queueRear (struct intqueue   *queue,
                      int *dataOutPtr) {
	if (!queue->count) 
	    return 0;
	else {    
		*dataOutPtr = queue->queueAry[queue->rear];
      	return 1;
     } /* else */

}	/* queueRear */

/*	=============== fullQueue ============== */
/*	This algorithm checks to see if a queue is full. The queue
	is full if the array is full. 
	Pre    queue is a pointer to a queue head node
	Return true if full, false if room for another node.
*/
int fullQueue (struct intqueue  *queue ) 
{
	return ( queue->count == queue->maxSize);

}	/* fullQueue */

/*	=============== destroyQueue ============== */
/* 	This function deletes the queue and array memory
	
	Pre    Queue is a valid queue.
	Post   All data have been deleted and recycled.
	Return null pointer
*/
struct intqueue *destroyQueue (struct intqueue *queue) 
{
/*	Statements */
	if (queue)
	    {
	     free (queue->queueAry); 
	     free (queue);
	    } /* if */
	return NULL;
}	/* destroyQueue */

/*	=============== emptyQueue ============== */
/*	This algorithm checks to see if a queue is empty 
		Pre		queue is a pointer to a queue head node
		Return		boolean true if empty, false if queue has data 
*/
int emptyQueue (struct intqueue *queue) 
{
/*	Statements */

	return (queue->count == 0);
}	/* emptyQueue */