Say you had to implement a class that takes as an argument (in the constructor) Iterator<Iterator<E>> iterator and returns an iterator that can iterate all the elements under Iterator<Iterator<E>> iterator in a round-robin manner, meaning, according to the order of the numbers in the following screenshot:

I searched online and found implementations such as this, this and even Guava but they are not helpful in our case since the order they are iterating is vertical: 1,7,13,17,2,8,14,18,3,9,4,…

So I decided to come up with my solution to the problem, and here’s what I got:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * Created by alfasin on 11/15/15.
 */


public class MultiIterator<E> implements Iterator {

    List<Iterator<E>> iterators = new LinkedList<>();
    Iterator<E> current = null;

    public MultiIterator(Iterator<Iterator<E>> iterator) {
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
    }

    @Override
    public boolean hasNext() {
        boolean result = false;
        if (iterators.isEmpty() && (current == null || !current.hasNext())) {
            return false;
        }

        if (current == null) {
            current = iterators.remove(0);
        }

        while (!current.hasNext() && !iterators.isEmpty()) {
            current = iterators.remove(0);
        }

        if (current.hasNext()) {
            result = true;
        }
        return result;
    }

    @Override
    public E next() {
        if (current == null) {
            try {
                current = iterators.remove(0);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        E result = current.next(); // if this method was called without checking 'hasNext' this line might raise NoSuchElementException which is fine
        iterators.add(current);
        current = iterators.remove(0);
        return result;
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        MultiIterator<Integer> it = new MultiIterator<>(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

A different approach would be to read all the elements, during initialization, into one list and then return an iterator of that list!

Let’s see how it works:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by alfasin on 11/15/15.
 */

public class MultiIterator<E> {

    Iterator<Iterator<E>> iterator = null;
    List<E> elements = new LinkedList<>();

    private MultiIterator(Iterator<Iterator<E>> iterator) {
        this.iterator = iterator;
    }

    private void copyElementsInOrder() {
        List<Iterator<E>> iterators = new LinkedList<>();
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
        // go over the list, round-robin, and grab one
        // element from each sub-iterator and add it to *elements*
        // empty sub-iterators will get dropped off the list
        while (!iterators.isEmpty()) {
            Iterator<E> subIterator = iterators.remove(0);
            if (subIterator.hasNext()) {
                elements.add(subIterator.next());
                iterators.add(subIterator);
            }
        }
    }

    public static <E> Iterator<E> iterator(Iterator<Iterator<E>> iterator) {
        MultiIterator<E> instance = new MultiIterator<>(iterator);
        instance.copyElementsInOrder();
        return instance.elements.iterator();
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

There are pros and cons to each one of these approaches:

The first approach is more complex because it requires checking and handling of many edge-cases (including catching an IndexOutOfBoundsException in case that our list of iterators is empty and throwing the proper NoSuchElementException instead).

The second approach is more concise on one hand, but on the other hand it requires copying, in-advance, all the elements (greedy) vs. the first approach which is lazy and should be preferred in cases of large datasets.

Note that the second approach implements a factory and as such it doesn’t implement the Iterator interface!

EDIT:

Now with Java 9, it’s much more elegant to create such lists (using the new collections APIs). I re-did this exercise and here’s what I got:

class MultiIterator<E> implements Iterator {

    private LinkedList<Iterator<E>> iterators = new LinkedList<>();
    private int current = 0;

    public MultiIterator(Iterator<Iterator<E>> iterator) {
        while(iterator.hasNext()) {
            iterators.add(iterator.next());
        }
    }
    /**
     * Returns {@code true} if the iteration has more elements.
     * (In other words, returns {@code true} if {@link #next} would
     * return an element rather than throwing an exception.)
     *
     * @return {@code true} if the iteration has more elements
     */
    @Override
    public boolean hasNext() {
        if (iterators.size() == 0) {
            return false;
        }
        if (iterators.get(current).hasNext()) {
            return true;
        }
        return false;
    }

    /**
     * Returns the next element in the iteration.
     *
     * @return the next element in the iteration
     * @throws NoSuchElementException if the iteration has no more elements
     */
    @Override
    public E next() {
        E next;
        try {
            next = iterators.get(current).next(); // might throw IndexOutOfBoundsException if wasn't called with hasNext()
            Iterator<E> iter = iterators.remove(current);
            if (iter.hasNext()) {
                iterators.add(iter);
            }
        } catch (IndexOutOfBoundsException e) {
            throw new NoSuchElementException();
        }
        return next;
    }

    public static void main(String[] args) {
        List<Integer> l1 = List.of(1, 2, 3, 4, 5, 6);
        List<Integer> l2 = List.of(5, 6, 7, 8);
        List<Integer> l3 = List.of(9, 10, 11, 12);
        Iterator<Iterator<Integer>> iterators = List.of(l1.iterator(), l2.iterator(), l3.iterator()).iterator();
        MultiIterator<Integer> iters = new MultiIterator<>(iterators);
        while (iters.hasNext()) {
            System.out.println(iters.next());
        }
    }
}