package Queue;

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

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

  /** refers to the head node */
  protected QNodeImpl head_node;

  /** refers to the tail node */
  protected QNodeImpl tail_node;

  /** item hash table */
  protected Hashtable hash_table;

  /**
   * Constructor, creates an empty queue.
   */
  public UniqQImpl()
  {
    this.num_elem = 0;
    this.hash_table = new Hashtable();
    this.head_node = new QNodeImpl(null);
    this.tail_node = new QNodeImpl(null, this.head_node, null);
    this.head_node.next = this.tail_node;
  }

  /**
   * 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.prev == this.head_node)
      throw new NoSuchElementException();
    else
      return this.tail_node.prev.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.next == this.tail_node)
      throw new NoSuchElementException();
    else
      return this.head_node.next.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.hash_table.containsKey(elem))
      throw new DuplicateElementException();
    QNodeImpl next_node = this.head_node.next;
    QNodeImpl temp =
      new QNodeImpl(elem, this.head_node, next_node);
    this.hash_table.put(elem, temp);
    this.head_node.next = next_node.prev = 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.hash_table.containsKey(elem))
      throw new DuplicateElementException();
    QNodeImpl prev_node = this.tail_node.prev;
    QNodeImpl temp =
      new QNodeImpl(elem, prev_node, this.tail_node);
    this.hash_table.put(elem, temp);
    this.tail_node.prev = prev_node.next = 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.next == this.tail_node)
      throw new NoSuchElementException();
    else
    {
      Object result = this.head_node.next.elem;
      this.hash_table.remove(result);
      this.head_node.next.remove();
      --this.num_elem;
      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.next == this.tail_node)
      throw new NoSuchElementException();
    else
    {
      Object result = this.tail_node.prev.elem;
      this.hash_table.remove(result);
      this.tail_node.prev.remove();
      --this.num_elem;
      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.next;
    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()
  {
    UniqQImpl result = new UniqQImpl();
    int len = this.num_elem;
    int indx;
    QNodeImpl cur_node = this.head_node.next;
    for (indx = 0; indx < len; ++indx)
    {
      result.insertLast(cur_node.elem);
      cur_node = cur_node.next;
    }
    return result;
  }

  /**
   * Returns true if the specified element is inside the queue.
   * False is returned otherwise.
   *
   * @param element the specified element
   * @return true or false
   */
  public synchronized boolean isInside(Object element)
  {
    return this.hash_table.containsKey(element);
  }

  /**
   * Remove the specified element from the queue.  If the element
   * is not inside the queue, then exception NoSuchElementException
   * will be thrown.
   *
   * @param element the specified element
   * @exception NoSuchElementException thrown when specified element
   * is not inside the queue.
   */
  public synchronized void removeElement(Object element)
    throws NoSuchElementException
  {
    if (! this.hash_table.containsKey(element))
      throw new NoSuchElementException();
    QNodeImpl mynode = (QNodeImpl) this.hash_table.get(element);
    this.hash_table.remove(element);
    mynode.remove();
    --this.num_elem;
  }

}