package queues.priorityqueues;

import java.util.Iterator;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Comparator;

/**
 * A PriorityQueue holding elements on a priority heap
 * according to their natural order.
 */
public class PriorityQueue<E>{
	
	private E[] elements; // array holding  priority queue elements	   
	private int size; // number of active elments in the priority queue
	private int capacity; // number of active elments in the array holding priority queue
	private Comparator<? super E> comparator;
	   
	/**
	 * Creates an empty  priority queue that holds elements with the
	 * specified generic type E.
	 */
	public PriorityQueue() {
		this(10);
	}
	
	/**
	 * Creates a  priority queue with given capacity 
	 * that holds elements with the specified generic type E.
	 */
	public PriorityQueue(int capacity) {
		this(capacity, null);
	}
	
	/**
	 * Constructs a priority queue with the specified capacity and comparator.
	 */
	public PriorityQueue(int capacity, Comparator<? super E> comparator) {
		if (capacity < 1) {
			throw new IllegalArgumentException();
		}
		size = 0;
		this.capacity = capacity ;
		elements = (E[])new Object[capacity];
		this.comparator = comparator;
	}

	 /**
	  * Returns the iterator of the priority queue, which will not return elements
	  * in any specified ordering.
	  */
	public Iterator<E> iterator() {
		return new PriorityQueueIterator();
	}
 
	/**
	 * Returns the size of the priority queue. If the size of the queue is greater
	 * than the Integer.MAX, then it returns Integer.MAX.
	 */ 
	public int size() {
		return size;
	}
	
	/**
	 * Returns the size of the priority queue. If the size of the queue is greater
	 * than the Integer.MAX, then it returns Integer.MAX.
	 */ 
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * Removes all the elements of the priority queue.
	 */
	public void clear() {
		Arrays.fill(elements, null);
		size = 0;
	}
	
	/**
	 * Inserts the element in the priority queue.
	 * throws ClassCastException if the element
	 * cannot be compared with the elements in the queue
	 */
	public boolean enqueue(E newElement) {
		if (newElement == null) 
			throw new NullPointerException();
		if(capacity - size < 2)
			ensureCapacity();
		elements[size] = newElement;
		siftUp(size++);
		return true;
	}
	
	/**
	 * Gets and removes the head of the queue.
	 */
	public E dequeue() {
		if (isEmpty()) 
			return null;
		E result = elements[0];
		removeAt(0);
		return result;
	}
	  
	/**
	 * Gets but does not remove the head of the queue.
	 */
	public E peek() {
		if (isEmpty()) 
			return null;
		return elements[0];
	}
	
	 /**
	  * Removes the specified object from the priority queue.
	  */
	public boolean remove(Object o) {
		if (o == null) 
			return false;
		for (int i = 0; i < size; i++) {
			if (elements[i].equals(o)) {
				removeAt(i);
				return true;
			}	
		}
		return false;
	}
	
	/**
	 * Cheks if there is an element in this queue equals to the object.
	 */
	public boolean contains(Object o) {
		for (int i = 0; i < size; i++) 
			if(elements[i].equals(o))
				return true;
	 	return false;
 	}
		
	public E[] toArray() {
		E[] array = (E[]) new Object[size];
		for(int i = 0; i < size; i++)
			array[i] = elements[i];
		return array;
	}

	private void ensureCapacity() {
		capacity = 2 * capacity;
		E[] oldArray = elements;
		elements = (E[])new Object[capacity];
		for (int i = 0; i < size; i++)
			elements[i] = oldArray[i];
		oldArray = null;
	}	
	
	private void removeAt(int index) {
		size--;
		elements[index] = elements[size];
		siftDown(index);
		elements[size] = null;
	}
	
	private int compare(E e1, E e2) {
		if (comparator != null) {
		 	return comparator.compare(e1,e2);
	 	}
	 	return ((Comparable<? super E>) e1).compareTo(e2);
	}

	
	private void siftUp(int child) {
		E newValue = elements[child];
		int parent;
		while (child > 0) {
			parent = (child - 1) / 2;
			E parentValue = elements[parent];
			if (compare(parentValue, newValue) > 0)
				break;
			elements[child] = parentValue;
			child = parent;
		}
		elements[child] = newValue;
	}
		
	private void siftDown(int root) {
		E lastValue = elements[root];
		int child;
		while ((child = root * 2 + 1) < size) {
			if (child + 1 < size && // two children
					compare(elements[child + 1], elements[child]) > 0) 
				child++;  // second child greater
			if (compare(lastValue, elements[child]) > 0) 
				break;
			elements[root] = elements[child];
			root = child;
		}
		elements[root] = lastValue;
	}
	
	private class PriorityQueueIterator implements Iterator<E> {
		 
		private int current = -1;		 
		private boolean removePossible = false;
		 
		public boolean hasNext() {
			return current < size - 1;
		}
	
		public E next() {
			if (!hasNext()) 
				throw new NoSuchElementException();
			removePossible = true;
			return elements[++current];
		}
		 
		public void remove() {
			if (!removePossible) 
				throw new IllegalStateException();
			removePossible = false;
			removeAt(current--);
		}
	}

}