/*
 * QUEUE.java
 *
 * Created on March 17, 2008, 1:21 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package split;


/**
 *
 * @author suchenek
 */
public class QUEUE {
    
    
   
    private int count;
    private int capacity;
    private int capacityIncrement;
    private int[] itemArray;
    private int in, out;
    
    /** Creates a new instance of PriorityQueue */
    public QUEUE() {
        count=0;
        capacity=10;
        capacityIncrement=2;
        itemArray=new int[capacity];
        in = 0;
        out = 0;
    }
    
    public void enqueue(int newItem)
    {
        cnt.incr();
        if(count==capacity) //no more space, "resize" the array up
                            //in == out
            Stretch();
        itemArray[in] = newItem;
        in = (in + 1)%capacity;
        count++;
        this.showAll();
    }
    
    public int dequeue()
    {
        int itemToReturn;
        if (count==0) return -99999;
        cnt3.incr();
        count--;
        itemToReturn=itemArray[out];
        itemArray[out] = 0; // for the students to see the contents
        if (count != 0)
        {
            out = (out + 1) % capacity;
        }
        else
        {
            in = 0;
            out = 0;
        }
        if ((count <= capacity / ((capacityIncrement)*(capacityIncrement))) &&  
                (10 <= capacity / capacityIncrement)) 
                //space wasted, "resize" the array down
                //count != 0 here because it msy only happen if capacity < 10 / capacityIncrement
                //before this dequeue()
                //So, in != out
            Shrink();
        this.showAll();
        
        return itemToReturn;
        }
      public int size()
      {
          return count;
          
      }
      
      public boolean isEmpty()
      {
          return count==0;
      }
            public int Length()
      {
          return itemArray.length;
          
      }
            public void dump()
            {
                int i = out;
                int j = count;
                System.out.println("Dump:");
                while (j > 0)
                {
                    System.out.print(itemArray[i] + " ");
                    j--;
                    i = (i + 1) % capacity;
                }
                System.out.println(" End Dump");
                
            }
            public void showAll()
            {
                 System.out.println("cap = " +capacity + 
                         " cnt = " + count + " in = " + in + 
                         " out = " + out);
               for (int i = 0; i < capacity; i++)
                System.out.print(itemArray[i] + " ");
                System.out.println();
            }

            private void Stretch()
            {
            System.out.println("Strech");
            int newCapacity=capacity*capacityIncrement;
            int[] newArray = new int[newCapacity];
            if (out == 0) //in == out == 0
            {
                    for (int i = 0; i < capacity; i++)
                        {
                            newArray[i] = itemArray[i];
                          cnt2.incr();
                            in = count; //in + newcapacity - capacity
                        }
            }
            else //in == out != 0
            {
                for (int i = 0; i < in; i++)
                {
                    newArray[i] = itemArray[i];
                  cnt2.incr();
                }
                for (int i = out; i < capacity; i++)
                {
                    newArray[i + newCapacity - capacity] = itemArray[i];
                  cnt2.incr();
               }
                out += newCapacity - capacity;

            }
            capacity = newCapacity;
            itemArray = newArray;

            }

            private void Shrink()
            {
          System.out.println("Shrink");
          int newCapacity = capacity / capacityIncrement;
          int[] newArray = new int[newCapacity];
          if (in < out) //queue is split on two parts
          {
            for (int i = 0; i < in; i++)
            {
                newArray[i] = itemArray[i];
                cnt4.incr();

            }
            for (int i = out; i < capacity; i++)
            {
                newArray[i - (capacity - newCapacity)] = itemArray[i];
                cnt4.incr();
            }
                out -= capacity - newCapacity;
          }
          else if (out < in)
          {
            for (int i = out; i < in; i++)
            {
                newArray[i - out] = itemArray[i];
                cnt4.incr();
            }
            out = 0;
            in = count%newCapacity;
          }
          itemArray = newArray;
          capacity = newCapacity;

            }
}