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


package priorityqueuetest;


/**
 *
 * @author suchenek
 */
public class PriorityQueueTest {
    
        
//    /** Creates a new instance of PriorityQueueTest */
//    public PriorityQueueTest() {
// }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here 
           int[] Array;
           int N;
 for (N = 1; N<=100; N++)
 {
        Array = new int[N];
        for (int i = 0; i < N; i++)
        Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
        for (int i = 0; i < N; i++)
        Array[i] = -i;
        
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        cnt.clr(); //counts moves of keys while sorting
        cnt2.clr(); //counts moves of keys while resizing
        Bcnt.clrAll(); //counts comparisons of keys while sorting
        PriorityQueueSort(Array);
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
//        Tcomp(N) is the sorting "time" measured by the number of comparisons
//        of keys
        System.out.print("Tcomp(" + N +")");
        Bcnt.out(" = ");
        System.out.print("  " + (N*(N-1)/2) + " = N*(N-1)/2");
//        Tmov(N) is the sorting "time" measured by the number of moves
//        of keys, not including resizing
        System.out.print("  Tmov(" + N +")");
        cnt.out(" = ");
        System.out.println("  " + (3*N + N*(N-1)/2) + " = 3*N + N*(N-1)/2");
//        R(N) is the resizing "time"
        System.out.print("R(" + N +")");
        cnt2.out(" = ");
        System.out.println(" " +
         (2*(10*Math.round(Math.exp(Math.log(2)*Math.ceil(Math.log(N/10.)/Math.log(2.)))) - 10)) +
         " = 2*(10*Math.round(Math.exp(Math.log(2)*Math.ceil(Math.log(N/10.)/Math.log(2.)))) - 10)");
//        Total cost of resizing is wice the cost of upsizing because the cost of downsizing is
//        the same as the cost of upsizing:
//        2*(10*2^(ceil(lg2(N/10))) - 10)
//        If the cost of the downsizing is half the cost of upsizing (in a faster version of remove)
//        then the total cost of resizing is:
//        3*(10*2^(ceil(lg2(N/10))) - 10)/2
 }
}
    public static void  PriorityQueueSort(int[] A)
    {
        int n = A.length;
        PriorityQueue PQ = new PriorityQueue();
        for (int i = 0; i < n; i++) PQ.insert(A[i]);
//        for (int i = n-1; i >= 0; i--) PQ.insert(A[i]);
//        System.out.println("A Size of PQ is " + PQ.Length());
        for (int i = n-1; i >= 0; i--) A[i]=PQ.remove();
//        for (int i = 0; i < n; i++) A[i]=PQ.remove();
//        System.out.println("B Size of PQ is " + PQ.Length());
        
    }

}