lab.util

Class FibonacciStackFrame

java.lang.Object

lab.util.FibonacciStackFrame

public class FibonacciStackFrame
extends Object

Constructor Summary

Constructors

Constructor and Description
FibonacciStackFrame(int n, FibonacciStackFrame caller) Creates a stack frame to compute F(n).

Method Summary

Methods

Modifier and Type	Method and Description
void	execute(Stack<FibonacciStackFrame> callStack) Start or resume execution of this stack frame.
static Map<Integer,BigInteger>	getCache() Get the cache of already computed Fibonacci numbers.
FibonacciStackFrame	getCaller() Get the creator of this call stack.
BigInteger	getfMinus1() Get the current value of fMinus1.
BigInteger	getfMinus2() Get the current value of fMinus2.
int	getN() Get the value of n.
BigInteger	getSum() Get the current value of the sum F(n) = F(n - 1) + F(n - 2).
void	receiveReturnValue(BigInteger retVal) Receive a return value from another FibonacciStackFrame instance.
void	returnValueToCaller(BigInteger retVal, Stack<FibonacciStackFrame> callStack) Returns the value of F(n) to the creator (this.caller) of this stack frame if the creator was another FibonacciStackFrame instance, and then pops this stack frame from the call stack.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FibonacciStackFrame

public FibonacciStackFrame(int n,
                   FibonacciStackFrame caller)

Creates a stack frame to compute F(n). caller is a reference to the FibonacciStackFrame that created this stack frame. If this stack frame is not being created by another FibonacciStackFrame instance, then caller is expected to be equal to null.

Throws:

IllegalArgumentException - if n < 0

Parameters:

n - the Fibonccci number to compute

caller - the FibonacciStackFrame that created this stack frame

Method Detail

receiveReturnValue

public void receiveReturnValue(BigInteger retVal)

Receive a return value from another FibonacciStackFrame instance. If this stack frame is computing F(n) it must create and push another two stack frame instances onto the the call stack to compute F(n - 1) and F(n - 2); these stack frame instances are expected to invoke receiveReturnValue on this stack frame to return the values of F(n - 1) and F(n - 2) to this stack frame. This stack frame stores the returned values to ultimately compute the sum F(n) = F(n - 1) + F(n - 2)

Throws:

IllegalStateException - if this stack frame has already received values for both F(n - 1) and F(n - 2)

Parameters:

retVal - the value of F(n - 1) or F(n - 2) returned from another FibonacciStackFrame instance

returnValueToCaller

public void returnValueToCaller(BigInteger retVal,
                       Stack<FibonacciStackFrame> callStack)

Returns the value of F(n) to the creator (this.caller) of this stack frame if the creator was another FibonacciStackFrame instance, and then pops this stack frame from the call stack.

Parameters:

retVal - the value of F(n) that is returned to another FibonacciStackFrame instance

callStack - the call stack

getSum

public BigInteger getSum()

Get the current value of the sum F(n) = F(n - 1) + F(n - 2). Note that the final correct value of F(n) will not be returned by this method until this stack frame has actually completed computing the sum F(n - 1) + F(n - 2)

Returns:

the current value of the sum F(n) = F(n - 1) + F(n - 2); the correct value of F(n) will not be returned by this method until this stack frame is actually finished computing the sum F(n - 1) + F(n - 2)

execute

public void execute(Stack<FibonacciStackFrame> callStack)

Start or resume execution of this stack frame. This method is expected to be invoked when this stack frame is on top of the call stack. When this method is invoked, this stack frame can be in one of six possible states:

1. this stack frame is computing F(0), in which case the value 0 can be returned to the caller
2. this stack frame is computing F(1), in which case the value 1 can be returned to the caller
3. this stack frame is computing F(n) and F(n) is in the cache, in which case the value F(n) can be retrieved from the cache and returned to the caller
4. this stack frame is computing F(n - 1), in which case this stack frame should push a new stack frame onto the call stack to compute F(n - 1) passing this as the caller of the new stack frame
5. this stack frame is computing F(n - 2), in which case this stack frame should push a new stack frame onto the call stack to compute F(n - 2) passing this as the caller of the new stack frame
6. this stack frame is computing the sum F(n - 1) + F(n - 2), in which case this stack frame should compute the sum, put the sum in the cache, and return the value of the sum to the caller

Parameters:

callStack -

getCache

public static Map<Integer,BigInteger> getCache()

Get the cache of already computed Fibonacci numbers. This method is here for debugging and testing purposes.

Returns:

the cache of already computed Fibonacci numbers

getN

public int getN()

Get the value of n. This method is here for debugging and testing purposes.

Returns:

the value of n

getCaller

public FibonacciStackFrame getCaller()

Get the creator of this call stack. This method is here for debugging and testing purposes.

Returns:

the creator of this call stack

getfMinus1

public BigInteger getfMinus1()

Get the current value of fMinus1. This method is here for debugging and testing purposes.

Returns:

the current value of fMinus1

getfMinus2

public BigInteger getfMinus2()

Get the current value of fMinus2. This method is here for debugging and testing purposes.

Returns:

the current value of fMinus2