/*
heap.c
Pedro Flynn - pflynn@microsoftsucks.org
*/

#include <stdlib.h>
#include <string.h>

#include "heap.h"


#define node_root(node)  ((int) (((node) -1)/2)) 
#define node_left(node)  (2*(node) + 1)
#define node_right(node) (2*(node) + 2)
	


Heap* heap_create(void (*destroy)(void*),int (*compare)(const void*,const void*))
{
Heap* heap;
	
if(!(heap = (Heap*) malloc(sizeof(Heap))))
	return NULL;

heap->size = 0;
heap->compare = compare;
heap->destroy = destroy;
heap->tree = NULL;

return heap;
}

void heap_destroy(Heap* heap)
{
int i;

if(heap->destroy)
	for(i=0;i<heap_size(heap);++i)
		heap->destroy(heap->tree[i]);
	
free(heap->tree);
	
return;
	
}

int heap_insert(Heap* heap,const void* data)
{
void* tmp;
int ipos,rpos;
	
	if(!(tmp = (void**) realloc(heap->tree,(heap_size(heap) + 1)*sizeof(void*))))
		return - 1;
	else
	heap->tree = tmp;
	
	heap->tree[heap_size(heap)] = (void*) data;
	
	ipos = heap_size(heap);
	rpos = node_root(ipos);
	
	while(ipos && (heap->compare(heap->tree[rpos],heap->tree[ipos]) < 0 )){
	tmp = heap->tree[rpos];
	heap->tree[rpos] = heap->tree[ipos];
	heap->tree[ipos] = tmp;
	ipos = rpos;
	rpos = node_root(ipos);
	}
	
	heap->size++;
	
	return 0;
	
	}

int heap_extract(Heap* heap,void** data)
{
void *save,*tmp;
int ipos,lpos,rpos,mpos;

if(!heap_size(heap))
	return -1;

*data = heap->tree[0];

save = heap->tree[heap_size(heap) - 1];

if(heap_size(heap) - 1 > 0){
	if(!(tmp = (void**) realloc(heap->tree,(heap_size(heap) - 1)*sizeof(void*))))
		return -1;
	else
		heap->tree = tmp;
	
	heap->size--;
	}else{
		free(heap->tree);
		heap->tree == NULL;
		heap->size = 0;
		return 0;
		}
		
		heap->tree[0] = save;
		
		ipos = 0;
		
		while(1){
		
		rpos = node_right(ipos);
		lpos = node_left(ipos);
		
		if(lpos < heap_size(heap) && heap->compare(heap->tree[lpos],heap->tree[ipos]) > 0 )
			mpos = lpos;
		else
			mpos = ipos;
		
		if(rpos < heap_size(heap) && heap->compare(heap->tree[rpos],heap->tree[mpos]) > 0)
			mpos = rpos;
		
		if(mpos == ipos)
			break;
		else{
			tmp = heap->tree[mpos];
			heap->tree[mpos] = heap->tree[ipos];
			heap->tree[ipos] = tmp;
      
			ipos = mpos;
			
		}
		
	}
	
	return 0;
}