import java.util.Random;


public class DynEqvSolver{


    int[] myElements;


    public DynEqvSolver(int size){
        init(size);
    }


    public void init(int size){
        myElements = new int[size];
        for(int i = 0; i < size; i++){
            myElements[i] = -1;
        }
    }

    public int find(int x){

        if(myElements[x] < 0){//is root
            return x;
        }else{
            return find(myElements[x]);
        }
    }

    public boolean union(int a, int b){

        int root1 = find(a);
        int root2 = find(b);

        if(root1 == root2){
            return false;
        }else{
            myElements[root2] = root1;
            return true;
        }
    }


    public boolean unionBySize(int a, int b){
        //TODO
    }
    

    public boolean unionByHeight(int a, int b){
        //TODO
    }

    public boolean equiv(int e1, int e2){
        return (find(e1) == find(e2));
    }




    public static void main(String[] args){

        int size = 1000;
        int elm1, elm2;

        Random random = new Random(System.currentTimeMillis());
        DynEqvSolver[] solver = new DynEqvSolver[3]; // one for each test

        solver[0] = new DynEqvSolver(size); // union
        solver[1] = new DynEqvSolver(size); // unionBySize
        solver[2] = new DynEqvSolver(size); // unionByHeight

        // join different elements into equivalence classes
        for(int i = 0; i < size/2; i++){
            
            elm1 = random.nextInt(size);
            elm2 = random.nextInt(size);

            solver[0].union(elm1,elm2);
            solver[1].unionBySize(elm1,elm2);
            solver[2].unionByHeight(elm1,elm2);
        }

        // make an array of random elements to
        // use for equivalence testing, which is
        // just a find(a) == find(b)
        int[] pair = new int[size*2];

        for(int i = 0; i < size*2; i+=2){
            pair[i] = random.nextInt(size);
            pair[i+1] = random.nextInt(size);
        }


        // test the pairs using the different DynEqvSolvers

        long t_0 = System.currentTimeMillis();

        for(int i = 0; i < size*2; i+=2){
           solver[0].equiv(pair[i], pair[i+1]);
        }

        long t_1 = System.currentTimeMillis();

        for(int i = 0; i < size*2; i+=2){
            solver[1].equiv(pair[i], pair[i+1]);
        }

        long t_2 = System.currentTimeMillis();

        for(int i = 0; i < size*2; i+=2){
            solver[2].equiv(pair[i], pair[i+1]);
        }

        long t_3 = System.currentTimeMillis();

        System.out.println(" union "+(t_1 - t_0)+" ms");
        System.out.println(" unionBySize "+(t_2 - t_1)+" ms");
        System.out.println(" unionByHeight "+(t_3 - t_2)+" ms");

    }

}