HPriorityQueue.java

gistfile1.java

public class HPriorityQueue<E extends Comparable<E>> {

	private PQNode<E> first;
	private PQNode<E> last;
	private int size;

	public HPriorityQueue() {
		first = null;
		last = null;
		size = 0;
	}

	/*
	 * Inserts the specified element into this priority queue.
	 */
	public boolean enqueue(E newNodeData) {
		PQNode<E> currentNode = first;
		// if the queue is empty
		if (currentNode == null) {
			first = new PQNode<E>(null, newNodeData, null);
			last = first;
		}
		// if the first item in the queue is bigger than newNodeData
		else if(newNodeData.compareTo(currentNode.getData()) < 0) {
			PQNode<E> prevNode = currentNode.prev;
			PQNode<E> newNode = new PQNode<E>(prevNode, newNodeData, first);
			first.setPrev(newNode);
			first = newNode;
		}
		// general case, if newNodeData should be in the middle or end of the queue
		else {
			// traverse the linked list until currentNode is the node
			// immediately bigger than newNodeData
			while (currentNode != null
					&& newNodeData.compareTo(currentNode.getData()) >= 0) {
				currentNode = currentNode.next;
			}
			// newNodeData is at the middle
			if (currentNode != null) {
				// make a reference to the node before the node immediately bigger than newNodeData
				PQNode<E> prevNode = currentNode.prev;
				PQNode<E> newNode = new PQNode<E>(prevNode, newNodeData, currentNode);
				prevNode.setNext(newNode);
				currentNode.setPrev(newNode);
			}
			// newNodeData is at the end
			else {
				PQNode<E> newNode = new PQNode<E>(last, newNodeData, null);
				last.setNext(newNode);
				last = newNode;
			}
		}
		size++;
		return true;
	}

	public E dequeue() {
		if (size == 0) {
			throw new IllegalStateException("Can't dequeue empty queue");
		}
		E firstData = first.getData();
		if (first == last) {
			first = null;
			last = null;
		} else {
			first = first.next;
			first.setPrev(null);
		}
		size--;
		return firstData;
	}
	
	
	/*
	 * A method that returns 1 if there's only 1 element left in the queue.
	 * Means the Huffman tree has been constructed.
	 */
	public boolean isReady() {
		return size == 1;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}

	public int size() {
		return size;
	}

	public String toString() {
		PQNode<E> currentNode = first;
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		while (currentNode != null) {
			sb.append(currentNode.getData());
			sb.append(", ");
			currentNode = currentNode.getNext();
		}
		if (size > 0) {
			// when the list is not empty
			// remove the last two characters of the StringBuilder so far: ", "
			sb.delete(sb.length() - 2, sb.length());
		}
		sb.append("]");
		return sb.toString();
	}

	private class PQNode<E> {
		private E data;
		private PQNode<E> next;
		private PQNode<E> prev;

		public PQNode() {
			this(null, null, null);
		}

		public PQNode(PQNode<E> prev, E data, PQNode<E> next) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}

		public E getData() {
			return data;
		}

		public PQNode<E> getNext() {
			return next;
		}

		public PQNode<E> getPrev() {
			return prev;
		}

		public void setData(E newData) {
			data = newData;
		}

		public void setNext(PQNode<E> newNext) {
			next = newNext;
		}

		public void setPrev(PQNode<E> newPrev) {
			prev = newPrev;
		}
	}


}