7
\$\begingroup\$

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);
    }
}
\$\endgroup\$
1

3 Answers 3

6
\$\begingroup\$

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();
    }
}
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Perhaps ChainedIterator to match the adjective + noun advice from your other answer. \$\endgroup\$ Jul 9, 2014 at 18:15
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Jul 9, 2014 at 18:21
  • \$\begingroup\$ I like IteratorOfIterator. \$\endgroup\$
    – kiltek
    Nov 9, 2018 at 14:36
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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());
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – skiwi
    Jul 10, 2014 at 11:00
  • \$\begingroup\$ 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. \$\endgroup\$
    – janos
    Jul 10, 2014 at 11:52
  • 1
    \$\begingroup\$ A fair point there, it might be just that I dislike working with arrays, but you are totally correct here. \$\endgroup\$
    – skiwi
    Jul 10, 2014 at 11:53
  • \$\begingroup\$ I dislike working with arrays, too, but like the varargs syntax. It's a shame it uses arrays and not lists. \$\endgroup\$
    – Ingo Bürk
    Jul 11, 2014 at 5:52
  • \$\begingroup\$ @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. \$\endgroup\$
    – janos
    Jul 11, 2014 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.