/*
 * pqueue.c
 *
 * Implementation of priority queue manipulation functions
 * 
 */


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


pqueue_t* pqueue_create(int init_size) {
	pqueue_t *queue;
	queue = (pqueue_t*) malloc(sizeof(pqueue_t));
	queue->array = (pqueue_element_t**) malloc(sizeof(pqueue_element_t*) * init_size);
	queue->size = 1;
	queue->avail = init_size;
	return queue;
}


int pqueue_destroy(pqueue_t *queue) {
	if (queue == NULL ) {
		return 0;
	}
	if (queue->size != 1) {
		return -1;
	} else {
		free(queue->array);
		free(queue);
		return 0;
	}
}


void pqueue_enqueue(pqueue_t *queue, timer_t *timer, int prio) {
	if (queue == NULL || timer == NULL) {
		return;
	}
	
	pqueue_element_t *new_element;
	new_element = (pqueue_element_t*) malloc(sizeof(pqueue_element_t));
	new_element->timer = timer;
	new_element->prio = prio;
	
	if (queue->size >= queue->avail) {
		int new_size = 2 * queue->size;
		queue->array = (pqueue_element_t**) realloc
			(queue->array, sizeof(pqueue_element_t*) * new_size);
		queue->avail = new_size;
	}
	
	int i = queue->size++;
	while(i > 1 && queue->array[i / 2]->prio > prio) {
		queue->array[i] = queue->array[i / 2];
		i /= 2;
	}
	
	queue->array[i] = new_element;
}


int pqueue_is_empty(pqueue_t *queue) {
	if (queue == NULL || queue->size == 1) {
		return 1;
	} else {
		return 0;
	}
}


int pqueue_minimum(pqueue_t *queue) {
	if (queue != NULL && queue->size > 1) {
		return queue->array[1]->prio;
	} else {
		return 0;
	}
}


timer_t* pqueue_dequeue(pqueue_t *queue) {
	if (queue == NULL || queue->size == 1) {
		return NULL;
	}
	
	int i = 1, j;
	pqueue_element_t *out_element = queue->array[1];
	pqueue_element_t *temp = queue->array[--queue->size];
	
	while (i <= queue->size / 2) {
		j = 2 * i;
		if (j < queue->size && queue->array[j]->prio > queue->array[j + 1]->prio) {
			j++;
		}
		
		if (queue->array[j]->prio >= temp->prio) {
			break;
		}
		
		queue->array[i] = queue->array[j];
		i = j;
	}
	
	queue->array[i] = temp;
	
	timer_t *timer = out_element->timer;
	free(out_element);
	return timer;
}


int pqueue_decrease_prio(pqueue_t *queue, int id, int prio) {
	if (queue == NULL || queue->size == 1) {
		return -1;
	}
	
	int i;
	
	for (i = 1; i < queue->size; i++) {
		if (queue->array[i]->timer->id == id) {
			queue->array[i]->prio = prio;
			break;
		}
	}
	
	if (i >= queue->size) { /* there is no timer with such id */
		return -1;
	}
	
	pqueue_element_t *element;
	
	while(i > 1 && queue->array[i / 2]->prio > prio) {
		element = queue->array[i];
		queue->array[i] = queue->array[i / 2];
		queue->array[i / 2] = element;
		i /= 2;
	}
	
	return 0;
}
