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

This is an old question, but nowadays (2019) we have JDK8+ goodies. In particular, we have streams, which make this task straightforward:

public static <T> Iterator<T> flatIterator(Collection<Collection<T>> collections) {

    return collections.stream()
            .filter(Objects::nonNull)
            .flatMap(Collection::stream)
            .iterator();
}

I'm filtering null inner collections out, just in case...

---

EDIT: If you also want to filter null elements out of the inner collections, just add an extra non-null filter aflter flatMap:

return collections.stream()
        .filter(Objects::nonNull)
        .flatMap(Collection::stream)
        .filter(Objects::nonNull)
        .iterator();

Answer 2

Here is another implementation:

import java.util.Iterator;
import java.util.NoSuchElementException;

import static java.util.Collections.emptyIterator;

public class Multiterator<E> implements Iterator<E> {
    private Iterator<Iterator<E>> root;
    private Iterator<E> current;

    public Multiterator(Iterator<Iterator<E>> root) {
        this.root = root;
        current = null;
    }

    @Override
    public boolean hasNext() {
        if (current == null || !current.hasNext()) {
            current = getNextNonNullOrEmpty(root);
        }
        return current.hasNext();
    }

    private Iterator<E> getNextNonNullOrEmpty(Iterator<Iterator<E>> root) {
        while (root.hasNext()) {
            Iterator<E> next = root.next();
            if (next != null && next.hasNext()) {
                return next;
            }
        }
        return emptyIterator();
    }

    @Override
    public E next() {
        if (current == null) {
            throw new NoSuchElementException();
        }
        return current.next();
    }
}

Answer 3

In this post you can see two implementations, the only (minor) difference is that it takes an iterator of iterators instead of a collection of collections.

This difference combined with the requirement to iterate the elements in a round-robin fashion (a requirement that wasn't requested by the OP in this question) adds the overhead of copying the iterators into a list.

The first approach is lazy: it will iterate an element only when this element is requested, the 'price' we have to pay is that the code is more complex because it needs to handle more edge-cases:

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

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,
        }
    }
}

and the second ('greedy' copying of all the elements from all the iterators in the requested order into a list and returning an iterator to that list ):

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

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,
        }
    }
}

I included a simple 'test' code in order to show the way to use the MultiIterator, this is not always trivial (because of the use of Generics) as you can see on the line:

Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());

Answer 4

if all you have to work with is the java Iterator: which just have hasNext(), next() and remove(), i figured you have to go around it.

Process it as you will process a 2D array, that is, with an outer and inner loop, because they have same "arrangement" but different datatype. As you process, you transfer them to a new collection.

so maybe a private method:

    private void convertToSingleCollection()
    {


         while("column")
         {
            //convert the "column" to an arra


           for( "Row")
           {
            //add to newCollection here
           }

          //remove the processed column from CollectionOFcollection
         } 
    }
    //call the above method in your constructor


    public iterator<T> Iterator()
    {
       newCollection.iterator();
    }

    public boolean hasNext()
    {
       return Iterator().hasNext()
    }

    public T next()
    {
       if(!hasNext())
       {
        //exception message or message
       }
       else
           //return "next"
    }

end

I hope this helps. There should be other ways to solve it i guess.

Answer 5

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 6

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.