package net.kidneyball;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 一个用于获取多个数组下标的笛卡尔积的迭代器。构造此迭代器时,指定各个数组的下标上限。
* 此迭代器每次迭代将获取这些数组下标的笛卡尔积集合中的下一个元素
*
* @author Daniel
* Date: 25/12/12
* Time: 9:25 PM
*/
public class IndexCartesianProductIterator implements Iterator<int[]>
{
private final int[] elementSizes;
private int[] next;
private boolean calculated;
private boolean hasNext;
private final int length;
private int tail;
/**
* 构造一个{@link IndexCartesianProductIterator}实例
*
* @param elementSizes 待求笛卡尔积的各个数组的下标上限
*/
public IndexCartesianProductIterator(int... elementSizes)
{
this.elementSizes = elementSizes;
length = elementSizes.length;
next = new int[length];
Arrays.fill(next, -1);
calculated = false;
tail = 0;
}
@Override
public boolean hasNext()
{
if (calculated) return hasNext;
calculated = true;
hasNext = findNext();
return hasNext;
}
@Override
public int[] next()
{
if (calculated)
{
if (hasNext)
{
calculated = false;
return next;
}
} else
{
hasNext = findNext();
if (hasNext) return next;
}
throw new NoSuchElementException();
}
/**
* 计算下一个笛卡尔积元素,存放在next数组中。若该元素存在则返回true,否则返回false
*
* @return 若存在下一个笛卡尔积元素,则返回ture,否则返回false
*/
protected boolean findNext()
{
for(;;) {
next[tail]++;
if (next[tail] >= elementSizes[tail]) {
tail--;
if (tail < 0) return false;
}
else if (tail < length - 1) next[++tail] = -1;
else return true;
}
}
@Override
public void remove()
{
throw new UnsupportedOperationException();
}
}
|