#include "PriorityQueue.h"


#define parent(u) (u / 2)
#define left(u) (u * 2)
#define right(u) (u * 2 + 1)

/* Utility function to check for NULL, and exit if so. */
void NULLCHECK(void* p, const char* sFunc) {
	if(p == NULL) {
		printf("PriorityQueue.c %s NULL argument. \n", sFunc);
		exit(1);
	}
}


typedef struct PriorityQueue {
	/* Array length and heapsize, respectively. */
	int n, heapsize;
	
	/* Array elements. */
	int* A;
	
	/* Inverse array elements. */
	int* I;
	
	/* Pointer to an external array. */
	double* key;
} PriorityQueue;


/* Private function, swaps array values in elements a and b. */
void swap(PriorityQueueRef Q, int a, int b) {
	int vA = Q->A[a], vB = Q->A[b];

	Q->A[a] = vB;
	Q->A[b] = vA;
	
	Q->I[vB] = a;
	Q->I[vA] = b;
}

/* Private function, maintains min heap property. */
void minHeapify(PriorityQueueRef Q, int i) {
	if(Q->heapsize < 1)
		return;
		
	int l = left(i), r = right(i);
	
	int smallest = i;
	if(l <= Q->heapsize && Q->key[Q->A[l]] < Q->key[Q->A[i]]) {
		smallest = l;
	}
	if(r <= Q->heapsize && Q->key[Q->A[r]] < Q->key[Q->A[smallest]]) {
		smallest = r;
	}
	
	if(smallest != i) {
		swap(Q, i, smallest);
		minHeapify(Q, smallest);
	}
}

/* Private function, builds a min heap. */
void buildMinHeap(PriorityQueueRef Q) {
	Q->heapsize = Q->n;
	int i = 1;
	for(i = Q->n/2; i >= 1; i--)
		minHeapify(Q, i);
}


/* Constructors-Destructors */
/*--------------------------------------------*/

/* Returns the handle to a new PriorityQueue object consisting of integers from 1 to n, */
/* and ordered according to the values in the array key[1...n], which is provided by */
/* the client. */
PriorityQueueRef newPriorityQueue(int n, double* key) {
	PriorityQueueRef Q = malloc(sizeof(PriorityQueue));
	
	Q->n = Q->heapsize = n;
	
	n = n + 1;
	int i = 0;
	
	Q->A = malloc(sizeof(int) * n);
	Q->I = malloc(sizeof(int) * n);
	for(i = 0; i <= Q->heapsize; i++)
		Q->A[i] = Q->I[i] = i;
	
	Q->key = key;

	buildMinHeap(Q);
	
	return Q;
}

/* Frees all memory associated with the PriorityQueue object, and sets the handle argument to NULL. */
/* Post: pQ = NULL */
void freePriorityQueue(PriorityQueueRef* pQ) {
	NULLCHECK(pQ, "freePriorityQueue()");
	
	PriorityQueueRef Q = *pQ;
	
	free(Q->A);
	free(Q->I);
	Q->key = NULL;
	
	pQ = NULL;
}



/* Access functions */
/*--------------------------------------------*/

/* Returns the number of integers remaining in Q. */
int getNumElements(PriorityQueueRef Q) {
	NULLCHECK(Q, "getNumElements()");
	
	return Q->heapsize;
}

/* Returns the vertex u for which the key is smallest. */
/* Pre: getNumElements(Q) >= 1 */
int getMin(PriorityQueueRef Q) {
	NULLCHECK(Q, "getMin()");
	if(getNumElements(Q) < 1) {
		printf("PriorityQueue.c getMin() precondition not met. \n");
		exit(1);
	}

	
	return Q->A[1];
}

/* Returns 1 if u belongs to Q, and returns 0 otherwise. */
int inQueue(PriorityQueueRef Q, int u) {
	NULLCHECK(Q, "inQueue()");
	
	if(u > Q->n)
		return 0;
	
	/*printf("inQueue() u = %d, n = %d, i[%d] = %d, heapsize = %d\n", u, Q->n, u, Q->I[u], Q->heapsize);*/
	if(Q->I[u] < 1 || Q->I[u] > Q->heapsize)
		return 0;
	return 1;
}



/* Manipulation procedures */
/*---------------------------------------------*/

/* Deletes the element in Q with smallest key. */
/* Pre: getNumElements() >= 1 */
void deleteMin(PriorityQueueRef Q) {
	NULLCHECK(Q, "deleteMin()");
	if(getNumElements(Q) < 1) {
		printf("PriorityQueue.c deleteMin() precondition not met. \n");
		exit(1);
	}
	
	Q->I[Q->A[1]] = 0;
	Q->A[1] = Q->A[Q->heapsize];
	Q->I[Q->A[1]] = 1;
	Q->heapsize = Q->heapsize - 1;
	
	/*printf("\n\n<?\n");*/
	/*printPriorityQueue(Q, NULL);*/
		
	minHeapify(Q, 1);
	
	/*printPriorityQueue(Q, NULL);*/
	/*printf("\n==============\n");*/
}

/* Sets key[u] = k if k < key[u], and does nothing otherwise. */
/* Pre: inQueue(Q, u) */
void decreaseKey(PriorityQueueRef Q, int u, double k) {
	NULLCHECK(Q, "decreaseKey()");
	
	/*printf("\n\ndecreaseKey() u = %d, k = %2.1f\n", u, k);*/

	if(!inQueue(Q, u)) {
		printf("PriorityQueue.c decreaseKey() precondition not met. \n");
		exit(1);
	}
	
	if(k < Q->key[u]) {
		printf("LESS\n");
		Q->key[u] = k;
	
		int i = Q->I[u];
		
		while(i > 1 && Q->key[Q->A[parent(i)]] > Q->key[Q->A[i]]) {
			swap(Q, i, parent(i));
			i = parent(i);
		}
	}
}



/* Other Functions */
/*---------------------------------------------*/

/* Prints the state of Q to the file handle out. */
/* Used only for diagnostic purposes. */
void printPriorityQueue(PriorityQueueRef Q, FILE* out) {
	NULLCHECK(Q, "printPriorityQueue()");
	
	printf("heapsize = %d\n", Q->heapsize);
	int i = 1;
	for(i = 1; i <= Q->heapsize; i++)
		printf("A[%d] = %d\n", i, Q->A[i]);
		
	for(i = 1; i <= Q->n; i++) {
		if(inQueue(Q, i))
			printf("\tI[%d] = %d \n", i, Q->I[i]);
		else
			printf("\tI[%d] = (%d) \n", i, Q->I[i]);
	}
	
	for(i = 1; i <= Q->n; i++) {
		if(inQueue(Q, i))
			printf("key[%d] = %2.1f\n", i, Q->key[i]);
		else
			printf("key[%d] = (%2.1f)\n", i, Q->key[i]);
	}
}