Life of the IT-Drummer

 
/**
 * Simple Node class, used in SimplePriorityQueue.
 * @author tol060
 *
 * @param <E>
 */
public class Node<E> {
	private E content;
	private Node<E> next, previous;
	private int value;
	public E getContent() { return content; }
	public void setContent(E content) { this.content = content; }
	public Node<E> getNext() {	return next; }
	public void setNext(Node<E> next) { this.next = next; }
	public Node<E> getPrevious() { return previous; }
	public void setPrevious(Node<E> previous) { this.previous = previous; }
	public int getValue() { return value; }
	public void setValue(int value) { this.value = value; }
	public Node(E newObj, int newValue) {
		this.content = newObj;
		value = newValue;
	}
}

 
/**
 * A simple priority queue. Insert values are O(n), getting values are O(1).
 * @author tol060
 *
 * @param <E>
 */
public class SimplePriorityQueue<E> {
	private Node<E> startNode;
	private int size;
 
	public SimplePriorityQueue() {
		size = 0;
	}
 
	/**
	 * Insert an object with a given value. O(n).
	 * @param Object to be inserted
	 * @param Weight of object
	 */
	public void insertValue(E obj, int value) {
		Node<E> newNode = new Node<E>(obj,value);
		if(size == 0) insertFirst(newNode);
		else insertGeneral(newNode);
		size++;
	}
 
	/**
	 * Retrieves the lowest valued object in the queue. O(1).
	 * Returns null if it's empty.
	 * @return Lowest valued object, null if empty queue
	 */
	public E getValue() {
		if(size==0) return null;
		Node<E> returnNode = startNode;
 
		if(startNode.getNext()==null) startNode = null;
		else startNode = startNode.getNext(); 
		size--;
		return (E) returnNode.getContent();
	}
 
	private void insertFirst(Node<E> newNode) {
		startNode = newNode;
	}
 
	private void insertGeneral(Node<E> newNode) {
		Node<E> current = startNode;
		Node<E> previous = null;
		boolean first = true;
		while(newNode.getValue() >= current.getValue()) {
			first = false;
			if(current.getNext()!=null) {
				previous = current;
				current = current.getNext();
			}
			else {
				current.setNext(newNode);
				newNode.setPrevious(current);
				return;
			}
		}
		if(previous!=null) previous.setNext(newNode);
 
		current.setPrevious(newNode);
		newNode.setNext(current);
		newNode.setPrevious(previous);	
		if(first) startNode = newNode;
	}
}