Iterator of iterator

Question

Given an iterator of iterators, return all of the elements from the iterators in order. Looking for code review, optimizations, and best practices. Verifying complexity to be \$O(n)\,ドル where \$n\$ is the total number of elements from all iterators.

public class IteratorOfIterator implements Iterator<Integer>{
 private final Iterator<Iterator<Integer>> iteratorOfIterator;
 private Iterator<Integer> currentIterator;
 public IteratorOfIterator(Iterator<Iterator<Integer>> iterator) {
 this.iteratorOfIterator = iterator;
 }
 @Override
 public boolean hasNext() {
 while (currentIterator == null || !currentIterator.hasNext()) {
 if (!iteratorOfIterator.hasNext()) return false;
 currentIterator = iteratorOfIterator.next();
 }
 return true;
 }
 @Override
 public Integer next() {
 if (!hasNext()) {
 throw new NoSuchElementException("the stuff cannot be null.");
 }
 return currentIterator.next();
 }
 @Override
 public void remove() {
 throw new UnsupportedOperationException("The remove operation is not supported.");
 }
}
public class IteratorOfIteratorTest {
 @Test
 public void testIterator() {
 List<Integer> list1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
 List<Integer> list2 = new ArrayList<>(Arrays.asList(5, 6, 7, 8));
 List<Iterator<Integer>> combined = new ArrayList<>(Arrays.asList(list1.iterator(), null, list2.iterator()));
 IteratorOfIterator ioi = new IteratorOfIterator(combined.iterator());
 int[] expected = {1, 2, 3, 4, 5, 6, 7, 8};
 int[] actual = new int[8];
 int i = 0;
 while (ioi.hasNext()) {
 actual[i] = ioi.next();
 i++;
 }
 assertArrayEquals(expected, actual);
 }
}

• palacsint: Iterators.concat from Guava

Answer 1

I don't see any reason to limit this to Integers. The solution can be trivially genericized.

IteratorOfIterator is a clumsy name. By analogy with Python's itertools.chain(), I suggest calling this class ChainIterator<T>. You can rename the iteratorOfIterator private variable accordingly, too.

I suggest adding an alternate constructor that takes an Iterable<Iterator<T>>, for convenience.

The hasNext() method seems fine. As for next(), the message in the NoSuchElementException that you throw seems a bit weird; I would just omit it.

With not much extra effort, you can add support for remove().

public class ChainIterator<T> implements Iterator<T> {
 private final Iterator<Iterator<T>> chain;
 private Iterator<T> currentIterator;
 private Iterator<T> lastIterator;
 public ChainIterator(Iterable<Iterator<T>> iterable) {
 this(iterable.iterator());
 }
 public ChainIterator(Iterator<Iterator<T>> iterator) {
 this.chain = iterator;
 }
 @Override
 public boolean hasNext() {
 while (currentIterator == null || !currentIterator.hasNext()) {
 if (!chain.hasNext()) return false;
 currentIterator = chain.next();
 }
 return true;
 }
 @Override
 public T next() {
 if (!this.hasNext()) {
 this.lastIterator = null; // to disallow remove()
 throw new NoSuchElementException();
 }
 this.lastIterator = currentIterator; // to support remove()
 return currentIterator.next();
 }
 @Override
 public void remove() {
 if (this.lastIterator == null) {
 throw new IllegalStateException();
 }
 this.lastIterator.remove();
 }
}

• David Harkness: Perhaps ChainedIterator to match the adjective + noun advice from your other answer.
• David Harkness: I'm not a huge fan of using this when it's not necessary, especially inconsistently in the same method as in next, but +1 otherwise.
• kiltek: I like IteratorOfIterator.

Answer 2

Reversing the logic a little bit on iterators can often make a big difference in the way the code reads, and it can remove code duplication.

One of the performance issues of iterators is that each time you call next(), you call hasNext() twice... consider a typical iterator use case:

while (it.hasNext()) {
 Object o = it.next();
 ... do something with o.
}

Now, you call hasNext() in the loop, and, internally, the first thing next() does, is call hasNext() again.

If the hasNext() method is 'heavy', it can be quite expensive. This is especially true because, often, most of the same work is required yet again, to perform the next() (a third time!).

There is a trick to prevent this work duplication: Do the work once in advance, and remember the state.

