//PAC: dynamic queue with strings
//jleblanc: 2.27.06


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

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

//element in queue
struct qnode
{           
	 char word[50]; 
	 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 
  		
		strcpy(p->word, item);   //copy the item into p's word
  		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))
 	{
		strcpy(item, q->top->word); //get the word 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
		}
	}
}

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

 	qinit(&queue);

 	do
 	{		
		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 word : ");
    			fflush(stdin);
			scanf("%s", item);
    			qadd( item, &queue);
 		}
 	//Remove
		else if (choice == '2')
 		{  
			if (! qempty(queue))
    			{ 
				qremove(item, &queue);
      				printf(" here is the removed character %s \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