Java Cartesian Iterator For An Array Of Iterables

• Tweet
• 

import java.util.Iterator;

/**
 * Iterates over Cartesian product for an array of Iterables, 
 * Returns an array of Objects on each step containing values from each of the Iterables.
 *
 * @author jacek.p.kolodziejczyk@gmail.com
 * @created 01-08-2010
 */
public class CartesianIterator implements Iterator<Object[]> {

	private final Iterable[] iterables;
	private final Iterator[] iterators;
	private Object[] values;
	private int size;
	private boolean empty;

	/**
	 * Constructor
	 * @param iterables array of Iterables being the source for the Cartesian product.
	 */
	public CartesianIterator(Iterable ...iterables) {
		this.size = iterables.length;
		this.iterables = iterables;
		this.iterators = new Iterator[size];
		
		// Initialize iterators
		for (int i = 0; i < size; i++) {
			iterators[i] = iterables[i].iterator();
			// If one of the iterators is empty then the whole Cartesian product is empty
			if (!iterators[i].hasNext()) {
				empty = true;
				break;
			}
		}
		
		// Initialize the tuple of the iteration values except the last one
		if (!empty) {
			values = new Object[size];
			for (int i = 0; i < size-1; i++) setNextValue(i);
		}
	}

	@Override
	public boolean hasNext() {
		if (empty) return false;
		for (int i = 0; i < size; i++)
			if (iterators[i].hasNext())
				return true;
		return false;
	}

	@Override
	public Object[] next() {
		// Find first in reverse order iterator the has a next element
		int cursor;
		for (cursor = size-1; cursor >= 0; cursor--)
			if (iterators[cursor].hasNext()) break;

		// Initialize iterators next from the current one  
		for (int i = cursor+1; i < size; i++) iterators[i] = iterables[i].iterator();
		
		// Get the next value from the current iterator and all the next ones  
		for (int i = cursor; i < size; i++) setNextValue(i);

		return values.clone();
	}

	/**
	 * Gets the next value provided there is one from the iterator at the given index. 
	 * @param index
	 */
	private void setNextValue(int index) {
		Iterator it = iterators[index];
		if (it.hasNext())
			values[index] = it.next();
	}

	@Override
	public void remove() { throw new UnsupportedOperationException(); }
}

Test cases:

import java.util.Arrays;

import junit.framework.TestCase;
import util.Strings;
import util.collect.CartesianIterator;

public class CartesianIteratorTest extends TestCase {
	
	public void test_empty() throws Exception {
		CartesianIterator it = new CartesianIterator();
		
		assertFalse(it.hasNext());
		try {
			assertEquals("", Strings.join("",it.next()));
			fail("Should throw NoSuchElementException");
		} catch (Exception e) { /* Ignore exception */ }
	}
		
	public void test_0() throws Exception {
		CartesianIterator it = new CartesianIterator(
				Arrays.asList(new String[] {}));
		
		assertFalse(it.hasNext());
		try {
			assertEquals("", Strings.join("",it.next()));
			fail("Should throw NoSuchElementException");
		} catch (Exception e) { /* Ignore exception */ }
	}
	
	public void test_1() throws Exception {
		CartesianIterator it = new CartesianIterator(
				Arrays.asList(new String[] {"a"}));
		
		assertTrue(it.hasNext());
		assertEquals("a", Strings.join("",it.next()));
		assertFalse(it.hasNext());
	}
	
	public void test_2() throws Exception {
		CartesianIterator it = new CartesianIterator(
				Arrays.asList(new String[] {"a", "b"}));
		
		assertTrue(it.hasNext());
		assertEquals("a", Strings.join("",it.next()));
		assertTrue(it.hasNext());
		assertEquals("b", Strings.join("",it.next()));
		assertFalse(it.hasNext());
	}
	
	public void test_2_0() throws Exception {
		CartesianIterator it = new CartesianIterator(
				Arrays.asList(new String[] {"a", "b"}),
				Arrays.asList(new String[] {}));
		
		assertFalse(it.hasNext());
		try {
			assertEquals("", Strings.join("",it.next()));
			fail("Should throw NoSuchElementException");
		} catch (Exception e) { /* Ignore exception */ }
	}
	
	public void test_2_2() throws Exception {
		CartesianIterator it = new CartesianIterator(
				Arrays.asList(new String[] {"a", "b"}),
				Arrays.asList(new String[] {"c", "d"}));
		
		assertTrue(it.hasNext());
		assertEquals("ac", Strings.join("",it.next()));
		assertTrue(it.hasNext());
		assertEquals("ad", Strings.join("",it.next()));
		assertTrue(it.hasNext());
		assertEquals("bc", Strings.join("",it.next()));
		assertTrue(it.hasNext());
		assertEquals("bd", Strings.join("",it.next()));
		assertFalse(it.hasNext());
	}
	
	public void test_2_3_4() throws Exception {
		CartesianIterator it = new CartesianIterator(
				Arrays.asList(new String[] {"a", "b"}),
				Arrays.asList(new String[] {"c", "d", "e"}),
				Arrays.asList(new String[] {"f", "g", "h", "i"}));
		
		assertTrue(it.hasNext());
		assertEquals("acf", Strings.join("",it.next()));
		assertTrue(it.hasNext());
		assertEquals("acg", Strings.join("",it.next()));
		assertEquals("ach", Strings.join("",it.next()));
		assertEquals("aci", Strings.join("",it.next()));
		assertEquals("adf", Strings.join("",it.next()));
		assertEquals("adg", Strings.join("",it.next()));
		assertEquals("adh", Strings.join("",it.next()));
		assertEquals("adi", Strings.join("",it.next()));
		assertEquals("aef", Strings.join("",it.next()));
		assertEquals("aeg", Strings.join("",it.next()));
		assertEquals("aeh", Strings.join("",it.next()));
		assertEquals("aei", Strings.join("",it.next()));
		assertEquals("bcf", Strings.join("",it.next()));
		assertEquals("bcg", Strings.join("",it.next()));
		assertEquals("bch", Strings.join("",it.next()));
		assertEquals("bci", Strings.join("",it.next()));
		assertEquals("bdf", Strings.join("",it.next()));
		assertEquals("bdg", Strings.join("",it.next()));
		assertEquals("bdh", Strings.join("",it.next()));
		assertEquals("bdi", Strings.join("",it.next()));
		assertEquals("bef", Strings.join("",it.next()));
		assertEquals("beg", Strings.join("",it.next()));
		assertEquals("beh", Strings.join("",it.next()));
		assertTrue(it.hasNext());
		assertEquals("bei", Strings.join("",it.next()));
		assertFalse(it.hasNext());
	}
}

Tags:
• cartesian
• iterable
• iterator
• java