/*
 * PriorityQueue.java
 * UNSORTED INSERT ARRAY IMPLEMENTATION WITH MULTIPLICATIVE INCREMENT
 * Created on February 20, 2008, 1:26 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package priorityqueuetest;

/**
 *
 * @author suchenek
 */
public class PriorityQueue {
    
   
    private int count;
    private int capacity;
    private int capacityIncrement;
    private int[] itemArray;
    
    /** Creates a new instance of PriorityQueue */
    public PriorityQueue() {
        count=0;
        capacity=10;
        capacityIncrement=2;
        itemArray=new int[capacity];
    }
    
    public void insert(int newItem)
//    Unsorted insert
    {
        if(count==capacity) //no more space, "resize" the array up
        {
            capacity*=capacityIncrement;
            int[] tempArray = new int[capacity];
            for (int i = 0; i < count; i++)
            {
                tempArray[i] = itemArray[i];
                cnt2.incr();
            }
            itemArray = tempArray;
           
    }
        cnt.incr();
//insert at the end
        itemArray[count++] = newItem;
    }
    
    public int remove()
    {
     if (count==0) return -999999;
     //here count != 0
        int maxPosition = 0;
        int maxItem = itemArray[0];
        cnt.incr();
        for (int i = 1; i < count; i++) 
        {
        if (itemArray[i] > maxItem & Bcnt.incr())
        {
           maxPosition=i;
           maxItem=itemArray[i];
           cnt.incr();
        }
        }
        itemArray[maxPosition]=itemArray[--count];
        cnt.incr();        
        if ((count <= capacity / capacityIncrement ) &&  (10 <= capacity / capacityIncrement)) //space wasted, "resize" the array down
        {
          capacity/=capacityIncrement;
            int[] tempArray = new int[capacity];
            for (int i = 0; i < count; i++)
            {
                tempArray[i] = itemArray[i];
                cnt2.incr();
            }
            itemArray = tempArray;  
        }
        
        return maxItem;
        }
      public int size()
      {
          return count;
          
      }
      
      public boolean isEmpty()
      {
          return count==0;
      }
            public int Length()
      {
          return itemArray.length;
          
      }
    }