/*
 * queue.c
 */
#include <stdlib.h>
#include<stdio.h>
#include "queue.h"
 
 
/* 
 * Initialize the queue.  Must be called before any other
 * queue function
 */
void q_init ( Queue *theQ )
{
	theQ -> front	=	NULL;
	theQ -> rear	=	NULL;
}
 
/*
 * Add value to the back of the queue 
 * returns 1 on success, 0 on failure
 */
int	q_enqueue ( Queue *theQ, int value )
{
	Node  *p = (Node *)malloc(sizeof(Node));
 
	if(!p)
	{
		printf("Malloc Failed.\n");
		return 0;
	}
	else
	{
		//make the element of the new node = value
		p -> element = value;
		p -> next		= NULL;
	}
 
	if(theQ -> front == NULL) //change where the front and rear 
	{							//pointers point
		theQ -> front	= p;
		theQ -> rear	= p -> next;
	}
	else
	{
		theQ -> rear	=  p;		
		theQ -> front -> next = theQ -> rear;	
        }
	return 1;
}
 
/*
 * Remove the first element from the queue
 * returns 1 on success, 0 on failure
 */
int	q_dequeue ( Queue *theQ, int *value)
{
	Node  *p;
 
	if( theQ -> front == NULL)
	{
		printf ("Queue is empty. Cannot dequeue.\n");
		return 0;
	}
 
	p = theQ -> front;
	*value = p -> element;
 
	if(theQ -> front == theQ -> rear)
	{
		theQ -> front = NULL;
		theQ -> rear = NULL;
                free(p -> element);
                free(p);	
        }
 
	else
	{
		theQ -> front = p -> next;
		free(p -> element);
		free(p);
	}
	return 1;	
}
 
/*
 * Is the queue empty?
 * returns 1 if the queue is empty, 0 otherwise
 */
int	q_isEmpty ( Queue *theQ )
{
	if(theQ -> front == NULL)
	{
		//printf ("Queue is empty.\n");
		return 1;
	}
	else
	{
		return 0;
	}
}

/*
 * queue.h
 */
#ifndef __QUEUE_H__
#define __QUEUE_H__
 
/*
 * This structure holds the individual nodes
 * in the queue structure
 */
typedef struct Node
{
	int			element;
	struct Node *next;
} Node;
 
/*
 * This is the actual Queue.  Notice there
 * are two Node pointers.  One points to
 * the front of the queue and one points to 
 * the rear of the queue
 */
typedef struct Queue
{
	Node	*front;
	Node	*rear;
} Queue;
 
/* 
 * Initialize the queue.  Must be called before any other
 * queue function
 */
void q_init ( Queue *theQ );
 
/*
 * Add value to the back of the queue 
 * returns 1 on success, 0 on failure
 */
int	q_enqueue ( Queue *theQ, int value );
 
/*
 * Remove the first element from the queue
 * returns 1 on success, 0 on failure
 */
int	q_dequeue ( Queue *theQ, int *value);
 
/*
 * Is the queue empty?
 * returns 1 if the queue is empty, 0 otherwise
 */
int	q_isEmpty ( Queue *theQ );
 
#endif

/*
 * queuetest.c
 */
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
 
