package lab.util;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Fibonacci {
  private static Map<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>();
  
  /**
   * Memoized recursive implementation for computing Fibonacci numbers.
   * 
   * @param n which Fibonacci number to compute 
   * @return the value of F(n)
   */
  public static BigInteger fib(int n) {
    BigInteger sum = null;
    if (n == 0) {
      sum = BigInteger.ZERO;
    }
    else if (n == 1) {
      sum = BigInteger.ONE;
    }
    else if (cache.containsKey(n)) {
      sum = cache.get(n); 
    }
    else {
      BigInteger fMinus1 = Fibonacci.fib(n - 1);
      BigInteger fMinus2 = Fibonacci.fib(n - 2);
      sum = fMinus1.add(fMinus2);
      cache.put(n, sum);
    }
    return sum;
  }
  
  
  /**
   * Memoized iterative implementation for computing Fibonacci numbers
   * using an explicit call stack and simulated stack frames.
   * 
   * @param n which Fibonacci number to compute 
   * @return the value of F(n)
   */
  public static BigInteger fib2(int n) {
    Stack<FibonacciStackFrame> callStack = new Stack<FibonacciStackFrame>();
    
    FibonacciStackFrame f = new FibonacciStackFrame(n, null);
    callStack.push(f);
    while (!callStack.isEmpty()) {
      f = callStack.peek();
      f.execute(callStack);
    }
    return f.getSum();
  }
  

}