/*
 * Uzyteczna implementacja kolejki FIFO. Sposob uzycia:
 *   Queue *Q;
 *   Q = createQueue( dane );   (utworzenie kolejki z pierwszym elementem)
 *   Q = enqueue( dane );       (dodanie elementu)
 *   dane = dequeue( &Q );      (usuniecie elementu)
 *   freeQueue( &Q );           (usuniecie calej kolejki)
 *
 * Ideograficznie kolejka ta wyglada tak:
 *
 * {____}---->{____}---->{____}---->null
 *  head    head->next
 *
 * Ta wersja kolejki uzywa uogolnionego typu danych
 * dlatego mozna trzymac w niej dowolne elementy.
 * Niestety, wymaga to odpowiedniej konwersji wskaznikow
 * przy ich wyciaganiu.
 *
 * [c] piotao, 20051205
 */

#ifndef __FIFO__
#define __FIFO__
#include <stdlib.h>

typedef struct QueueNode {
	void* data;
	struct QueueNode *next;
} QueueNode;

typedef struct {
	int size;
	QueueNode *first;
	QueueNode *last;  // dla przyspieszenia dzialania kolejki - nie trzeba szukac ostatniego bo go pamietamy
} Queue;

QueueNode* newNode(){
	return (QueueNode*) malloc( sizeof( QueueNode ) );
}

int sizeQueue( Queue* queue ){
	QueueNode *tmp;
	int size = 0;
	if(queue != NULL){
		tmp = queue->first;
		while( tmp != NULL ){
			size++;
			tmp = tmp->next;
		}
	}
	return size;
}

Queue* newQueue( QueueNode* head ){
	Queue* Q = (Queue*) malloc( sizeof(Queue) );
	Q->first = head;
	Q->size = sizeQueue(Q);
	return Q;
}

QueueNode *defNode( QueueNode *node, void* data, QueueNode *nextNode ){
	if(node != NULL){
		node->data = data;
		node->next = nextNode;
	}
	return node;
}

Queue* createQueue( void* data ){
	return newQueue( defNode( newNode(), data, NULL ));
}

Queue* enqueue( Queue* queue, void* data ){
	QueueNode* tmp;
	if(queue == NULL){
		queue = newQueue( defNode( newNode(), data, NULL) );
		queue->last = queue->first;
	}
	else{
		tmp = defNode( newNode(), data, NULL );
		queue->last->next = tmp;
		queue->last = queue->last->next;
		queue->size++;
	}
	return queue;
}

void* dequeue(Queue **queue){
	QueueNode *tmp;
	void* data;
	if(queue && *queue && (*queue)->first){
		tmp = (*queue)->first;
		(*queue)->first = (*queue)->first->next;
		(*queue)->size--;
		data = tmp->data;
		free(tmp);
		if((*queue)->size == 0){
			free(*queue);
			*queue = NULL;
		}
		return data;
	}
	else{
		return NULL;
	}
}

void freeQueue(Queue** queue){
	QueueNode *tmp1,*tmp2;
	if(queue && *queue){
		tmp1 = (*queue)->first;
		while( tmp1 ){
			tmp2 = tmp1->next;
			free(tmp1);
			tmp1 = tmp2;
		}
		free(*queue);
		*queue = NULL;
	}
}

#endif