/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package bs_tree_test;

/**
 *
 * @author suchenek
 */
public class BS_purge {
    /**
     * @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];
        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 comparisons to elements of tree
        cnt2.clr(); //counts recursive calls
        int M = BStreePurge(Array);
        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.println("  " + (N + N*(N+1)/2) + " = N + N*(N+1)/2");
        //        R(N) is the recursive calls count
        System.out.print("R(" + N +")");
        cnt2.out(" = ");
        System.out.println(" " +
         (200*Math.round((Math.exp(Math.log(2)*Math.ceil(Math.log(N/10.)/Math.log(2.)))-1)) ) +
         " = 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  BStreePurge(int[] A)
//            Removes duplicates from array A while maintaining the original order of first instances
//            Returns the actual length of array after purging
    {
        int n = A.length;
        BStree T = new BStree();
        int j = 0;
        for (int i = 0; i < n; i++)
            if(T.insert(A[i])) A[j++] = A[i];
//        System.out.println("A Size of T is " + T.Length());
//        for (int i = j; i < n; i++)
//            A[i] = 0;
//        System.out.println("B Size of T is " + T.Length());
        return j;

    }


}