/*
 * 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
 *
 *      http://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.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import org.apache.commons.collections4.list.UnmodifiableList;


Provides an ordered iteration over the elements contained in a collection of
ordered Iterators.
 Given two ordered Iterator instances A and
B, the next method on this iterator will return the lesser of A.next() and B.next().
Since:
2.1/**
 * Provides an ordered iteration over the elements contained in a collection of
 * ordered Iterators.
 * <p>
 * Given two ordered {@link Iterator} instances <code>A</code> and
 * <code>B</code>, the {@link #next} method on this iterator will return the
 * lesser of <code>A.next()</code> and <code>B.next()</code>.
 *
 * @since 2.1
 */
public class CollatingIterator<E> implements Iterator<E> {

    
The Comparator used to evaluate order. /** The {@link Comparator} used to evaluate order. */
    private Comparator<? super E> comparator = null;

    
The list of Iterators to evaluate. /** The list of {@link Iterator}s to evaluate. */
    private List<Iterator<? extends E>> iterators = null;

    
Next objects peeked from each iterator. /** {@link Iterator#next Next} objects peeked from each iterator. */
    private List<E> values = null;

    
Whether or not each CollatingIterator<E>.values element has been set. /** Whether or not each {@link #values} element has been set. */
    private BitSet valueSet = null;

    
Index of the iterator from whom the last returned value was obtained. /**
     * Index of the {@link #iterators iterator} from whom the last returned
     * value was obtained.
     */
    private int lastReturned = -1;

    // Constructors
    // ----------------------------------------------------------------------
    
Constructs a new CollatingIterator. A comparator must be set by calling setComparator(Comparator) before invoking hasNext(), or next() for the first time. Child iterators will have to be manually added using the addIterator(Iterator) method. /**
     * Constructs a new <code>CollatingIterator</code>. A comparator must be
     * set by calling {@link #setComparator(Comparator)} before invoking
     * {@link #hasNext()}, or {@link #next()} for the first time. Child
     * iterators will have to be manually added using the
     * {@link #addIterator(Iterator)} method.
     */
    public CollatingIterator() {
        this(null, 2);
    }

    
Constructs a new CollatingIterator that will used the specified comparator for ordering. Child iterators will have to be manually added using the addIterator(Iterator) method. 
Params:
comp – the comparator to use to sort; must not be null, unless you'll be invoking setComparator(Comparator) later on./**
     * Constructs a new <code>CollatingIterator</code> that will used the
     * specified comparator for ordering. Child iterators will have to be
     * manually added using the {@link #addIterator(Iterator)} method.
     *
     * @param comp the comparator to use to sort; must not be null,
     *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
     */
    public CollatingIterator(final Comparator<? super E> comp) {
        this(comp, 2);
    }

    
Constructs a new CollatingIterator that will used the specified comparator for ordering and have the specified initial capacity. Child iterators will have to be manually added using the addIterator(Iterator) method. 
Params:
comp – the comparator to use to sort; must not be null, unless you'll be invoking setComparator(Comparator) later on.
initIterCapacity – the initial capacity for the internal list of
  child iterators/**
     * Constructs a new <code>CollatingIterator</code> that will used the
     * specified comparator for ordering and have the specified initial
     * capacity. Child iterators will have to be manually added using the
     * {@link #addIterator(Iterator)} method.
     *
     * @param comp the comparator to use to sort; must not be null,
     *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
     * @param initIterCapacity the initial capacity for the internal list of
     *   child iterators
     */
    public CollatingIterator(final Comparator<? super E> comp, final int initIterCapacity) {
        iterators = new ArrayList<>(initIterCapacity);
        setComparator(comp);
    }

    
Constructs a new CollatingIterator that will use the
specified comparator to provide ordered iteration over the two given
iterators.
Params:
comp – the comparator to use to sort; must not be null, unless you'll be invoking setComparator(Comparator) later on.
a – the first child ordered iterator
b – the second child ordered iterator
Throws:
NullPointerException – if either iterator is null/**
     * Constructs a new <code>CollatingIterator</code> that will use the
     * specified comparator to provide ordered iteration over the two given
     * iterators.
     *
     * @param comp the comparator to use to sort; must not be null,
     *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
     * @param a the first child ordered iterator
     * @param b the second child ordered iterator
     * @throws NullPointerException if either iterator is null
     */
    public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E> a,
                             final Iterator<? extends E> b) {
        this(comp, 2);
        addIterator(a);
        addIterator(b);
    }

    
Constructs a new CollatingIterator that will use the
specified comparator to provide ordered iteration over the array of
iterators.
Params:
comp – the comparator to use to sort; must not be null, unless you'll be invoking setComparator(Comparator) later on.
iterators – the array of iterators
Throws:
NullPointerException – if iterators array is or contains null/**
     * Constructs a new <code>CollatingIterator</code> that will use the
     * specified comparator to provide ordered iteration over the array of
     * iterators.
     *
     * @param comp the comparator to use to sort; must not be null,
     *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
     * @param iterators the array of iterators
     * @throws NullPointerException if iterators array is or contains null
     */
    public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E>[] iterators) {
        this(comp, iterators.length);
        for (final Iterator<? extends E> iterator : iterators) {
            addIterator(iterator);
        }
    }

    
