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

java.lang.Object
  edu.rice.cs.plt.iter.ReadOnlyIterator<R>
      edu.rice.cs.plt.iter.DiagonalCartesianIterator<T1,T2,R>

All Implemented Interfaces:

Composite, java.util.Iterator<R>

public class DiagonalCartesianIterator<T1,T2,R>
extends ReadOnlyIterator<R>
implements Composite

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 iterators 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. Iterator.remove() is not supported.

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

Constructor Summary

DiagonalCartesianIterator(java.util.Iterator<? extends T1> left, java.util.Iterator<? 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	hasNext()
static <T1,T2,R> DiagonalCartesianIterator<T1,T2,R>	make(java.util.Iterator<? extends T1> left, java.util.Iterator<? extends T2> right, Lambda2<? super T1,? super T2,? extends R> combiner) Call the constructor (allows the type arguments to be inferred)
R	next()

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

remove

Methods inherited from class java.lang.Object

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

Constructor Detail

DiagonalCartesianIterator

public DiagonalCartesianIterator(java.util.Iterator<? extends T1> left,
                                 java.util.Iterator<? extends T2> right,
                                 Lambda2<? super T1,? super T2,? extends R> combiner)

Method Detail

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

hasNext

public boolean hasNext()

Specified by:

hasNext in interface java.util.Iterator<R>

next

public R next()

Specified by:

next in interface java.util.Iterator<R>

make

public static <T1,T2,R> DiagonalCartesianIterator<T1,T2,R> make(java.util.Iterator<? extends T1> left,
                                                                java.util.Iterator<? extends T2> right,
                                                                Lambda2<? super T1,? super T2,? extends R> combiner)

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