/* File: ArrayHeap.java - May 2011 */
package l25;
import java.util.Arrays;
/**
 *  An array based heap implementation
 *
 *  @author Michael Albert
 *
 */
public class ArrayHeap<T extends Comparable<T>>  implements Heap<T>{

   public static final int DEFAULT_CAPACITY = 31;
   private T[] heap;
   private int size = 0;

   public ArrayHeap() {
      this(DEFAULT_CAPACITY);
   }

   @SuppressWarnings("unchecked")
   public ArrayHeap(int capacity){
      heap = (T[]) new Comparable[capacity];
   }

   public void add(T element) {
      if (size == heap.length) expandCapacity();
      heap[size] = element;
      size++;
      int childIndex = size-1;
      int parentIndex = (childIndex-1)/2;
      while (parentIndex >= 0 && 
             heap[parentIndex].compareTo(heap[childIndex]) < 0) {
         swap(childIndex, parentIndex);
         childIndex = parentIndex;
         parentIndex = (childIndex-1)/2;
      }
      
   }

   public T get() {
      return heap[0];
   }

   public T remove() {

      T result = heap[0];
      heap[0] = heap[size-1];
      size--;
      int parentIndex = 0;
      while (!heapCondition(parentIndex) && !isLeaf(parentIndex)) {
         int largerChildIndex = getLargerChildIndex(parentIndex);
         swap(parentIndex, largerChildIndex);
         parentIndex = largerChildIndex;
      }
      return result;
   }

   public boolean isEmpty() {
      return size == 0;
   }

   public int size() {
      return size;
   }

   private void expandCapacity() {
      heap = Arrays.copyOf(heap, 2*heap.length+1);
   }

   private void swap(int i, int j) {
      T temp = heap[i];
      heap[i] = heap[j];
      heap[j] = temp;
   }

   private boolean heapCondition(int i) {
      if (2*i + 1 < size) {
         if (heap[i].compareTo(heap[2*i+1]) < 0) return false;
      }
      if (2*i + 2 < size) {
         if (heap[i].compareTo(heap[2*i+2]) < 0) return false;
      }
      return true;
   }

   private int getLargerChildIndex(int i) {
      int l = 2*i+1;
      int r = 2*i+2;
      if (r >= size || heap[r].compareTo(heap[l]) < 0) return l;
      return r;
   }

   private boolean isLeaf(int i) {
      return (2*i+1 >= size);
   }

   public String toString() {
      StringBuilder result = new StringBuilder("Heap: ");
      for(int i = 0; i < size; i++) {
         result.append(heap[i].toString() + " ");
      }
      return result.toString();
   }
}