    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.iterators;
    018
    019import java.util.ArrayList;
    020import java.util.Iterator;
    021import java.util.List;
    022import java.util.NoSuchElementException;
    023
    024import org.apache.commons.collections4.FluentIterable;
    025
    026/**
    027 * Provides an interleaved iteration over the elements contained in a
    028 * collection of Iterators.
    029 * <p>
    030 * Given two {@link Iterator} instances {@code A} and {@code B}, the
    031 * {@link #next} method on this iterator will switch between {@code A.next()}
    032 * and {@code B.next()} until both iterators are exhausted.
    033 *
    034 * @since 4.1
    035 */
    036public class ZippingIterator<E> implements Iterator<E> {
    037
    038    /** The {@link Iterator}s to evaluate. */
    039    private final Iterator<Iterator<? extends E>> iterators;
    040
    041    /** The next iterator to use for next(). */
    042    private Iterator<? extends E> nextIterator = null;
    043
    044    /** The last iterator which was used for next(). */
    045    private Iterator<? extends E> lastReturned = null;
    046
    047    // Constructors
    048    // ----------------------------------------------------------------------
    049
    050    /**
    051     * Constructs a new <code>ZippingIterator</code> that will provide
    052     * interleaved iteration over the two given iterators.
    053     *
    054     * @param a  the first child iterator
    055     * @param b  the second child iterator
    056     * @throws NullPointerException if either iterator is null
    057     */
    058    @SuppressWarnings("unchecked")
    059    public ZippingIterator(final Iterator<? extends E> a, final Iterator<? extends E> b) {
    060        this(new Iterator[] {a, b});
    061    }
    062
    063    /**
    064     * Constructs a new <code>ZippingIterator</code> that will provide
    065     * interleaved iteration over the three given iterators.
    066     *
    067     * @param a  the first child iterator
    068     * @param b  the second child iterator
    069     * @param c  the third child iterator
    070     * @throws NullPointerException if either iterator is null
    071     */
    072    @SuppressWarnings("unchecked")
    073    public ZippingIterator(final Iterator<? extends E> a,
    074                           final Iterator<? extends E> b,
    075                           final Iterator<? extends E> c) {
    076        this(new Iterator[] {a, b, c});
    077    }
    078
    079    /**
    080     * Constructs a new <code>ZippingIterator</code> that will provide
    081     * interleaved iteration of the specified iterators.
    082     *
    083     * @param iterators  the array of iterators
    084     * @throws NullPointerException if any iterator is null
    085     */
    086    public ZippingIterator(final Iterator<? extends E>... iterators) {
    087        // create a mutable list to be able to remove exhausted iterators
    088        final List<Iterator<? extends E>> list = new ArrayList<>();
    089        for (final Iterator<? extends E> iterator : iterators) {
    090            if (iterator == null) {
    091                throw new NullPointerException("Iterator must not be null.");
    092            }
    093            list.add(iterator);
    094        }
    095        this.iterators = FluentIterable.of(list).loop().iterator();
    096    }
    097
    098    // Iterator Methods
    099    // -------------------------------------------------------------------
    100
    101    /**
    102     * Returns {@code true} if any child iterator has remaining elements.
    103     *
    104     * @return true if this iterator has remaining elements
    105     */
    106    @Override
    107    public boolean hasNext() {
    108        // the next iterator has already been determined
    109        // this might happen if hasNext() is called multiple
    110        if (nextIterator != null) {
    111            return true;
    112        }
    113
    114        while(iterators.hasNext()) {
    115            final Iterator<? extends E> childIterator = iterators.next();
    116            if (childIterator.hasNext()) {
    117                nextIterator = childIterator;
    118                return true;
    119            }
    120            // iterator is exhausted, remove it
    121            iterators.remove();
    122        }
    123        return false;
    124    }
    125
    126    /**
    127     * Returns the next element from a child iterator.
    128     *
    129     * @return the next interleaved element
    130     * @throws NoSuchElementException if no child iterator has any more elements
    131     */
    132    @Override
    133    public E next() throws NoSuchElementException {
    134        if (!hasNext()) {
    135            throw new NoSuchElementException();
    136        }
    137
    138        final E val = nextIterator.next();
    139        lastReturned = nextIterator;
    140        nextIterator = null;
    141        return val;
    142    }
    143
    144    /**
    145     * Removes the last returned element from the child iterator that produced it.
    146     *
    147     * @throws IllegalStateException if there is no last returned element, or if
    148     *   the last returned element has already been removed
    149     */
    150    @Override
    151    public void remove() {
    152        if (lastReturned == null) {
    153            throw new IllegalStateException("No value can be removed at present");
    154        }
    155        lastReturned.remove();
    156        lastReturned = null;
    157    }
    158
    159}