//Copyright Dr. Marek A. Suchenek, 2005 - 2025
/*
 * PriorityQueue.java
 *
 * 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 {
    
    //Uses heap as implementation
    
   
    private int count; //actual number of elements
    private int capacity; //the size of the array - 1 (itemArray[0] never used)
    private int capacityIncrement;
    private int[] itemArray;
    
    /** Creates a new instance of PriorityQueue */
    public PriorityQueue() {
        count=0;
        capacity=10;
        capacityIncrement=2;
        itemArray=new int[capacity + 1]; //itemArray[0] never used
    }
    
    public void insert(int newItem)
    {
        if(count==capacity) //no more space, "resize" the array up
        {
            capacity*=capacityIncrement;
            int[] tempArray = new int[capacity + 1]; //because itemArray[0] is not used
            for (int i = 1; i <= count; i++)
            {
                tempArray[i] = itemArray[i];
                 cnt2.incr();
            }
            itemArray = tempArray;
           
    }
        //try insert at the end
        count++; //1st element sits at index 1, 2nd element at index 2, etc,...
        //the newly inserted element may be too large to be a leaf
        int i = count; //initial "logical" position of newItem
                        //we keep it in itemArray[0] to save time on swapping
        while ((i > 1) && (cnt3.incr() & (newItem > itemArray[i/2])))
        {
            itemArray[i] = itemArray[i/2]; //demote the parent
            cnt.incr();
            i = i/2; //promote the new one i /= 2;
        }
        //here i is the index for the newly inserted element
        itemArray[i] = newItem;
        cnt.incr();
    }
    
    public int remove()
    {
     if (count==0) return -9999;
     //here count != 0
        int maxItem = itemArray[1]; //the root
        int demotee = count;
        count--;
        int i = 1;
        boolean demoted = true;
        while ((2*i <= count) && demoted)
        {
            int j = 2*i; // first child
            if ((j < count) && (cnt3.incr() & (itemArray[j] < itemArray[j + 1]))) j++;
            if (cnt3.incr() & (itemArray[j] > itemArray[demotee])) //demote patch
            {
                itemArray[i] = itemArray[j]; //promote its larger child
                cnt.incr();
                i = j; //demote patch's index

            }
            else
            {
                demoted = false;
            }
        }
        //i is the place for the patch
        itemArray[i] = itemArray[demotee];
        cnt.incr();
        itemArray[demotee] = 0; // for demonstration purpose only

        if ((count < capacity / capacityIncrement) &&  (10 <= capacity / capacityIncrement)) //space wasted, "resize" the array down
        {
          capacity/=capacityIncrement;
            int[] tempArray = new int[capacity+1];  //because itemArray[0] is not used
            for (i = 1; 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;
      }
    
      public void dump()
      {
          System.out.print("Dump heap: ");
          for (int i = 1; i <= count; i++) System.out.print(itemArray[i] + " ");
          System.out.println();
      }
}