package D2;

import java.util.Random;

import edu.princeton.cs.algs4.StdOut;
//import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;


public class testQU {

	private static int[] numbers;  //búum til int array numbers sem inniheldur tölurnar sem við ætlum að para saman
	static int count; //

public static int count()
	   { return count;  }

public static boolean connected(int p, int q)  // ef ég kalla á þetta þá fæ ég já eru tengt - nei ekki tengd
	   {  return find(p) == find(q);  }

private static int find(int p)
{  // Find component name.
	while (p != numbers[p]) p = numbers[p];
	return p;
}
public static void union(int p, int q) // tengjum saman tölur
{  // Give p and q the same root.
	int pRoot = find(p);
	int qRoot = find(q);
	if (pRoot == qRoot)
		return;
	numbers[pRoot] = qRoot;
	count--;
}
public static int connect(int N)
{
	count = N;
	numbers = new int[N];

	for (int i = 0; i < N; i++)  // Initialize component id array.
	   { numbers[i] = i; } ;

		int cnt = 0;
	   while( cnt < N )
		{
			 Random rand = new Random();
			 int i = rand.nextInt(N - 0);
			 int j = rand.nextInt(N - 0);

			testQU.connected(i,j); //continue;  // Ignore if connected.
	        testQU.union(i,j);                    // Combine components
		    //StdOut.println(i + " " + j);       //   and print connection.   þarf ekki núna
		    cnt++;
		}
	   return cnt;
}
public static double timeTrial(int N)//tekur tíman á hvað N margar tölur eru að parast
{
	//int MAX = 1000000;
	//int[] a = new int[N];
	//for (int i = 0; i < N; i++)
	//	a[i] = StdRandom.uniform(-MAX, MAX);

	Stopwatch timer = new Stopwatch();
	int cnt = connect(N);
	return timer.elapsedTime();
	}

public static void main(String[] args)   // fáum inn tölu eigum að tvöfalda hana og finna öll möguleg pör.
{       					//Ath hvað það tekur mikinn tíma.

	double prev = timeTrial(12);
	for (int N = 250; true; N += N)
	{
		double time = timeTrial(N);
		StdOut.printf("%6d %7.1f ", N, time);

		StdOut.printf("%5.1f\n", time/prev);
		prev = time;
	}

}
}