//PAC: dynamic queue
//jleblanc: 2.16.06

/*
Your queue implementation should follow the model of
the dynamic stack.

The driver program should allow the user to test each
feature, including full and empty.

The data structure "queuetype" will include fields for
the first and last nodes, and a counter to keep track
of how many nodes are in the queue.

The functions should follow the same definitions as
with the stack, with the following modifications:

*  precede each function name with the letter 'q',
such that "init" becomes "qinit", and "empty" becomes
"qempty";

*  what was "push" will now be "qadd", and what was
"pop" will be "qremove".
*/

#include <stdio.h>
#include <stdlib.h>

//Set up boolean type
typedef enum {FALSE, TRUE}  boolean; 

//element in queue
struct qnode
{           
	 char  info;
	 struct qnode  *next;
};
typedef struct qnode  qnode;

//queue management record
//it is this record that is passed to functions
struct queuetype
{         
	 int   count;          
 	qnode  *top;
	qnode *rear;
};
typedef struct queuetype  queuetype;


boolean qempty(const queuetype q)
{  
	return ((boolean) (q.top == NULL));
	// we could also test the count field, but we are emphasizing pointers
} 

boolean qfull (const queuetype q)
{  
	return FALSE; 
	//we should check available memory first, but we'll keep it simple for now
}

void qmany(int *answer, queuetype *q)
{
	*answer=q->count;
}

void qinit ( queuetype *q )
{  
	q -> count = 0;
  	q -> top   = NULL;
	q->rear = NULL;
}

//ADD to rear of the list
void qadd(char item, queuetype *q )
{
	qnode *p;
 	 if (! qfull(*q))
  	{
  		p = malloc(sizeof(qnode));   //  request the space, put address in p 
  		p -> info = item;           //  transfer the item into p's info     
  		p->next=NULL;	//set new node's pointer to NULL since at the end
		if(q->rear != NULL)
		{
			q->rear->next=p;    //set the current rear node's next to the new node (only if current rear exsists)
		}
		else
		{
			q->top=p;  // if rear is NULL then there are no nodes, so top must be set to the new node
		}
		q->rear=p; 	//set the queue's rear to the new rear
  		q -> count ++;            //  increment the 'count' field         
  	}

}

//REMOVE from the front of the list
void qremove( char *item, queuetype *q )
{
 	qnode *p;
 	if (! qempty(*q))
 	{
		*item=q->top->info;   //get the item info of first node
		p=q->top;	//p points to first node
		q->top=p->next;  //top points to the next node
		free(p);   //delete the node
		q->count--;  //decrement the count field
		if(q->top==NULL)
		{
			q->rear=NULL; //if top points to NULL then there are no nodes so rear points to NULL also
		}
	}
}

//Below here is the implimentation to Add to the Front, and Remove from the Rear.
//As the code shows it requires a bit more work.
//This code can be substituted for the 2 functions above with no difference to the user.
/*
void qadd ( char item, queuetype *q )
{  
	node *p;
 	 if (! full(*q))
  	{
  		p = malloc(sizeof(node));   //  request the space, put address in p 
  		p -> info = item;           //  transfer the item into p's info     
  		p -> next = q -> top;     //  set p's next to the old top         
 		q -> top = p;             //  set new top of stack to point to p  
  		q -> count ++;            //  increment the 'count' field         
  	}
	if(q->count==1)
	{
		q->rear=q->top;
	}
}

void qremove( char *item, queuetype *q )
{
 	node *p;
 	if (! empty(*q))
 	{
 		*item = q -> rear -> info;  // transfer the info from rear of queue 
		
		//Figure out how to do this more cleanly
		
		p     = q -> top;          //  set temporary pointer p to top      
		if(q->count == 1)
		{
			q->top=NULL;
			q->rear=NULL;
			q->count--;
			free(p);
		}
		else
		{
			for(int x=1; x<((q->count)-1); x++)
			{
				p=p->next;
			}
 			free(p->next); //kills the last one
			p->next=NULL;
			q->rear=p;
 			q -> count--;              //  decrement the count field of stack  
		}
 	}
}
*/

void main ()
{
 	queuetype queue;
 	char   choice;
	char   item;
	int howmany;

 	qinit(&queue);

 	do
 	{
 		/*printf("  (1)  add an item  ");
 		printf("  (2)  remove  an item  ");
 		printf("  (5)  quit  ");
		printf("  please enter your choice : ");*/
		
		printf("TYPE: 1 add, 2 remove, 3 empty?, 4 full?, 5 how many, 6 quit >> ");

 		fflush(stdin);
 		choice = getchar();
 		
	//Add
		if (choice == '1')
 		{  
			printf (" enter a character : ");
    			fflush(stdin);
    			item = getchar();
    			qadd( item, &queue);
 		}
 	//Remove
		else if (choice == '2')
 		{  
			if (! qempty(queue))
    			{ 
				qremove(&item, &queue);
      				printf(" here is the removed character %c \n\n", item);
    			}
    			else printf (" sorry, the queue was empty \n\n");
 		}
	//Empty?
		else if (choice == '3')
 		{  
			if(qempty(queue)==TRUE)
			{
				printf(" The queue is empty\n\n");
			}
			else
			{
				printf(" The queue is not empty\n\n");
			}
 		}
	//Full?
		else if (choice == '4')
 		{  
			if(qfull(queue)==TRUE)
			{
				printf(" The queue is full\n\n");
			}
			else
			{
				printf(" The queue is not full\n\n");
			}
 		}
	//How Many?
		else if (choice == '5')
 		{  
			qmany(&howmany, &queue);
			printf(" There are %d items in the queue \n\n", howmany);
 		}
 	} while (choice != '6');

}//END main