/**
 * A Queue is a first-in, first-out (FIFO) abstract data type.
 *
 * @author Zach Tomaszewski
 * @param <E>  The data type of elements to be stored in this Queue.
 */
public class Queue<E> {

  //new items are added to back and removed from front.
  //Node links should go from back towards front.
  private Node<E> front;
  private Node<E> back;

  /**
   * Constructs a new empty Queue.
   */
  public Queue() {
    this.front = null;
    this.back = null;
  }

  /**
   * Adds the given item to the back of this queue.
   * If this item is added to an empty queue, it will also become the
   * first item in the queue.
   */
  public void offer(E item) {
    if (this.back == null) {
      this.back = new Node<E>(item);
      this.front = this.back;
    }else {
      this.back.setNext(new Node<E>(item));
      this.back = this.back.getNext();
    }
  }

  /**
   * Returns the item at the front of this Queue.
   * If there is no such item (queue is empty) will throw an
   * IllegalStateException instead.
   */
  public E peek() {
    if (this.front != null) {
      return this.front.getData();
    }else {
      throw new IllegalStateException("Cannot peek() at empty queue.");
    }
  }

  /**
   * Removes and returns the item at the front of this Queue.
   * If there is no such item (queue is empty) will throw an
   * IllegalStateException instead.
   */
  public E poll() {
    E item = this.peek();  //may throw exception if empty queue
    this.front = this.front.getNext();
    if (this.front == null) {
      this.back = null;
    }
    return item;
  }

  /**
   * Returns the number of items currently in this Queue.
   */
  public int size() {
    //not very efficient, but means you don't need to track size elsewhere
    int size = 0;
    for (Node<E> curr = this.front; curr != null; curr = curr.getNext()) {
      size++;
    }
    return size;
  }

  /**
   * Returns a String showing the contents of the queue from front to back.
   */
  @Override
  public String toString() {
    StringBuilder str = new StringBuilder();
    str.append("[");
    for (Node<E> curr = this.front; curr != null; curr = curr.getNext()) {
      str.append(curr.getData());
      if (curr.getNext() != null) {
        str.append(", ");
      }
    }
    str.append("]");
    return str.toString();
  }


  /**
   * Runs some tests of a queue.  Should print all true in the left column.
   */
  public static void main(String[] args) {
    Queue<Integer> q = new Queue<Integer>();
    int size = 0;

    //empty queue behavior
    System.out.print("\tEmpty queue. ");
    testQueueState(q, size, 0, "[]");

    testOffer(q, 3, ++size, 3, "[3]");
    testOffer(q, 5, ++size, 3, "[3, 5]");
    testOffer(q, 7, ++size, 3, "[3, 5, 7]");

    testPoll(q, --size, 5, "[5, 7]");
    testOffer(q, 9, ++size, 5, "[5, 7, 9]");
    testPoll(q, --size, 7, "[7, 9]");
    testPoll(q, --size, 9, "[9]");
    testPoll(q, --size, 0, "[]");

    testOffer(q, 2, ++size, 2, "[2]");
  }

  /**
   * Offers the given val to the given queue, after which it should have the
   * given front, size and str representation.  If expected size is 0, front
   * will be ignored and will check that peek() throws an exception instead.
   */
  private static void testOffer(Queue<Integer> q, int val,
                                int size, int front, String str) {
    System.out.print("\tOffering " + val + ".  ");
    q.offer(val);
    testQueueState(q, size, front, str);
  }

  private static void testPoll(Queue<Integer> q,
                                int size, int front, String str) {
    System.out.print("\tPolling ");
    int returned = q.poll();
    System.out.print(returned + ". ");
    testQueueState(q, size, front, str);
  }

  private static void testQueueState(Queue<Integer> q,
                                     int size, int front, String str) {
    System.out.println("Queue now size " + q.size() + ": " + q);
    System.out.println(q.toString().equals(str));
    System.out.println(q.size() == size);
    if (size != 0) {
      System.out.println(q.peek().equals(front));
    }else {
      try {
        q.peek();
        System.out.println(false);
      }catch (IllegalStateException e) {
        System.out.println(true);
      }
    }
  }

}