package com.genuinevm.puzzlers;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

public class MemoFib {

	private static Optional<Long>[] memo1;
	private static Map<Integer, Long> memo2;

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		long time = System.nanoTime();
		memo1 = new Optional[1024];
		Arrays.fill(memo1, Optional.empty());
		for (int i = 0; i <= 200; i++) {
//			if (i >= memo.length)
//				memo = resizeArray(memo);
			fib1(i);
		}
		System.out.println("fib1 took " + (System.nanoTime() - time) + " nanoseconds.");
		time = System.nanoTime();
		memo2 = new HashMap<Integer, Long>(1024);
		for (int i = 0; i <= 200; i++) {
			fib2(i);
		}
		System.out.println("fib2 took " + (System.nanoTime() - time) + " nanoseconds.");
	}

	public static long fib1(int number) {
		if (number <= 1)
			return 1;
		if (!memo1[number].isPresent())
			memo1[number] = Optional.of(fib1(number - 1) + fib1(number - 2));
		return memo1[number].get();
	}
	
	public static long fib2(int number) {
		if (number <= 1)
			return 1;
		if (!memo2.containsKey(number))
			memo2.put(number, fib1(number - 1) + fib1(number - 2));
		return memo2.get(number);
	}

	// Wont be used in this example.
	@SuppressWarnings("rawtypes")
	private static Optional[] resizeArray(Optional[] opts) {
		Optional[] out = new Optional[opts.length * 2];
		Arrays.fill(out, Optional.empty());
		for (int i = 0; i < opts.length; i++)
			out[i] = opts[i];
		return out;
	}
}

// fib1 took 891176 nanoseconds.
// fib2 took 605662 nanoseconds.