/**
 * RBTreeTime
 *

/*
 * Used to check the time it takes to perform each important action 
 *
 */

public class RBTreeTime
{

    public static boolean ifExists(int[] a, int elem) {
        for (int i=0; i<a.length; i++)
            if (a[i] == elem) return true;
        return false;
    }


    public static long calculateTime(long start, long end){
    	return (end-start)/1000;
    }
    /**
     * A main routine to test the binary tree routine.
     */

    public static void checkRuntime(int size)
    {
    	long start = System.nanoTime(); // Get start time
        long end = System.nanoTime(); // Get end time
        long insertTime;
        long containsTime;
        int elemForInsert = 0;
        int elemForContains = 0;
        int elemNum = 0;
        int inserts_num = 1000;
        int contains_num = 1000;
        
    	RBTree t = new RBTree();    

    	// BUILD TREE
        for (int i = 0; i < size; i++)
        {
        	do {
        		elemForInsert = (int) Math.round(Math.random() * 1000000);
        	} while ( t.contains(elemForInsert) == true);
            t.insert(elemForInsert);
        	elemNum++;
        }
        System.out.println("tree size = " + size);
        
        // CHECK TIME FOR CONTAINS (mostly worst case)
        containsTime = 0;
        for (int i = 0; i < contains_num; ++i) {
        	elemForContains = (int) Math.round(Math.random() * 10000);
    		start=System.nanoTime();
    		t.contains(elemForContains);
    		end=System.nanoTime(); 
    		containsTime+=end - start;
        		
        }
        System.out.println("duration of contains in microseconds: " + containsTime/(1000.0*contains_num));     

        // CHECK TIME FOR INSERT
        insertTime = 0;
        for (int i = 0; i < inserts_num+100; ++i) {
        	//find a not-existing element
        	do {
        		elemForInsert = (int) Math.round(Math.random() * 100000);
        	} while (t.contains(elemForInsert) == true);
            start=System.nanoTime();
            t.insert(elemForInsert);
            end=System.nanoTime();
            if (i >= 100)
            	insertTime+=end - start;
            t.delete(elemForInsert);
        }
        System.out.println("duration of insert in microseconds: " + insertTime/(1000.0*inserts_num));
                
           } 

    public static void main(String[] args) {
       checkRuntime(100000); 
       checkRuntime(10000);
       checkRuntime(1000);
        
    }
}