/* Version 0.0
** From "Wayne's Little DSA Library" (DSA == Data Structures and
** Algorithms) Feel free to change, modify, or burn these sources, but if
** you modify them please don't distribute your changes without a clear
** indication that you've done so.  If you think your change is spiffy,
** send it to me and maybe I'll include it in the next release.
**
** Wayne Hayes, wayne@csri.utoronto.ca (preffered), or wayne@csri.toronto.edu
*/

#include "heap.h"
#include "misc.h"
#include <stdlib.h>
#include <stdio.h>

/* Heap routines: a smallest-at-top heap.  You also supply
a comparison function, but THE ENTRIES ARE ASSUMED TO BE THE SAME SIZE AS
INTS!!!! (uh-oh, the age old pointer as int story).  You must ensure that
heap is set to your heap storage, HEAPSIZE is set to it's maximum size,
and HeapCmp is a pointer to a function to compare your entries. */

/* HeapAlloc: allocate a heap with maxsize, and comparison function
*/
HEAP *HeapAlloc(int maxSize, pCmpFcn Cmp)
{
    HEAP *Heap = Malloc(sizeof(HEAP));
    Heap->heap = Malloc(sizeof(foint) * (maxSize + 1));
    Heap->HEAPSIZE = maxSize;
    Heap->HeapCmp = Cmp;
    Heap->heap[0].i = 0;    /* initialize the heap to have 0 elements */
    return Heap;
}

/* HeapReset: set number of items to zero for re-use.
*/
void HeapReset(HEAP *Heap)
{
    Heap->heap[0].i = 0;
}

int HeapSize(HEAP *Heap)
{
    return Heap->heap[0].i;
}

/* HeapFree: free a heap and all it's storage.  It does not have to be
** empty.
*/
void HeapFree(HEAP *Heap)
{
    free(Heap->heap);
    free(Heap);
}

/* HeapInsert: return new value after inserting.  If heap is full, make it
** bigger, damnit!  :-)  (Memory limts?  What memory limits?)
*/
foint HeapInsert(HEAP *Heap, foint newEntry)
{
    int place;
    foint *heap = Heap->heap;
    
    heap[0].i++;
    if(heap[0].i > Heap->HEAPSIZE)  /* growing pains... */
    {
	Heap->HEAPSIZE *= 2;
	heap = Heap->heap = Realloc(heap, (Heap->HEAPSIZE+1) * sizeof(foint));
    }

    heap[heap[0].i] = newEntry; /* put the entry in the last position */
    place = heap[0].i;

    /* bubble it up */
    while(place > 1 && Heap->HeapCmp(heap[place / 2], newEntry) > 0)
    {
	heap[place] = heap[place / 2];
	place /= 2;
	heap[place] = newEntry;
    }
    return newEntry;
}


/* peek at the top of the heap without getting it */
foint HeapPeek(HEAP *Heap)
{
    if(Heap->heap[0].i < 1)       /* the heap is empty! */
	return ABSTRACT_ERROR;
    return Heap->heap[1];
}

/* This deletes the top entry and returns its value; if the heap is empty
** it returns ABSTRACT_ERROR
*/
foint HeapNext(HEAP *Heap)
{
    int place, child1, child2;
    foint *heap = Heap->heap, top, bubble;
    
    if(heap[0].i < 1)       /* the heap is empty! */
	return ABSTRACT_ERROR;
    top = heap[1];      /* store the top element so we can return it */
    heap[1] = bubble = heap[heap[0].i]; /* bring the bottom to the top */
    heap[0].i--;
    place = 1;

    /* Now bubble down.  Note that we should logically check if *either* of
    ** the children are "within" the heap; however since child2 = child1+1,
    ** then clearly it's sufficient to check only child1.
    ** This is NOT the comparison of the *elements* in the heap; it is
    ** simply the check to see if children *exist* in the heap.
    */
    while( /* set child1 and child2*/
	child1 = 2*place, child2 = child1 + 1,
	/* Now test the while condition */
	child1 <= heap[0].i         /*** || child2 <= heap[0].i ***/ )
    {
	int smallestChild = child1;
	if(child2 <= heap[0].i && Heap->HeapCmp(heap[child2], heap[child1]) < 0)
	    smallestChild = child2;

	if(Heap->HeapCmp(bubble, heap[smallestChild]) <= 0)     /* we're done */
	    break;

	/* exchange with smallest child */
	heap[place] = heap[smallestChild];
	place = smallestChild;
	heap[place] = bubble;
    }
    return top;
}


