Interleaving Iterator

Creating an interleaving iterator is a popular interview question in the Java world.

What is an Interleaving Iterator?

An interleaving iterator is an iterator of iterators. An iterator is a class that implements the following methods (others exist but are not mandatory).

boolean hasNext();
T next();

Iterators are designed to “iterate” (cycle through) a sequence of elements of unknown length. You don’t know how many elements there are; you just know that hasNext() returns true so more elements exist (or it returns false and you’re done with the iterator).

So, an iterator of iterators is an iterator that iterates over iterators which iterate over sequences of elements of another type.

Iterators can even be potentially infinite; they may never end!

Solution Details

There are quite a few different solutions for this… but the easiest one I’ve seen leverages a queue. The basic approach is:

  • Create a member variable in the class that is a Queue.
  • On construction, populate the queue with all of the provided iterators.
  • Create a utility method (getNext() in the solution below).
    • This method is designed to get the next element if it hasn’t already been found.
    • It stores it in a member variable of the class so that we know if it has already been found.
    • The methods next() and hasNext() both defer to this method to test if there is a next element and/or retrieve the next element.
    • This is important as when using the iterator, callers will call hasNext() to see if there is a next element (which must clearly get the next element to know if it exists). We want to return that already-found element when next is called instead of accidentally skipping ahead to yet-another element.
    • Also, if I (badly) made an iterator of iterators that I knew I put 10 elements in overall, I should technically be able to just call next() 10 times without calling hasNext(), even though it is bad practice.
    • IMPORTANT – the method must basically consist of:
    • while next element isn’t found and some iterators remain in the queue:
      • Take next iterator.
      • See if it has more elements.
      • If it does, take the next element and put it back in the queue if it has more.
      • If it doesn’t have more elements, add it back to the queue.
  • The next() method just gets the next element using the utility method and returns it, or throws a NoSuchElementException if there wasn’t one.
  • The hasNext() method just returns whether or not the utility method says there are more elements.

Implementation (Java)

import java.util.*;

public class InterleavingIterator<T> implements Iterator<T> {

    private Queue<Iterator<T>> iteratorQueue;
    private T next;

    public InterleavingIterator(Iterator<Iterator<T>> masterIterator) {
        if (masterIterator == null) {
            throw new IllegalArgumentException("Iterator cannot be null.");
        }
        iteratorQueue = new ArrayDeque<>();
        masterIterator.forEachRemaining(iteratorQueue::add);
    }

    private T getNext() {
        while (next == null && !iteratorQueue.isEmpty()) {
            Iterator<T> iterator = iteratorQueue.poll();
            if (iterator.hasNext()) {
                next = iterator.next();
                if (iterator.hasNext()) {
                    iteratorQueue.add(iterator);
                }
                return next;
            }
        }
        return next;
    }

    @Override
    public boolean hasNext() {
        return getNext() != null;
    }

    @Override
    public T next() {
        T n = getNext();
        next = null;
        if (n == null) throw new NoSuchElementException();
        return n;
    }

    //Test it out!
    public static void main(String[] args) {

        //Create 4 lists with a range of test cases.
        List<String> a = Arrays.asList("a", "d", "f");
        List<String> b = Arrays.asList("b", "e", "g", "h");
        List<String> c = Collections.singletonList("c");
        List<String> d = Collections.emptyList();

        Iterator<Iterator<String>> masterIterator = Arrays.asList(
                a.iterator(),
                b.iterator(),
                c.iterator(),
                d.iterator()).iterator();

        InterleavingIterator<String> interleaving =
                new InterleavingIterator<>(masterIterator);

        while (interleaving.hasNext()) {
            System.out.println(interleaving.next());
        }
    }
}

Output

a
b
c
d
e
f
g
h

It begins!

Hey, I’m John Humphreys, and this is the first post to my new blog!

“Every great developer you know got there by solving problems they were unqualified to solve until they actually did it.” – Patrick McKenzie

In the past, I have worked hard to maintain a website in order to keep notes on all of my problems to help others.  But with the current trend of having to rewrite your front-end every six weeks, its just too hard to keep up with that on top of work.  Plus… having a toddler at home just sweetens the deal!

Anyway, in light of all that, I’m migrating my old site(s) into this word-press blog where I hope to post more often :).

Thanks for reading, and check back later for what are hopefully a large number of very interesting posts!

-John