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;
023import java.util.Objects;
024
025import org.apache.commons.collections4.FluentIterable;
026
027/**
028 * Provides an interleaved iteration over the elements contained in a
029 * collection of Iterators.
030 * <p>
031 * Given two {@link Iterator} instances {@code A} and {@code B}, the
032 * {@link #next} method on this iterator will switch between {@code A.next()}
033 * and {@code B.next()} until both iterators are exhausted.
034 * </p>
035 *
036 * @param <E> the type of elements returned by this iterator.
037 * @since 4.1
038 */
039public class ZippingIterator<E> implements Iterator<E> {
040
041    /** The {@link Iterator}s to evaluate. */
042    private final Iterator<Iterator<? extends E>> iterators;
043
044    /** The next iterator to use for next(). */
045    private Iterator<? extends E> nextIterator;
046
047    /** The last iterator which was used for next(). */
048    private Iterator<? extends E> lastReturned;
049
050    /**
051     * Constructs a new {@code ZippingIterator} that will provide
052     * interleaved iteration of the specified iterators.
053     *
054     * @param iterators  the array of iterators
055     * @throws NullPointerException if any iterator is null
056     */
057    public ZippingIterator(final Iterator<? extends E>... iterators) {
058        // create a mutable list to be able to remove exhausted iterators
059        final List<Iterator<? extends E>> list = new ArrayList<>();
060        for (final Iterator<? extends E> iterator : iterators) {
061            Objects.requireNonNull(iterator, "iterator");
062            list.add(iterator);
063        }
064        this.iterators = FluentIterable.of(list).loop().iterator();
065    }
066
067    /**
068     * Constructs a new {@code ZippingIterator} that will provide
069     * interleaved iteration over the two given iterators.
070     *
071     * @param a  the first child iterator
072     * @param b  the second child iterator
073     * @throws NullPointerException if either iterator is null
074     */
075    @SuppressWarnings("unchecked")
076    public ZippingIterator(final Iterator<? extends E> a, final Iterator<? extends E> b) {
077        this(new Iterator[] {a, b});
078    }
079
080    /**
081     * Constructs a new {@code ZippingIterator} that will provide
082     * interleaved iteration over the three given iterators.
083     *
084     * @param a  the first child iterator
085     * @param b  the second child iterator
086     * @param c  the third child iterator
087     * @throws NullPointerException if either iterator is null
088     */
089    @SuppressWarnings("unchecked")
090    public ZippingIterator(final Iterator<? extends E> a,
091                           final Iterator<? extends E> b,
092                           final Iterator<? extends E> c) {
093        this(new Iterator[] {a, b, c});
094    }
095
096    /**
097     * Returns {@code true} if any child iterator has remaining elements.
098     *
099     * @return true if this iterator has remaining elements
100     */
101    @Override
102    public boolean hasNext() {
103        // the next iterator has already been determined
104        // this might happen if hasNext() is called multiple
105        if (nextIterator != null) {
106            return true;
107        }
108
109        while (iterators.hasNext()) {
110            final Iterator<? extends E> childIterator = iterators.next();
111            if (childIterator.hasNext()) {
112                nextIterator = childIterator;
113                return true;
114            }
115            // iterator is exhausted, remove it
116            iterators.remove();
117        }
118        return false;
119    }
120
121    /**
122     * Returns the next element from a child iterator.
123     *
124     * @return the next interleaved element
125     * @throws NoSuchElementException if no child iterator has any more elements
126     */
127    @Override
128    public E next() throws NoSuchElementException {
129        if (!hasNext()) {
130            throw new NoSuchElementException();
131        }
132
133        final E val = nextIterator.next();
134        lastReturned = nextIterator;
135        nextIterator = null;
136        return val;
137    }
138
139    /**
140     * Removes the last returned element from the child iterator that produced it.
141     *
142     * @throws IllegalStateException if there is no last returned element, or if
143     *   the last returned element has already been removed
144     */
145    @Override
146    public void remove() {
147        if (lastReturned == null) {
148            throw new IllegalStateException("No value can be removed at present");
149        }
150        lastReturned.remove();
151        lastReturned = null;
152    }
153
154}