package lab.util;

import java.util.NoSuchElementException;

/**
 * A classic first-in first-out queue data structure.
 * 
 * @param <E>
 *          the type of element held in this queue
 */
public class Queue<E> {

  /**
   * Queue uses a node based implementation, where the nodes form a singly
   * linked-list like structure. The queue must maintain a reference to the node
   * holding the element at the front of the queue, and a reference to the node
   * holding the element at the end of the queue.
   */

  /**
   * The node at the front of the queue (the first node, or head, of the linked
   * list).
   */
  private Node<E> front;

  /**
   * The node at the back of the queue (the last node of the linked list)
   */
  private Node<E> back;

  /**
   * The number of elements stored in this queue (or the number of nodes)
   */
  private int size;

  /**
   * Creates an empty queue (size is zero).
   */
  public Queue() {


  }

  /**
   * Enqueue an element. This operation adds the element to the back of the
   * queue.
   * 
   * @param element
   *          the element to add to the back of the queue
   */
  public void enqueue(E element) {


  }

  /**
   * Dequeue an element. This operation removes and returns the element at the
   * front of the queue if the queue is not empty.
   * 
   * @return the element at the front of the queue if the queue is not empty
   * @throws NoSuchElementException
   *           if the queue is empty
   */
  public E dequeue() {


  }

  /**
   * Return the element at the front of the queue without dequeuing the element.
   * 
   * @return the element at the front of the queue if the queue is not empty
   * @throws NoSuchElementException
   *           if the queue is empty
   */
  public E peek() {


  }

  /**
   * Returns the number of elements in this queue.
   * 
   * @return the number of elements in this queue
   */
  public int size() {


  }

  /**
   * Returns true if this queue is empty, and false otherwise.
   * 
   * @return true if this queue is empty, and false otherwise
   */
  public boolean isEmpty() {


  }

  /**
   * Returns the node at the front of the queue. This method is here for
   * debugging and testing purposes.
   * 
   * @return the node at the front of the queue
   */
  Node<E> getFront() {
    return this.front;
  }

  /**
   * Returns the node at the back of the queue. This method is here for
   * debugging and testing purposes.
   * 
   * @return the node at the back of the queue
   */
  Node<E> getBack() {
    return this.back;
  }

  /**
   * Returns a hash code for this queue. The hash code is computed using the
   * elements of this stack.
   * 
   * @return a hash code for this queue
   * @see java.lang.Object#hashCode()
   */
  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    NodeIterator<E> itr = new NodeIterator<E>(this.front);
    boolean hasNext = itr.hasNext();
    while (hasNext) {
      result = prime * result + itr.next().getElement().hashCode();
      hasNext = itr.hasNext();
    }
    return result;
  }

  /**
   * Compares the specified object to this queue for equality. Two queues are
   * equal if they contain the same number of elements in the same order.
   * 
   * @param obj
   *          the object to compare to this queue for equality
   * @return true if the specified object is equal to this queue
   * @see java.lang.Object#equals(java.lang.Object)
   */
  @Override
  public boolean equals(Object obj) {
    boolean eq = false;
    if (this == obj) {
      eq = true;
    } else if (obj != null && this.getClass() == obj.getClass()) {
      Queue<E> other = (Queue<E>) obj;
      if (this.size == other.size()) {
        NodeIterator<E> itr1 = new NodeIterator<E>(this.front);
        NodeIterator<E> itr2 = new NodeIterator<E>(other.front);
        boolean hasNext = itr1.hasNext();
        eq = true;
        while (hasNext && eq) {
          E e1 = itr1.next().getElement();
          E e2 = itr2.next().getElement();
          eq = eq && e1.equals(e2);
          hasNext = itr1.hasNext();
        }
      }
    }
    return eq;
  }

  /**
   * Returns a string representation of this queue. The string representation
   * consists of a list of the queue's elements from the front of the queue to
   * the back of the queue, enclosed in square brackets ("[]"). Adjacent
   * elements are separated by the characters ", " (comma and space). Elements
   * are converted to strings as by String.valueOf(Object).
   * 
   * @return a string representation of this queue
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString() {
    NodeIterator<E> itr = new NodeIterator<E>(this.front);
    StringBuilder b = new StringBuilder("[");
    boolean hasNext = itr.hasNext();
    while (hasNext) {
      Node<E> n = itr.next();
      b.append(n.getElement().toString());
      hasNext = itr.hasNext();
      if (hasNext) {
        b.append(", ");
      }
    }
    b.append("]");
    return b.toString();
  }
}