package Queue;

import java.lang.*;
import java.util.*;
import Queue.*;

/**
 * Class QImpl implements the interface Queue.  Operations on
 * the queue interface are synchronized to allow concurrent access.
 *
 * @see Queue.Queue
 * @author Thomas Wang
 * @version 0.55
 */
public class QImpl
  implements Queue
{
  /** keep track of queue size */
  protected int num_elem;

  /** refers to the first element */
  protected QNodeImpl head_node;

  /** refers to the last element */
  protected QNodeImpl tail_node;

  /**
   * Constructor, creates an empty queue.
   */
  public QImpl()
  {
    this.num_elem = 0;
    this.head_node = null;
    this.tail_node = null;
  }

  /**
   * Returns the last element of the queue without removing the
   * element.
   * @return the last element
   */
  public synchronized Object lastElement()
    throws NoSuchElementException
  {
    if (this.tail_node == null)
      throw new NoSuchElementException();
    else
      return this.tail_node.elem;
  }

  /**
   * Returns the first element of the queue without removing the
   * element.
   * @return the first element
   */
  public synchronized Object firstElement()
    throws NoSuchElementException
  {
    if (this.head_node == null)
      throw new NoSuchElementException();
    else
      return this.head_node.elem;
  }

  /**
   * Insert the specified element into the front of the queue.
   * @param elem element to be inserted
   */
  public synchronized void insertFirst(Object elem)
  {
    if (this.head_node == null)
    {
      this.head_node = this.tail_node =
        new QNodeImpl(elem);
    }
    else
    {
      QNodeImpl temp =
        new QNodeImpl(elem, null, this.head_node);
      this.head_node.prev = temp;
      this.head_node = temp;
    }
    ++this.num_elem;
  }

  /**
   * Insert the specified element into the back of the queue.
   * @param elem element to be inserted
   */
  public synchronized void insertLast(Object elem)
  {
    if (this.head_node == null)
    {
      this.head_node = this.tail_node =
        new QNodeImpl(elem);
    }
    else
    {
      QNodeImpl temp =
        new QNodeImpl(elem, this.tail_node, null);
      this.tail_node.next = temp;
      this.tail_node = temp;
    }
    ++this.num_elem;
  }

  /**
   * Remove and return an element from the front of the queue.
   * @return the element at the front of the queue
   * @exception NoSuchElementException thrown when there are no
   * elements in the queue
   */
  public synchronized Object removeFirst()
    throws NoSuchElementException
  {
    if (this.head_node == null)
      throw new NoSuchElementException();
    else
    {
      Object result = this.head_node.elem;
      --this.num_elem;
      if (this.head_node == this.tail_node)
      {
        this.head_node = this.tail_node = null;
      }
      else
      {
        QNodeImpl newhead = this.head_node.next;
        newhead.prev = null;
        this.head_node = newhead;
      }
      return result;
    }
  }

  /**
   * Remove and return an element from the back of the queue.
   * @return the element at the back of the queue
   * @exception NoSuchElementException thrown when there are no
   * elements in the queue
   */
  public synchronized Object removeLast()
    throws NoSuchElementException
  {
    if (this.head_node == null)
      throw new NoSuchElementException();
    else
    {
      Object result = this.tail_node.elem;
      --this.num_elem;
      if (this.head_node == this.tail_node)
      {
        this.head_node = this.tail_node = null;
      }
      else
      {
        QNodeImpl newtail = this.tail_node.prev;
        newtail.next = null;
        this.tail_node = newtail;
      }
      return result;
    }
  }

  /**
   * Returns the number of elements in the queue.
   */
  public synchronized int size()
  {
    return this.num_elem;
  }

  /**
   * Returns an enumeration of the elements in the queue.
   * @see java.util.Enumeration
   * @return the enumeration
   */
  public synchronized Enumeration elements()
  {
    int len = this.num_elem;
    FixEnumImpl the_enum = new FixEnumImpl(len);
    int indx;
    QNodeImpl cur_node = this.head_node;
    for (indx = 0; indx < len; ++indx)
    {
      the_enum.addMember(cur_node.elem);
      cur_node = cur_node.next;
    }
    return the_enum;
  }

  /**
   * Returns a shallow copy of the queue.
   * @see java.lang.Object#clone
   */
  public synchronized Object clone()
  {
    QImpl result = new QImpl();
    int len = this.num_elem;
    int indx;
    QNodeImpl cur_node = this.head_node;
    for (indx = 0; indx < len; ++indx)
    {
      result.insertLast(cur_node.elem);
      cur_node = cur_node.next;
    }
    return result;
  }
}