/**
 * @file heap.c
 * @author Joe Wingbermuehle
 * @date 2007-07-05
 */

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

/** Heap data. */
typedef struct HeapType {
   HeapComparator comparator;
   void **data;
   int size;
   int max_size;
} HeapType;

/** Create an empty heap. */
Heap *CreateHeap(HeapComparator comparator) {

   HeapType **heap;

   heap = malloc(sizeof(HeapType*));
   *heap = malloc(sizeof(HeapType));

   (*heap)->comparator = comparator;
   (*heap)->max_size = 8;
   (*heap)->data = malloc(sizeof(void*) * ((*heap)->max_size + 1));
   (*heap)->size = 0;

   return (Heap*)heap;

}

/** Destroy a heap. */
void DestroyHeap(Heap *heap) {

   HeapType **hp = (HeapType**)heap;
   free((*hp)->data);
   free(*hp);
   free(hp);

}

/** Insert an item to a heap. */
void InsertHeap(Heap *heap, void *value) {

   HeapType *hp = *(HeapType**)heap;
   void *temp;
   int index, next_index;

   /* Alocate more space if needed. */
   if(hp->size >= hp->max_size) {
      hp->max_size <<= 1;
      hp->data = realloc(hp->data, (hp->max_size  + 1) * sizeof(void*));
   }

   /* Put the item at the end of the heap. */
   ++hp->size;
   index = hp->size;
   hp->data[index] = value;

   /* Restore the heap property. */
   while(index > 1) {

      /* Get the index of the parent. */
      next_index = index >> 1;

      /* Check if we need to swap. */
      temp = hp->data[next_index];
      if((hp->comparator)(hp->data[index], temp) < 0) {
         hp->data[next_index] = hp->data[index];
         hp->data[index] = temp;
      } else {
         break;
      }

      index = next_index;

   }

}

/** Remove the least item from a heap. */
void *RemoveHeap(Heap *heap) {

   HeapType *hp = *(HeapType**)heap;
   void *result;
   void *left, *right, *current;
   void *temp;
   int index;
   int max_index;
   int right_index;
   int left_index;
   int repeat;

   /* If there is nothing in the heap just return NULL. */
   if(hp->size == 0) {
      return NULL;
   }

   /* Get the item to return. */
   result = hp->data[1];

   /* Reduce the size of the heap. */
   --hp->size;
   if(hp->size > 0) {

      /* Move the last element to the beginning of the heap. */
      hp->data[1] = hp->data[hp->size + 1];

      /* Restore the heap property. */
      index = 1;
      do {

         repeat = 0;
         left_index = index << 1;
         if(left_index <= hp->size) {

            /* Check the left child. */
            max_index = index;
            current = hp->data[index];
            left = hp->data[left_index];
            if((hp->comparator)(left, current) < 0) {
               max_index = left_index;
               current = left;
            }

            /* Check the right child. */
            right_index = left_index + 1;
            if(right_index <= hp->size) {
               right = hp->data[right_index];
               if((hp->comparator)(right, current) < 0) {
                  max_index = right_index;
               }
            }

            /* Swap and go again if needed. */
            if(max_index != index) {
               temp = hp->data[max_index];
               hp->data[max_index] = hp->data[index];
               hp->data[index] = temp;
               index = max_index;
               repeat = 1;
            }

         }

      } while(repeat);

   }

   /* Check if we should decrease the space allocated for the heap. */
   if(hp->size << 1 < hp->max_size && hp->max_size > 8) {
      hp->max_size >>= 1;
      hp->data = realloc(hp->data, (hp->max_size + 1) * sizeof(void*));
   }

   return result;

}

/** Get the least item from a heap. */
void *GetHeap(Heap *heap) {

   HeapType *hp = *(HeapType**)heap;
   if(hp->size > 0) {
      return hp->data[1];
   } else {
      return NULL;
   }

}

/** Get the size of a heap. */
int GetHeapSize(Heap *heap) {
   HeapType *hp = *(HeapType**)heap;
   return hp->size;
}