edu.rice.cs.plt.recur
Class PrecomputedRecursionStack<T,R>

java.lang.Object
  edu.rice.cs.plt.recur.PrecomputedRecursionStack<T,R>

public class PrecomputedRecursionStack<T,R>
extends Object

A stack used to store the arguments of a recursive invocation in order to prevent infinite recursion. By checking that a given argument has not been used previously before recurring, a client can prevent infinite recursion in some circumstances (such as when traversing an infinite, immutable data structure).

While RecursionStack allows arbitrary application result values to be provided for the infinite case, this class follows a stricter discipline: the infinite case result must be provided at the time of the first invocation of an argument; that value will be stored, and a second invocation will return it. In this way, the result of a recursive computation is always precomputed -- that is, it must be determined before the computation takes place. Classes like DelayedThunk can be used to create precomputed values, providing an initial "empty box" that can be "filled" when computation is complete. This allows the definition, for example, of data structures that contain themselves. Due to the restricted applicability of this class (in comparison to RecursionStack), methods that involve invoking Runnables or recurring multiple times based on a threshold value are not defined here.

The client may either choose to explicity check for containment, push(T, R) the argument, recur, and then pop(T), or invoke one of a variety of lambda-based methods that perform these bookkeeping tasks automatically. In the latter case, when an exception occurs between a push and a matching pop, the pop is guaranteed to execute before the exception propagates upward. Thus, clients who do not directly invoke push(T, R) and pop(T) may assume that the stack is always in a consistent state.

See Also:

RecursionStack, PrecomputedRecursionStack2, PrecomputedRecursionStack3, PrecomputedRecursionStack4

Constructor Summary

PrecomputedRecursionStack()
Create an empty recursion stack with an IdentityWrapper factory

PrecomputedRecursionStack(Lambda<? super T,? extends Wrapper<T>> wrapperFactory)
Create an empty recursion stack with the given Wrapper factory

Method Summary

R	apply(Lambda<? super T,? extends R> lambda, Lambda<? super T,? extends R> precomputed, T arg) Evaluate the given lambda with argument arg, unless arg is already on the stack; push arg onto the stack with the given precomputed result during lambda's evaluation
R	apply(Lambda<? super T,? extends R> lambda, R precomputed, T arg) Evaluate the given lambda with argument arg, unless arg is already on the stack; push arg onto the stack with the given precomputed result during lambda's evaluation
R	apply(Lambda<? super T,? extends R> lambda, Thunk<? extends R> precomputed, T arg) Evaluate the given lambda with argument arg, unless arg is already on the stack; push arg onto the stack with the given precomputed result during lambda's evaluation
R	apply(Thunk<? extends R> thunk, Lambda<? super T,? extends R> precomputed, T arg) Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack with the given precomputed result during thunk's evaluation
R	apply(Thunk<? extends R> thunk, R precomputed, T arg) Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack with the given precomputed result during thunk's evaluation
R	apply(Thunk<? extends R> thunk, Thunk<? extends R> precomputed, T arg) Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack with the given precomputed result during thunk's evaluation
boolean	contains(T arg)
R	get(T arg)
boolean	isEmpty()
static <T,R> PrecomputedRecursionStack<T,R>	make() Call the constructor (allows the type arguments to be inferred)
static <T,R> PrecomputedRecursionStack<T,R>	make(Lambda<? super T,? extends Wrapper<T>> wrapperFactory) Call the constructor (allows the type arguments to be inferred)
void	pop(T arg) Remove arg from the top of the stack
void	push(T arg, Lambda<? super T,? extends R> value) Add arg to the top of the stack with the given lambda producing its infinite-case result.
void	push(T arg, R value) Add arg to the top of the stack with the given infinite-case result.
void	push(T arg, Thunk<? extends R> value) Add arg to the top of the stack with the given thunk producing its infinite-case result.
int	size()

Methods inherited from class java.lang.Object

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

Constructor Detail

PrecomputedRecursionStack

public PrecomputedRecursionStack()

Create an empty recursion stack with an IdentityWrapper factory

PrecomputedRecursionStack

public PrecomputedRecursionStack(Lambda<? super T,? extends Wrapper<T>> wrapperFactory)

Create an empty recursion stack with the given Wrapper factory

Parameters:

wrapperFactory - A lambda used to produce a wrapper for values placed on the stack. This provides clients with control over the method used to determine if a value has been seen previously.

Method Detail

contains

public boolean contains(T arg)

Returns:

true iff a value identical (according to ==) to arg is currently on the stack

get

public R get(T arg)

Returns:

The infinite-case result provided for arg

Throws:

IllegalStateException - If arg is not on the stack

push

public void push(T arg,
                 R value)

Add arg to the top of the stack with the given infinite-case result.

Throws:

IllegalArgumentException - If arg is already on the stack

push

public void push(T arg,
                 Thunk<? extends R> value)

Add arg to the top of the stack with the given thunk producing its infinite-case result.

Throws:

IllegalArgumentException - If arg is already on the stack

push

public void push(T arg,
                 Lambda<? super T,? extends R> value)

Add arg to the top of the stack with the given lambda producing its infinite-case result.

Throws:

IllegalArgumentException - If arg is already on the stack

pop

public void pop(T arg)

Remove arg from the top of the stack

Throws:

IllegalArgumentException - If arg is not at the top of the stack

size

public int size()

Returns:

The current size (depth) of the stack

isEmpty

public boolean isEmpty()

Returns:

true iff the stack is currently empty

apply

public R apply(Thunk<? extends R> thunk,
               R precomputed,
               T arg)

Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack with the given precomputed result during thunk's evaluation

Returns:

The value of thunk, or a previously-provided precomputed value

apply

public R apply(Thunk<? extends R> thunk,
               Thunk<? extends R> precomputed,
               T arg)

Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack with the given precomputed result during thunk's evaluation

Returns:

The value of thunk, or a previously-provided precomputed value

apply

public R apply(Thunk<? extends R> thunk,
               Lambda<? super T,? extends R> precomputed,
               T arg)

Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack with the given precomputed result during thunk's evaluation

Returns:

The value of thunk, or a previously-provided precomputed value

apply

public R apply(Lambda<? super T,? extends R> lambda,
               R precomputed,
               T arg)

Evaluate the given lambda with argument arg, unless arg is already on the stack; push arg onto the stack with the given precomputed result during lambda's evaluation

Returns:

The value of lambda, or a previously-provided precomputed value

apply

public R apply(Lambda<? super T,? extends R> lambda,
               Thunk<? extends R> precomputed,
               T arg)

Evaluate the given lambda with argument arg, unless arg is already on the stack; push arg onto the stack with the given precomputed result during lambda's evaluation

Returns:

The value of lambda, or a previously-provided precomputed value

apply

public R apply(Lambda<? super T,? extends R> lambda,
               Lambda<? super T,? extends R> precomputed,
               T arg)

Evaluate the given lambda with argument arg, unless arg is already on the stack; push arg onto the stack with the given precomputed result during lambda's evaluation

Returns:

The value of lambda, or a previously-provided precomputed value

make

public static <T,R> PrecomputedRecursionStack<T,R> make()

Call the constructor (allows the type arguments to be inferred)

make

public static <T,R> PrecomputedRecursionStack<T,R> make(Lambda<? super T,? extends Wrapper<T>> wrapperFactory)

Call the constructor (allows the type arguments to be inferred)