/* This finds an entry, if it exists, and deletes it from the heap,
** and then returns it.  We just use a linear search to find the
** element for two reasons: 1) we don't delete elements all that
** often in this simulation; 2) doing it in less than O(n) time
** would require way too much extra cruft for this assignment.
*/
foint HeapDelete(HEAP *Heap, foint delete)
{
    foint *heap = Heap->heap, entry;
    int place, child1, child2;

    if(heap[0].i < 1)   /* empty heap! */
	return puts("HeapDelete: heap empty"), ABSTRACT_ERROR;

    /* We only check up to the second last element, in case the one we're
    ** deleting is the last element.  We check this case after the loop,
    ** and then just bump the heapsize down one.
    */
    for(place = 1; place < heap[0].i; place++)
    {
	if(Heap->HeapCmp(heap[place], delete) == 0)
	{
	    heap[place] = entry = heap[heap[0].i];
	    heap[0].i--;

	    /* now decide whether to bubble it up or down -- only one or the
	    ** other is done.  The first section bubbles up.
	    */
	    while(place > 1 && Heap->HeapCmp(heap[place / 2], entry) > 0)
	    {
		heap[place] = heap[place / 2];
		place /= 2;
		heap[place] = entry;
	    }
	    
	    /* Now bubble down.  This loop will not execute if we bubbled up at all.
	    */
	    while( /* set child1 and child2 */
		child1 = 2*place, child2 = child1 + 1,
		/* Now test the while condition */
		child1 <= heap[0].i         /*** || child2 <= heap[0] ***/ )
	    {
		int smallestChild = child1;
		if(child2 <= heap[0].i && Heap->HeapCmp(heap[child2], heap[child1]) < 0)
		    smallestChild = child2;

		if(Heap->HeapCmp(entry, heap[smallestChild]) <= 0)      /* we're done */
		    break;

		/* exchange with smallest child */
		heap[place] = heap[smallestChild];
		place = smallestChild;
		heap[place] = entry;
	    }
	    
	    return delete;
	}
    }

    /* if we get here, the element either is the last one, or
    ** isn't in the heap
    */
    if(Heap->HeapCmp(delete, heap[heap[0].i]) == 0)
    {
	heap[0].i--;
	return delete;
    }
    else
	return puts("HeapDelete: item not found"), ABSTRACT_ERROR;
}
		    
		

/* I know we don't need HeapSort in an event driven simulaiton, but since I
** have HeapInsert and HeapNext, it's trivial and fun, so what the heck?
** HeapSort returns the number of elements in the array.
*/
#if 0
int HeapSort(foint *array)
{
    int N = array[0], i, storeOldHEAPSIZE = HEAPSIZE;
    foint *storeOldHeap = heap;

    heap = array;
    HEAPSIZE = N;
    heap[0].i = 0;
    
    for(i=1; i<=N; i++)
	HeapInsert(array[i]);
    for(i=1; i<=N; i++)
	array[N-i+1] = HeapNext();

    array[0] = N;
    heap = storeOldHeap;
    HEAPSIZE = storeOldHEAPSIZE;
    return N;
}

void hsort (__ptr_t __base, size_t __nmemb, size_t __size,
	    __compar_fn_t __compar);

#endif



/* Used as a cheap checksum during testing of HeapSort to "assert" that
** the array we get is a permutation of the original.
*/
static int SumArray(int *l, int n)
{
    int i, sum=0;
    for(i=0; i<n; i++)
	sum += l[i];
    return sum;
}




/* Print out the entire heap in a semi-intuitive way.
 * Change the #if to 0 if you include your own HeapTypePrint,
 * which you need to do if you ever want to actually print out
 * your heap.
 */

#if 1
void HeapTypePrint() {}
#endif
void HeapPrint(HEAP *Heap)
{
    int i,n = 1;
    foint *heap = Heap->heap;

    for(i=1; i<=heap[0].i; i++)
    {
	HeapTypePrint(heap[i]);
	if(i == (1 << n) - 1)   /* add a newline here for binary tree effect */
	{
	    n++;
	    printf("\n");
	}
    }
    printf("\n");
}




/* check to ensure we have a valid heap. 0 = not valid, else valid.
*/
int HeapSanityCheck(HEAP *Heap)
{
    int i;
    foint *heap = Heap->heap;

    for(i=1; i <= heap[0].i; i++)
    {
	int child1 = 2*i, child2 = child1+1;
	if(child1 <= heap[0].i && Heap->HeapCmp(heap[child1], heap[i]) < 0)
	{
	    printf("INVALID HEAP: position %d has lesser child on left\n", i);
	    HeapPrint(Heap);
	    return 0;
	}
	if(child2 <= heap[0].i && Heap->HeapCmp(heap[child2], heap[i]) < 0)
	{
	    printf("INVALID HEAP: position %d has lesser child on right\n", i);
	    HeapPrint(Heap);
	    return 0;
	}
    }
    return 1;
}
