package be.ac.vub.ir.multithreading;

import be.ac.vub.ir.util.Chrono;

public class Fibonacci{
	
	final static int numThreads=32;
	static int count=0;
	long solution = 0;
	long[] result = new long[numThreads];
	Thread[] thread = new Thread[numThreads];
	
	public Fibonacci(){
	}
	
	public long parFib(int n, int numThreads) throws InterruptedException {
		Spawner(n, (int) (Math.log(numThreads)/Math.log(2)));
		System.out.println((int) (Math.log(numThreads)/Math.log(2)));
		for(int i=0;i<numThreads;i++) {
			thread[i].join();
			solution+=result[i];
		}
		return solution;
	}
	
	/**
	 * PROGRAM
	 * @throws InterruptedException 
	 */
	public static void main(String[] args) throws InterruptedException {
		int N = 45;
		Chrono chronoSeq = new Chrono();
		long resultSeq = Fibonacci.fib(N);
		long time = chronoSeq.stop();
		System.out.println("Fib of "+ N +" is "+ resultSeq +" in "+ chronoSeq);
	    Fibonacci parallel = new Fibonacci();
		Chrono chronoPar = new Chrono();
	    long resultPar = parallel.parFib(N, numThreads);
	    time = chronoPar.stop();
	    System.out.println("Fib of "+ N +" is "+ resultPar +" in "+ chronoPar);

	}

	public static long fib(int n){
		if (n > 2)
			return fib(n-1) + fib(n-2);
		else
			return 1;
	}
	
	//Precondition: depth is a power of 2
	public void Spawner(int n, int depth){
		if (depth == 0) {
			thread[count]=new Thread (new Fibonacci.Worker(n, count));
			thread[count].start();
			count++;
		}
		else{
			Spawner(n-1, depth-1);
			Spawner(n-2, depth-1);
		}
	}
	
	class Worker implements Runnable {
		final int myId;
		final int n;
		public Worker(int n, int x) {
			myId=x;
			this.n=n;
		}
		public void run() {
			result[myId]=fib(n);
		}
	}
}