    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.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() or hasNext()
    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     * Constructs an IteratorChain with no Iterators.
    079     * <p>
    080     * You will normally use {@link #addIterator(Iterator)} to add some
    081     * iterators after using this constructor.
    082     * </p>
    083     */
    084    public IteratorChain() {
    085    }
    086
    087    /**
    088     * Constructs a new {@code IteratorChain} over the collection of
    089     * iterators.
    090     * <p>
    091     * This method takes a collection of iterators. The newly constructed
    092     * iterator will iterate through each one of the input iterators in turn.
    093     * </p>
    094     *
    095     * @param iteratorQueue the collection of iterators, not null
    096     * @throws NullPointerException if iterators collection is or contains null
    097     * @throws ClassCastException if iterators collection doesn't contain an
    098     * iterator
    099     */
    100    public IteratorChain(final Collection<? extends Iterator<? extends E>> iteratorQueue) {
    101        for (final Iterator<? extends E> iterator : iteratorQueue) {
    102            addIterator(iterator);
    103        }
    104    }
    105
    106    /**
    107     * Constructs an IteratorChain with a single Iterator.
    108     * <p>
    109     * This method takes one iterator. The newly constructed iterator will
    110     * iterate through that iterator. Thus calling this constructor on its own
    111     * will have no effect other than decorating the input iterator.
    112     * </p>
    113     * <p>
    114     * You will normally use {@link #addIterator(Iterator)} to add some more
    115     * iterators after using this constructor.
    116     * </p>
    117     *
    118     * @param iterator the first child iterator in the IteratorChain, not null
    119     * @throws NullPointerException if the iterator is null
    120     */
    121    public IteratorChain(final Iterator<? extends E> iterator) {
    122        addIterator(iterator);
    123    }
    124
    125    /**
    126     * Constructs a new {@code IteratorChain} over the array of iterators.
    127     * <p>
    128     * This method takes an array of iterators. The newly constructed iterator
    129     * will iterate through each one of the input iterators in turn.
    130     * </p>
    131     *
    132     * @param iteratorQueue the array of iterators, not null
    133     * @throws NullPointerException if iterators array is or contains null
    134     */
    135    public IteratorChain(final Iterator<? extends E>... iteratorQueue) {
    136        for (final Iterator<? extends E> element : iteratorQueue) {
    137            addIterator(element);
    138        }
    139    }
    140
    141    /**
    142     * Constructs a new {@code IteratorChain} over the two given iterators.
    143     * <p>
    144     * This method takes two iterators. The newly constructed iterator will
    145     * iterate through each one of the input iterators in turn.
    146     * </p>
    147     *
    148     * @param first the first child iterator in the IteratorChain, not null
    149     * @param second the second child iterator in the IteratorChain, not null
    150     * @throws NullPointerException if either iterator is null
    151     */
    152    public IteratorChain(final Iterator<? extends E> first, final Iterator<? extends E> second) {
    153        addIterator(first);
    154        addIterator(second);
    155    }
    156
    157    /**
    158     * Add an Iterator to the end of the chain
    159     *
    160     * @param iterator Iterator to add
    161     * @throws IllegalStateException if I've already started iterating
    162     * @throws NullPointerException if the iterator is null
    163     */
    164    public void addIterator(final Iterator<? extends E> iterator) {
    165        checkLocked();
    166        iteratorQueue.add(Objects.requireNonNull(iterator, "iterator"));
    167    }
    168
    169    /**
    170     * Checks whether the iterator chain is now locked and in use.
    171     */
    172    private void checkLocked() {
    173        if (isLocked) {
    174            throw new UnsupportedOperationException("IteratorChain cannot be changed after the first use of a method from the Iterator interface");
    175        }
    176    }
    177
    178    /**
    179     * Return true if any Iterator in the IteratorChain has a remaining element.
    180     *
    181     * @return true if elements remain
    182     */
    183    @Override
    184    public boolean hasNext() {
    185        lockChain();
    186        updateCurrentIterator();
    187        lastUsedIterator = currentIterator;
    188        return currentIterator.hasNext();
    189    }
    190
    191    /**
    192     * Determine if modifications can still be made to the IteratorChain.
    193     * IteratorChains cannot be modified once they have executed a method from
    194     * the Iterator interface.
    195     *
    196     * @return true if IteratorChain cannot be modified, false if it can
    197     */
    198    public boolean isLocked() {
    199        return isLocked;
    200    }
    201
    202    /**
    203     * Lock the chain so no more iterators can be added. This must be called
    204     * from all Iterator interface methods.
    205     */
    206    private void lockChain() {
    207        if (!isLocked) {
    208            isLocked = true;
    209        }
    210    }
    211
    212    /**
    213     * Returns the next Object of the current Iterator
    214     *
    215     * @return Object from the current Iterator
    216     * @throws java.util.NoSuchElementException if all the Iterators are
    217     * exhausted
    218     */
    219    @Override
    220    public E next() {
    221        lockChain();
    222        updateCurrentIterator();
    223        lastUsedIterator = currentIterator;
    224
    225        return currentIterator.next();
    226    }
    227
    228    /**
    229     * Removes from the underlying collection the last element returned by the
    230     * Iterator. As with next() and hasNext(), this method calls remove() on the
    231     * underlying Iterator. Therefore, this method may throw an
    232     * UnsupportedOperationException if the underlying Iterator does not support
    233     * this method.
    234     *
    235     * @throws UnsupportedOperationException if the remove operator is not
    236     * supported by the underlying Iterator
    237     * @throws IllegalStateException if the next method has not yet been called,
    238     * or the remove method has already been called after the last call to the
    239     * next method.
    240     */
    241    @Override
    242    public void remove() {
    243        lockChain();
    244        if (currentIterator == null) {
    245            updateCurrentIterator();
    246        }
    247        lastUsedIterator.remove();
    248    }
    249
    250    /**
    251     * Returns the remaining number of Iterators in the current IteratorChain.
    252     *
    253     * @return Iterator count
    254     */
    255    public int size() {
    256        return iteratorQueue.size();
    257    }
    258
    259    /**
    260     * Updates the current iterator field to ensure that the current Iterator is
    261     * not exhausted
    262     */
    263    protected void updateCurrentIterator() {
    264        if (currentIterator == null) {
    265            if (iteratorQueue.isEmpty()) {
    266                currentIterator = EmptyIterator.<E>emptyIterator();
    267            } else {
    268                currentIterator = iteratorQueue.remove();
    269            }
    270            // set last used iterator here, in case the user calls remove
    271            // before calling hasNext() or next() (although they shouldn't)
    272            lastUsedIterator = currentIterator;
    273        }
    274        while (!currentIterator.hasNext() && !iteratorQueue.isEmpty()) {
    275            currentIterator = iteratorQueue.remove();
    276        }
    277    }
    278
    279}