package dataStructures;

/**
 * <p>Titulo: Uma implementaçao vectorial da Fila</p>
 * <p>Descrição: Esta implementaçao usa um vector circular crescente
                 definida na execução do construtor</p>
 * @version 1.0
 */

public class VQueue implements Queue,Cloneable {

   private final int DELTA = 128;
   private Object[]  theQueue;
   private int       begin, end;

   public VQueue() {
     theQueue = new Object[DELTA];
     begin    = 0;
     end      = theQueue.length - 1;
   }

   public Queue empty() {
     return new VQueue();
   }

   public boolean isEmpty() {
     return (end+1)%theQueue.length == begin;
   }

   /**
    * Increments the structure length (adds 'DELTA' new slots)
    */
   private void grow() {
     Object[] newQueue = new Object[theQueue.length + DELTA];

     for(int i=begin,j=0;i!=(end+1)%theQueue.length;i=(i+1)%theQueue.length,j++)
       newQueue[j] = theQueue[i];

     begin = 0;
     end = theQueue.length-2;
     theQueue = newQueue;
   }

   public void enqueue(Object item) {
     if ((end+2)%theQueue.length == begin)
        grow();

     end           = (end+1) % theQueue.length;
     theQueue[end] = item;
   }

   public Object front() {
     return theQueue[begin];
   }

   public void dequeue() {
     theQueue[begin] = null;
     begin = (begin+1) % theQueue.length;
   }

   public boolean equals(Queue q) {
     int actual = begin;
     Queue   cp = (Queue)(q.clone());

     while (!cp.isEmpty()) {
       if (actual==(end+1)%theQueue.length || !theQueue[actual].equals(cp.front()))
         return false;
       cp.dequeue();
       actual = (actual+1)%theQueue.length;
     }

     return actual==(end+1)%theQueue.length;
   }

   public Object clone() {
     VQueue cp = new VQueue();

     cp.theQueue = new Object[theQueue.length];
     cp.begin    = begin;
     cp.end      = end;

     for(int i=0;i<theQueue.length;i++)
       cp.theQueue[i] = theQueue[i];

     return cp;
   }

   public String toString() {
     if (isEmpty())
       return "<[]<";

     String s = "<[" + theQueue[begin];
     for(int i=(begin+1)%theQueue.length;
             i!=(end+1)%theQueue.length;
             i=(i+1)%theQueue.length)
       s += "," + theQueue[i];
     return s + "]<";
   }

   //********************************************************************
   public static void main(String[] args) {
    VQueue v1 = new VQueue(),
           v2 = new VQueue();

    v1.enqueue(new Integer(1));
    v1.enqueue(new Integer(2));
    v1.enqueue(new Integer(3));
    v1.enqueue(new Integer(4));
    v1.enqueue(new Integer(5));
    v1.enqueue(new Integer(6));
    v1.enqueue(new Integer(7));
    v1.enqueue(new Integer(8));
    v1.enqueue(new Integer(9));
    v1.dequeue();
    v1.dequeue();
    v1.dequeue();
    v1.enqueue(new Integer(1));
    v1.enqueue(new Integer(2));
    v1.enqueue(new Integer(3));
    v1.dequeue();
    v1.dequeue();
    v1.dequeue();
    v1.dequeue();
    v1.dequeue();
    VQueue v3 = (VQueue)v1.clone();

    System.out.println(v3.equals(v1)?"==":"!=");
    System.out.println(v1 + " " + v2 + " " + v3);
  }
}  // endClass AQueue