/**
  realizza l'interfaccia Queue usando internamente un array riempito parzialmente.
  @author Adriano Luchetta
  @version 16-Nov-2003
  @version 27-Nov-2004
  @version 21-Nov-2005
*/
public class ArQueue implements Queue
{
   // parte privata
   private Object[] list;
   private int front;
   private int back;
   
   public ArQueue()
   {
      list = new Object[1];
      makeEmpty();
   }
   
   /**
     O(1)
   */
   public boolean isEmpty()
   {
      return front == back;
   }
   
   /**
     O(1)
   */
   public void makeEmpty()
   {
      front = back = 0;
   }
   
   /**
     O(1)
   */
   public int size()
   {
      if (back > front)
         return back - front;
         
      return list.length - front + back;
   }
   
   /**
     in media O(1)
   */
   public void enqueue(Object obj)
   {
      if (increment(back) == front)
      {
         Object[] newList = new Object[2 * list.length];
         for (int i = 0; i < list.length; i++)
            newList[i] = list[i];
            
         list = newList;
      
         if (back < front)
         {
            for (int i = 0; i < back; i++)
               list[list.length/2 + i] = list[i];
            
            back += list.length/2;
         }
      }

      list[back] = obj;
      back = increment(back);
   }

   /**
     O(1)
   */
   public Object front() throws EmptyQueueException
   {
      if (isEmpty())
         throw new EmptyQueueException();

      return list[front];
   }

   /**
     O(1)
   */
   public Object dequeue() throws EmptyQueueException
   {
      Object obj = front();
      list[front] = null;
      front = increment(front);
      return obj;
   }
   
   private int increment(int n)
   {
      return (n + 1) % list.length;
   }
}