edu.rice.cs.plt.recur
Class RecursionStack<T>

java.lang.Object
  edu.rice.cs.plt.recur.RecursionStack<T>

public class RecursionStack<T>
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).

The client may either choose to explicity check for containment, push(T) 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) and pop(T) may assume that the stack is always in a consistent state.

See Also:

PrecomputedRecursionStack, RecursionStack2, RecursionStack3, RecursionStack4

Constructor Summary

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

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

Method Summary

<V extends T,R> R	apply(Lambda<? super V,? extends R> lambda, Lambda<? super V,? extends R> infiniteCase, V arg) If arg is not on the stack, evaluate lambda with argument arg; otherwise, evaluate infiniteCase.
<V extends T,R> R	apply(Lambda<? super V,? extends R> lambda, Lambda<? super V,? extends R> infiniteCase, V arg, int threshold) If less than threshold instances of arg are on the stack, evaluate lambda with argument arg; otherwise, evaluate infiniteCase.
<V extends T,R> R	apply(Lambda<? super V,? extends R> lambda, R infiniteCase, V arg) Evaluate the given lambda with argument arg, unless arg is already on the stack; push arg onto the stack during lambda evaluation
<V extends T,R> R	apply(Lambda<? super V,? extends R> lambda, R infiniteCase, V arg, int threshold) Evaluate the given lambda with argument arg, unless threshold instances of arg are already on the stack; push arg onto the stack during lambda evaluation
<R> R	apply(Thunk<? extends R> thunk, R infiniteCase, T arg) Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack during thunk evaluation
<R> R	apply(Thunk<? extends R> thunk, R infiniteCase, T arg, int threshold) Evaluate the given thunk, unless threshold instances of arg are already on the stack; push arg onto the stack during thunk evaluation
<R> R	apply(Thunk<? extends R> thunk, Thunk<? extends R> infiniteCase, T arg) If arg is not on the stack, evaluate thunk; otherwise, evaluate infiniteCase.
<R> R	apply(Thunk<? extends R> thunk, Thunk<? extends R> infiniteCase, T arg, int threshold) If less than threshold instances of arg are on the stack, evaluate thunk; otherwise, evaluate infiniteCase.
boolean	contains(T arg)
boolean	contains(T arg, int threshold)
boolean	isEmpty()
static <T> RecursionStack<T>	make() Call the constructor (allows T to be inferred)
static <T> RecursionStack<T>	make(Lambda<? super T,? extends Wrapper<T>> wrapperFactory) Call the constructor (allows T to be inferred)
void	pop(T arg) Remove arg from the top of the stack
void	push(T arg) Add arg to the top of the stack
<V extends T> void	run(Runnable1<? super V> r, Runnable1<? super V> infiniteCase, V arg) If arg is not on the stack, run r with argument arg; otherwise, run infiniteCase.
<V extends T> void	run(Runnable1<? super V> r, Runnable1<? super V> infiniteCase, V arg, int threshold) If less than threshold instances of arg are on the stack, run r with argument arg; otherwise, run infiniteCase.
<V extends T> void	run(Runnable1<? super V> r, V arg) Run the given runnable with argument arg, unless arg is already on the stack; push arg onto the stack during runnable execution
<V extends T> void	run(Runnable1<? super V> r, V arg, int threshold) Run the given runnable with argument arg, unless threshold instances of arg are already on the stack; push arg onto the stack during runnable execution
void	run(Runnable r, Runnable infiniteCase, T arg) If arg is not on the stack, run r; otherwise, run infiniteCase.
void	run(Runnable r, Runnable infiniteCase, T arg, int threshold) If less than threshold instances of arg are on the stack, run r; otherwise, run infiniteCase.
void	run(Runnable r, T arg) Run the given runnable, unless arg is already on the stack; push arg onto the stack during runnable execution
void	run(Runnable r, T arg, int threshold) Run the given runnable, unless threshold instances of arg are already on the stack; push arg onto the stack during runnable execution
int	size()

Methods inherited from class java.lang.Object

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

Constructor Detail

RecursionStack

public RecursionStack()

Create an empty recursion stack with an IdentityWrapper factory

