package net.datastructures;

/**
 * Realization of a queue by means of a singly-linked list of nodes.
 * All operations are performed in constant time.
 *
 * @author Roberto Tamassia
 */
/** 
 * @costaContext net/datastructures/Node
 */ 
public class NodeQueue implements Queue {

	protected Node head, tail;  // the head and tail nodes
	protected int size;         // Keeps track of number of elements in queue

	/** Creates an empty queue. */
	public NodeQueue() {
		head = null;
		tail = null;
		size = 0;
	}
  
	public int size() {       //# Return the current queue size
		return size;
	}
  
	public boolean isEmpty() {      //# Returns true iff queue is empty
		if ( (head==null) && (tail==null) )
		return true;
		return false;
	}

	public void enqueue(Object obj) {
		Node node = new Node();
		node.setElement(obj);
		node.setNext(null); // node will be new tail node
		if (size == 0)
			head = node; // special case of a previously empty queue
		else
			tail.setNext(node); // add node at the tail of the list
		tail = node; // update the reference to the tail node
		size++;
	}

	public Object front()     //# Return the first queue element
		throws EmptyQueueException {
		if (size == 0)
		throw new EmptyQueueException("Queue is empty.");
		return head.getElement();
	}
  
	public Object dequeue() throws EmptyQueueException {
		if (size == 0)
			throw new EmptyQueueException("Queue is empty.");
		Object obj = head.getElement();
		head = head.getNext();
		size--;
		if (size == 0)
			tail = null; // the queue is now empty
		return obj;
	}

	public String toString() {
		String s = "";
		s += "(";
		if (!isEmpty()) {
			Node p = head;
			do {
				s += p.getElement() ;
				if (p != tail)
					s += ", ";
				p = p.getNext();
			} while (p != null); 
		}
		s += ")";
		return s;
	}

	public static void main(String[] args) {
		
		// Prepare the test
		NodeQueue test = new NodeQueue();
		for (int i = 0; i < 10; i++) {
			Integer testNumber = i;
			test.enqueue(testNumber);
		}
	
		// Test
		for (int i = 0; i < 10; i++) {
			test.dequeue();
		}
				
	}
  
}