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

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

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