public class IteratorOfIterator implements Iterator<Integer>{
 private final Iterator<Iterator<Integer>> iteratorOfIterator;
 private Iterator<Integer> currentIterator = null;
 private Integer next = null;
 private boolean isvalid = false;
 public IteratorOfIterator(Iterator<Iterator<Integer>> iterator) {
 this.iteratorOfIterator = iterator;
 // call advance from the constructor!!
 advance();
 }
 private void advance() {
 if (currentIterator != null && currentIterator.hasNext()) {
 isvalid = true;
 next = currentIterator.next();
 return;
 }
 currentIterator = null;
 while (currentIterator == null && iteratorOfIterator.hasNext()) {
 currentIterator = iteratorOfIterator.next();
 if (currentIterator != null && currentIterator.hasNext()) {
 next = currentIterator.next();
 isvalid = true;
 return;
 }
 }
 next = null;
 isvalid = false;
 }
 @Override
 public boolean hasNext() {
 return isvalid;
 }
 @Override
 public Integer next() {
 if (isvalid) {
 throw new NoSuchElementException("the stuff cannot be null.");
 }
 Integer val = next;
 advance();
 return val;
 }
 @Override
 public void remove() {
 throw new UnsupportedOperationException("The remove operation is not supported.");
 }
}

The above code:

• reduces the multiple hasNext() calls to a simple boolean check
• the advance method is called only once per item
• it handles null values in both the iteratorOfIterators and in the currentIterator

Answer 3

Limiting to Integer type is really unnecessary. It's easy enough to generalize, you can simply change the signature to public class IteratorOfIterator<E> implements Iterator<E> and replace all occurrences of Integer with E, that's it.

The constructor is not ergonomic. You can see this in the unit test, you have to bend over backwards to create a test case: put iterators in a list and then get iterator from that. How about simply a varargs of Iterators:

public IteratorOfIterator(Iterator<E>... iterators) {
 // ...
}

As @rolfl pointed out, think from the perspective of typical use cases to catch this kind of problems, and refactor to avoid repeated calls to hasNext().

Your implementation allows null iterators. I think null iterators indicate messy code. If you are working with legacy projects you might be forced to handle these. If that's the case, I think it's better to filter out the null values in the constructor.

As @rolfl pointed out, in your next method you don't need to handle the case when there is no next element. Let the underlying iterator take care of it. The user is not supposed to call next anyway without checking hasNext first.

Suggested implementation

public class ChainIterator<E> implements Iterator<E> {
 private final Iterator<E>[] iterators;
 private int index = 0;
 public ChainIterator(Iterator<E>... iterators) {
 this.iterators = iterators;
 }
 @Override
 public boolean hasNext() {
 while (true) {
 if (iterators[index].hasNext()) {
 return true;
 }
 if (index == iterators.length - 1) {
 return false;
 }
 ++index;
 }
 }
 @Override
 public E next() {
 return iterators[index].next();
 }
 @Override
 public void remove() {
 throw new UnsupportedOperationException();
 }
}
public class ChainIteratorTest {
 @Test
 public void testSingle() {
 List<Integer> list1 = Arrays.asList(1, 2, 3);
 ChainIterator<Integer> iter2x = new ChainIterator<>(list1.iterator());
 for (Integer item : list1) {
 assertTrue(iter2x.hasNext());
 assertEquals(item, iter2x.next());
 }
 assertFalse(iter2x.hasNext());
 }
 @Test
 public void testConcatWithManyEmpty() {
 List<Integer> list1 = Arrays.asList(1, 2, 3);
 List<Integer> list2 = Arrays.asList(4, 5);
 ChainIterator<Integer> iter2x = new ChainIterator<>(
 Collections.<Integer>emptyList().iterator(),
 list1.iterator(),
 Collections.<Integer>emptyList().iterator(),
 Collections.<Integer>emptyList().iterator(),
 list2.iterator());
 for (Integer item : list1) {
 assertTrue(iter2x.hasNext());
 assertEquals(item, iter2x.next());
 }
 for (Integer item : list2) {
 assertTrue(iter2x.hasNext());
 assertEquals(item, iter2x.next());
 }
 assertFalse(iter2x.hasNext());
 }
}

• skiwi: I wouldn't store the iterators in an array (yet do accept them in such format!), you can easily use a List<Iterator<E>> by using Arrays.asList at the expensive of only one wrapper object.
• janos: You forgot to mention why do that. The current code doesn't need it. There's just no point, is there? If the code evolves in such a way that a List will make more sense, I can easily change it.
• skiwi: A fair point there, it might be just that I dislike working with arrays, but you are totally correct here.
• Ingo Bürk: I dislike working with arrays, too, but like the varargs syntax. It's a shame it uses arrays and not lists.
• janos: @IngoBürk I don't "like" arrays, but I very rarely use them. In most practical situations I need the power of lists. I dislike unnecessary things, and this array does everything I need, so why not.