/******************************************************************************
 *  Name:   Andy Guna 
 *  NetID:   guna@princeton.edu	
 *  Precept: P01
 *
 * Description: This example creates a table of values of N(data size) versus
 * T(runtime) when using WeightedQuickUnionUF to connect 0 and N-1. These values
 * can be used to estimate the runtime of the algorithm
*******************************************************************************/

import edu.princeton.cs.algs4.WeightedQuickUnionUF;
import edu.princeton.cs.algs4.Stopwatch;
import edu.princeton.cs.algs4.StdRandom;
  
public class UFExample2 {
    public static void main(String[] args) { 
      for (int k=1000; k <= 8000; k*=2) {        
        Stopwatch Clock = new Stopwatch();
        int N = k*k;
        int nexttolast = N-1;
        WeightedQuickUnionUF UF1 = new WeightedQuickUnionUF(N);
        while (true) {
           int i = StdRandom.uniform(N);
           int j = StdRandom.uniform(N);
           if (!UF1.connected(i,j)){
              UF1.union(i,j);
              //System.out.println("connecting " + i + " and " + j);
           }
           if (UF1.connected(0,N-1)) {
             //System.out.println("\n EXITING ... now  0 and " + nexttolast + " are connected ");
             break;
           }
        }  
        System.out.println( N + "  " + Clock.elapsedTime());
      }
    }
}