Java Cartesian iterator for an array of Iterables

Saturday, 31 July 2010 23:59
the-exception-new-string[]-void

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 This e-mail address is being protected from spambots. You need JavaScript enabled to view it
* @created 01-08-2010
*/
public class CartesianIterator implements Iterator {

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());
}
}

Read more: http://feeds.dzone.com/~r/dzone/snippets/~3/x0Vy9US5UQI/11959

Scroll To Top