Constructs a new CollatingIterator that will use the
specified comparator to provide ordered iteration over the collection of
iterators.
Params:
comp – the comparator to use to sort; must not be null, unless you'll be invoking setComparator(Comparator) later on.
iterators – the collection of iterators
Throws:
NullPointerException – if the iterators collection is or contains null
ClassCastException – if the iterators collection contains an element that's not an Iterator/**
     * Constructs a new <code>CollatingIterator</code> that will use the
     * specified comparator to provide ordered iteration over the collection of
     * iterators.
     *
     * @param comp the comparator to use to sort; must not be null,
     *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
     * @param iterators the collection of iterators
     * @throws NullPointerException if the iterators collection is or contains null
     * @throws ClassCastException if the iterators collection contains an
     *   element that's not an {@link Iterator}
     */
    public CollatingIterator(final Comparator<? super E> comp, final Collection<Iterator<? extends E>> iterators) {
        this(comp, iterators.size());
        for (final Iterator<? extends E> iterator : iterators) {
            addIterator(iterator);
        }
    }

    // Public Methods
    // ----------------------------------------------------------------------
    
Adds the given Iterator to the iterators being collated. 
Params:
iterator – the iterator to add to the collation, must not be null
Throws:
IllegalStateException – if iteration has started
NullPointerException – if the iterator is null/**
     * Adds the given {@link Iterator} to the iterators being collated.
     *
     * @param iterator the iterator to add to the collation, must not be null
     * @throws IllegalStateException if iteration has started
     * @throws NullPointerException if the iterator is null
     */
    public void addIterator(final Iterator<? extends E> iterator) {
        checkNotStarted();
        if (iterator == null) {
            throw new NullPointerException("Iterator must not be null");
        }
        iterators.add(iterator);
    }

    
Sets the iterator at the given index.
Params:
index – index of the Iterator to replace
iterator – Iterator to place at the given index
Throws:
IndexOutOfBoundsException – if index < 0 or index > size()
IllegalStateException – if iteration has started
NullPointerException – if the iterator is null/**
     * Sets the iterator at the given index.
     *
     * @param index index of the Iterator to replace
     * @param iterator Iterator to place at the given index
     * @throws IndexOutOfBoundsException if index &lt; 0 or index &gt; size()
     * @throws IllegalStateException if iteration has started
     * @throws NullPointerException if the iterator is null
     */
    public void setIterator(final int index, final Iterator<? extends E> iterator) {
        checkNotStarted();
        if (iterator == null) {
            throw new NullPointerException("Iterator must not be null");
        }
        iterators.set(index, iterator);
    }

    
Gets the list of Iterators (unmodifiable).
Returns:
the unmodifiable list of iterators added/**
     * Gets the list of Iterators (unmodifiable).
     *
     * @return the unmodifiable list of iterators added
     */
    public List<Iterator<? extends E>> getIterators() {
        return UnmodifiableList.unmodifiableList(iterators);
    }

    
Gets the Comparator by which collatation occurs. 
Returns:
the Comparator/**
     * Gets the {@link Comparator} by which collatation occurs.
     *
     * @return the {@link Comparator}
     */
    public Comparator<? super E> getComparator() {
        return comparator;
    }

    
Sets the Comparator by which collation occurs. If you would like to use the natural sort order (or, in other words, if the elements in the iterators are implementing the Comparable interface), then use the ComparableComparator. 
Params:
comp – the Comparator to set
Throws:
IllegalStateException – if iteration has started/**
     * Sets the {@link Comparator} by which collation occurs. If you
     * would like to use the natural sort order (or, in other words,
     * if the elements in the iterators are implementing the
     * {@link java.lang.Comparable} interface), then use the
     * {@link org.apache.commons.collections4.comparators.ComparableComparator}.
     *
     * @param comp the {@link Comparator} to set
     * @throws IllegalStateException if iteration has started
     */
    public void setComparator(final Comparator<? super E> comp) {
        checkNotStarted();
        comparator = comp;
    }

    // Iterator Methods
    // -------------------------------------------------------------------
    
Returns true if any child iterator has remaining elements.
Returns:
true if this iterator has remaining elements/**
     * Returns <code>true</code> if any child iterator has remaining elements.
     *
     * @return true if this iterator has remaining elements
     */
    @Override
    public boolean hasNext() {
        start();
        return anyValueSet(valueSet) || anyHasNext(iterators);
    }

    
Returns the next ordered element from a child iterator.
Throws:
NoSuchElementException – if no child iterator has any more elements
Returns:
the next ordered element/**
     * Returns the next ordered element from a child iterator.
     *
     * @return the next ordered element
     * @throws NoSuchElementException if no child iterator has any more elements
     */
    @Override
    public E next() throws NoSuchElementException {
        if (hasNext() == false) {
            throw new NoSuchElementException();
        }
        final int leastIndex = least();
        if (leastIndex == -1) {
            throw new NoSuchElementException();
        }
        final E val = values.get(leastIndex);
        clear(leastIndex);
        lastReturned = leastIndex;
        return val;
    }

    
