/* Heap als Implementierung einer Priority Queue  */
package fha.inf3.heap;
class Heap implements PriorityQueue {
	private HeapNode[] heap; // Array to store the heap elements
	private int size;  // position of last insertion into the heap

	/**
	 * Construct the binary heap.
	 * @param size how many items the heap can store
	 */
	Heap(int size) {
		// Array f?r 'size' HeapNodes anlegen
		// heap[0] is reserved for the dummy element
		this.heap = new HeapNode[size+1];
	}

	/**
	 * Returns the number of elements in this priority queue.
	 * @return the number of elements in this priority queue.
	 */	
	public int size(){
		return this.size;
	}
	
	/**
	 * Check whether the heap is empty.
	 * @return true if there are no items in the heap.
	 */
	public boolean isEmpty() {
		return this.size == 0;
	}
	
	/**
	 * Check whether the heap is full.
	 * @return true if no further elements can be inserted into the heap.
	 */
	public boolean isFull() {
		return size == heap.length-1;
	}

	/**
	 * Make the heap (logically) empty.
	 */	
	public void clear() {
		for(int i = 1; i <= size; i++) {
			this.heap[i] = null;
		}
		this.size = 0;
	}

	/**
	 * Insert into the priority queue, maintaining heap order.
	 * Duplicates are allowed.
	 * @param obj the item to insert
	 * @param priority the priority to be assigned to the item obj
	 * @exception Overflow if the heap is full
	 */
	public void insert(Object obj, long priority) throws QueueFullException {
		this.heap[0] = new HeapNode(obj, priority);
		int pos = ++size;
		while(this.heap[0].priority < this.heap[pos/2].priority) {
			this.heap[pos] = this.heap[pos/2];
			pos = pos/2;
		}
		this.heap[pos] = this.heap[0];
	}

	/**
	 * Delete the smallest item from the priority queue, maintaining heap order.
	 * @return the the smallest item, or null, if empty
	 */
	public Object deleteMin() throws QueueEmptyException {
		try {
			if (!isEmpty()) {
				return this.heap[1].obj;
			}
			else {
				return null;
			}
		}
		finally {
			this.heap[0] = this.heap[this.size];
			this.heap[this.size] = null;
			this.size--;
			this.percolateDown(1);
		}
	}
	
	/**
	 * Internal method to percolate down in the heap.
	 * @param start the index at which the percolate begins
	 */
	private void percolateDown(int start) {
		if(2*start> this.size) {
			this.heap[start] = this.heap[0];
			return;
		}
		else {
			int min = 2*start;
			if ((this.heap[2*start+1] != null) && (this.heap[2*start].priority >  this.heap[2*start+1].priority)) {
					min = 2*start+1;
			}
			if (this.heap[min].priority < this.heap[0].priority) {
				this.heap[start] = this.heap[min];
				this.heap[min] = this.heap[0];
				
				
				percolateDown(min);
			}
			else {
				this.heap[start] = this.heap[0];
			}
		}	
	}

	public long[] toLongArray() {
	// gibt alle Prioritaeten als array zur?ck. An der Position 0
	// soll die hoechste Prioritaet (kleinster Wert) stehen, das
	// dummy Element soll nicht ber?cksichtigt werden.
		long[] res = new long[this.size];
		for(int i = 0; i < res.length; i++) {
			res[i] = this.heap[i+1].priority;
		}
		return res;
	}
}

class HeapNode {
	Object obj;
	long priority;
	
	HeapNode( Object obj, long priority) {
		this.obj = obj;
		this.priority = priority;
	}
}