/* COPYRIGHT DR. MAREK SUCHENEK 2008 - 2030
 * O_QUEUE.java
 *
 * Created on March 18, 2008, 7:44 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package split;


/**
 *
 * @author suchenek
 */
public class O_QUEUE {
    
//A queue of Objects implemeted as circular queue with exponential
//resizing up and down.
    
//Average time of resizing per enqueue/dequeue is O(1).
    
    //instance variables here (there is no class variables)
           
    private int count; //actual number of elements
    private int capacity; //maximum number of elements
    private int resizeFactor; //resizing factor - must be integer in this variant
    private Object[] itemArray; //"circular" array
    private int in; //index for next insertion, incremented %capacity
    private int out; //index for next deletion, incremented %capacity
    //in == out iff count == 0 (queue empty) or count == capacity (queue full)
    
    /** Creates a new instance of O_QUEUE */
    public O_QUEUE() 
    //Empty queue with initial capacity 10, resizing factor 2 
    {
        count=0; //empty
        capacity=10; //initial capacity
        resizeFactor=2; //must be integer >= 2 in this variant
        itemArray=new Object[capacity];
        out = 0; //cound be any index
        in = 0; //because out == 0 here
    }
    
    public void enqueue(Object newItem)
//Inserts new element at the "end" of this queue
    {
        if(count==capacity) //no more space, "resize" the array up
                            //in == out
        {
            int newcapacity=capacity*resizeFactor;
            Object[] tempArray = new Object[newcapacity];
            if (out == 0) //in == out == 0; this queue is in one piece
            {
                    //copy this queue in one piece
                    for (int i = 0; i < capacity; i++)
                        {
                            tempArray[i] = itemArray[i];
                            in = count; //because out == 0 here
                        }
            }
            else //in == out != 0; this queue is split onto 2 pieces
            {
                //copy the "left" part of this queue
                for (int i = 0; i < in; i++)
                {
                    tempArray[i] = itemArray[i];
                }
                //copy the "right" part of this queue
                for (int i = out; i < capacity; i++)
                {
                    tempArray[i + newcapacity - capacity] = itemArray[i];
                }
                //out needs to be "moved" to the right by the size of the strech
                out += newcapacity - capacity;
            }
            capacity = newcapacity; //sterch done
            itemArray = tempArray; //updaing reference
    }
        //at this point there is room for insertion
        itemArray[in] = newItem;
        in = (in + 1)%capacity; //% because array is "circular"
        count++; //insertion complete
    }
    
    public Object dequeue()
    {
        Object itemToReturn;
        if (count==0) return null; //this queue was empty
        count--; //will remove one element
        itemToReturn=itemArray[out];
        if (count != 0)
        {
            out = (out + 1) % capacity; //because array is "circular"
        }
        else //this queue is empty here
        {
            in = 0;
            out = 0;
        }
        if ((count <= capacity / (resizeFactor*resizeFactor)) &&  
                //resFact squared to avoid instability of resizing
                (10 <= capacity / (resizeFactor*resizeFactor))) 
                //space wasted, "resize" the array down
                //count != 0 here because it was conunt = capacity
                //before this dequeue()
                //So, in != out
        {
          int newcapacity = capacity / resizeFactor;
          Object[] tempArray = new Object[newcapacity];
          if (in < out) //this queue is split on two parts
          {
            //copying the "left" part 
            for (int i = 0; i < in; i++)
            {
                tempArray[i] = itemArray[i];
            }
            //copying the "right" part"
            for (int i = out; i < capacity; i++)
            {
                tempArray[i - capacity + newcapacity] = itemArray[i];
            }
                out -= capacity - newcapacity; //out was moved to the left
          }
          else if (out < in) //this que is in one piece
          {
            //copy to the begining of the array
            for (int i = out; i < in; i++)
            {
                tempArray[i - out] = itemArray[i];
            }
            out = 0; 
            in = count; //since out == 0 but count < capacity here
          } //in == out can't happen because that would mean
            //that queue before shrinking was either full or empty
          itemArray = tempArray; //updating reference
          capacity = newcapacity; //shrinking done
        }
        return itemToReturn;
        }
    
      public int size()
      //returns the actual number of elements in this queue
      {
          return count;        
      }
      
      public boolean isEmpty()
      //returns true is this queue is empty, returns false otherwise
      {
          return count==0;
      }
      
      public int Length()
      //returns the size ot the array that implements this queue
      {
          return itemArray.length;         
      }
}