/** Un QueuedSet è come una coda e un insieme allo stesso tempo. */

import java.util.*;

public class QueuedSet extends HashSet implements Queue {

	 private DLLNode head, tail;

	 /** Costruisce l'insieme vuoto. */
	 public QueuedSet() {
		  super(); // Insieme vuoto
		  head = new DLLNode( null );
		  tail = new DLLNode( null );
		  tail.insertAfter( head );
	 }

	 /* --- I metodi isEmpty(), size() non vengono riscritti --- */
	 /* --- Metodi di Set che dobbiamo riscrivere --- */

	 public boolean add( Object o ) {
		  DLLNode node = new DLLNode( o );
		  boolean newNode = super.add( node );
		  if ( newNode ) node.insertBefore( tail );
		  return newNode;
	 }

	 public boolean addAll(Collection c) {
		  Iterator it = c.iterator();
		  boolean someNewNode = false;
		  while ( it.hasNext() ) 
				someNewNode = someNewNode || add( it.next() );
		  return someNewNode;
	 }

	 public void clear() {
		  super.clear();
		  head = new DLLNode( null );
		  tail = new DLLNode( null );
		  tail.insertAfter( head );
	 }

	 public boolean contains(Object o) {
		  return super.contains( new DLLNode( o ) );
	 }

	 public boolean containsAll(Collection c) {
		  Iterator it = c.iterator();
		  while ( it.hasNext() )
				if ( ! ( contains( it.next() ) ) ) 
					 return false;
		  return true;
	 }
	 
	 public boolean equals( Object o ) {
		  if ( ! ( o instanceof QueuedSet ) ) return false;
		  Iterator it = this.iterator();
		  Iterator other = ((QueuedSet) o).iterator();
		  while ( it.hasNext() && other.hasNext() ) 
				if ( ! ( it.next().equals( other.next() ) ) ) return false;
		  if ( it.hasNext() ) return false;
		  if ( other.hasNext() ) return false;
		  return true;
	 }
	 
	 public int hashCode() {
		  return size();
	 }

	 public Object[] toArray( Object a[] ) {
		  int n = size();
		  Object res[];

		  if ( a.length >= n ) res = a;
		  else res = new Object[n];

		  Iterator it = iterator();
		  int i = 0;
		  while ( it.hasNext() ) {
				res[i++] = it.next();
		  }

		  return res;
	 }

	 public Object[] toArray() {
		  return toArray( new Object[0] );
	 }

	 /* --- Metodi opzionali di Set che non implementiamo --- */

	 public boolean remove(Object o) 
	 { throw new UnsupportedOperationException(); }
	 public boolean removeAll(Collection c) 
	 { throw new UnsupportedOperationException(); }
	 public boolean retainAll(Collection c) 
	 { throw new UnsupportedOperationException(); }

	 /* --- Metodi di Queue --- */
	 public void enqueue( Object o ) { 
		  add( o );
	 }

	 public Object dequeue() {
		  if ( isEmpty() ) return null;
		  DLLNode node = head.getNext();
		  node.remove();
		  super.remove( node );
		  return node.getContent();
	 }

	 public Iterator iterator() {
		  return new QueuedSetIterator();
	 }

	 /**** CLASSE PRIVATA QueuedSetIterator */

	 private class QueuedSetIterator implements Iterator {
		  
		  DLLNode current;

		  private QueuedSetIterator() { 
				current = head.getNext(); 
		  }
		  public boolean hasNext() { 
				return ( current != tail ); 
		  }
		  public Object next() { 
				Object res = current.getContent();
				current = current.getNext();
				return res;
		  }
		  public void remove() 
		  { throw new UnsupportedOperationException(); }
	 }
}