/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.iterators;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * An IteratorChain is an Iterator that wraps a number of Iterators.
 * <p>
 * This class makes multiple iterators look like one to the caller. When any
 * method from the Iterator interface is called, the IteratorChain will delegate
 * to a single underlying Iterator. The IteratorChain will invoke the Iterators
 * in sequence until all Iterators are exhausted.
 * </p>
 * <p>
 * Under many circumstances, linking Iterators together in this manner is more
 * efficient (and convenient) than reading out the contents of each Iterator
 * into a List and creating a new Iterator.
 * </p>
 * <p>
 * Calling a method that adds new Iterator <i>after a method in the Iterator
 * interface has been called</i> will result in an UnsupportedOperationException.
 * </p>
 * <p>
 * NOTE: As from version 3.0, the IteratorChain may contain no iterators. In
 * this case the class will function as an empty iterator.
 * </p>
 * <p>
 * NOTE: As from version 4.0, the IteratorChain stores the iterators in a queue
 * and removes any reference to them as soon as they are not used anymore. Thus,
 * the methods {@code setIterator(Iterator)} and {@code getIterators()} have been
 * removed and {@link #size()} will return the number of remaining iterators in
 * the queue.
 * </p>
 *
 * @param <E> The type of elements in this iterator.
 * @since 2.1
 */
public class IteratorChain<E> implements Iterator<E> {

    /** The chain of iterators */
    private final Queue<Iterator<? extends E>> iteratorQueue = new LinkedList<>();

    /** The current iterator */
    private Iterator<? extends E> currentIterator;

    /**
     * The "last used" Iterator is the Iterator upon which next()
     * was most recently called used for the remove() operation only
     */
    private Iterator<? extends E> lastUsedIterator;

    /**
     * ComparatorChain is "locked" after the first time compare(Object, Object)
     * is called
     */
    private boolean isLocked;

    /**
     * Contains the result of the last hasNext() call until next() is invoked
     */
    private Boolean cachedHasNextValue;

    /**
     * Constructs an IteratorChain with no Iterators.
     * <p>
     * You will normally use {@link #addIterator(Iterator)} to add some
     * iterators after using this constructor.
     * </p>
     */
    public IteratorChain() {
    }

    /**
     * Constructs a new {@code IteratorChain} over the collection of
     * iterators.
     * <p>
     * This method takes a collection of iterators. The newly constructed
     * iterator will iterate through each one of the input iterators in turn.
     * </p>
     *
     * @param iteratorQueue The collection of iterators, not null
     * @throws NullPointerException if iterators collection is or contains null
     * @throws ClassCastException if iterators collection doesn't contain an
     * iterator
     */
    public IteratorChain(final Collection<? extends Iterator<? extends E>> iteratorQueue) {
        for (final Iterator<? extends E> iterator : iteratorQueue) {
            addIterator(iterator);
        }
    }

    /**
     * Constructs an IteratorChain with a single Iterator.
     * <p>
     * This method takes one iterator. The newly constructed iterator will
     * iterate through that iterator. Thus calling this constructor on its own
     * will have no effect other than decorating the input iterator.
     * </p>
     * <p>
     * You will normally use {@link #addIterator(Iterator)} to add some more
     * iterators after using this constructor.
     * </p>
     *
     * @param iterator The first child iterator in the IteratorChain, not null
     * @throws NullPointerException if the iterator is null
     */
    public IteratorChain(final Iterator<? extends E> iterator) {
        addIterator(iterator);
    }

    /**
     * Constructs a new {@code IteratorChain} over the array of iterators.
     * <p>
     * This method takes an array of iterators. The newly constructed iterator
     * will iterate through each one of the input iterators in turn.
     * </p>
     *
     * @param iteratorQueue The array of iterators, not null
     * @throws NullPointerException if iterators array is or contains null
     */
    public IteratorChain(final Iterator<? extends E>... iteratorQueue) {
        for (final Iterator<? extends E> element : iteratorQueue) {
            addIterator(element);
        }
    }

    /**
     * Constructs a new {@code IteratorChain} over the two given iterators.
     * <p>
     * This method takes two iterators. The newly constructed iterator will
     * iterate through each one of the input iterators in turn.
     * </p>
     *
     * @param first The first child iterator in the IteratorChain, not null
     * @param second The second child iterator in the IteratorChain, not null
     * @throws NullPointerException if either iterator is null
     */
    public IteratorChain(final Iterator<? extends E> first, final Iterator<? extends E> second) {
        addIterator(first);
        addIterator(second);
    }

    /**
     * Add an Iterator to the end of the chain
     *
     * @param iterator Iterator to add
     * @throws IllegalStateException if I've already started iterating
     * @throws NullPointerException if the iterator is null
     */
    public void addIterator(final Iterator<? extends E> iterator) {
        checkLocked();
        Objects.requireNonNull(iterator, "iterator");
        if (iterator instanceof UnmodifiableIterator) {
            final Iterator<? extends E> underlyingIterator = ((UnmodifiableIterator) iterator).unwrap();
            if (underlyingIterator instanceof IteratorChain) {
                // in case it is an IteratorChain, wrap every underlying iterators as unmodifiable
                // multiple rechainings would otherwise lead to exponential growing number of function calls
                // when the iteratorChain gets used.
                for (final Iterator<? extends E> nestedIterator : ((IteratorChain<? extends E>) underlyingIterator).iteratorQueue) {
                    iteratorQueue.add(UnmodifiableIterator.unmodifiableIterator(nestedIterator));
                }
            } else {
                // we don't know anything about the underlying iterator, simply add it here
                iteratorQueue.add(iterator);
            }
        } else if (iterator instanceof IteratorChain) {
            // add the wrapped iterators directly instead of reusing the given instance
            // multiple rechainings would otherwise lead to exponential growing number of function calls
            // when the iteratorChain gets used.
            iteratorQueue.addAll(((IteratorChain) iterator).iteratorQueue);
        } else {
            // arbitrary other iterator
            iteratorQueue.add(iterator);
        }
    }

    /**
     * Checks whether the iterator chain is now locked and in use.
     */
    private void checkLocked() {
        if (isLocked) {
            throw new UnsupportedOperationException("IteratorChain cannot be changed after the first use of a method from the Iterator interface");
        }
    }

    /**
     * Return true if any Iterator in the IteratorChain has a remaining element.
     *
     * @return true if elements remain
     */
    @Override
    public boolean hasNext() {
        lockChain();
        if (cachedHasNextValue == null) {
            updateCurrentIterator();
        }
        return cachedHasNextValue;
    }

    /**
     * Determine if modifications can still be made to the IteratorChain.
     * IteratorChains cannot be modified once they have executed a method from
     * the Iterator interface.
     *
     * @return true if IteratorChain cannot be modified, false if it can
     */
    public boolean isLocked() {
        return isLocked;
    }

    /**
     * Lock the chain so no more iterators can be added. This must be called
     * from all Iterator interface methods.
     */
    private void lockChain() {
        if (!isLocked) {
            isLocked = true;
        }
    }

    /**
     * Returns the next Object of the current Iterator
     *
     * @return Object from the current Iterator
     * @throws java.util.NoSuchElementException if all the Iterators are
     * exhausted
     */
    @Override
    public E next() {
        lockChain();
        if (cachedHasNextValue == null) {
            updateCurrentIterator();
        }
        lastUsedIterator = currentIterator;
        cachedHasNextValue = null;
        return currentIterator.next();
    }

    /**
     * Removes from the underlying collection the last element returned by the
     * Iterator. As with next() and hasNext(), this method calls remove() on the
     * underlying Iterator. Therefore, this method may throw an
     * UnsupportedOperationException if the underlying Iterator does not support
     * this method.
     *
     * @throws UnsupportedOperationException if the remove operator is not
     * supported by the underlying Iterator
     * @throws IllegalStateException if the next method has not yet been called,
     * or the remove method has already been called after the last call to the
     * next method.
     */
    @Override
    public void remove() {
        lockChain();
        if (lastUsedIterator == null)  {
            throw new IllegalStateException("remove() has been invoked without next()");
        }
        lastUsedIterator.remove();
        lastUsedIterator = null;  // must never be used twice without next() being invoked
    }

    /**
     * Returns the remaining number of Iterators in the current IteratorChain.
     *
     * @return Iterator count
     */
    public int size() {
        return iteratorQueue.size();
    }

    /**
     * Updates the current iterator field to ensure that the current Iterator is
     * not exhausted
     */
    protected void updateCurrentIterator() {
        if (currentIterator == null) {
            if (iteratorQueue.isEmpty()) {
                currentIterator = EmptyIterator.<E>emptyIterator();
            } else {
                currentIterator = iteratorQueue.remove();
            }
        }
        while (true) {
            cachedHasNextValue = currentIterator.hasNext();
            if (cachedHasNextValue) {
                break;
            }
            if (iteratorQueue.isEmpty()) {
                break;
            }
            currentIterator = iteratorQueue.remove();
        }
    }
}