/**
 * Test of an array-based Fibonacci number calculator.
 *
 * @author Wayne Eberly
 */

public class Fibonacci2 {

	/**
	 * Test of an array-based Fibonacci number calculator.
	 */
	public static void main(String[] args) {
		System.out.println("Test of an Array-Based Fibonacci Number Calculator");
		System.out.println("");
		for (int i=0; i <= 40; i++){
			System.out.print("n: ");
			System.out.printf("%2d", i);
			System.out.print(";     nth Fibonacci number: ");
			System.out.printf("%10d", fib(i));
			System.out.println("");
		}
	}

	/**
	 * Computes a specified Fibonacci number as a long integer
	 * iteratively, using an array to store and reuse values
	 * as needed.
	 * 
	 * <p>
	 *  <strong>Precondition:</strong>
	 *       <code>i</code> is a nonnegative integer.<br />
	 *  <strong>Postcondition:</strong>
	 *       Value returned is the <code>i</code><sup>th</sup>
	 *       Fibonacci number.
	 * </p>
	 * 
	 * @param i Index of the Fibonacci number to be calculated
	 * @return The ith Fibonacci number
	 * @throws IllegalArgumentException If the input integer is negative
	 * 
	 */

	public static long fib(int i) {
		if (i<0) {
			throw new IllegalArgumentException("Negative Input: " + i);
		} else {				// i >= 0
			if (i==0) {
				return 0;
			} else {			// i >= 1
				if (i==1) {
					return 1;
				} else {		// i >= 2
					long[] A = new long[i+1];
					A[0] = 0;
					A[1] = 1;
					for (int j=2; j <= i; j++) {
					/*
					* Loop Invariant:
					*  a) j is an integer such that 2 <= j <= i
					*  b) For every integer k such that
					*     0 <= k <= j-1, A[k] is equal to
					*     the kth Fibonacci number
					* Loop Variant: i-j+1
					*/
						A[j] = A[j-1] + A[j-2];
					};
					assert A[i] == sfib(i);
					return A[i];
				}
			}
		}
	}

	/**
	 * Computes a specified Fibonacci number as a long integer by a direct
	 * application of the recursive definition.
	 * 
	 * <p>
	 *  <strong>Precondition:</strong>
	 *       <code>i</code> is a nonnegative integer.<br />
	 *  <strong>Postcondition:</strong>
	 *       Value returned is the <code>i</code><sup>th</sup>
	 *       Fibonacci number.
	 * </p>
	 * 
	 * @param i Index of the Fibonacci number to be calculated
	 * @return The ith Fibonacci number
	 * @throws IllegalArgumentException If the input integer is negative
	 *
	 */
	 public static long sfib(int i) {
		 if (i<0) {
			 throw new IllegalArgumentException("Negative Input: " + i);
		 } else {				// i >= 0
			 if (i==0) {
				 return 0;
			 } else {			// i >= 1
				 if (i==1) {
					 return 1;
				 } else {		// i >= 2
					 return sfib(i-1) + sfib(i-2);
				 } 
			 }
		 }
	 }

}