/* Queue.java          Authors: Koffman & Wolz
 * A class that represents a queue implemented as
 * a linked list.
 */

public class Queue {
	// Data fields
	private ListNode front;  // reference to front of queue
	private ListNode rear;   // reference to rear of queue
	private int size;         // size of queue

  class ListNode {

	  // Data fields
	  Object info;           // data stored in the node
	  ListNode link;         // link to next node

	  // Methods
	  // Constructors
	  public ListNode() {info = ""; link = null;}

	  public ListNode(Object i) {info = i; link = null;}
	
	  public ListNode(Object i, ListNode l) {
		  info = i;
		  link = l;
	  }
  } // class ListNode

	// Methods
	// postcondition: Inserts item in a new node and resets
  // rear to reference the new node. If the queue has
  // 1 element, front references the new node also.
	public void insert(Object item) {

		if (isEmpty()) { //empty queue
			// Link rear and front to only node.
			rear = new ListNode(item);
			front = rear;
		}
    else { //extend a non-empty queue
			rear.link = new ListNode(item);
			rear = rear.link;  // Move rear to new node.
		}

		size++;                 //Increment queue size.
	}


	// postcondition: If the queue is not empty, returns its
	//   first element & front references new first element.
	public Object remove() {
		Object item = peek();   // Retrieve first item.

		// Remove first element
		front = front.link;    // Delete first node.
		size--;                // Decrement queue size.

		return item;
	}


	// precondition : The queue has been created.
	// postcondition: If the queue is not empty, returns its
	//    first element.
	public Object peek() {
		if (isEmpty())
			throw new NullPointerException();
		return front.info;
	}


  // postcondition: Returns true if queue is empty;
  //   otherwise, returns False.
	public boolean isEmpty() {
	   return (size == 0);
	}


	public int getSize() {
		return size;
	}

	public String toString() {
    String result = "";
		ListNode next = front;

		while (next != null) {
		   result = result + next.info + "\n";
		   next = next.link;
		}
    return result;
	}

	public void moveToRear() {
		Object first = remove();
		insert(first);
	}


	public void moveToFront() {
		ListNode oldRear = rear;
		Object nextItem;

		while (front != oldRear) {
			nextItem = remove();
			insert(nextItem);
		}
	}



} // class Queue