edu.rice.cs.plt.iter
Class DiagonalCartesianIterable<T1,T2,R>

java.lang.Object
  edu.rice.cs.plt.iter.AbstractIterable<R>
      edu.rice.cs.plt.iter.DiagonalCartesianIterable<T1,T2,R>

All Implemented Interfaces:

OptimizedLastIterable<R>, SizedIterable<R>, Composite, java.io.Serializable, java.lang.Iterable<R>

public class DiagonalCartesianIterable<T1,T2,R>
extends AbstractIterable<R>
implements SizedIterable<R>, OptimizedLastIterable<R>, Composite, java.io.Serializable

Enumerates the elements of a cartesian (or cross) product in diagonal order. Where the "index" of the ith item in an iterator is i, this class produces all pairs of values with indices that sum to n before proceding to those with indices that sum to n+1. This allows the cartesian product of two infinite iterables to be methodically traversed. Within the set of pairs with indices summing to n, the order is lexographical in terms of the respective indices. For example, [0, 1, 2] crossed with itself will produce (under string concatenation) [00, 01, 10, 02, 11, 20, 12, 21, 22]. The combiner function is used, rather than simply producing Pairs, in order to provide a greater degree of flexibility.

In order to support this traversal, the set of previously-seen values must be cached in each iterator. The amount of space required by an iterator after n invocations of next() is in O(sqrt(n)).

See Also:

Serialized Form

Constructor Summary

DiagonalCartesianIterable(java.lang.Iterable<? extends T1> left, java.lang.Iterable<? extends T2> right, Lambda2<? super T1,? super T2,? extends R> combiner)

Method Summary

int	compositeHeight() Get the maximum path length from this node to a leaf.
int	compositeSize() Get the number of nodes in the tree rooted at this node.
boolean	hasFixedSize() true if this iterable is known to have a fixed size.
boolean	isEmpty() Whether the iterable does not contain any elements.
boolean	isInfinite() true if the iterable is known to have infinite size.
boolean	isStatic() Always false: results of a lambda may be arbitrary.
DiagonalCartesianIterator<T1,T2,R>	iterator()
R	last() Get the last element of the list.
static <T1,T2,R> DiagonalCartesianIterable<T1,T2,R>	make(java.lang.Iterable<? extends T1> left, java.lang.Iterable<? extends T2> right, Lambda2<? super T1,? super T2,? extends R> combiner) Call the constructor (allows the type arguments to be inferred)
static <T1,T2,R> SnapshotIterable<R>	makeSnapshot(java.lang.Iterable<? extends T1> left, java.lang.Iterable<? extends T2> right, Lambda2<? super T1,? super T2,? extends R> combiner) Create a DiagonalCartesianIterable and wrap it in a SnapshotIterable, forcing immediate evaluation of the permutations.
int	size() Compute the number of elements in the iterable.
int	size(int bound) Compute the number of elements in the iterable, up to the given bound.

Methods inherited from class edu.rice.cs.plt.iter.AbstractIterable

equals, hashCode, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DiagonalCartesianIterable

public DiagonalCartesianIterable(java.lang.Iterable<? extends T1> left,
                                 java.lang.Iterable<? extends T2> right,
                                 Lambda2<? super T1,? super T2,? extends R> combiner)

Method Detail

iterator

public DiagonalCartesianIterator<T1,T2,R> iterator()

Specified by:

iterator in interface java.lang.Iterable<R>

compositeHeight

public int compositeHeight()

Description copied from interface: Composite

Get the maximum path length from this node to a leaf.

Specified by:

compositeHeight in interface Composite

compositeSize

public int compositeSize()

Description copied from interface: Composite

Get the number of nodes in the tree rooted at this node. Always 1 or greater.

Specified by:

compositeSize in interface Composite

isEmpty

public boolean isEmpty()

Description copied from interface: SizedIterable

Whether the iterable does not contain any elements.

Specified by:

isEmpty in interface SizedIterable<R>

size

public int size()

Description copied from interface: SizedIterable

Compute the number of elements in the iterable. If the size is infinite or too large to be represented as an int, Integer.MAX_VALUE should be returned. Otherwise, next() may be safely invoked on the iterator exactly this number of times.

Specified by:

size in interface SizedIterable<R>

size

public int size(int bound)

Description copied from interface: SizedIterable

Compute the number of elements in the iterable, up to the given bound. If the size is infinite or greater than bound, bound is returned.

Specified by:

size in interface SizedIterable<R>

Parameters:

bound - Maximum result. Assumed to be nonnegative.

isInfinite

public boolean isInfinite()

Description copied from interface: SizedIterable

true if the iterable is known to have infinite size. If true, an iterator over the iterable in its current state will never return false from hasNext().

Specified by:

isInfinite in interface SizedIterable<R>

hasFixedSize

public boolean hasFixedSize()

Description copied from interface: SizedIterable

true if this iterable is known to have a fixed size. This is the case if the iterable is immutable, or if changes can only replace values, not remove or add them. An infinite iterable may be fixed if it is guaranteed to never become finite.

Specified by:

hasFixedSize in interface SizedIterable<R>

isStatic

public boolean isStatic()

Always false: results of a lambda may be arbitrary.

Specified by:

isStatic in interface SizedIterable<R>

last

public R last()

Description copied from interface: OptimizedLastIterable

Get the last element of the list. Assumed to execute more quickly than a traversal over all elements.

Specified by:

last in interface OptimizedLastIterable<R>

make

public static <T1,T2,R> DiagonalCartesianIterable<T1,T2,R> make(java.lang.Iterable<? extends T1> left,
                                                                java.lang.Iterable<? extends T2> right,
                                                                Lambda2<? super T1,? super T2,? extends R> combiner)

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

makeSnapshot

public static <T1,T2,R> SnapshotIterable<R> makeSnapshot(java.lang.Iterable<? extends T1> left,
                                                         java.lang.Iterable<? extends T2> right,
                                                         Lambda2<? super T1,? super T2,? extends R> combiner)

Create a DiagonalCartesianIterable and wrap it in a SnapshotIterable, forcing immediate evaluation of the permutations.