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

#include "Pq.h"

#define INITIAL_CAPACITY 8

struct pq {
	struct pqItem *items;
	int numItems;
	int capacity;
};

struct pqItem {
	int item;
	int priority;
};

static void resize(Pq pq);

Pq PqNew(void) {
	Pq pq = malloc(sizeof(struct pq));
	if (pq == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	pq->numItems = 0;
	pq->capacity = INITIAL_CAPACITY;
	pq->items = malloc(pq->capacity * sizeof(struct pqItem));

	return pq;
}

void PqFree(Pq pq) {
	free(pq->items);
	free(pq);
}

void PqInsert(Pq pq, int item, int priority) {
	if (pq->numItems == pq->capacity) {
		resize(pq);
	}

	// TODO
	pq->items[pq->numItems].item = item;
	pq->items[pq->numItems].priority = priority;

	pq->numItems++;
}

static void resize(Pq pq) {
	pq->capacity *= 2;
	pq->items = realloc(pq->items, pq->capacity * sizeof(struct pqItem));
	if (pq->items == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}
}

int PqDelete(Pq pq) {
	if (pq->numItems == 0) {
		fprintf(stderr, "error: pq is empty\n");
		exit(EXIT_FAILURE);
	}

	// TODO
	// Find index of item with highest priority
	int maxIndex = 0;
	for(int i=0; i<pq->numItems; i++) {
		if(pq->items[i].priority > pq->items[maxIndex].priority) {
			maxIndex = i;
		}
	}

	// Save the value to return
	int item = pq->items[maxIndex].item;
	
	// Move all the later items over (or drop last element into currently empty spot)
	pq->numItems--;
	pq->items[maxIndex].item = pq->items[pq->numItems].item;
	pq->items[maxIndex].priority = pq->items[pq->numItems].priority;

	return item;
}

int PqPeek(Pq pq) {
	if (pq->numItems == 0) {
		fprintf(stderr, "error: pq is empty\n");
		exit(EXIT_FAILURE);
	}

	// TODO
	// Find index of item with highest priority
	int maxIndex = 0;
	for(int i=0; i<pq->numItems; i++) {
		if(pq->items[i].priority > pq->items[maxIndex].priority) {
			maxIndex = i;
		}
	}

	return pq->items[maxIndex].item;
	
}