/*
	Queue a.k.a. FIFO

	http://en.wikipedia.org/wiki/Queue

	(c) BruXy -- http://bruxy.regnet.cz/fel/
   */

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

/*********************
 * Globalni promenne *
 *********************/

typedef struct stack{
	int data;
	int priority;
	struct stack *odkaz;
} STACK;

STACK *START; /* Zacatek fronty */

/*********************
 *     Funkce        *
 *********************/

STACK *create(void){
	STACK *test;

	test = ( (STACK *) malloc(sizeof(STACK)) );
	if(test==NULL){
		printf("Malo pameti!\n");
		return NULL;
	}
	test->odkaz=NULL;

	return test;
}

short int qprazdna(STACK *queue_top)
{
	if(queue_top == NULL){
		printf("Fronta je prazdna!\n");
		return 0;
	}
	else
		return 1;
}

void print_item(STACK *queue_item){
	printf("Item_Addr: %p = [ %d, P: %d -> %p ]\n", 
			(void *) queue_item,
			queue_item->data,
			queue_item->priority,
			(void *) queue_item->odkaz		);
}


STACK *queue_sort(STACK *queue_top, STACK *queue_end)
/* Zarazeni prvku na spravne misto */
{
	STACK *start, *stop, *pred;
	int nprior = queue_end->priority;

	stop = queue_end; 
	start = queue_top;

	/* Vlozeni pred prvni prvek */
	if(start->priority > nprior)
	{
		queue_end->odkaz = start;
		/* Musi vratit novy zacatek fronty pres glob. promennou */
		START = start = queue_end; 
	}
	else
	{
		while(start != NULL)
		{
			/* Priorita 0 - nejvyssi, 65564 - nejnizzsi */
			if( start->priority > nprior )
			{
				pred->odkaz = queue_end;
				queue_end->odkaz = start;
				break;
			}
			pred = start; /* predchozi prvek */
			start = start->odkaz;
		}
	}

	/* Projde celou frontu a nastavi NULL u odkazu posledniho prvku */
	
	if(stop->odkaz != NULL){ 
		while(start->odkaz != stop)
		{
			start = start->odkaz;
		}
		start->odkaz = NULL;
	} 
	else
		return queue_end;
	
	/* Vraci posledni prvek po odscrollovani vsim */
	return start;
}
	

STACK *push(int cislo, int priority)
{
	STACK *queue_new; 
	
	/* Vytvori novy konec */
	queue_new = create(); 

	queue_new->data = cislo;
	queue_new->priority = priority;

	return queue_new;
}


STACK *pop(STACK *queue_top)
/* Vymaze prvni cislo ve fronte a nastavi novou adresu cela fronty */
{
	STACK *queue_delete;

	if(qprazdna(queue_top) != 0){
		queue_delete = queue_top;
		free(queue_delete);
		return queue_top->odkaz;
	}
	else
	{
		return NULL;
	}
}

void print_data(STACK *queue_top){

		while(queue_top != NULL) 
		{
			printf("Addr: %p (%d) %6d -> %p \n", (void *) queue_top, queue_top->priority, queue_top->data, (void *) queue_top->odkaz);
			queue_top = queue_top->odkaz;	
		}
}

void free_data(STACK *queue_top){
	while(queue_top != NULL) 
	{
		queue_top = pop(queue_top);
	}
}

/*********************
 *       Main        *
 *********************/

int main(){
	int cislo, size, priorita;
	int citac = 0;

	STACK *s_current, *s_temp;

	printf("Kolik prvku ma obsahovat fronta?: ");
	scanf("%d", &size);
	
	/* Ukazatel na zacatek */
	START = NULL;

	for(;;) /* Zapis prvku do fronty */
	{
		if(citac == size){
			break;
		}

		printf("Zadej cislo %d. a jeho prioritu : ", citac+1);
		scanf("%d %d", &cislo, &priorita);
		printf("Ukladam %d na adresu %p.\n", cislo, (void *) s_current);

		s_temp = push(cislo, priorita);

		if(!citac){
			START = s_current = s_temp;
		}
		else{
			s_current->odkaz = s_temp;
			s_current = s_temp;

			/* Umisti prvek na spravne misto */
			s_current = queue_sort(START, s_temp); 
		}	

		printf("Addr -> %p.\n", (void *) s_current);
		putchar('\n');
		citac++;
	}

	/* Vypsani obsahu cele fronty  */
	printf("Vypis naplnenych dat, od adresy: %p\n", (void *) START);

	print_data(START);

	printf("\nKolik mam vymazat prvku?:");
	scanf("%d", &cislo);
	citac = 0;
	
	
	for(;;)
	{
		if(citac == cislo) break;

		START = pop(START);
		if(START == NULL)
			break;
		

		citac++;	
	}

	print_data(START);
	/* Na zaver po sobe uklidime */
	free_data(START); 

	return 0;
}