Removes the last returned element from the child iterator that produced it.
Throws:
IllegalStateException – if there is no last returned element, or if
the last returned element has already been removed/**
     * Removes the last returned element from the child iterator that produced it.
     *
     * @throws IllegalStateException if there is no last returned element, or if
     * the last returned element has already been removed
     */
    @Override
    public void remove() {
        if (lastReturned == -1) {
            throw new IllegalStateException("No value can be removed at present");
        }
        iterators.get(lastReturned).remove();
    }

    
Returns the index of the iterator that returned the last element.
Throws:
IllegalStateException – if there is no last returned element
Returns:
the index of the iterator that returned the last element/**
     * Returns the index of the iterator that returned the last element.
     *
     * @return the index of the iterator that returned the last element
     * @throws IllegalStateException if there is no last returned element
     */
    public int getIteratorIndex() {
        if (lastReturned == -1) {
            throw new IllegalStateException("No value has been returned yet");
        }

        return lastReturned;
    }

    // Private Methods
    // -------------------------------------------------------------------
    
Initializes the collating state if it hasn't been already.
/**
     * Initializes the collating state if it hasn't been already.
     */
    private void start() {
        if (values == null) {
            values = new ArrayList<>(iterators.size());
            valueSet = new BitSet(iterators.size());
            for (int i = 0; i < iterators.size(); i++) {
                values.add(null);
                valueSet.clear(i);
            }
        }
    }

    
Sets the CollatingIterator<E>.values and CollatingIterator<E>.valueSet attributes at position i to the next value of the iterator at position i, or clear them if the ith iterator has no next
value.
Returns:
false iff there was no value to set/**
     * Sets the {@link #values} and {@link #valueSet} attributes at position
     * <i>i</i> to the next value of the {@link #iterators iterator} at position
     * <i>i</i>, or clear them if the <i>i</i><sup>th</sup> iterator has no next
     * value.
     *
     * @return {@code false} iff there was no value to set
     */
    private boolean set(final int i) {
        final Iterator<? extends E> it = iterators.get(i);
        if (it.hasNext()) {
            values.set(i, it.next());
            valueSet.set(i);
            return true;
        }
        values.set(i, null);
        valueSet.clear(i);
        return false;
    }

    
Clears the CollatingIterator<E>.values and CollatingIterator<E>.valueSet attributes at position i.
/**
     * Clears the {@link #values} and {@link #valueSet} attributes at position
     * <i>i</i>.
     */
    private void clear(final int i) {
        values.set(i, null);
        valueSet.clear(i);
    }

    
Throws IllegalStateException if iteration has started via start. 
Throws:
IllegalStateException – if iteration started/**
     * Throws {@link IllegalStateException} if iteration has started via
     * {@link #start}.
     *
     * @throws IllegalStateException if iteration started
     */
    private void checkNotStarted() throws IllegalStateException {
        if (values != null) {
            throw new IllegalStateException("Can't do that after next or hasNext has been called.");
        }
    }

    
Returns the index of the least element in CollatingIterator<E>.values, setting any uninitialized values. 
Throws:
NullPointerException – if no comparator is set/**
     * Returns the index of the least element in {@link #values},
     * {@link #set(int) setting} any uninitialized values.
     *
     * @throws NullPointerException if no comparator is set
     */
    private int least() {
        int leastIndex = -1;
        E leastObject = null;
        for (int i = 0; i < values.size(); i++) {
            if (valueSet.get(i) == false) {
                set(i);
            }
            if (valueSet.get(i)) {
                if (leastIndex == -1) {
                    leastIndex = i;
                    leastObject = values.get(i);
                } else {
                    final E curObject = values.get(i);
                    if (comparator == null) {
                        throw new NullPointerException("You must invoke setComparator() to set a comparator first.");
                    }
                    if (comparator.compare(curObject, leastObject) < 0) {
                        leastObject = curObject;
                        leastIndex = i;
                    }
                }
            }
        }
        return leastIndex;
    }

    
Returns true iff any bit in the given set is
true.
/**
     * Returns <code>true</code> iff any bit in the given set is
     * <code>true</code>.
     */
    private boolean anyValueSet(final BitSet set) {
        for (int i = 0; i < set.size(); i++) {
            if (set.get(i)) {
                return true;
            }
        }
        return false;
    }

    
Returns true iff any Iterator in the given list has a next value. /**
     * Returns <code>true</code> iff any {@link Iterator} in the given list has
     * a next value.
     */
    private boolean anyHasNext(final List<Iterator<? extends E>> iters) {
        for (final Iterator<? extends E> iterator : iters) {
            if (iterator.hasNext()) {
                return true;
            }
        }
        return false;
    }

}