//Deian Stefan
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
#include "heap.h"

struct node {
	int id;
	int key;
	void *data;
};
typedef struct node node_t;
typedef node_t *pnode_t;

struct heap {
	int size;
	int capacity;
	node_t *elements; 
	int *map;	   
};

static void percolate_up(pheap_t h,int index) {
	int id = (h->elements[index]).id;
	int key = (h->elements[index]).key;
	void *data = (h->elements[index]).data;
	int i;
	for(i = index;((h->elements[i/2]).id != 0) && 
					((h->elements[i/2]).key > key);i/=2) {
		(h->elements[i]).id = (h->elements[i/2]).id;
		(h->elements[i]).key = (h->elements[i/2]).key;
		(h->elements[i]).data = (h->elements[i/2]).data;
		h->map[(h->elements[i]).id] = i;
	}
	(h->elements[i]).id = id;
	(h->elements[i]).key = key;
	(h->elements[i]).data = data;
	h->map[id] = i;
}

static void percolate_down(pheap_t h,int index) {
	int id = (h->elements[index]).id;
	int key = (h->elements[index]).key;
	void *data = (h->elements[index]).data;
	int i,child;
	for(i = index;i*2 <= h->size;i = child) {
		child = i*2;
		if((child != h->size) && ((h->elements[child+1]).key 
						< (h->elements[child]).key)) {
			child++;
		}

		if(key > (h->elements[child]).key) {
			(h->elements[i]).id = (h->elements[child]).id;
			(h->elements[i]).key = (h->elements[child]).key;
			(h->elements[i]).data = (h->elements[child]).data;
			h->map[(h->elements[i]).id] = i;
		} else {
			break;
		}
	}
	(h->elements[i]).id = id;
	(h->elements[i]).key = key;
	(h->elements[i]).data = data;
	h->map[id] = i;
}

pheap_t create_heap(int capacity) {
	pheap_t h = malloc(sizeof(heap_t));
	if(h == NULL) {
		fprintf(stderr,"Fatal Error: Could not allocate memory!\n");
		exit(1);
	}
	h->size = 0;
	h->capacity = capacity;
	h->elements = malloc(sizeof(node_t)*(capacity+1));
	if(h->elements == NULL) {
		fprintf(stderr,"Fatal Error: Could not allocate memory!\n");
		exit(1);
	}
	h->map = malloc(sizeof(int)*(capacity+1));
	if(h->map == NULL) {
		fprintf(stderr,"Fatal Error: Could not allocate memory!\n");
		exit(1);
	}
	int i;
	//set all IDs to 0
	for(i = 0;i <= capacity;i++) {
		(h->elements[i]).id = 0;
		h->map[i] =0;
	}
	return h;
}

int insert(pheap_t h, void *pData, int key, int id) {
	if(id > h->capacity || id < 1) {
		return 1;
	}
	if(h->map[id] != 0) {
		return 2;
	}
	if(h->capacity == h->size) {
		//should not get here, if full then all id's are taken
		//so should return 2
		return 3;
	}
	// INSERT INTO heap_t 
	(h->elements[++h->size]).id = id;
	(h->elements[h->size]).key = key;
	(h->elements[h->size]).data = pData;
	h->map[id] = h->size;
	percolate_up(h,h->size);
	return 0;
}

int set_key(pheap_t h, int id, int key) {
	if(id > h->capacity || id < 1) {
		return 1;
	}
	if(h->map[id] == 0) {
		return 2;
	}
	int old_key = (h->elements[h->map[id]]).key;
	(h->elements[h->map[id]]).key = key;
	if(key < old_key) {
		percolate_up(h,h->map[id]);
	} else if(key > old_key) {
		percolate_down(h,h->map[id]);
	}
	return 0;
}

void *delete_min(pheap_t h, int *pKey, int *pId) {
	if(h->size > 0) {
		if(pKey != NULL) {
			*pKey = (h->elements[1]).key;
		}
		if(pId != NULL) {
			*pId = (h->elements[1]).id;
		}

		void *data = (h->elements[1]).data;
		h->map[(h->elements[1]).id] = 0;
		if(h->size>1){
			(h->elements[1]).id = (h->elements[h->size]).id;
			(h->elements[1]).key = (h->elements[h->size]).key;
			(h->elements[1]).data = (h->elements[h->size]).data;
			h->map[(h->elements[1]).id] = 1;
			h->map[(h->elements[h->size]).id] = 0;
			(h->elements[h->size--]).id = 0;
			percolate_down(h,1);
		}else { 
			(h->elements[h->size--]).id = 0;
		}
	
		return data;
	}
	return NULL;
}

int delete(pheap_t h, int id, void *ppData){ 
	if(id > h->capacity || id < 1) {
		return 1;
	} 
	if(h->map[id] == 0) {
		return 2;
	}
       	set_key(h,id,(h->elements[1]).key-1); //set to smallest key
	if(ppData != NULL) {
		*(void **)ppData = delete_min(h,NULL,NULL);
		return 0;
	}
	delete_min(h,NULL,NULL);
	return 0;
}

void *get_min(pheap_t h, int *pKey, int *pId) {
	if(h->size > 0) {
		if(pKey != NULL) {
			*pKey = (h->elements[1]).key;
		}
		if(pId != NULL) {
			*pId = (h->elements[1]).id;
		}
		return (h->elements[1]).data;
	}
	return NULL;
}

int get_by_id(pheap_t h, int id, int *key,void *pData) {
	if(id > h->capacity || id < 1) {
		return 1;
	}
	if(h->map[id] == 0) {
		return 2;
	}
	if(key != NULL) {
		*key=(h->elements[h->map[id]]).key;
	}
	if(pData != NULL) {
		*(void **)pData = (h->elements[h->map[id]]).data;
	}
	return 0;
}