common
Class TupleIterator

java.lang.Object
  common.TupleIterator

All Implemented Interfaces:

java.util.Iterator

public class TupleIterator
extends java.lang.Object
implements java.util.Iterator

This class is an iterator over all tuples in a finite cartesian product of finite sets. Some special cases: if the number of sets passed in is zero, then the Cartesian product contains one element, the empty tuple. If an empty set is passed in, then the Cartesian product is empty.

Constructor Summary

TupleIterator(java.util.List cartproduct)
Constructor.

Method Summary

boolean	hasNext() Returns true if there are any more elements in the Cartesian product to return.
static void	main(java.lang.String[] args) Test program.
java.lang.Object	next() Returns another tuple not returned previously.
void	remove() OPTIONAL METHOD -- NOT IMPLEMENTED.

Methods inherited from class java.lang.Object

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

Constructor Detail

TupleIterator

public TupleIterator(java.util.List cartproduct)

Constructor.

Parameters:

cartproduct - a List of Collections from which the tuples' components are to be draw.

Method Detail

hasNext

public boolean hasNext()

Returns true if there are any more elements in the Cartesian product to return.

Specified by:

hasNext in interface java.util.Iterator

next

public java.lang.Object next()

Returns another tuple not returned previously.

The iterator stores its state in the private member currstate -- an ArrayList of the iterators of the individual Collections in the cartesian product. In the start state, each iterator returns a single element. Afterwards, while iterator #1 has anything to return, we replace the first element of the previous tuple to obtain a new tuple. Once iterator #1 runs out of elements we replace it and advance iterator #2. We keep on advancing iterator #1 until it runs out of elements for the second time, reinitialize it again, and advance iterator #2 once more. We repeat these operations until iterator #2 runs out of elements and we start advancing iterator #3, and so on, until all iterators run out of elements.

This method of generating the m-tuples is very similar to producing all numbers of m "digits" in the order of their magnitude, where the i-th "digit" is in base_i = #(i-th Collection in the cartesian product) and we assume that the "numbers" in the i-th Collection are ordered in some way.

Specified by:

next in interface java.util.Iterator

remove

public void remove()

OPTIONAL METHOD -- NOT IMPLEMENTED.

Specified by:

remove in interface java.util.Iterator

main

public static void main(java.lang.String[] args)

Test program. The program takes any number of command line arguments, each of which represents a collection. A collection is represented as a whitespace-separated list of elements (so it must be put in quotes, or else it will be broken into separate command line arguments by the shell). The program should print out all the tuples that can be formed from these collections. For example:

> java -cp . common.TupleIterator "a b" "c d"
[a, c]
[a, d]
[b, c]
[b, d]