#include "BinaryHeap.h"

/**
 * Construct the binary heap.
 * capacity is the capacity of the binary heap.
 */
BinaryHeap::BinaryHeap(int capacity) :
  array(capacity + 1), currentSize( 0) {
}

/**
 * Insert item x into the priority queue, maintaining heap order.
 * Duplicates are allowed.
 * Throw Overflow if container is full.
 */
void BinaryHeap::insert(NodeData * x) {
  // Percolate up
  int hole = ++currentSize;
  for (; hole > 1 && x->key < array[ hole / 2 ]->key; hole /= 2) {
    array[ hole ] = array[ hole / 2 ];
  }
  array[ hole ] = x;
}

/**
 * Find the smallest item in the priority queue.
 * Return the smallest item, or throw Underflow if empty.
 */
NodeData * BinaryHeap::findMin() const {
  return array[ 1 ];
}

/**
 * Remove the smallest item from the priority queue and return it.
 */
NodeData* BinaryHeap::deleteMin() {
  NodeData * minItem = array[ 1 ];
  array[ 1 ] = array[ currentSize-- ];
  percolateDown( 1);
  return minItem;
}

/**
 * Establish heap order property from an arbitrary
 * arrangement of items. Runs in linear time.
 */
void BinaryHeap::buildHeap() {
  for (int i = currentSize / 2; i > 0; i--) {
    percolateDown(i);
  }
}

/**
 * Test if the priority queue is logically empty.
 * Return true if empty, false otherwise.
 */
bool BinaryHeap::isEmpty() const {
  return currentSize == 0;
}

/**
 * Test if the priority queue is logically full.
 * Return true if full, false otherwise.
 */
bool BinaryHeap::isFull() const {
  return currentSize == array.size() - 1;
}

/**
 * Internal method to percolate down in the heap.
 * hole is the index at which the percolate begins.
 */
void BinaryHeap::percolateDown(int hole) {
  int child;
  NodeData *tmp = array[ hole ];

  for (; hole * 2 <= currentSize; hole = child) {
    child = hole * 2;
    if (child != currentSize && (array[ child + 1 ]->key < array[ child ]->key)) {
      child++;
    }
    if (array[ child ]->key < tmp->key) {
      array[ hole ] = array[ child ];
    }
    else {
      break;
    }
  }
  array[ hole ] = tmp;
}