//Copyright Dr. Marek A. Suchenek, 2013 - 2025
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package bs_tree_test;

/**
 *
 * @author suchenek
 */
public class BS_sort_plus {
    /**
     * @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<=1000; N++) //N = 1 ... for big Oh
 {
        Array = new int[N];
        BSfill(Array, 0, 1, N); //best cases generator
//        for (int i = 0; i < N; i++) //semi-average cases generator
//        Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
//        for (int i = 0; i < N; i++) //worst cases generator
//        Array[i] = i;
        System.out.print("Array: ");
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        cnt.clr(); //counts comparisons to elements of tree
        cnt2.clr(); //counts recursive calls
        int M = BStreeSort(Array);
        System.out.print("Sorted: ");
        for (int i = 0; i < M; i++) System.out.print(Array[i] + " ");
        System.out.println();
        //        C(N) is the count of number of comparisons to elements of tree
        System.out.print("C(" + N +")");
        cnt.out(" = ");
        System.out.print("  " + (N*(N-1)/2) + " = N*(N-1)/2");
        System.out.println("       1.386*N *Math.log(N)/Math.log(2) - 2.846*N = " + (1.386*N*Math.log(N)/Math.log(2) - 2.846*N));
        System.out.println("(N+1)*floor(lg N) - 2^(floor(lg N) + 1) + 2 = " + ((N+1)*MyMath.floorLg(N) - 2*MyMath.twoToFloorLg(N) + 2));
        //        R(N) is the recursive calls count
        System.out.print("R(" + N +")");
        cnt2.outln(" = ");
//         (200*Math.round((Math.exp(Math.log(2)*Math.ceil(Math.log(N/10.)/Math.log(2.)))-1)) - Math.round(Math.ceil(Math.log(N/10.)/Math.log(2.)))) +
//         " = 200*Math.round((Math.exp(Math.log(2)*Math.ceil(Math.log(N/10.)/Math.log(2.)))-1)) - Math.round(Math.ceil(Math.log(N/10.)/Math.log(2.)))");
 }
    }
    public static int  BStreeSort(int[] A)
//            Ignores duplicates
//            Returns the length of array after sorting
    {
        int n = A.length;
        BStree T = new BStree();
        for (int i = 0; i < n; i++) T.insert(A[i]);
//        System.out.println("A Size of T is " + T.Length());
        return T.inOrderToArray(A);
//        System.out.println("B Size of T is " + T.Length());

    }

    public static void  BSfill(int[] A, int index, int lo, int hi)
//            Fills array with consecutive integers lo, ..., hi
//            Beginning from index
//            Best case generator for BS sort
    {
        int n = A.length;
        if (index >= n) return;
        if (lo>hi) return;
        A[index] = (lo+hi)/2;
        BSfill(A, index+1, lo, (lo+hi)/2-1);
        BSfill(A, index+(lo+hi)/2-lo+1, (lo+hi)/2+1, hi);
//        System.out.print("BSfill: ");
//        for (int i = 0; i < n; i++)
//            System.out.print(A[i] + " ");
//        System.out.println();
    }

}