/**********************************************************
* queue.c: This program creates a priority queue for use
* with compression.c
***********************************************************/
#include "compress.h"

/*q_mknode: This function creates a node for a character, c.
* This function is also used to create the first node in
* a queue. This function returns a pointer to the created node*/
qtptr q_mknode(char	c) {
	qtptr qnode;
	
	qnode =	malloc(sizeof(qtnode));
	qnode->c = c;
	qnode->priority	= 1;
	qnode->next	= NULL;
	qnode->previous	= NULL;

	qnode->left	= NULL;
	qnode->right = NULL;

	return qnode;
}

/*q_enqueue: This function places qnode in the proper location
* in the queue, designated by the pointer to the first node,
* qfirst. This function then returns the pointer to the first node*/

qtptr q_enqueue(qtptr qfirst,qtptr qnode) {
	qtptr qcurrent;

	qcurrent = qfirst;
	/*Go through queue to find proper location for node*/
	while(qcurrent->priority < qnode->priority)	{
		/*If qtemp has the greatest	priority*/
		if(qcurrent->next == NULL) {
			break;
		}
		qcurrent = qcurrent->next;
	}

	if(qcurrent->priority >= qnode->priority) {
	/*If proper location has been found, insert into queue*/
		qnode->previous	= qcurrent->previous;
		qnode->next	= qcurrent;
		if(qcurrent->previous != NULL) {
			qcurrent->previous->next = qnode;
		}
		else {
			qfirst = qnode;
		}
		qcurrent->previous = qnode;
	}

	/*qnode	has	the	greatest priority value*/
	else {
		qcurrent->next = qnode;
		qnode->previous	= qcurrent;
		qnode->next	= NULL;
	}
	/*Return pointer to	first element in queue*/
	return qfirst;
}

/*q_dequeue: This function obtains a pointer to the first
element of a queue and a pointer to a node. The pointer to a node
is linked to the element in the queue with the lowest priority
and a pointer to the first element in the queue is returned.*/

qtptr q_dequeue(qtptr qfirst,qtptr *qnode) {
	*qnode = qfirst;
	qfirst = qfirst->next;
	if(qfirst != NULL) {
		qfirst->previous = NULL;
	}
	return qfirst;
}
/*q_addInst: Adds a	character c, into a queue desginated by qfirst.
* qfirst is a pointer to the first element in the node. This function
* then returns a pointer to the first element in the node*/	

qtptr q_addchar(qtptr qfirst,char c)	{
	qtptr qcurrent,qtemp;

	/*Set current to first location	in queue*/
	qcurrent = qfirst;
	/*Traverse the queue until matching	character is found*/
	while(qcurrent != NULL)	{
		/*If match is found, break*/
		if(qcurrent->c == c) {
				break;
		}
		qcurrent = qcurrent->next;
	}
	
	/*If not match has been	found...*/
	if(qcurrent	== NULL) {
		qtemp =	q_mknode(c);
		qfirst = q_enqueue(qfirst, qtemp);
	}
	/*If match has been	found*/
	else {
		/*Increase priority*/
		(qcurrent->priority)++;
		
		/*Remove node from queue*/
		if((qcurrent->previous == NULL)&&(qcurrent->next==NULL)) {
			/*If not other elements in queue, set qfirst to null*/
			qfirst = NULL;
		}
		else if(qcurrent->previous == NULL) {
			/*If removing first element..*/
			qcurrent->next->previous = NULL;
			qfirst = qcurrent->next;
		}
		else if	(qcurrent->next	== NULL) {
			/*If removing last element*/
			qcurrent->previous->next = NULL;
		}
		else {
			/*If removing element in the middle*/
			qcurrent->previous->next = qcurrent->next;
			qcurrent->next->previous = qcurrent->previous;
		}
					
		/*Temporarily save removed node*/
		qtemp =	qcurrent;
		/*If queue is not empty, enqueue*/
		if(qfirst != NULL) {
			qfirst = q_enqueue(qfirst,qtemp);
		}
		/*If queue is empty, then set qfirst to the current node*/
		else {
			qfirst = qcurrent;
		}
	}
	/*Return pointer to first node in queue*/
	return qfirst;
}

/*q_filestore: This function takes a file pointer
* as well as a pointer to the first element in the 
* queue and stores the queue in the output file. */
void q_filestore(qtptr qfirst, FILE *output) {
	int nelems = 0;					/*Counter for the number of elements in queue*/
	char cout;						/*Temporary character for storing elements to file*/
	qtptr qtemp;					/*Temporary pointer to element in queue*/

	qtemp = qfirst;
	/*Calculate number of elements in queue*/
	while(qtemp != NULL) {
		nelems++;
		qtemp = qtemp->next;
	}
	/*Transform integer into character and store into file*/
	cout = nelems & 0xFF;
	fputc(cout,output);
	
	qtemp = qfirst;
	/*store all elements in queue into file*/
	while(qtemp != NULL) {
		fputc(qtemp->c,output);
		/*Transform integer into character and store into file*/
		cout = qtemp->priority & 0x000000FF;
		fputc(cout,output);
		qtemp = qtemp->next;
	}
}