join multiple iterators in java

Question

How can I join multiple iterators in Java? The solution I found iterate through one iterator first, and then move on to the next one. However, what I want is when next() gets called, it first returns the first element from the first iterator. Next time when next() gets called, it returns the first element from the second iterator, and so on.

Answer 1

Using Guava's AbstractIterator for simplicity:

final List<Iterator<E>> theIterators;
return new AbstractIterator<E>() {
  private Queue<Iterator<E>> queue = new ArrayDeque<Iterator<E>>(theIterators);
  @Override protected E computeNext() {
    while(!queue.isEmpty()) {
      Iterator<E> topIter = queue.poll();
      if(topIter.hasNext()) {
        E result = topIter.next();
        queue.offer(topIter);
        return result;
      }
    }
    return endOfData();
  }
};

This will give you the desired "interleaved" order, it's smart enough to deal with the collections having different sizes, and it's quite compact.

If you really, really can't tolerate another third-party library, you can more or less do the same thing with some additional work, like so:

return new Iterator<E>() {
  private Queue<Iterator<E>> queue = new ArrayDeque<Iterator<E>>(theIterators);
  public boolean hasNext() {
    // If this returns true, the head of the queue will have a next element
    while(!queue.isEmpty()) {
      if(queue.peek().hasNext()) {
        return true;
      }
      queue.poll();
    }
    return false;
  }
  public E next() {
    if(!hasNext()) throw new NoSuchElementException();
    Iterator<E> iter = queue.poll();
    E result = iter.next();
    queue.offer(iter);
    return result;
  }
  public void remove() { throw new UnsupportedOperationException(); }
};

For reference, the "all of iter1, all of iter2, etc" behavior can also be obtained using Iterators.concat(Iterator<Iterator>) and its overloads.