RecursionStack

public RecursionStack(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

contains

public boolean contains(T arg,
                        int threshold)

Returns:

true iff at least threshold values identical (according to ==) to arg are currently on the stack

push

public void push(T arg)

Add arg to the top of 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

run

public void run(Runnable r,
                T arg)

Run the given runnable, unless arg is already on the stack; push arg onto the stack during runnable execution

run

public void run(Runnable r,
                T arg,
                int threshold)

Run the given runnable, unless threshold instances of arg are already on the stack; push arg onto the stack during runnable execution

run

public void run(Runnable r,
                Runnable infiniteCase,
                T arg)

If arg is not on the stack, run r; otherwise, run infiniteCase. In either case, push arg onto the stack during runnable execution.

run

public void run(Runnable r,
                Runnable infiniteCase,
                T arg,
                int threshold)

If less than threshold instances of arg are on the stack, run r; otherwise, run infiniteCase. In either case, push arg onto the stack during runnable execution.

run

public <V extends T> void run(Runnable1<? super V> r,
                              V arg)

Run the given runnable with argument arg, unless arg is already on the stack; push arg onto the stack during runnable execution

run

public <V extends T> void run(Runnable1<? super V> r,
                              V arg,
                              int threshold)

Run the given runnable with argument arg, unless threshold instances of arg are already on the stack; push arg onto the stack during runnable execution

run

public <V extends T> void run(Runnable1<? super V> r,
                              Runnable1<? super V> infiniteCase,
                              V arg)

If arg is not on the stack, run r with argument arg; otherwise, run infiniteCase. In either case, push arg onto the stack during runnable execution.

run

public <V extends T> void run(Runnable1<? super V> r,
                              Runnable1<? super V> infiniteCase,
                              V arg,
                              int threshold)

If less than threshold instances of arg are on the stack, run r with argument arg; otherwise, run infiniteCase. In either case, push arg onto the stack during runnable execution.

apply

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

Evaluate the given thunk, unless arg is already on the stack; push arg onto the stack during thunk evaluation

Returns:

The value of thunk, or infiniteCase

apply

public <R> R apply(Thunk<? extends R> thunk,
                   R infiniteCase,
                   T arg,
                   int threshold)

Evaluate the given thunk, unless threshold instances of arg are already on the stack; push arg onto the stack during thunk evaluation

Returns:

The value of thunk, or infiniteCase

apply

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

If arg is not on the stack, evaluate thunk; otherwise, evaluate infiniteCase. In either case, push arg onto the stack during thunk evaluation.

Returns:

The value of thunk, or the value of infiniteCase

apply

public <R> R apply(Thunk<? extends R> thunk,
                   Thunk<? extends R> infiniteCase,
                   T arg,
                   int threshold)

If less than threshold instances of arg are on the stack, evaluate thunk; otherwise, evaluate infiniteCase. In either case, push arg onto the stack during thunk evaluation.

Returns:

The value of thunk, or the value of infiniteCase

apply

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

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

Returns:

The value of lambda, or infiniteCase

apply

public <V extends T,R> R apply(Lambda<? super V,? extends R> lambda,
                               R infiniteCase,
                               V arg,
                               int threshold)

Evaluate the given lambda with argument arg, unless threshold instances of arg are already on the stack; push arg onto the stack during lambda evaluation

Returns:

The value of lambda, or infiniteCase

apply

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

If arg is not on the stack, evaluate lambda with argument arg; otherwise, evaluate infiniteCase. In either case, push arg onto the stack during lambda evaluation.

Returns:

The value of lambda, or the value of infiniteCase

apply

public <V extends T,R> R apply(Lambda<? super V,? extends R> lambda,
                               Lambda<? super V,? extends R> infiniteCase,
                               V arg,
                               int threshold)

If less than threshold instances of arg are on the stack, evaluate lambda with argument arg; otherwise, evaluate infiniteCase. In either case, push arg onto the stack during lambda evaluation.

Returns:

The value of lambda, or the value of infiniteCase

make

public static <T> RecursionStack<T> make()

Call the constructor (allows T to be inferred)

make

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

Call the constructor (allows T to be inferred)