Interview: Create an Iterator for a Collection of Collections

Question

Create an iterator for collection collections in java. The iterator should hide the nesting, allowing you to iterate over all elements belonging to all collections, as if you were working with one collection

Answer 1

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 2

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

This difference, combined with the requirement of looping through elements (a requirement that was not requested by the OP in this question) adds the overhead of copying iterators to the list.

The first approach is lazy: it will iterate over the element only when requesting this element, the "price" we have to pay is that the code is more complicated 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 elements from all iterators in the requested order to the list and returning the iterator to this 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 to show how to use MultiIterator, this is not always trivial (due to the use of Generics), as you can see on the line:

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

Answer 3

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 4

First, consider an iterator implementation in java.util.LinkedList

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

From there, your task is easy to simply implement one iterator, which takes into account the fact that it iterates over collections.

Sincerely.

Answer 5

if all you need to work with is a java Iterator: which has hasNext (), next () and remove (), I decided that you need to get around this.

Process it when you process a 2D array, i.e. with the outer and inner loop, because they have the same “layout”, but different data types. As you migrate, you transfer them to a new collection.

therefore, perhaps 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

Hope this helps. There must be other ways to solve this, I think.

Answer 6

This is an old question, but at present (2019) we have JDK8 + goodies. In particular, we have threads that simplify this task:

 public static <T> Iterator<T> flatIterator(Collection<Collection<T>> collections) { return collections.stream() .filter(Objects::nonNull) .flatMap(Collection::stream) .iterator(); } 

I'm filtering null internal collections, just in case ...

---

EDIT: If you also want to filter null elements from internal collections, just add an additional non-zero filter after flatMap :

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