int main ( )
{
	/* Here are two different ways to create a queue.
	 * the first one allocates the queue on the stack, so we
	 * need to pass the address of this queue to the q_ methods
	 * 
	 * The second one uses a pointer, and allocates storage for the
	 * queue dynamically.  This means we have to call free on the
	 * pointer to deallocate the memory.
	 */
	Queue	q1;
	Queue	*q2 = (Queue *)malloc (sizeof(Queue));
	Queue	*q3 = (Queue *)malloc (sizeof(Queue));
	int	i, j, passed;
 
	if (!q2 || !q3)
	{
		printf ("Failed allocation.\n");
		return 0;
	}
 
	q_init (&q1);	/* Note the use of the & operator */
	q_init (q2);
	q_init (q3);
 
	/*
	 * Make sure that newly created queues are empty
	 */
	if (q_isEmpty(&q1))
		printf ("Test 1 passed. Queue is empty.\n");
	else
		printf ("Test 1 failed. Newly created queue is not empty\n");
 
	if (q_isEmpty(q2))
		printf ("Test 2 passed. Queue is empty.\n");
	else
		printf ("Test 2 failed. Newly created queue is not empty\n");	
 
	/*
	 * Enqueue 1000 integers and verify that the values
	 * are dequeued in the correct order
	 */
	passed = 1;
	for ( i = 0; i < 1000; i++ )
	{
		if ( !q_enqueue(&q1, i) )
		{
			passed = 0;
			break;
		}
	}
	if (passed)
	{
		for ( i = 0; i < 1000; i++ )
		{
			int	val;
			if (!q_dequeue (&q1, &val) )
			{
				passed = 0;
				break;
			}
			if ( val != i )
			{
				passed = 0;
				break;
			}
		}
		if (passed)
			printf ("Test 3 passed. Enqueue and Dequeue\n");
		else
			printf ("Test 3 failed. Dequeue\n");
	}
	else
	{
		printf ("Test 3 failed.  Didn't enqueue.\n");
	}
 
	/*
	 * enqueue 1 item, then dequeue it.
	 * then enqueue two more items and dequeue them.
	 * then verify the queue is empty.
	 */
	if (q_enqueue (q2, 7))
	{
		if (q_isEmpty(q2))
		{
			printf ("Test 4 failed. empty after enqueue\n");
		}
		else
		{
			int	val;
			if (q_dequeue(q2, &val))
			{
				if (val == 7)
				{
					if (q_enqueue(q2, 9))
					{
						if (q_enqueue(q2, 11))
						{
							int val1, val2;
 
							if (q_dequeue(q2,&val1))
							{
								if (q_dequeue(q2,&val2))
								{
									if (val1 == 9 && val2 == 11 && q_isEmpty(q2) )
									{
										printf ("Test 4 passed.\n");
									}
									else
									{
										printf ("Test 4 failed. 9 & 11\n");
									}
								}
								else
								{
									printf ("Test 4 failed. dequeue 11\n");
								}
							}
							else
							{
								printf ("Test 4 failed. dequeue 9.\n");
							}
						}
						else
						{
							printf("Test 4 failed. enqueue 11\n");
						}
					}
					else
					{
						printf ("Test 4 failed. enqueue 9\n");
					}
				}
				else
				{
					printf ("Test 4 failed. dequeue != 7\n");
				}
			}
			else
			{
				printf("Test 4 failed. dequeue 7\n");
			}
		}
	}
	else
	{
		printf ("Test 4 failed. enqueue 7.\n");
	}
 
	if (q_isEmpty(q3))
		printf ("Test 5 passed. Queue is empty.\n");
	else
		printf ("Test 5 failed. Newly created queue is not empty\n");	
 
	passed = 1;
	for ( i = 0; i < 10; i++ )
	{
		q_enqueue(q3, i);
	}
 
	for ( j = 0; j < 5; j++ )
	{
		int val;
		if ( !q_dequeue (q3, &val) )
		{
			passed = 0;
		}
		else
		{
			if ( val != j )
			{
				passed = 0;
				break;
			}
		}
	}
 
	if ( passed )
	{
		int val;
 
		for ( i = 10; i < 20; i++ )
		{
			q_enqueue ( q3, i);
		}
		for ( j = 5; j < 20 ; j++ )
		{
			if ( !q_dequeue (q3, &val))
			{
				passed = 0;
				break;
			}
			else
			{
				if ( val != j )
				{
					passed = 0;
					break;
				}
			}
		}
	}
 
	if ( passed )
		printf ("Test 6 passed.\n");
	else
		printf ("Test 6 failed.\n");
 
	/* Not technically required since we're about to end the program
	 * but it is a good habit to free any memory you malloc
	 */
	free(q2);
	free(q3);
	return 0;
}