//Copyright Dr. Marek A. Suchenek, 2005 - 2025
/*
 * PriorityQueueTest.java
 *
 * Created on February 20, 2008, 1:02 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 Lim = 20;
           int N;
 for (N = 1; N<=Lim; 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)%(100*Lim);
//        for (int i = 0; i < N; i++)
//        Array[i] = -i;
        System.out.println("*** N = " + N + " ***");
        System.out.print("Input: ");
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        cnt.clr(); //counts copying of keys while sorting
        cnt2.clr(); //counts copying of keys while resizing
        cnt3.clr(); //counts comparisons of keys
        PriorityQueueSort(Array);
        System.out.print("Sorted: ");
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        System.out.print("C(" + N +")");
        cnt3.out(" = ");
        int Flgn = (int)(Math.floor(Math.log(N)/Math.log(2)));
        int Flgn1 = (int)(Math.max(0,Math.floor(Math.log(N-1)/Math.log(2))));
        int E2Flgn = 1;
        for (int i = 0; i < Flgn; i++)
            E2Flgn *= 2;
        System.out.println("  Worst case comps = " + ((3*N+1)*Flgn - 3*E2Flgn*2 -Flgn1  + 6) +
                " = (3*N+1)*Flgn - 3*E2Flgn*2 - Flgn1  + 6");
        if (N < 3) System.out.println("A lower bound on best case comps = " + (N - 1) + " = N - 1");
        else System.out.println("A lower bound on best case comps = " + (3 * (N - 2)) + " = 3*(N - 2)");
        System.out.print("M(" + N +")");
        cnt.out(" = ");
        System.out.println("  Worst case moves while sorting = " + ((2*N+1)*Flgn + 2*N - 2*E2Flgn*2 + 4) +
                " = (2*N+1)*Flgn + 2*N - 2*E2Flgn*2 + 4");
        System.out.println("A lower bound on best case moves while sorting = " + (2*N) + " = 2*N");
        System.out.print("R(" + N +")");
        cnt2.out(" = ");
        int Clgn10 = (int)(Math.max(0,Math.ceil(Math.log(N/10.0)/Math.log(2))));
        int E2Clgn10 = 1;
        for (int i = 0; i < Clgn10; i++)
            E2Clgn10 *= 2;
        System.out.println(" = " + (int)(20*E2Clgn10 - Clgn10 - 20) + " = 20*E2Clgn10 - Clgn10 - 20");
        System.out.println();
        }
    }
    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]);
        System.out.println("A: Length of itemArray in PQ is " + PQ.Length());
        System.out.println("A: Size of PQ is " + PQ.size());
        PQ.dump();
        for (int i = 0; i < n; i++) A[i]=PQ.remove();
        System.out.println("B: Length of itemArray in PQ is " + PQ.Length());
        System.out.println("B: Size of PQ is " + PQ.size());
    }
    }