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}