/*
 * 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();
//        {
//            System.out.println("Strech");
//            int newcapacity=capacity*capacityIncrement;
//            int[] tempArray = new int[newcapacity];
//            {
//                for (int i = 0; i < in; i++)
//                {
//                    tempArray[i] = itemArray[i];
//                  cnt2.incr();
////                  cnt.outln(" push resize incr ");
//                }
//                for (int i = out; i < capacity; i++)
//                {
//                    tempArray[i + newcapacity - capacity] = itemArray[i];
//                  cnt2.incr();
////                  cnt.outln(" push resize incr ");
//               }
////                System.out.println();
////                System.out.println("strech in<out pre out: " + out);
//                out += newcapacity - capacity;
////                System.out.println("strech in<out post out: " + out);
//
//            }
//            capacity = newcapacity;
//            itemArray = tempArray;
////           this.dump();
//    }
//        cnt.incr();
//insert at the end
//        System.out.println("pre in: " + in);
        itemArray[in] = newItem;
        in = (in + 1)%capacity;
//        System.out.println("post in: " + in);
        count++;
        this.showAll();
    }
    
    public int dequeue()
    {
        int itemToReturn;
        if (count==0) return -99999;
        cnt3.incr();
        count--;
//        cnt.incr();
//        System.out.println();
//        System.out.println("Deq out = " + out);
        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();
//        {
//          System.out.println("Shrink");
//          int newcapacity = capacity / capacityIncrement;
//          int[] tempArray = new int[newcapacity];
//          if (in < out) //queue is split on two parts
//          {
//            for (int i = 0; i < in; i++)
//            {
//                tempArray[i] = itemArray[i];
//                cnt4.incr();
////                cnt.outln(" pop resize incr ");
//
//            }
//            for (int i = out; i < capacity; i++)
//            {
//                tempArray[i - (capacity - newcapacity)] = itemArray[i];
//                cnt4.incr();
////                cnt.outln(" pop resize incr ");
//            }
////                System.out.println();
////                System.out.println("shrink in<out pre out: " + out);
//                out -= capacity - newcapacity;
////                System.out.println();
////                System.out.println("shrink in<out post out: " + out);
//          }
//          else if (out < in)
//          {
//            for (int i = out; i < in; i++)
//            {
//                tempArray[i - out] = itemArray[i];
//                cnt4.incr();
////                cnt.outln(" pop resize incr ");
//            }
//            out = 0;
//            in = count%newcapacity;
//          }
//            //in == out can't happen because that would mean
//            //that queue before shrinking was either full or empty
//          itemArray = tempArray;
//          capacity = newcapacity;
//
////          this.dump();
//        }
        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];

            {
                for (int i = 0; i < in; i++)
                {
                    newArray[i] = itemArray[i];
                  cnt2.incr();
//                  cnt.outln(" push resize incr ");
                }
                for (int i = out; i < capacity; i++)
                {
                    newArray[i + newCapacity - capacity] = itemArray[i];
                  cnt2.incr();
//                  cnt.outln(" push resize incr ");
               }
//                System.out.println();
//                System.out.println("strech in<out pre out: " + out);
                out += newCapacity - capacity;
//                System.out.println("strech in<out post out: " + out);

            }
            capacity = newCapacity;
            itemArray = newArray;
//           this.dump();

            }

            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();
//                cnt.outln(" pop resize incr ");

            }
            for (int i = out; i < capacity; i++)
            {
                newArray[i - (capacity - newCapacity)] = itemArray[i];
                cnt4.incr();
//                cnt.outln(" pop resize incr ");
            }
//                System.out.println();
//                System.out.println("shrink in<out pre out: " + out);
                out -= capacity - newCapacity;
//                System.out.println();
//                System.out.println("shrink in<out post out: " + out);
          }
          else if (out < in)
          {
            for (int i = out; i < in; i++)
            {
                newArray[i - out] = itemArray[i];
                cnt4.incr();
//                cnt.outln(" pop resize incr ");
            }
            out = 0;
            in = count%newCapacity;
          }
            //in == out can't happen because that would mean
            //that queue before shrinking was either full or empty
          itemArray = newArray;
          capacity = newCapacity;

//          this.dump();
            }
}