/***********************************************
 *  CS2510 Fall 2011
 *  Assignment 09
 *  Algorithmic Complexity
 ***********************************************/

import java.util.ArrayList;

import tester.*;

class Algos {
	// Analyze number of + operations
	public static int fib(int n) {
		if (n == 0 || n == 1) {
			return n;
		} else {
			return fib(n-1) + fib(n-2);
		}
	}

	// Analyze number of + operations
	public static int fibmem(int n) {
		ArrayList<Integer> mem = new ArrayList<Integer>();
		mem.add(0);
		mem.add(1);
		
		for(int i = 2; i <= n; i++) {
			mem.add(mem.get(i-1) + mem.get(i-2));
		}
		return mem.get(n);
	}
	
	// Analyze number of * operations
	public static ArrayList<ArrayList<Integer>> vectMult(ArrayList<Integer> a, ArrayList<Integer> b) {
		ArrayList<ArrayList<Integer>> out = new ArrayList<ArrayList<Integer>>();
		
		for(Integer i : a) {
			ArrayList<Integer> v = new ArrayList<Integer>();
			
			for(Integer j : b) {
				v.add(i*j);
			}
			
			out.add(v);
		}
		
		return out;
	}
	
	// Analyze number of - operations
	public static int bar(int i) {
		if (i <= 1) {
			return i;
		} else {
			return i - bar(i/2);
		}
	}
}

// Tests of the Algorithms
class ComplexityExamples{
	Timer timer = new Timer();
	ComplexityExamples(){
    	System.out.printf("Algorithm\tOutput\t\tN\tTime (millisec)\n");
    }
    
    
    // Test for Algos.fib
    public void testFib(Tester t) { 
    	int n = 37;
    	
    	timer.start();
    	int o = Algos.fib(n);
    	System.out.printf("Fib\t\t%d\t%d\t%.0f\n", o, n, timer.stop());
    }
    
    // Test for Algos.fibmem
    public void testFibmem(Tester t) { 
    	int n = 37;
    	
    	timer.start();
    	int o = Algos.fibmem(n);
    	System.out.printf("Fibmem\t\t%d\t%d\t%.0f\n", o, n, timer.stop());
    }

    // Test for Algos.vectMult
    public void testVectMult(Tester t) { 
    	int n = 37;
    	
    	
    	ArrayList<Integer> a = new ArrayList<Integer>(n);
    	ArrayList<Integer> b = new ArrayList<Integer>(n);
    	for(int i = 0; i < n; i++) {
    		a.add(i);
    		b.add(i);
    	}
    	timer.start();
    	Algos.vectMult(a,b);
    	System.out.printf("VectMult\tN/A\t\t%d\t%.0f\n", n, timer.stop());
    }
    
    // Test for Algos.bar
    public void testBar(Tester t) { 
    	int n = 37;
    	
    	timer.start();
    	int o = Algos.bar(n);
    	System.out.printf("Bar\t\t%d\t\t%d\t%.0f\n", o, n, timer.stop());
    }

}

// Allows us to see how long has passed
class Timer {
    
    private long start = 0;

    // Stores the start time
    public void start() {
        start = System.currentTimeMillis();
    }

    // Returns the current time minus the start time
    public double stop() {
        return (System.currentTimeMillis() - start);
    }
}

class Complexity {
	// Another way to run the program
	public static void main(String[] args) {
		Tester t = new Tester();
		ComplexityExamples ec = new ComplexityExamples();
		ec.testFib(t);
		ec.testFibmem(t);
		ec.testVectMult(t);
		ec.testBar(t);
	}
}