package priorityqueue;
import java.util.Iterator;

// A heap is a left-complete tree in which the value of a node is greater than the value of its sons.
// Hence the root holds the greatest value.
public abstract class Heap<T extends Comparable<T>> extends PriorityQueue<T> implements Iterable<T> {
  private T[] tree_;
  private int size_;

  //@ Compare two elements of the heap (redefined in MaxHeap and MinHeap)
  protected abstract boolean less(T k1, T k2);

  public Heap() {
    this(5);
  }

  public Heap(int capacity) {
    this.size_ = 0;
    resize(capacity);
  }

  protected Heap(T[] array) {
    this.tree_ = array;
    this.size_ = array.length;
    for (int i = 1; i < this.size_; i++) {
      swim(i);
    }
  }

  // Heap sort of array T[] a:
  //   MaxHeap<T> heap(a);
  //   a = heap.sort();
  public T[] sort() {
    int n = this.size_;
    for(int i = 0; i < n; i++) {
      removeMax();
    }
    return this.tree_;
  }

  @Override
  public void insert(T item) {
    if ((this.size_ + 1) <= this.tree_.length) {
      grow();
    }
    int ins_index = this.size_++;
    this.tree_[ins_index] = item;
    if ( ! less (this.tree_[ins_index], this.tree_[parent(ins_index)]) ) {
      this.swim(ins_index);
    }
  }

  @Override
  public T removeMax() {
    T res = this.tree_[0];
    exchange(0, --this.size_);
    sink(0);
    return res;
  }

  public T remove(T item) {
    for (int i = 0; i < this.size_; i++) {
      if (this.tree_[i].equals(item)) {
	exchange(i, --this.size_);
	if (this.swim(i) == i) {
	  this.sink(i);
	}
	return this.tree_[this.size_];
      }
    }
    return null;
  }

  private int swim(int start) {
    if ((start > 0) && ( ! less(this.tree_[start], this.tree_[parent(start)])) ) {
      exchange(start, parent(start));
      return swim(parent(start));
    }
    return start;
  }

  private int sink(int start) {
    if (start < this.size_) {
      int left = left_son(start);
      int right = right_son(start);
      int max_son = left;
      if ((right < this.size_) && less(this.tree_[left], this.tree_[right])) {
	max_son = right;
      }
      if ((left < this.size_) &&  !less(this.tree_[max_son], this.tree_[start])) {
	exchange(max_son, start);
	return sink(max_son);
      }
    }
    return start;
  }

  @Override
  public int size() {
    return this.size_;
  }

  private void exchange(int i, int j) {
    T z = this.tree_[i];
    this.tree_[i] = this.tree_[j];
    this.tree_[j] = z;
  }

  private static int parent(int i) {
    return (i-1)/2;
  }

  private static int left_son(int i) {
    return 2*i+1;
  }

  private static int right_son(int i) {
    return 2*(i+1);
  }

  private void grow() {
    resize(2*this.tree_.length);
  }

  private void resize(int capacity) {
    @SuppressWarnings("unchecked")
    T[] newtree = (T[]) new Comparable[capacity];
    for (int i = 0; i < this.size_; i++) {
      newtree[i] = this.tree_[i];
    }
    this.tree_ = newtree;
  }

  private class HeapIterator implements Iterator<T> {
    private int next = 0;
    @Override
    public boolean hasNext() {
      return (this.next < Heap.this.size_);
    }
    @Override
    public T next() {
      return Heap.this.tree_[this.next++];
    }
    @Override
    public void remove() {
      // TODO Auto-generated method stub
    }
  }

  @Override
  public Iterator<T> iterator() {
    return new HeapIterator();
  }

  private void printSubTree(int root, StringBuffer buf, String indent) {
    if (root < this.size_) {
      buf.append(indent);
      buf.append(this.tree_[root].toString());
      buf.append(System.getProperty("line.separator"));
      printSubTree(left_son(root), buf, indent+"  ");
      printSubTree(right_son(root), buf, indent+"  ");
    }
  }

  @Override
  public String toString() {
    StringBuffer buf = new StringBuffer();
    printSubTree(0,buf,"");
    return buf.toString();
  }
}