import java.util.HashMap;
import java.util.Map;


interface DecorateMethod {

    public void runMe();

}


public class FibonacciFun {

    private static Map<Integer, Long> results;

    static {
        results = new HashMap<>();
        results.put(0, 0l);
        results.put(1, 1l);
    }

    public static long dynamicFib(int n) {
        if (results.containsKey(n)) {
            return results.get(n);
        } else {
            results.put(n, dynamicFib(n - 1) + dynamicFib(n - 2));
            return results.get(n);
        }
    }

    public static long dumbFib(int n) {
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
        else
            return dumbFib(n - 1) + dumbFib(n - 2);
    }

    public static long smartFib(int n) {
        int iteration = 0;
        int a = 0;
        int b = 1;
        while (iteration++ < n) {
            b = a + b;
            a = b - a;
        }
        return a;
    }

    public static long arrayFib(int n, boolean printMe) {
        int[] results = new int[n + 1];
        results[0] = 0;
        if (n > 0) {
            results[1] = 1;
            for (int i = 2; i <= n; i++) {
                results[i] = results[i - 1] + results[i - 2];
            }
        }
        if (printMe) {
            System.out.println(results.length);
        }
        return results[n];
    }

    public static long testMethod(DecorateMethod method) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            method.runMe();
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

    public static void main(String[] beans) {
        //Test array fib
        System.out.println("Array fib1 " + testMethod(new DecorateMethod() {
            @Override
            public void runMe() {
                for (int i = 0; i < 20; i++)
                    arrayFib(i, false);
            }
        }));

        long start, end;

        start = System.currentTimeMillis();
        for (int j = 0; j < 1000; j++) {
            for (int i = 0; i < 20; i++) {
                long d = (arrayFib(i, false));
            }
        }
        end = System.currentTimeMillis();
        System.out.printf("Array fib %d\n", end - start);


        start = System.currentTimeMillis();
        for (int j = 0; j < 1000; j++) {
            for (int i = 0; i < 20; i++) {
                long d = (smartFib(i));
            }
        }
        end = System.currentTimeMillis();
        System.out.printf("Smart fib %d\n", end - start);


        start = System.currentTimeMillis();
        for (int j = 0; j < 1000; j++) {
            for (int i = 0; i < 20; i++) {
                long d = (dumbFib(i));
            }
            end = System.currentTimeMillis();
        }
        System.out.printf("Dumb fib %d\n", end - start);

        start = System.currentTimeMillis();
        for (int j = 0; j < 1000; j++) {
            for (int i = 0; i < 20; i++) {
                long d = (dynamicFib(i));
            }
        }
        end = System.currentTimeMillis();
        System.out.printf("Dynamic fib %d\n", end - start);
    }

}