    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 *      https://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.Collection;
    020import java.util.Iterator;
    021import java.util.LinkedList;
    022import java.util.Objects;
    023import java.util.Queue;
    024
    025/**
    026 * An IteratorChain is an Iterator that wraps a number of Iterators.
    027 * <p>
    028 * This class makes multiple iterators look like one to the caller. When any
    029 * method from the Iterator interface is called, the IteratorChain will delegate
    030 * to a single underlying Iterator. The IteratorChain will invoke the Iterators
    031 * in sequence until all Iterators are exhausted.
    032 * </p>
    033 * <p>
    034 * Under many circumstances, linking Iterators together in this manner is more
    035 * efficient (and convenient) than reading out the contents of each Iterator
    036 * into a List and creating a new Iterator.
    037 * </p>
    038 * <p>
    039 * Calling a method that adds new Iterator <i>after a method in the Iterator
    040 * interface has been called</i> will result in an UnsupportedOperationException.
    041 * </p>
    042 * <p>
    043 * NOTE: As from version 3.0, the IteratorChain may contain no iterators. In
    044 * this case the class will function as an empty iterator.
    045 * </p>
    046 * <p>
    047 * NOTE: As from version 4.0, the IteratorChain stores the iterators in a queue
    048 * and removes any reference to them as soon as they are not used anymore. Thus,
    049 * the methods {@code setIterator(Iterator)} and {@code getIterators()} have been
    050 * removed and {@link #size()} will return the number of remaining iterators in
    051 * the queue.
    052 * </p>
    053 *
    054 * @param <E> The type of elements in this iterator.
    055 * @since 2.1
    056 */
    057public class IteratorChain<E> implements Iterator<E> {
    058
    059    /** The chain of iterators */
    060    private final Queue<Iterator<? extends E>> iteratorQueue = new LinkedList<>();
    061
    062    /** The current iterator */
    063    private Iterator<? extends E> currentIterator;
    064
    065    /**
    066     * The "last used" Iterator is the Iterator upon which next()
    067     * was most recently called used for the remove() operation only
    068     */
    069    private Iterator<? extends E> lastUsedIterator;
    070
    071    /**
    072     * ComparatorChain is "locked" after the first time compare(Object, Object)
    073     * is called
    074     */
    075    private boolean isLocked;
    076
    077    /**
    078     * Contains the result of the last hasNext() call until next() is invoked
    079     */
    080    private Boolean cachedHasNextValue;
    081
    082    /**
    083     * Constructs an IteratorChain with no Iterators.
    084     * <p>
    085     * You will normally use {@link #addIterator(Iterator)} to add some
    086     * iterators after using this constructor.
    087     * </p>
    088     */
    089    public IteratorChain() {
    090    }
    091
    092    /**
    093     * Constructs a new {@code IteratorChain} over the collection of
    094     * iterators.
    095     * <p>
    096     * This method takes a collection of iterators. The newly constructed
    097     * iterator will iterate through each one of the input iterators in turn.
    098     * </p>
    099     *
    100     * @param iteratorQueue The collection of iterators, not null
    101     * @throws NullPointerException if iterators collection is or contains null
    102     * @throws ClassCastException if iterators collection doesn't contain an
    103     * iterator
    104     */
    105    public IteratorChain(final Collection<? extends Iterator<? extends E>> iteratorQueue) {
    106        for (final Iterator<? extends E> iterator : iteratorQueue) {
    107            addIterator(iterator);
    108        }
    109    }
    110
    111    /**
    112     * Constructs an IteratorChain with a single Iterator.
    113     * <p>
    114     * This method takes one iterator. The newly constructed iterator will
    115     * iterate through that iterator. Thus calling this constructor on its own
    116     * will have no effect other than decorating the input iterator.
    117     * </p>
    118     * <p>
    119     * You will normally use {@link #addIterator(Iterator)} to add some more
    120     * iterators after using this constructor.
    121     * </p>
    122     *
    123     * @param iterator The first child iterator in the IteratorChain, not null
    124     * @throws NullPointerException if the iterator is null
    125     */
    126    public IteratorChain(final Iterator<? extends E> iterator) {
    127        addIterator(iterator);
    128    }
    129
    130    /**
    131     * Constructs a new {@code IteratorChain} over the array of iterators.
    132     * <p>
    133     * This method takes an array of iterators. The newly constructed iterator
    134     * will iterate through each one of the input iterators in turn.
    135     * </p>
    136     *
    137     * @param iteratorQueue The array of iterators, not null
    138     * @throws NullPointerException if iterators array is or contains null
    139     */
    140    public IteratorChain(final Iterator<? extends E>... iteratorQueue) {
    141        for (final Iterator<? extends E> element : iteratorQueue) {
    142            addIterator(element);
    143        }
    144    }
    145
    146    /**
    147     * Constructs a new {@code IteratorChain} over the two given iterators.
    148     * <p>
    149     * This method takes two iterators. The newly constructed iterator will
    150     * iterate through each one of the input iterators in turn.
    151     * </p>
    152     *
    153     * @param first The first child iterator in the IteratorChain, not null
    154     * @param second The second child iterator in the IteratorChain, not null
    155     * @throws NullPointerException if either iterator is null
    156     */
    157    public IteratorChain(final Iterator<? extends E> first, final Iterator<? extends E> second) {
    158        addIterator(first);
    159        addIterator(second);
    160    }
    161
    162    /**
    163     * Add an Iterator to the end of the chain
    164     *
    165     * @param iterator Iterator to add
    166     * @throws IllegalStateException if I've already started iterating
    167     * @throws NullPointerException if the iterator is null
    168     */
    169    public void addIterator(final Iterator<? extends E> iterator) {
    170        checkLocked();
    171        Objects.requireNonNull(iterator, "iterator");
    172        if (iterator instanceof UnmodifiableIterator) {
    173            final Iterator<? extends E> underlyingIterator = ((UnmodifiableIterator) iterator).unwrap();
    174            if (underlyingIterator instanceof IteratorChain) {
    175                // in case it is an IteratorChain, wrap every underlying iterators as unmodifiable
    176                // multiple rechainings would otherwise lead to exponential growing number of function calls
    177                // when the iteratorChain gets used.
    178                for (final Iterator<? extends E> nestedIterator : ((IteratorChain<? extends E>) underlyingIterator).iteratorQueue) {
    179                    iteratorQueue.add(UnmodifiableIterator.unmodifiableIterator(nestedIterator));
    180                }
    181            } else {
    182                // we don't know anything about the underlying iterator, simply add it here
    183                iteratorQueue.add(iterator);
    184            }
    185        } else if (iterator instanceof IteratorChain) {
    186            // add the wrapped iterators directly instead of reusing the given instance
    187            // multiple rechainings would otherwise lead to exponential growing number of function calls
    188            // when the iteratorChain gets used.
    189            iteratorQueue.addAll(((IteratorChain) iterator).iteratorQueue);
    190        } else {
    191            // arbitrary other iterator
    192            iteratorQueue.add(iterator);
    193        }
    194    }
    195
    196    /**
    197     * Checks whether the iterator chain is now locked and in use.
    198     */
    199    private void checkLocked() {
    200        if (isLocked) {
    201            throw new UnsupportedOperationException("IteratorChain cannot be changed after the first use of a method from the Iterator interface");
    202        }
    203    }
    204
    205    /**
    206     * Return true if any Iterator in the IteratorChain has a remaining element.
    207     *
    208     * @return true if elements remain
    209     */
    210    @Override
    211    public boolean hasNext() {
    212        lockChain();
    213        if (cachedHasNextValue == null) {
    214            updateCurrentIterator();
    215        }
    216        return cachedHasNextValue;
    217    }
    218
    219    /**
    220     * Determine if modifications can still be made to the IteratorChain.
    221     * IteratorChains cannot be modified once they have executed a method from
    222     * the Iterator interface.
    223     *
    224     * @return true if IteratorChain cannot be modified, false if it can
    225     */
    226    public boolean isLocked() {
    227        return isLocked;
    228    }
    229
    230    /**
    231     * Lock the chain so no more iterators can be added. This must be called
    232     * from all Iterator interface methods.
    233     */
    234    private void lockChain() {
    235        if (!isLocked) {
    236            isLocked = true;
    237        }
    238    }
    239
    240    /**
    241     * Returns the next Object of the current Iterator
    242     *
    243     * @return Object from the current Iterator
    244     * @throws java.util.NoSuchElementException if all the Iterators are
    245     * exhausted
    246     */
    247    @Override
    248    public E next() {
    249        lockChain();
    250        if (cachedHasNextValue == null) {
    251            updateCurrentIterator();
    252        }
    253        lastUsedIterator = currentIterator;
    254        cachedHasNextValue = null;
    255        return currentIterator.next();
    256    }
    257
    258    /**
    259     * Removes from the underlying collection the last element returned by the
    260     * Iterator. As with next() and hasNext(), this method calls remove() on the
    261     * underlying Iterator. Therefore, this method may throw an
    262     * UnsupportedOperationException if the underlying Iterator does not support
    263     * this method.
    264     *
    265     * @throws UnsupportedOperationException if the remove operator is not
    266     * supported by the underlying Iterator
    267     * @throws IllegalStateException if the next method has not yet been called,
    268     * or the remove method has already been called after the last call to the
    269     * next method.
    270     */
    271    @Override
    272    public void remove() {
    273        lockChain();
    274        if (lastUsedIterator == null)  {
    275            throw new IllegalStateException("remove() has been invoked without next()");
    276        }
    277        lastUsedIterator.remove();
    278        lastUsedIterator = null;  // must never be used twice without next() being invoked
    279    }
    280
    281    /**
    282     * Returns the remaining number of Iterators in the current IteratorChain.
    283     *
    284     * @return Iterator count
    285     */
    286    public int size() {
    287        return iteratorQueue.size();
    288    }
    289
    290    /**
    291     * Updates the current iterator field to ensure that the current Iterator is
    292     * not exhausted
    293     */
    294    protected void updateCurrentIterator() {
    295        if (currentIterator == null) {
    296            if (iteratorQueue.isEmpty()) {
    297                currentIterator = EmptyIterator.<E>emptyIterator();
    298            } else {
    299                currentIterator = iteratorQueue.remove();
    300            }
    301        }
    302        while (true) {
    303            cachedHasNextValue = currentIterator.hasNext();
    304            if (cachedHasNextValue) {
    305                break;
    306            }
    307            if (iteratorQueue.isEmpty()) {
    308                break;
    309            }
    310            currentIterator = iteratorQueue.remove();
    311        }
    312    }
    313}