Interview: Design an iterator for a collection of collections

Question

Design an iterator for a collection of collections in java. The iterator should hide the nesting, allowing you to iterate all of the elements belonging to all of the collections as if you were working with a single collection

Answer 1

First, take a look at the implementation of the iterator in java.util.LinkedList

http://www.docjar.com/html/api/java/util/LinkedList.java.html

From there your task is easy just implement a single iterator that takes into account the fact that it is iterating over collections.

Regards.

Answer 2

Here is a possible implementation. Note that I left remove() unimplemented:

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

    private Iterator<? extends Collection<T>> it;
    private Iterator<T> innerIt;
    private T next;
    private boolean hasNext = true;

    public MultiIterator(Collection<? extends Collection<T>> collections) {
        it = collections.iterator();    
        prepareNext();
    }

    private void prepareNext() {
        do {
            if (innerIt == null || !innerIt.hasNext()) {
                if (!it.hasNext()) {
                    hasNext = false;
                    return;
                } else
                    innerIt = it.next().iterator();
            }
        } while (!innerIt.hasNext());

        next = innerIt.next();
    }

    @Override
    public boolean hasNext() {
        return hasNext;
    }

    @Override
    public T next() {
        if (!hasNext)
            throw new NoSuchElementException();
        T res = next;
        prepareNext();
        return res;
    }

    @Override
    public void remove() {
        //TODO
    }

}

Answer 3

You've already accepted an answer, but if you want to look at code, wouldn't it make more sense to look at code that's actually heavily tested and widely used in production?

http://guava-libraries.googlecode.com/svn/tags/release06/javadoc/src-html/com/google/common/collect/Iterators.html#line.499