/*
 * PriorityQueue2faster.java
 * SORTED INSERT ARRAY IMPLEMENTATION WITH ADDITIVE INCREMENT, resizing while inserting
 * Created on October 10, 2012, 3:40 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package priorityqueuetest;

/**
 *
 * @author suchenek
 */
public class PriorityQueue2faster {

    private int count;
    private int capacity;
    private int capacityIncrement;
    private int[] itemArray;

    /** Creates a new instance of PriorityQueue */
    public PriorityQueue2faster() {
        count=0;
        capacity=10;
        capacityIncrement=5;
        itemArray=new int[capacity];
    }

    public void insert(int newItem)
//    Sorted insert
    {
        int insertPosition = count;
        if(count==capacity) //no more space, "resize" the array up
        {
            capacity+=capacityIncrement;
            int[] tempArray = new int[capacity];
         while ((insertPosition > 0) && ((itemArray[insertPosition - 1] > newItem) & Bcnt.incr()))
         {
             insertPosition--;
             tempArray[insertPosition+1] = itemArray[insertPosition];
             cnt.incr();
         }

        tempArray[insertPosition] = newItem;
        count++;
        cnt.incr();
            for (int i = 0; i < insertPosition; i++)
            {
                tempArray[i] = itemArray[i];
                cnt2.incr();
            }
            itemArray = tempArray;
    }
        else
        {
        while ((insertPosition > 0) && ((itemArray[insertPosition - 1] > newItem) & Bcnt.incr()))
         {
             insertPosition--;
             itemArray[insertPosition+1] = itemArray[insertPosition];
             cnt.incr();
         }

        itemArray[insertPosition] = newItem;
        count++;
        cnt.incr();
        }
     }

    public int remove()
    {
        if (count==0) return -9999;
        int itemReturned = itemArray[--count];
        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;
        }
        cnt.incr();
        return itemReturned;
        }


      public int size()
      {
          return count;

      }

      public boolean isEmpty()
      {
          return count==0;
      }
                  public int Length()
      {
          return itemArray.length;

      }
    }