Resource Library

Given an iterator of iterators, implement an interleaving iterator

Background: Iterator defined

In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled. This code snippet illustrates:

int[] arr = [1, 2, 3];Iterator<Integer> it = arr.iterator();while(it.hasNext()){  print it.next();}// 123hasNext() // returns whether or not the iterator has additional elementsnext() // returns next element in iterator, throws NoSuchElementException otherwise.    

Your challenge, should you choose to accept it...

Given an iterator of iterators, implement an interleaving iterator that takes in an iterator of iterators, and emits elements from the nested iterators in interleaved order. That is, if we had the iterators i and j iterating over the elements [ia, ib, ic] and [ja, jb] respectively, the order in which your interleaving iterator should emit the elements would be [ia, ja, ib, jb, ic].

Your interleaving iterator should implement the Iterator interface, take in the iterator of iterators in its constructor, and provide the next and hasNext methods. Assume that there are no additional methods offered by the iterator.

Given the following three iterators put into an array of iterators…

int[] arr1 = [1, 2, 3];int[] arr2 = [4, 5];int[] arr3 = [6, 7, 8, 9];Iterator<Integer> a = arr1.iterator();Iterator<Integer> b = arr2.iterator();Iterator<Integer> c = arr3.iterator();Iterator<Integer>[] iterlist = [a, b, c];    

… build an “Interleaving Flattener” (IF), which works much like an iterator:

IF itfl = new IF(iterlist);while(IF.hasNext()){  print IF.next();}// 1 4 6 2 5 7 3 8 9    

To assist you, here’s a skeleton for the class:

class IF{  public IF(Iterator<T>[] iterlist){  }  public T next(){  }    public boolean hasNext(){  }}    

Learning objectives

This question gives you the chance to practice with iterators, iteration, data structures, classes, and nesting. It calls for thoughtful problem-solving and optimizing your solution. If you write it successfully in one language, try it again in a second.

Here are some possible solutions:

Less Efficient Solution - O(k) operations

Initialize by iterating over the nested iterators, adding them to a member list or array (linked list is fine).

Have a helper to move to the next iterator that can provide the next element. This can be called in both hasNext() and next(). Helper should only go through each nested iterator once (no more elements if it goes a full cycle without finding anything)

To interleave you have to hold on to references to all the inner Iterators (i.e. all the iterators returned by the outer Iterator) in order to be able to revisit the first one once you reach the last one. This is correct for the ones for which hasNext() is true. So the solution must use a data structure from which you can prune the empties.

This requires maintaining a bit more state than just the collection of iterators. A common solution is to store all the iterators in a List, then when it hits the end of the list, wrap back until each iterator is expired. If you hit an iterator that is expired (.hasNext() returns false), you can skip over it.

More Efficient Solution - O(1) operations, O(k) initialization

Don't add an iterator to the iterator list upon initialization if it’s empty. If an iterator does not have any more elements, remove it from the list. This will also simplify the helper method by not having to keep track of a cycle.

Note that for this to be O(1) for next() then getting the next iterator and removing it must also be O(1) - using a linked list for storage and its iterator (a new one for each cycle) for getting and removal is one possibility.

Another possibility is a queue, where you only add an iterator back to the end of the queue if it has more elements.

The Queue (generally more optimal)

Use the queue to do the cycling of the list for you. When you pull an element from an iterator, check to see if the iterator is empty. If the iterator is not empty, add it back to the queue. If it’s empty, then you’re out of elements.

If done correctly, this is a slightly easier version of Solution 2 to write, as it leverages existing data structures to do most of the abstraction for you.

Assumes:

implementation (assuming O(1) pop), this should be: