package com.dwave.util;

public class PriorityHeap {
  private Node[] heapArray;
  private int maxSize;
  private int nItems;

  public PriorityHeap(int size) {
    maxSize = size;
    nItems = 0;
    heapArray = new Node[maxSize];
  }

  public boolean isEmpty() { return nItems == 0; }
  public boolean insert(Object o, int priority) {
    try {
      if(nItems==maxSize)
        _resize();
      Node newNode = new Node(o, priority);
      heapArray[nItems] = newNode;
      shiftUp(nItems++);
      return true;
    }
    catch(Exception e) { return false; }
  }

  public void shiftUp(int index) {
    int parent = (index-1)/2;
    Node bottom = heapArray[index];
    while(index > 0 && heapArray[parent].priority < bottom.priority) {
      heapArray[index] = heapArray[parent];
      index = parent;
      parent = (parent-1) / 2;
    }
    heapArray[index] = bottom;
  }

  public Object remove() {
    Node root = heapArray[0];
    heapArray[0] = heapArray[--nItems];
    shiftDown(0);
    return root.object;
  }

  public void shiftDown(int index) {
    int larger;
    Node top = heapArray[index];
    while(index < nItems/2) {
      int left = 2*index + 1;
      int right = left + 1;
      if(right < nItems && heapArray[left].priority < heapArray[right].priority)
        larger = right;
      else
        larger = left;
      if(top.priority >= heapArray[larger].priority)
        break;
      heapArray[index] = heapArray[larger];
      index = larger;
    }
    heapArray[index] = top;
  }



  private void _resize() {
  }

  class Node {
    Object object;
    int priority;

    Node(Object o, int priority) {
      object = o;
      this.priority = priority;
    }
  }
}